网站关键词掉了,彭阳网站建设多少钱,自己制作wordpress主题,个人主页设计模板图片目录 1. 最长公共前缀
1.1. 题目描述
1.2. 解题方案
方案一#xff1a;纵向对比
方案二#xff1a;横向对比
方案三#xff1a;最值对比
方案四#xff1a;分治
方案五#xff1a;二分
1.3. 知识归纳
2. 左旋转字符串#xff08;简单#xff09;
2.1. 题目描述…目录 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) {MapState, MapCharType, State transfer new HashMapState, MapCharType, State();MapCharType, State initialMap new HashMapCharType, 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);MapCharType, State intSignMap new HashMapCharType, State() {{put(CharType.CHAR_NUMBER, State.STATE_INTEGER);put(CharType.CHAR_POINT, State.STATE_POINT_WITHOUT_INT);}};transfer.put(State.STATE_INT_SIGN, intSignMap);MapCharType, State integerMap new HashMapCharType, 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);MapCharType, State pointMap new HashMapCharType, 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);MapCharType, State pointWithoutIntMap new HashMapCharType, State() {{put(CharType.CHAR_NUMBER, State.STATE_FRACTION);}};transfer.put(State.STATE_POINT_WITHOUT_INT, pointWithoutIntMap);MapCharType, State fractionMap new HashMapCharType, 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);MapCharType, State expMap new HashMapCharType, State() {{put(CharType.CHAR_NUMBER, State.STATE_EXP_NUMBER);put(CharType.CHAR_SIGN, State.STATE_EXP_SIGN);}};transfer.put(State.STATE_EXP, expMap);MapCharType, State expSignMap new HashMapCharType, State() {{put(CharType.CHAR_NUMBER, State.STATE_EXP_NUMBER);}};transfer.put(State.STATE_EXP_SIGN, expSignMap);MapCharType, State expNumberMap new HashMapCharType, State() {{put(CharType.CHAR_NUMBER, State.STATE_EXP_NUMBER);put(CharType.CHAR_SPACE, State.STATE_END);}};transfer.put(State.STATE_EXP_NUMBER, expNumberMap);MapCharType, State endMap new HashMapCharType, 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为负所以能表示的范围
是-3276832767-2e152e15-1而无符号整数就是定义为unsigned int因为第一位不用代
表正负了没有符号全是正的啊所以16位全为有效位所以范围是06553502e16-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、ab的最大公约数记为ab同样的abc的最大公约数记为abc多个整数的最
大公约数也有同样的记号。
求最大公约数有多种方法常见的有质因数分解法、短除法、辗转相除法、更相减损法。
与最大公约数相对应的概念是最小公倍数ab的最小公倍数记为[ab]。
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();// 正则匹配连续的空白字符作为分隔符分割ListString 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;}DequeString d new ArrayDequeString();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(n0) return s;StringBuffer resnew 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(n0) return s;StringBuffer resnew 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))); }StackString tempnew StackString();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) {// 哈希集合记录每个字符是否出现过SetCharacter occ new HashSetCharacter();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 ListInteger findAnagrams(String s, String p) {int sLen s.length(), pLen p.length();if (sLen pLen) {return new ArrayListInteger();}ListInteger ans new ArrayListInteger();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 ListInteger findAnagrams(String s, String p) {int sLen s.length(), pLen p.length();if (sLen pLen) {return new ArrayListInteger();}ListInteger ans new ArrayListInteger();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[ipLen] 的数量与字符串 p 中的数量从不同变得相同--differ;} else if (count[s.charAt(i pLen) - a] 0) { // 窗口中字母 s[ipLen] 的数量与字符串 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();}
}
