LeetCode
8. 字符串转换整数 (atoi)
请你来实现一个 atoi 函数，使其能将字符串转换成整数。
思路：
分三步。分别处理开头的空字符、符号位和数字字符。
- 从开头开始判断，如果为空字符则 i 自增；
- 判断符号位，为 ‘-‘ 则 sign 为 -1，否则（为空或为 ‘+’ ），sign 为 1。
遇到非数字字符则跳出循环，对数字字符进行累加，超过 Integer 的范围则返回对应的边界值。
class Solution {public int myAtoi(String str) {if(str == null || str.length() == 0) return 0;int i = 0;while(i < str.length() && str.charAt(i) == ' ') i++;int sign = 1;if(i < str.length() && (str.charAt(i) == '+' || str.charAt(i) == '-')) {sign = str.charAt(i) == '-' ? -1 : 1;i++;}long count = 0;while(i < str.length()) {if(!Character.isDigit(str.charAt(i))) {break;}count = count * 10 + str.charAt(i++) - '0';if(count * sign > Integer.MAX_VALUE || count * sign < Integer.MIN_VALUE) {return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;}}return (int) (count * sign);}}
10. 正则表达式匹配
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。
方法一：递归
本题难点在于’’ 匹配零个或多个前面的那一个元素，例如a，则a可以为0个或多个
所以根据’‘是否为p中的第二个元素，分两种情况考虑
1.p中第二个元素不为’‘，每次比较第一个元素，相同后，去除第一个元素，进入下一次递归，直至p对s匹配完
2.p中第二个元素为’’，必然p长度要大于2，因为’’前面必然有一个元素，分为匹配前零个和匹配前一个元素两种情况考虑
2.1 匹配前零个元素，即’’的前一个元素没有匹配的，则s不变，将p中的’’和前一个元素去除，即去除首部2个元素
2.2 匹配前一个元素，即’‘的前一个元素有匹配的，则将s的第一个元素去除，p不变
类似存在s=’abb’,p=’aabb’;
按2.1来说，p剪去两个元素，s=’abb’,p=’abb’，成功；
按2.2来说，s=’bb’,p=’a*abb’,失败；
所以，2.1与2.2的关系是或，只要2.1或2.2有一个为真则返回真
class Solution {
public boolean isMatch(String s, String p) {
// 递归终止条件
if (p.isEmpty()) {
return s.isEmpty();
}
// 第一个字符串是否匹配
boolean firstMatch = !s.isEmpty() && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.');
// 模式串下一个是否为'*'
if (p.length() > 1 && p.charAt(1) == '*') {
return isMatch(s, p.substring(2)) || (firstMatch && isMatch(s.substring(1), p));
}
return firstMatch && isMatch(s.substring(1), p.substring(1));
}
}
方法二：动态规划
dp[i][j] 表示的状态是 s 的前 i 项和 p 的前 j 项是否匹配
1. s[i] == p[j] or p[j] == ‘.’：比如 abb 和 abb，或者 abb 和 ab.，
很容易得到 dp[i][j] = dp[i-1][j-1] = True。
因为 ab 和 ab 是匹配的，如果后面分别加一个 b，或者 s 加一个 b 而 p 加一个 ，仍然是匹配的。
2. p[j] == ‘‘：当 p[j] 为’‘时，由于’‘与前面的字符相关，
因此我们比较’‘前面的字符 p[j-1] 和 s[i] 的关系。根据’‘前面的字符与 s[i] 是否相等，又可分为以下两种情况：
2.1 p[j-1] != s[i]：如果’‘前一个字符匹配不上，即’‘号匹配了0次，因忽略’‘和其前面的一个字母，看p[j-2] 和 s[i] 是否匹配。 这时 dp[i][j] = dp[i][j-2]。
2.2 p[j-1] == s[i] or p[j-1] == ‘.’: ‘‘前面的字符可以与 s[i] 匹配，这种情况下，’‘可能匹配了前面的字符的 0 个，也可能匹配了前面字符的多个，
2.2.1 当匹配 0 个时，如 ab 和 abb，或者 ab 和 ab. ，这时我们需要去掉 p 中的 b 或 . 后进行比较，即 dp[i][j] = dp[i][j-2]；
2.2.2 当匹配多个（包括1个）时，如 abbb 和 ab，ab和ab，或者 abbb 和 a.，则s[i-1]=p[j]，即 dp[i][j] = dp[i-1][j]
只要2.2.1或2.2.2其中有一个为真，则返回真
3. 特殊情况，当s为空时即dp[0][j]，若p的长度大于2，如a或ab，可以匹配成功，即dp[0][j] = dp[0]dp[j-2]
4. 以上两种情况把能匹配的都考虑全面了，所以其他情况为不匹配，即 dp[i][j] = False
44. 通配符匹配
给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 ‘?’ 和 ‘*’ 的通配符匹配。
class Solution {
public boolean isMatch(String s, String p) {
int m = s.length(), n = p.length();
boolean[][] dp = new boolean[m + 1][n + 1];
// dp[i][j] 表示 s中前i个字符组成的子串和p中前j个字符组成的子串是否能匹配
dp[0][0] = true;
// 当s为空，p为连续的星号时的情况
for (int j = 1; j <= n; j++) {
if (p.charAt(j - 1) == '*') {
dp[0][j] = dp[0][j - 1];
}
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (p.charAt(j - 1) == '*') {
dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
} else {
dp[i][j] = (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '?') && dp[i - 1][j - 1];
}
}
}
return dp[m][n];
}
}
151. 翻转字符串里的单词
415. 字符串相加
给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和。
提示：
- num1 和num2 的长度都小于 5100
- num1 和num2 都只包含数字 0-9
- num1 和num2 都不包含任何前导零
- 你不能使用任何內建 BigInteger 库， 也不能直接将输入的字符串转换为整数形式
思路：
class Solution {
public String addStrings(String num1, String num2) {
StringBuilder sb = new StringBuilder();
int i = num1.length() - 1, j = num2.length() - 1, carry = 0;
while (i >=0 || j >= 0 || carry != 0) {
if (i >= 0) {
carry += num1.charAt(i--) - '0';
}
if (j >= 0) {
carry += num2.charAt(j--) - '0';
}
sb.append(carry % 10);
carry = carry / 10;
}
return sb.reverse().toString();
}
}
剑指 Offer
剑指 Offer 05. 替换空格
请实现一个函数，把字符串 s 中的每个空格替换成”%20”。
思路：
①利用replaceAll()进行替换。
class Solution {
public String replaceSpace(String s) {
return s.replaceAll(" ", "%20");
}
}
②字符数组。初始化数组长度为字符串长度的三倍，然后遍历字符数组。
class Solution {
public String replaceSpace(String s) {
int length = s.length();
char[] array = new char[length * 3];
int size = 0;
for (int i = 0; i < length; i++) {
char c = s.charAt(i);
if (c == ' ') {
array[size++] = '%';
array[size++] = '2';
array[size++] = '0';
} else {
array[size++] = c;
}
}
String newStr = new String(array, 0, size);
return newStr;
}
}
③使用StringBuilder。
class Solution {
public String replaceSpace(String s) {
StringBuilder stringBuilder = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == ' ')
stringBuilder.append("%20");
else
stringBuilder.append(s.charAt(i));
}
return stringBuilder.toString();
}
}
剑指 Offer 19. 正则表达式匹配
请实现一个函数用来匹配包含'. '和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但与"aa.a"和"ab*a"均不匹配。
思路：
①字符串。先匹配第一个字符。然后看模式串的第二个字符是否为'*'，如果是，则看以下两种情况是否匹配：一，'*'表示前一个字符为空；二，'*'表示前一个字符有多个。
class Solution {
public boolean isMatch(String s, String p) {
// 递归出口
if (p.isEmpty()) {
return s.isEmpty();
}
boolean firstMatch = !s.isEmpty() && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.');
if (p.length() > 1 && p.charAt(1) == '*') {
return isMatch(s, p.substring(2)) || (firstMatch && isMatch(s.substring(1), p));
}
return firstMatch && isMatch(s.substring(1), p.substring(1));
}
}
剑指 Offer 20. 表示数值的字符串
请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串”+100”、”5e2”、”-123”、”3.1416”、”-1E-16”、”0123”都表示数值，但”12e”、”1a3.14”、”1.2.3”、”+-5”及”12e+5.4”都不是。
思路：
字符串。
- 用
trim()去除两边的空格； - 以
-53.5e-2为例，先找符号位，然后查找数字； - 接着小数点，再次查找数字；
然后看是否有
E，如果有则要先找符号位，再找数字。class Solution { private int index = 0; public boolean isNumber(String s) { if (s.length() < 1) return false; s = s.trim(); int len = s.length(); boolean flag = scanInteger(s); if (index < len && s.charAt(index) == '.') { index++; flag = scanUnsignedInteger(s) || flag; } if (index < len && (s.charAt(index) == 'E' || s.charAt(index) == 'e')) { index++; flag = flag && scanInteger(s); } return flag && index == len; } private boolean scanInteger(String s) { if (index < s.length() && (s.charAt(index) == '+' || s.charAt(index) == '-')) { index++; } return scanUnsignedInteger(s); } private boolean scanUnsignedInteger(String s) { int start = index; while (index < s.length() && s.charAt(index) >= '0' && s.charAt(index) <= '9') { index++; } return start < index; // 是否存在整数 } }剑指 Offer 38. 字符串的排列
输入一个字符串，打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
思路：
①深度优先搜索。主要是处理重复字符的情况，见注释。
class Solution {
public String[] permutation(String s) {
List<String> list = new ArrayList<>();
if (s.equals("")) {
return new String[]{};
}
String[] strs = s.split("");
boolean[] used = new boolean[strs.length];
StringBuilder sb = new StringBuilder();
Arrays.sort(strs); // 便于处理重复字符
dfs(strs, used, sb, list);
String[] res = new String[list.size()];
for (int i = 0; i < list.size(); i++) {
res[i] = list.get(i);
}
return res;
}
private void dfs(String[] strs, boolean[] used, StringBuilder sb, List<String> list) {
if (sb.length() == strs.length){
list.add(sb.toString());
}
for (int i = 0; i < strs.length; i++) {
if (used[i]) {
continue;
}
// 按顺序使用，重复字符如果前一个用过了，才用接下来的一个；如果前一个没用过，当前的就不用。避免重复。
if (i > 0 && strs[i - 1].equals(strs[i]) && !used[i - 1]) {
continue;
}
used[i] = true;
sb.append(strs[i]);
dfs(strs, used, sb, list);
sb.delete(sb.length()-1, sb.length());
used[i] = false;
}
}
}
②深度优先搜索，优化版本。String转成字符数组，使用toArray方法。
class Solution {
public String[] permutation(String s) {
int len = s.length();
if (len == 0) {
return new String[0];
}
// 转换成字符数组是常见的做法
char[] charArr = s.toCharArray();
// 排序是为了去重方便
Arrays.sort(charArr);
// 由于操作的都是字符，使用 StringBuilder
StringBuilder path = new StringBuilder();
boolean[] used = new boolean[len];
// 为了方便收集结果，使用动态数组
List<String> res = new ArrayList<>();
dfs(charArr, len, 0, used, path, res);
// 记得转成字符串数组
return res.toArray(new String[0]);
}
/**
* @param charArr 字符数组
* @param len 字符数组的长度
* @param depth 当前递归深度
* @param used 当前字符是否使用
* @param path 从根结点到叶子结点的路径
* @param res 保存结果集的变量
*/
private void dfs(char[] charArr,
int len,
int depth,
boolean[] used,
StringBuilder path,
List<String> res) {
if (depth == len) {
// path.toString() 恰好生成了新的字符对象
res.add(path.toString());
return;
}
for (int i = 0; i < len; i++) {
if (!used[i]) {
if (i > 0 && charArr[i] == charArr[i - 1] && !used[i - 1]) {
continue;
}
used[i] = true;
path.append(charArr[i]);
dfs(charArr, len, depth + 1, used, path, res);
// 递归完成以后，需要撤销选择，递归方法执行之前做了什么，递归方法执行以后就需要做相应的逆向操作
path.deleteCharAt(path.length() - 1);
used[i] = false;
}
}
}
}
剑指 Offer 58 - I. 翻转单词顺序
输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串”I am a student. “，则输出”student. a am I”。
说明：
- 无空格字符构成一个单词。
- 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
- 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
思路：
字符串。删除首尾空格，分割字符串。倒序遍历单词列表。遇到空单词则跳过。将单词拼接至 StringBuilder。转化为字符串，删除尾部空格，并返回。
执行用时：2 ms, 在所有 Java 提交中击败了87.74%的用户
内存消耗：40.1 MB, 在所有 Java 提交中击败了100.00%的用户
class Solution {
public String reverseWords(String s) {
String[] strs = s.trim().split(" ");
StringBuilder res = new StringBuilder();
for (int i = strs.length - 1; i >= 0; i--) {
if (strs[i].equals("")) {
continue;
}
res.append(strs[i] + " ");
}
return res.toString().trim();
}
}
剑指 Offer 58 - II. 左旋转字符串
字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串”abcdefg”和数字2，该函数将返回左旋转两位得到的结果”cdefgab”。
思路：
字符串。
执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：39.5 MB, 在所有 Java 提交中击败了100.00%的用户
class Solution {
public String reverseLeftWords(String s, int n) {
if(s.length() < n) return "";
StringBuffer sb = new StringBuffer();
sb.append(s.substring(n)).append(s.substring(0,n));
return sb.toString();
}
}
面试
给定一个字符串s，输出含有连续两个s作为子串的最短字符串
思路：
- 从特殊到一般
abc -> abcabc，aba -> ababa，aaa -> aaaa，abcdab -> abcdabcdab - 论证确实是寻找包含s中最后一个字符的s的子串与包含s中第一个字符的s的子串相等的最长子串。
- 显然result.length > s.length
abcdab -> abcdabcd 不能是 abcdabcddc非最短字符串
public class shortestTwoString { public static void main(String[] args) { System.out.println(generateString("abc")); System.out.println(generateString("abca")); System.out.println(generateString("abcdab")); System.out.println(generateString("aaa")); System.out.println(generateString("aaabbbaaa")); } private static String generateString(String str) { int len = str.length(), index = 0; for (int i = len - 1; i >= 0; i--) { String prefix = str.substring(0, i); if (str.endsWith(prefix)) { index = Math.max(i, index); } } return str + str.substring(index, len); } }
若有收获，就点个赞吧
0 人点赞
