02数组+字符串+滑动窗口+前缀和与差分+双指针（D2_字符串（D2_刷题练习））
目录
1. 最长公共前缀
1.1. 题目描述
1.2. 解题方案
方案一：纵向对比
方案二：横向对比
方案三：最值对比
方案四：分治
方案五：二分
1.3. 知识归纳
2. 左旋转字符串（简单）
2.1. 题目描述
2.2. 解题思路
方法一：字符串切片
方法二：列表遍历拼接
方法三：字符串遍历拼接
3. 表示数值的字符串（中等）
3.1. 题目描述
3.2. 解题思路
方法一：确定有限状态自动机
4. 把字符串转换成整数（中等）
4.1. 题目描述
4.2. 解题思路
5. 交替合并字符串（简单）
5.1. 题目描述
5.2. 解题思路
方法一：双指针
6. 字符串的最大公因子（简单）
6.1. 题目描述
6.2. 解题思路
方法一：枚举
方法二：枚举优化
方法三：数学
7. 反转字符串中的元音字母（简单）
7.1. 题目描述
7.2. 解题思路
方法一：双指针
8. 递增的三元子序列（中等）
8.1. 题目描述
8.2. 解题思路
方法一：双向遍历
方法二：贪心
9. 压缩字符串（中等）
9.1. 题目描述
9.2. 解题思路
方法一：双指针
10. 反转字符串中的单词（中等）
10.1. 题目描述
10.2. 解题思路
方法一：使用语言特性
方法二：自行编写对应的函数
方法三：双端队列
11. 字符串变形（简单）
11.1. 题目描述
11.2. 解题思路
方法一：双逆转（推荐使用）
方法二：分割字符串+栈（扩展思路）
12. 最长公共前缀
12.1. 题目描述
12.2. 解题思路
方法一：遍历查找(推荐使用)
13. 验证IP地址
13.1. 题目描述
13.2. 解题思路
方法一：分割字符串比较法（推荐使用）
方法二：正则表达式（扩展思路）
14. 大数加法
14.1. 题目描述
14.2. 解题思路
方法一：模拟法（建议使用）
15. 无重复字符的最长子串
15.1. 题目描述
15.2. 解题思路
方法一：滑动窗口
16. 找到字符串中所有字母异位词（中等）
16.1. 题目描述
16.2. 解题思路
方法一：滑动窗口
方法二：优化的滑动窗口
17. 定长子串中元音的最大数目（中等）
17.1. 题目描述
17.2. 解题思路
方法一：滑动窗口
18. 判断是否为回文字符串
18.1. 题目描述
18.2. 解题思路
方法一：首尾依次比较法（推荐使用）
方法二：反转字符串比较法（扩展思路）
19. 最小覆盖子串（较难）
19.1. 题目描述
19.2. 解题思路
方法一：哈希表匹配（推荐使用）
20. 反转字符串（入门）
20.1. 题目描述
20.2. 解题思路
解法一
解法二
解法三
1. 最长公共前缀
1.1. 题目描述
1.2. 解题方案
对于一个问题，采用一题多解，才能深刻理解其考察的知识点，进行举一反三。
最长公共前缀，可横向对比 / 竖向对比 / 最值对比 / 分治 / 二分方法来完成题解。
方案一：纵向对比
public String longestCommonPrefix(String[] strs) {for (int i = 0; i < strs[0].length(); i++) {char ch = strs[0].charAt(i);for (int j = 1; j < strs.length; j++) {if (i == strs[j].length() || strs[j].charAt(i) != ch) return strs[0].substring(0, i);}}return strs[0];}方案二：横向对比
// idea6:横向扫描（暴力之一）public String longestCommonPrefix6(String[] strs) {String prefix = strs[0];for (String s : strs) prefix = compareStr(prefix, s);return prefix;}private String compareStr(String s1, String s2) {int idx = 0;while (idx < s1.length() && idx < s2.length() && s1.charAt(idx) == s2.charAt(idx)) ++idx;return s1.substring(0, idx);}方案三：最值对比
public String longestCommonPrefix3(String[] strs) {String min = strs[0], max = strs[0];for (String str : strs) {// bug1:字符串的compare和integer的不一样，并非-1 / 0 / 1，而是长度相减作为返回值。if (min.compareTo(str) > 0) min = str;if (max.compareTo(str) < 0) max = str;}return compareStr(min, max);}private String compareStr(String s1, String s2) {int idx = 0;while (idx < s1.length() && idx < s2.length() && s1.charAt(idx) == s2.charAt(idx)) ++idx;return s1.substring(0, idx);}方案四：分治
private String partition(String[] strs, int left, int right) {if (left == right) return strs[left];int mid = left + (right - left >> 1);String s1 = partition(strs, left, mid);String s2 = partition(strs, mid + 1, right);return compareStr(s1, s2);}private String compareStr(String s1, String s2) {int idx = 0;while (idx < s1.length() && idx < s2.length() && s1.charAt(idx) == s2.charAt(idx)) ++idx;return s1.substring(0, idx);}方案五：二分
public String longestCommonPrefix5(String[] strs) {String s = strs[0];// 有可能需要idx = 0的位置，所以也会需要s.len的位置。int low = 0, high = s.length();// 用二分法去快速寻找公共前缀的右边界。while (low < high) {int mid = low + (high - low + 1 >> 1);// 为了low不越界，这里必须+1防止死循环。String midStr = s.substring(0, mid);if (isMatchAll(strs, midStr)) low = mid;else high = mid - 1;}return s.substring(0, low);}private boolean isMatchAll(String[] strs, String str) {for (String s : strs) {if (s.length() < str.length() || !str.equals(s.substring(0, str.length()))) return false;}return true;}1.3. 知识归纳
最长公共前缀，可横向对比 / 竖向对比 / 最值对比 / 分治 / 二分方法来完成题解。
对于分治来讲，可多线程操作加快速度；
对于二分，考察对抽象二分的理解，将二分规则进行抽象。
2. 左旋转字符串（简单）
2.1. 题目描述
2.2. 解题思路
方法一：字符串切片
class Solution {public String reverseLeftWords(String s, int n) {return s.substring(n, s.length()) + s.substring(0, n);}
}方法二：列表遍历拼接
class Solution {public String reverseLeftWords(String s, int n) {StringBuilder res = new StringBuilder();for(int i = n; i < s.length(); i++)res.append(s.charAt(i));for(int i = 0; i < n; i++)res.append(s.charAt(i));return res.toString();}
}方法三：字符串遍历拼接
class Solution {public String reverseLeftWords(String s, int n) {String res = "";for(int i = n; i < s.length(); i++)res += s.charAt(i);for(int i = 0; i < n; i++)res += s.charAt(i);return res;}
}3. 表示数值的字符串（中等）
3.1. 题目描述
3.2. 解题思路
方法一：确定有限状态自动机
class Solution {public boolean isNumber(String s) {Map<State, Map<CharType, State>> transfer = new HashMap<State, Map<CharType, State>>();Map<CharType, State> initialMap = new HashMap<CharType, State>() {{put(CharType.CHAR_SPACE, State.STATE_INITIAL);put(CharType.CHAR_NUMBER, State.STATE_INTEGER);put(CharType.CHAR_POINT, State.STATE_POINT_WITHOUT_INT);put(CharType.CHAR_SIGN, State.STATE_INT_SIGN);}};transfer.put(State.STATE_INITIAL, initialMap);Map<CharType, State> intSignMap = new HashMap<CharType, State>() {{put(CharType.CHAR_NUMBER, State.STATE_INTEGER);put(CharType.CHAR_POINT, State.STATE_POINT_WITHOUT_INT);}};transfer.put(State.STATE_INT_SIGN, intSignMap);Map<CharType, State> integerMap = new HashMap<CharType, State>() {{put(CharType.CHAR_NUMBER, State.STATE_INTEGER);put(CharType.CHAR_EXP, State.STATE_EXP);put(CharType.CHAR_POINT, State.STATE_POINT);put(CharType.CHAR_SPACE, State.STATE_END);}};transfer.put(State.STATE_INTEGER, integerMap);Map<CharType, State> pointMap = new HashMap<CharType, State>() {{put(CharType.CHAR_NUMBER, State.STATE_FRACTION);put(CharType.CHAR_EXP, State.STATE_EXP);put(CharType.CHAR_SPACE, State.STATE_END);}};transfer.put(State.STATE_POINT, pointMap);Map<CharType, State> pointWithoutIntMap = new HashMap<CharType, State>() {{put(CharType.CHAR_NUMBER, State.STATE_FRACTION);}};transfer.put(State.STATE_POINT_WITHOUT_INT, pointWithoutIntMap);Map<CharType, State> fractionMap = new HashMap<CharType, State>() {{put(CharType.CHAR_NUMBER, State.STATE_FRACTION);put(CharType.CHAR_EXP, State.STATE_EXP);put(CharType.CHAR_SPACE, State.STATE_END);}};transfer.put(State.STATE_FRACTION, fractionMap);Map<CharType, State> expMap = new HashMap<CharType, State>() {{put(CharType.CHAR_NUMBER, State.STATE_EXP_NUMBER);put(CharType.CHAR_SIGN, State.STATE_EXP_SIGN);}};transfer.put(State.STATE_EXP, expMap);Map<CharType, State> expSignMap = new HashMap<CharType, State>() {{put(CharType.CHAR_NUMBER, State.STATE_EXP_NUMBER);}};transfer.put(State.STATE_EXP_SIGN, expSignMap);Map<CharType, State> expNumberMap = new HashMap<CharType, State>() {{put(CharType.CHAR_NUMBER, State.STATE_EXP_NUMBER);put(CharType.CHAR_SPACE, State.STATE_END);}};transfer.put(State.STATE_EXP_NUMBER, expNumberMap);Map<CharType, State> endMap = new HashMap<CharType, State>() {{put(CharType.CHAR_SPACE, State.STATE_END);}};transfer.put(State.STATE_END, endMap);int length = s.length();State state = State.STATE_INITIAL;for (int i = 0; i < length; i++) {CharType type = toCharType(s.charAt(i));if (!transfer.get(state).containsKey(type)) {return false;} else {state = transfer.get(state).get(type);}}return state == State.STATE_INTEGER || state == State.STATE_POINT || state == State.STATE_FRACTION || state == State.STATE_EXP_NUMBER || state == State.STATE_END;}public CharType toCharType(char ch) {if (ch >= '0' && ch <= '9') {return CharType.CHAR_NUMBER;} else if (ch == 'e' || ch == 'E') {return CharType.CHAR_EXP;} else if (ch == '.') {return CharType.CHAR_POINT;} else if (ch == '+' || ch == '-') {return CharType.CHAR_SIGN;} else if (ch == ' ') {return CharType.CHAR_SPACE;} else {return CharType.CHAR_ILLEGAL;}}enum State {STATE_INITIAL,STATE_INT_SIGN,STATE_INTEGER,STATE_POINT,STATE_POINT_WITHOUT_INT,STATE_FRACTION,STATE_EXP,STATE_EXP_SIGN,STATE_EXP_NUMBER,STATE_END}enum CharType {CHAR_NUMBER,CHAR_EXP,CHAR_POINT,CHAR_SIGN,CHAR_SPACE,CHAR_ILLEGAL}
}4. 把字符串转换成整数（中等）
4.1. 题目描述
请问什么是有符号整数？
有符号整数，就是int，因为有正负之分，所以16位的第一位表示正负，0为正，1为负所以能表示的范围
是-32768～+32767（-2e15～2e15-1）而无符号整数，就是定义为unsigned int，因为第一位不用代
表正负了，没有符号，全是正的啊，所以16位全为有效位，所以范围是0～65535（0～2e16-1）
4.2. 解题思路
class Solution {public int strToInt(String str) {char[] c = str.trim().toCharArray();if(c.length == 0) return 0;int res = 0, bndry = Integer.MAX_VALUE / 10;int i = 1, sign = 1;if(c[0] == '-') sign = -1;else if(c[0] != '+') i = 0;for(int j = i; j < c.length; j++) {if(c[j] < '0' || c[j] > '9') break;if(res > bndry || res == bndry && c[j] > '7') return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;res = res * 10 + (c[j] - '0');}return sign * res;}
}若不使用trim() / strip() 方法，而从头开始遍历字符串，则可以将空间复杂度降低至 O(1) ，代码如下：
class Solution {public int strToInt(String str) {int res = 0, bndry = Integer.MAX_VALUE / 10;int i = 0, sign = 1, length = str.length();if(length == 0) return 0;while(str.charAt(i) == ' ')if(++i == length) return 0;if(str.charAt(i) == '-') sign = -1;if(str.charAt(i) == '-' || str.charAt(i) == '+') i++;for(int j = i; j < length; j++) {if(str.charAt(j) < '0' || str.charAt(j) > '9') break;if(res > bndry || res == bndry && str.charAt(j) > '7')return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;res = res * 10 + (str.charAt(j) - '0');}return sign * res;}}5. 交替合并字符串（简单）
5.1. 题目描述
5.2. 解题思路
方法一：双指针
class Solution {public String mergeAlternately(String word1, String word2) {int m = word1.length(), n = word2.length();int i = 0, j = 0;StringBuilder ans = new StringBuilder();while (i < m || j < n) {if (i < m) {ans.append(word1.charAt(i));++i;}if (j < n) {ans.append(word2.charAt(j));++j;}}return ans.toString();}
}
6. 字符串的最大公因子（简单）
6.1. 题目描述
什么是最大公因数 最大公因数的解释
1、最大公因数，也称为最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个。
2、a，b的最大公约数记为（a，b），同样的，a，b，c的最大公约数记为（a，b，c），多个整数的最
大公约数也有同样的记号。
求最大公约数有多种方法，常见的有质因数分解法、短除法、辗转相除法、更相减损法。
与最大公约数相对应的概念是最小公倍数，a，b的最小公倍数记为[a，b]。
6.2. 解题思路
方法一：枚举
class Solution {// 字符串最大公因子public String gcdOfStrings(String str1, String str2) {// 获取两个字符串长度int len1 = str1.length(), len2 = str2.length();// 从长度小的开始枚举for (int i = Math.min(len1, len2); i >= 1; --i) {// 前缀串的长度必然是两个字符串长度的约数才能满足条件if (len1 % i == 0 && len2 % i == 0) {// 截取子串String X = str1.substring(0, i);// 检测子串是否能被两个字符串整除if (check(X, str1) && check(X, str2)) {return X;}}}return "";}public boolean check(String t, String s) {int lenx = s.length() / t.length();StringBuffer ans = new StringBuffer();for (int i = 1; i <= lenx; ++i) {ans.append(t);}return ans.toString().equals(s);}
}
方法二：枚举优化
class Solution {// 字符串最大公因子public String gcdOfStrings(String str1, String str2) {// 获取两个字符串长度int len1 = str1.length(), len2 = str2.length();// 截取子串（截取到最大公因子）String T = str1.substring(0, gcd(len1, len2));// 检测子串是否能被两个字符串整除if (check(T, str1) && check(T, str2)) {return T;}return "";}public boolean check(String t, String s) {int lenx = s.length() / t.length();StringBuffer ans = new StringBuffer();for (int i = 1; i <= lenx; ++i) {ans.append(t);}return ans.toString().equals(s);}// 求最大公因子public int gcd(int a, int b) {int remainder = a % b;while (remainder != 0) {a = b;b = remainder;remainder = a % b;}return b;}
}
方法三：数学
class Solution {// 字符串最大公因子public String gcdOfStrings(String str1, String str2) {// 两个字符串相连不相等，直接返回空串if (!str1.concat(str2).equals(str2.concat(str1))) {return "";}// return str1.substring(0, gcd(str1.length(), str2.length()));}// 截取子串（截取到最大公因子）public int gcd(int a, int b) {int remainder = a % b;while (remainder != 0) {a = b;b = remainder;remainder = a % b;}return b;}
}
7. 反转字符串中的元音字母（简单）
7.1. 题目描述
7.2. 解题思路
方法一：双指针
class Solution {public String reverseVowels(String s) {int n = s.length();char[] arr = s.toCharArray();int i = 0, j = n - 1;while (i < j) {while (i < n && !isVowel(arr[i])) {++i;}while (j > 0 && !isVowel(arr[j])) {--j;}if (i < j) {swap(arr, i, j);++i;--j;}}return new String(arr);}public boolean isVowel(char ch) {return "aeiouAEIOU".indexOf(ch) >= 0;}public void swap(char[] arr, int i, int j) {char temp = arr[i];arr[i] = arr[j];arr[j] = temp;}
}
8. 递增的三元子序列（中等）
8.1. 题目描述
8.2. 解题思路
方法一：双向遍历
class Solution {public boolean increasingTriplet(int[] nums) {int n = nums.length;if (n < 3) {return false;}int[] leftMin = new int[n];leftMin[0] = nums[0];for (int i = 1; i < n; i++) {leftMin[i] = Math.min(leftMin[i - 1], nums[i]);}int[] rightMax = new int[n];rightMax[n - 1] = nums[n - 1];for (int i = n - 2; i >= 0; i--) {rightMax[i] = Math.max(rightMax[i + 1], nums[i]);}for (int i = 1; i < n - 1; i++) {if (nums[i] > leftMin[i - 1] && nums[i] < rightMax[i + 1]) {return true;}}return false;}
}
方法二：贪心
class Solution {public boolean increasingTriplet(int[] nums) {int n = nums.length;if (n < 3) {return false;}int first = nums[0], second = Integer.MAX_VALUE;for (int i = 1; i < n; i++) {int num = nums[i];if (num > second) {return true;} else if (num > first) {second = num;} else {first = num;}}return false;}
}
9. 压缩字符串（中等）
9.1. 题目描述
9.2. 解题思路
方法一：双指针
class Solution {public int compress(char[] chars) {int n = chars.length;int write = 0, left = 0;for (int read = 0; read < n; read++) {if (read == n - 1 || chars[read] != chars[read + 1]) {chars[write++] = chars[read];int num = read - left + 1;if (num > 1) {int anchor = write;while (num > 0) {chars[write++] = (char) (num % 10 + '0');num /= 10;}reverse(chars, anchor, write - 1);}left = read + 1;}}return write;}public void reverse(char[] chars, int left, int right) {while (left < right) {char temp = chars[left];chars[left] = chars[right];chars[right] = temp;left++;right--;}}
}
10. 反转字符串中的单词（中等）
10.1. 题目描述
10.2. 解题思路
方法一：使用语言特性
class Solution {public String reverseWords(String s) {// 除去开头和末尾的空白字符s = s.trim();// 正则匹配连续的空白字符作为分隔符分割List<String> wordList = Arrays.asList(s.split("\\s+"));Collections.reverse(wordList);return String.join(" ", wordList);}
}
方法二：自行编写对应的函数
class Solution {public String reverseWords(String s) {StringBuilder sb = trimSpaces(s);// 翻转字符串reverse(sb, 0, sb.length() - 1);// 翻转每个单词reverseEachWord(sb);return sb.toString();}public StringBuilder trimSpaces(String s) {int left = 0, right = s.length() - 1;// 去掉字符串开头的空白字符while (left <= right && s.charAt(left) == ' ') {++left;}// 去掉字符串末尾的空白字符while (left <= right && s.charAt(right) == ' ') {--right;}// 将字符串间多余的空白字符去除StringBuilder sb = new StringBuilder();while (left <= right) {char c = s.charAt(left);if (c != ' ') {sb.append(c);} else if (sb.charAt(sb.length() - 1) != ' ') {sb.append(c);}++left;}return sb;}public void reverse(StringBuilder sb, int left, int right) {while (left < right) {char tmp = sb.charAt(left);sb.setCharAt(left++, sb.charAt(right));sb.setCharAt(right--, tmp);}}public void reverseEachWord(StringBuilder sb) {int n = sb.length();int start = 0, end = 0;while (start < n) {// 循环至单词的末尾while (end < n && sb.charAt(end) != ' ') {++end;}// 翻转单词reverse(sb, start, end - 1);// 更新start，去找下一个单词start = end + 1;++end;}}
}
方法三：双端队列
class Solution {public String reverseWords(String s) {int left = 0, right = s.length() - 1;// 去掉字符串开头的空白字符while (left <= right && s.charAt(left) == ' ') {++left;}// 去掉字符串末尾的空白字符while (left <= right && s.charAt(right) == ' ') {--right;}Deque<String> d = new ArrayDeque<String>();StringBuilder word = new StringBuilder();while (left <= right) {char c = s.charAt(left);if ((word.length() != 0) && (c == ' ')) {// 将单词 push 到队列的头部d.offerFirst(word.toString());word.setLength(0);} else if (c != ' ') {word.append(c);}++left;}d.offerFirst(word.toString());return String.join(" ", d);}
}
11. 字符串变形（简单）
11.1. 题目描述
11.2. 解题思路
方法一：双逆转（推荐使用）
Java代码实现:
import java.util.*;
public class Solution {public String trans(String s, int n) {if(n==0) return s;StringBuffer res=new StringBuffer();for(int i = 0; i < n; i++){//大小写转换if(s.charAt(i) <= 'Z' && s.charAt(i) >= 'A') res.append((char)(s.charAt(i) - 'A' + 'a'));else if(s.charAt(i) >= 'a' && s.charAt(i) <= 'z') res.append((char)(s.charAt(i) - 'a' + 'A'));else //空格直接复制res.append(s.charAt(i)); } //翻转整个字符串res = res.reverse();for (int i = 0; i < n; i++){int j = i;//以空格为界，二次翻转while(j < n && res.charAt(j) != ' ') j++;String temp = res.substring(i,j);StringBuffer buffer = new StringBuffer(temp);temp = buffer.reverse().toString();res.replace(i,j,temp);i = j;}return res.toString();}
}
方法二：分割字符串+栈（扩展思路）
java代码实现：
import java.util.*;
public class Solution {public String trans(String s, int n) {if(n==0) return s;StringBuffer res=new StringBuffer();for (int i = 0; i < n; i++){//大小写转换if(s.charAt(i) <= 'Z' && s.charAt(i) >= 'A') res.append((char)(s.charAt(i) - 'A' + 'a'));else if(s.charAt(i) >= 'a' && s.charAt(i) <= 'z') res.append((char)(s.charAt(i) - 'a' + 'A'));else //空格直接复制res.append((char)(s.charAt(i))); }Stack<String> temp=new Stack<String>();for (int i = 0; i < n; i++){int j = i;//以空格为界，分割单词while(j < n && res.charAt(j) != ' ') j++;//单词进栈temp.push((String)(res.substring(i, j))); i = j;}//排除结尾空格的特殊情况if(s.charAt(n - 1) == ' ') res = new StringBuffer(" ");elseres = new StringBuffer();//栈遵循先进后厨，单词顺序是反的while(!temp.empty()){ res.append(temp.peek());temp.pop();if(!temp.empty())res.append(" ");}return res.toString();}
}
12. 最长公共前缀
12.1. 题目描述
12.2. 解题思路
方法一：遍历查找(推荐使用)
Java代码实现:
import java.util.*;
public class Solution {public String longestCommonPrefix (String[] strs) {int n = strs.length;//空字符串数组if(n == 0) return "";//遍历第一个字符串的长度for(int i = 0; i < strs[0].length(); i++){ char temp = strs[0].charAt(i); //遍历后续的字符串for(int j = 1; j < n; j++) //比较每个字符串该位置是否和第一个相同if(i == strs[j].length() || strs[j].charAt(i) != temp) //不相同则结束return strs[0].substring(0, i); }//后续字符串有整个字一个字符串的前缀return strs[0]; }
}
13. 验证IP地址
13.1. 题目描述
13.2. 解题思路
方法一：分割字符串比较法（推荐使用）
java代码实现:
import java.util.*;
public class Solution {boolean isIPv4 (String IP) {if(IP.indexOf('.') == -1){return false;}String[] s = IP.split("\\."); //IPv4必定为4组if(s.length != 4) return false;for(int i = 0; i < s.length; i++){//不可缺省，有一个分割为零，说明两个点相连if(s[i].length() == 0) return false;//比较数字位数及不为零时不能有前缀零if(s[i].length() < 0 || s[i].length() > 3 || (s[i].charAt(0)=='0' && s[i].length() != 1)) return false;int num = 0;//遍历每个分割字符串，必须为数字for(int j = 0; j < s[i].length(); j++){ char c = s[i].charAt(j);if (c < '0' || c > '9') return false;//转化为数字比较，0-255之间num = num * 10 + (int)(c - '0'); if(num < 0 || num > 255) return false;}} return true;}boolean isIPv6 (String IP) {if (IP.indexOf(':') == -1) {return false;}String[] s = IP.split(":",-1);//IPv6必定为8组if(s.length != 8){ return false;}for(int i = 0; i < s.length; i++){ //每个分割不能缺省，不能超过4位if(s[i].length() == 0 || s[i].length() > 4){ return false; }for(int j = 0; j < s[i].length(); j++){//不能出现a-fA-F以外的大小写字符char c = s[i].charAt(j);boolean expr = (c >= '0' && c <= '9') || (c >= 'a' && c <= 'f') || (c >= 'A' && c <= 'F') ;if(!expr){return false;}}}return true;}String solve(String IP) {if(isIPv4(IP))return "IPv4";else if(isIPv6(IP))return "IPv6";return "Neither";}
}
方法二：正则表达式（扩展思路）
Java代码实现:
import java.util.regex.Pattern;
public class Solution {String solve(String IP) {//正则表达式限制0-255 且没有前缀0 四组齐全String ipv4="(([0-9]|[1-9][0-9]|1[0-9][0-9]|2[0-4][0-9]|25[0-5])\\.){3}([0-9]|[1-9][0-9]|1[0-9][0-9]|2[0-4][0-9]|25[0-5])";Pattern ipv4_pattern = Pattern.compile(ipv4);//正则表达式限制出现8组，0-9a-fA-F的数，个数必须是1-4个String ipv6="([0-9a-fA-F]{1,4}\\:){7}[0-9a-fA-F]{1,4}";Pattern ipv6_pattern = Pattern.compile(ipv6);//调用正则匹配函数if (ipv4_pattern.matcher(IP).matches()) return "IPv4";else if (ipv6_pattern.matcher(IP).matches()) return "IPv6";else return "Neither";}
}
14. 大数加法
14.1. 题目描述
14.2. 解题思路
方法一：模拟法（建议使用）
Java代码实现:
import java.util.*;
public class Solution {public String solve (String s, String t) {//若是其中一个为空，返回另一个if(s.length()<=0)return t;if(t.length()<=0)return s;//让s为较长的，t为较短的if(s.length() < t.length()){ String temp = s;s = t;t = temp;}int carry = 0; //进位标志char[] res = new char[s.length()];//从后往前遍历较长的字符串for(int i = s.length() - 1; i >= 0; i--){ //转数字加上进位int temp = s.charAt(i) - '0' + carry; //转较短的字符串相应的从后往前的下标int j = i - s.length() + t.length(); //如果较短字符串还有if(j >= 0) //转数组相加temp += t.charAt(j) - '0'; //取进位carry = temp / 10; //去十位temp = temp % 10; //修改结果res[i] = (char)(temp + '0'); }String output = String.valueOf(res);//最后的进位if(carry == 1) output = '1' + output;return output;}
}
15. 无重复字符的最长子串
15.1. 题目描述
15.2. 解题思路
方法一：滑动窗口
class Solution {public int lengthOfLongestSubstring(String s) {// 哈希集合，记录每个字符是否出现过Set<Character> occ = new HashSet<Character>();int n = s.length();// 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动int rk = -1, ans = 0;for (int i = 0; i < n; ++i) {if (i != 0) {// 左指针向右移动一格，移除一个字符occ.remove(s.charAt(i - 1));}while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {// 不断地移动右指针occ.add(s.charAt(rk + 1));++rk;}// 第 i 到 rk 个字符是一个极长的无重复字符子串ans = Math.max(ans, rk - i + 1);}return ans;}
}
16. 找到字符串中所有字母异位词（中等）
16.1. 题目描述
16.2. 解题思路
方法一：滑动窗口
class Solution {public List<Integer> findAnagrams(String s, String p) {int sLen = s.length(), pLen = p.length();if (sLen < pLen) {return new ArrayList<Integer>();}List<Integer> ans = new ArrayList<Integer>();int[] sCount = new int[26];int[] pCount = new int[26];for (int i = 0; i < pLen; ++i) {++sCount[s.charAt(i) - 'a'];++pCount[p.charAt(i) - 'a'];}if (Arrays.equals(sCount, pCount)) {ans.add(0);}for (int i = 0; i < sLen - pLen; ++i) {--sCount[s.charAt(i) - 'a'];++sCount[s.charAt(i + pLen) - 'a'];if (Arrays.equals(sCount, pCount)) {ans.add(i + 1);}}return ans;}
}
方法二：优化的滑动窗口
class Solution {public List<Integer> findAnagrams(String s, String p) {int sLen = s.length(), pLen = p.length();if (sLen < pLen) {return new ArrayList<Integer>();}List<Integer> ans = new ArrayList<Integer>();int[] count = new int[26];for (int i = 0; i < pLen; ++i) {++count[s.charAt(i) - 'a'];--count[p.charAt(i) - 'a'];}int differ = 0;for (int j = 0; j < 26; ++j) {if (count[j] != 0) {++differ;}}if (differ == 0) {ans.add(0);}for (int i = 0; i < sLen - pLen; ++i) {if (count[s.charAt(i) - 'a'] == 1) { // 窗口中字母 s[i] 的数量与字符串 p 中的数量从不同变得相同--differ;} else if (count[s.charAt(i) - 'a'] == 0) { // 窗口中字母 s[i] 的数量与字符串 p 中的数量从相同变得不同++differ;}--count[s.charAt(i) - 'a'];if (count[s.charAt(i + pLen) - 'a'] == -1) { // 窗口中字母 s[i+pLen] 的数量与字符串 p 中的数量从不同变得相同--differ;} else if (count[s.charAt(i + pLen) - 'a'] == 0) { // 窗口中字母 s[i+pLen] 的数量与字符串 p 中的数量从相同变得不同++differ;}++count[s.charAt(i + pLen) - 'a'];if (differ == 0) {ans.add(i + 1);}}return ans;}
}
17. 定长子串中元音的最大数目（中等）
17.1. 题目描述
17.2. 解题思路
方法一：滑动窗口
class Solution {public int maxVowels(String s, int k) {int n = s.length();int vowel_count = 0;for (int i = 0; i < k; ++i) {vowel_count += isVowel(s.charAt(i));}int ans = vowel_count;for (int i = k; i < n; ++i) {vowel_count += isVowel(s.charAt(i)) - isVowel(s.charAt(i - k));ans = Math.max(ans, vowel_count);}return ans;}public int isVowel(char ch) {return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u' ? 1 : 0;}
}
18. 判断是否为回文字符串
18.1. 题目描述
18.2. 解题思路
方法一：首尾依次比较法（推荐使用）
Java代码实现:
import java.util.*;
public class Solution {public boolean judge (String str) {//首指针int left = 0; //尾指针int right = str.length() - 1;//首尾往中间靠 while(left < right){ //比较前后是否相同if(str.charAt(left) != str.charAt(right)) return false;left++;right--;}return true;}
}
方法二：反转字符串比较法（扩展思路）
import java.util.*;
public class Solution {public boolean judge (String str) {StringBuffer temp = new StringBuffer(str);//反转字符串String s = temp.reverse().toString();//比较字符串是否相等if(s.equals(str))return true;return false;}
}
19. 最小覆盖子串（较难）
19.1. 题目描述
19.2. 解题思路
方法一：哈希表匹配（推荐使用）
Java代码实现：
import java.util.*;
public class Solution {//检查是否有小于0的boolean check(int[] hash) { for (int i = 0; i < hash.length; i++) {if (hash[i] < 0)return false;}return true;};public String minWindow (String S, String T) {int cnt = S.length() + 1;//记录目标字符串T的字符个数int[] hash = new int[128]; for(int i = 0; i < T.length(); i++)//初始化哈希表都为负数，找的时候再加为正hash[T.charAt(i)] -= 1; int slow = 0, fast = 0; //记录左右区间int left = -1, right = -1; for(; fast < S.length(); fast++){char c = S.charAt(fast);//目标字符匹配+1hash[c]++;//没有小于0的说明都覆盖了，缩小窗口while(check(hash)){ //取最优解if(cnt > fast - slow + 1){ cnt = fast - slow + 1; left = slow;right = fast;}c = S.charAt(slow);//缩小窗口的时候减1hash[c]--; //窗口缩小slow++; }}//找不到的情况if(left == -1) return "";return S.substring(left, right + 1);}
}
20. 反转字符串（入门）
20.1. 题目描述
20.2. 解题思路
解法一
import java.util.*;
public class Solution {public String solve (String str) {char[] ans = str.toCharArray();int len = str.length();for(int i = 0 ; i < len ;i++){ans[i] = str.charAt(len-1-i);}return new String(ans);}
}解法二
import java.util.*;
public class Solution {public String solve (String str) {char[] cstr = str.toCharArray();int len = str.length();for(int i = 0 ; i < len/2 ;i++){char t = cstr[i];cstr[i] = cstr[len-1-i];cstr[len-1-i]=t;}return new String(cstr);}
}解法三
直接调用库函数
import java.util.*;
public class Solution {public String solve (String str) {StringBuffer sb =new StringBuffer(str);//此方法针对的是io流，不能针对字符串。return sb.reverse().toString();}
}相关文章：
02数组+字符串+滑动窗口+前缀和与差分+双指针（D2_字符串（D2_刷题练习））
目录 1. 最长公共前缀 1.1. 题目描述 1.2. 解题方案 方案一：纵向对比 方案二：横向对比 方案三：最值对比 方案四：分治 方案五：二分 1.3. 知识归纳 2. 左旋转字符串（简单） 2.1. 题目描述…...
【redis进阶】集群 (Cluster)
目录 一、基本概念 二、数据分片算法 2.1 哈希求余 2.2 一致性哈希算法 3.3 哈希槽分区算法 (Redis 使用) 三、集群搭建 (基于 docker) 3.1 创建目录和配置 3.2 编写 docker-compose.yml 3.3 启动容器 3.4 构建集群 四、主节点宕机 4.1 处理流程 五、集群扩容 六、集群缩容 (选…...
Python案例--100到200的素数
一、问题描述 素数（Prime Number）是指在大于1的自然数中，除了1和它本身以外不再有其他因数的数。判断一个数是否为素数是计算机科学和数学中的一个经典问题。本实例的目标是找出101到200之间的所有素数，并统计它们的数量。 二、…...
C语言，无法正常释放char*的空间
问题描述 #include <stdio.h> #include <stdio.h>const int STRSIZR 10;int main() {char *str (char *)malloc(STRSIZR*sizeof(char));str "string";printf("%s\n", str);free(str); } 乍一看，这块代码没有什么问题。直接书写…...
重回C语言之老兵重装上阵（十五）C语言错误处理
C语言错误处理 在C语言中，错误处理是非常重要的一部分。C语言没有像高级语言（例如Python、Java）那样内建的异常处理机制（如try-catch），但它提供了几种方法来捕捉和处理错误。正确的错误处理可以提高程序的稳…...
基于微信的课堂助手小程序设计与实现（LW+源码+讲解）
专注于大学生项目实战开发,讲解,毕业答疑辅导，欢迎高校老师/同行前辈交流合作✌。 技术范围：SpringBoot、Vue、SSM、HLMT、小程序、Jsp、PHP、Nodejs、Python、爬虫、数据可视化、安卓app、大数据、物联网、机器学习等设计与开发。 主要内容：…...
Effective C++ 规则50：了解 new 和 delete 的合理替换时机
1、背景 在 C 中，new 和 delete 是动态分配内存的核心操作符。然而，直接使用它们有时会增加程序的复杂性，甚至导致内存泄漏和其他问题。因此，了解何时替换 new 和 delete 并选择更适合的内存管理策略，是编写高效、健壮…...
Alfresco Content Services dockerCompose自动化部署详尽操作
Alfresco Content Services docker社区部署文档 Alfresco Content Services简介 Alfresco Content Services（简称ACS）是一款功能完备的企业内容管理（ECM）解决方案，主要面向那些对企业级内容管理有高要求的组织。具体…...
学习第七十六行
提高github下载速度方法 1.github转码云 2.https://github.com.cnpmjs.org com后面加东西 对于面试笔试，最好方法刷力扣，1000题包进大厂的...
YOLOv11改进，YOLOv11检测头融合DynamicHead，并添加小目标检测层（四头检测），适合目标检测、分割等任务
摘要 作者提出一种新的检测头，称为“动态头”，旨在将尺度感知、空间感知和任务感知统一在一起。如果我们将骨干网络的输出（即检测头的输入）视为一个三维张量，其维度为级别 空间 通道，这样的统一检测头可以看作是一个注意力学习问题，直观的解决方案是对该张量进行全自…...
一个基于Python+Appium的手机自动化项目~~
本项目通过PythonAppium实现了抖音手机店铺的自动化询价，可以直接输出excel，并带有详细的LOG输出。 1.excel输出效果: 2. LOG效果: 具体文件内容见GitCode： 项目首页 - douyingoods:一个基于Pythonappium的手机自动化项目，实现了…...
【后端开发】字节跳动青训营之性能分析工具pprof
性能分析工具pprof 一、测试程序介绍二、pprof工具安装与使用2.1 pprof工具安装2.2 pprof工具使用 资料链接： 项目代码链接实验指南pprof使用指南 一、测试程序介绍 package mainimport ("log""net/http"_ "net/http/pprof" // 自…...
Linux：线程池和单例模式
一、普通线程池 1.1 线程池概念 线程池：一种线程使用模式。线程过多会带来调度开销，进而影响缓存局部性和整体性能。而线程池维护着多个线程，等待着监督管理者分配可并发执行的任务。这避免了在处理短时间任务时创建与销毁线程的代价&…...
使用iis服务器模拟本地资源服务器unityaddressables热更新出错记录
editor中设置了using exculexing 模拟远程加载addressable可以实现资源热更新，build后的软件却没有成功。 iis服务器中mime中需要设置bundle的文件扩展名，时editor成功，build后失败 原因没有设置hash的扩展名，设置后editor和buil…...
TikTok广告投放优化策略：提升ROI的核心技巧
在短许多品牌和商家纷纷投入广告营销，争夺这片潜力巨大的市场。然而，在激烈的竞争环境中，如何精准有效地投放广告，优化广告效果，实现更高的投资回报率（ROI）成为了广告主关注的核心。 一. 精准受…...
Hash表
哈希表存储结构（开放寻址法，拉链法）字符串哈希方式（添加、查找h(x)） 常见从0~10^9映射到0~10^5就要对10^5取mod（取模一般要质数最好）但是可能会有冲突 1.拉链法：O(1)，每…...
题解：P10972 I-Country
题目传送门 思路 因为占据的连通块的左端点先递减、后递增，右端点先递增、后递减，所以设 f i , j , l , r , x ( 0 / 1 ) , y ( 0 / 1 ) f_{i,j,l,r,x(0/1),y(0/1)} fi,j,l,r,x(0/1),y(0/1) 为前 i i i 行中，选择 j j j 个方格&#x…...
linux常用加固方式
目录 一.系统加固 二.ssh加固 三.换个隐蔽的端口 四.防火墙配置 五.用户权限管理 六.暴力破解防护 七.病毒防护 八.磁盘加密 九.双因素认证2FA 十.日志监控 十一.精简服务 一.系统加固 第一步：打好系统补丁 sudo apt update && sudo apt upgra…...
笔灵ai写作技术浅析（二）：自然语言处理
一、词法分析（Lexical Analysis） 1.1 概述 词法分析是NLP的第一步，主要任务是将连续的文本分割成有意义的单元（词或词组），并对这些单元进行标注，如词性标注（POS tagging）。词法分析的质量直接影响后续的句法分析和语义理解。 1.2 技术细节 1.分词（Tokenization）…...
PyCharm介绍
PyCharm的官网是https://www.jetbrains.com/pycharm/。 以下是在PyCharm官网下载和安装软件的步骤： 下载步骤 打开浏览器，访问PyCharm的官网https://www.jetbrains.com/pycharm/。在官网首页，点击“Download”按钮进入下载页面。选择适合自…...
深度解析：基于Vue 3与Element Plus的学校管理系统技术实现
一、项目架构分析 1.1 技术栈全景 核心框架：Vue 3 TypeScript UI组件库：Element Plus（含图标动态注册） 状态管理：Pinia（用户状态持久化） 路由方案：Vue Router（动态路…...
Python从0到100（八十五）：神经网络-使用迁移学习完成猫狗分类
前言： 零基础学Python：Python从0到100最新最全教程。 想做这件事情很久了，这次我更新了自己所写过的所有博客，汇集成了Python从0到100，共一百节课，帮助大家一个月时间里从零基础到学习Python基础语法、Python爬虫、Web开发、 计算机视觉、机器学习、神经网络以及人工智能…...
苍穹外卖 项目记录 day09 历史订单
文章目录 查询历史订单查询订单详情取消订单再来一单 查询历史订单 分页查询历史订单可以根据订单状态查询展示订单数据时，需要展示的数据包括：下单时间、订单状态、订单金额、订单明细（商品名称、图片） #OrderController/*** 历…...
记录 | 基于Docker Desktop的MaxKB安装
目录 前言一、MaxKBStep 1Step2 二、运行MaxKB更新时间 前言 参考文章：如何利用智谱全模态免费模型，生成大家都喜欢的图、文、视并茂的文章！ MaxKB的Github下载地址 参考视频：【2025最新MaxKB教程】10分钟学会一键部署本地私人专属…...
WordPress web-directory-free插件存在本地文件包含导致任意文件读取漏洞(CVE-2024-3673)
免责声明: 本文旨在提供有关特定漏洞的深入信息，帮助用户充分了解潜在的安全风险。发布此信息的目的在于提升网络安全意识和推动技术进步，未经授权访问系统、网络或应用程序，可能会导致法律责任或严重后果。因此，作者不对读者基于本文内容所采取的任何行为承担责任。读者在…...
LLM：BERT or BART 之BERT
文章目录 前言一、BERT1. Decoder-only2. Encoder-only3. Use of Bidirectional Context4. Masked Language Model (MLM)5. Next Sentence Prediction (NSP)6. Fine-tune1、情感分析2、句对分析3、命名实体识别（NER） 7. BERT总结 总结 前言 NLP选手对这…...
EtherCAT主站IGH-- 18 -- IGH之fsm_mbox_gateway.h/c文件解析
EtherCAT主站IGH-- 18 -- IGH之fsm_mbox_gateway.h/c文件解析 0 预览一 该文件功能`fsm_mbox_gateway.c` 文件功能函数预览二 函数功能介绍`fsm_mbox_gateway.c` 中主要函数的作用1. `ec_fsm_mbg_init`2. `ec_fsm_mbg_clear`3. `ec_fsm_mbg_transfer`4. `ec_fsm_mbg_exec`5. `e…...
深入探讨防抖函数中的 this 上下文
深入剖析防抖函数中的 this 上下文 最近我在研究防抖函数实现的时候，发现一个耗费脑子的问题，出现了令我困惑的问题。接下来，我将通过代码示例，深入探究这些现象背后的原理。 示例代码 function debounce(fn, delay) {let time…...
【AI论文】魔鬼在细节：关于在训练专用混合专家模型时实现负载均衡损失
摘要：本文重新审视了在训练混合专家（Mixture-of-Experts, MoEs）模型时负载均衡损失（Load-Balancing Loss, LBL）的实现。具体来说，MoEs的LBL定义为N_E乘以从1到N_E的所有专家i的频率f_i与门控得分平均值p_i的…...
Gurobi基础语法之addVar 和 addVars
addVar 和 addVars作为 Gurobi模型对象中的方法，常常用来生成变量，本文介绍了Python中的这两个接口的使用 addVar addVar(lb0.0, ubfloat(inf), obj0.0, vtypeGRB.CONTINUOUS, name, columnNone) lb 和 ub让变量在生成的时候就有下界和上届，…...