天津市建行網(wǎng)站百度指數(shù)查詢手機(jī)版app
目錄
1. 最長(zhǎng)公共前綴
1.1. 題目描述
1.2. 解題方案
方案一：縱向?qū)Ρ?/p>
方案二：橫向?qū)Ρ?/p>
方案三：最值對(duì)比
方案四：分治
方案五：二分
1.3. 知識(shí)歸納
2. 左旋轉(zhuǎn)字符串（簡(jiǎn)單）
2.1. 題目描述
2.2. 解題思路
方法一：字符串切片
方法二：列表遍歷拼接
方法三：字符串遍歷拼接
3. 表示數(shù)值的字符串（中等）
3.1. 題目描述
3.2. 解題思路
方法一：確定有限狀態(tài)自動(dòng)機(jī)
4. 把字符串轉(zhuǎn)換成整數(shù)（中等）
4.1. 題目描述
4.2. 解題思路
5. 交替合并字符串（簡(jiǎn)單）
5.1. 題目描述
5.2. 解題思路
方法一：雙指針
6. 字符串的最大公因子（簡(jiǎn)單）
6.1. 題目描述
6.2. 解題思路
方法一：枚舉
方法二：枚舉優(yōu)化
方法三：數(shù)學(xué)
7. 反轉(zhuǎn)字符串中的元音字母（簡(jiǎn)單）
7.1. 題目描述
7.2. 解題思路
方法一：雙指針
8. 遞增的三元子序列（中等）
8.1. 題目描述
8.2. 解題思路
方法一：雙向遍歷
方法二：貪心
9. 壓縮字符串（中等）
9.1. 題目描述
9.2. 解題思路
方法一：雙指針
10. 反轉(zhuǎn)字符串中的單詞（中等）
10.1. 題目描述
10.2. 解題思路
方法一：使用語(yǔ)言特性
方法二：自行編寫對(duì)應(yīng)的函數(shù)
方法三：雙端隊(duì)列
11. 字符串變形（簡(jiǎn)單）
11.1. 題目描述
11.2. 解題思路
方法一：雙逆轉(zhuǎn)（推薦使用）
方法二：分割字符串+棧（擴(kuò)展思路）
12. 最長(zhǎng)公共前綴
12.1. 題目描述
12.2. 解題思路
方法一：遍歷查找(推薦使用)
13. 驗(yàn)證IP地址
13.1. 題目描述
13.2. 解題思路
方法一：分割字符串比較法（推薦使用）
方法二：正則表達(dá)式（擴(kuò)展思路）
14. 大數(shù)加法
14.1. 題目描述
14.2. 解題思路
方法一：模擬法（建議使用）
15. 無(wú)重復(fù)字符的最長(zhǎng)子串
15.1. 題目描述
15.2. 解題思路
方法一：滑動(dòng)窗口
16. 找到字符串中所有字母異位詞（中等）
16.1. 題目描述
16.2. 解題思路
方法一：滑動(dòng)窗口
方法二：優(yōu)化的滑動(dòng)窗口
17. 定長(zhǎng)子串中元音的最大數(shù)目（中等）
17.1. 題目描述
17.2. 解題思路
方法一：滑動(dòng)窗口
18. 判斷是否為回文字符串
18.1. 題目描述
18.2. 解題思路
方法一：首尾依次比較法（推薦使用）
方法二：反轉(zhuǎn)字符串比較法（擴(kuò)展思路）
19. 最小覆蓋子串（較難）
19.1. 題目描述
19.2. 解題思路
方法一：哈希表匹配（推薦使用）
20. 反轉(zhuǎn)字符串（入門）
20.1. 題目描述
20.2. 解題思路
解法一
解法二
解法三
1. 最長(zhǎng)公共前綴
1.1. 題目描述
1.2. 解題方案
對(duì)于一個(gè)問(wèn)題，采用一題多解，才能深刻理解其考察的知識(shí)點(diǎn)，進(jìn)行舉一反三。
最長(zhǎng)公共前綴，可橫向?qū)Ρ?/ 豎向?qū)Ρ?/ 最值對(duì)比 / 分治 / 二分方法來(lái)完成題解。
方案一：縱向?qū)Ρ?/h5>
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];}
方案二：橫向?qū)Ρ?/h5>
// 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);}
方案三：最值對(duì)比
public String longestCommonPrefix3(String[] strs) {String min = strs[0], max = strs[0];for (String str : strs) {// bug1:字符串的compare和integer的不一樣，并非-1 / 0 / 1，而是長(zhǎng)度相減作為返回值。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的位置，所以也會(huì)需要s.len的位置。int low = 0, high = s.length();// 用二分法去快速尋找公共前綴的右邊界。while (low < high) {int mid = low + (high - low + 1 >> 1);// 為了low不越界，這里必須+1防止死循環(huán)。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. 知識(shí)歸納
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);}方案三：最值對(duì)比
public String longestCommonPrefix3(String[] strs) {String min = strs[0], max = strs[0];for (String str : strs) {// bug1:字符串的compare和integer的不一樣，并非-1 / 0 / 1，而是長(zhǎng)度相減作為返回值。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的位置，所以也會(huì)需要s.len的位置。int low = 0, high = s.length();// 用二分法去快速尋找公共前綴的右邊界。while (low < high) {int mid = low + (high - low + 1 >> 1);// 為了low不越界，這里必須+1防止死循環(huán)。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. 知識(shí)歸納
最長(zhǎng)公共前綴，可橫向?qū)Ρ?/ 豎向?qū)Ρ?/ 最值對(duì)比 / 分治 / 二分方法來(lái)完成題解。
對(duì)于分治來(lái)講，可多線程操作加快速度；
對(duì)于二分，考察對(duì)抽象二分的理解，將二分規(guī)則進(jìn)行抽象。
2. 左旋轉(zhuǎn)字符串（簡(jiǎn)單）
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. 表示數(shù)值的字符串（中等）
3.1. 題目描述
3.2. 解題思路
方法一：確定有限狀態(tài)自動(dòng)機(jī)
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. 把字符串轉(zhuǎn)換成整數(shù)（中等）
4.1. 題目描述
請(qǐng)問(wèn)什么是有符號(hào)整數(shù)？
有符號(hào)整數(shù)，就是int，因?yàn)橛姓?fù)之分，所以16位的第一位表示正負(fù)，0為正，1為負(fù)所以能表示的范圍
是-32768～+32767（-2e15～2e15-1）而無(wú)符號(hào)整數(shù)，就是定義為unsigned int，因?yàn)榈谝晃徊挥么?/p>
表正負(fù)了，沒(méi)有符號(hào)，全是正的啊，所以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() 方法，而從頭開始遍歷字符串，則可以將空間復(fù)雜度降低至 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. 交替合并字符串（簡(jiǎn)單）
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. 字符串的最大公因子（簡(jiǎn)單）
6.1. 題目描述
什么是最大公因數(shù) 最大公因數(shù)的解釋
1、最大公因數(shù)，也稱為最大公約數(shù)、最大公因子，指兩個(gè)或多個(gè)整數(shù)共有約數(shù)中最大的一個(gè)。
2、a，b的最大公約數(shù)記為（a，b），同樣的，a，b，c的最大公約數(shù)記為（a，b，c），多個(gè)整數(shù)的最
大公約數(shù)也有同樣的記號(hào)。
求最大公約數(shù)有多種方法，常見的有質(zhì)因數(shù)分解法、短除法、輾轉(zhuǎn)相除法、更相減損法。
與最大公約數(shù)相對(duì)應(yīng)的概念是最小公倍數(shù)，a，b的最小公倍數(shù)記為[a，b]。
6.2. 解題思路
方法一：枚舉
class Solution {// 字符串最大公因子public String gcdOfStrings(String str1, String str2) {// 獲取兩個(gè)字符串長(zhǎng)度int len1 = str1.length(), len2 = str2.length();// 從長(zhǎng)度小的開始枚舉for (int i = Math.min(len1, len2); i >= 1; --i) {// 前綴串的長(zhǎng)度必然是兩個(gè)字符串長(zhǎng)度的約數(shù)才能滿足條件if (len1 % i == 0 && len2 % i == 0) {// 截取子串String X = str1.substring(0, i);// 檢測(cè)子串是否能被兩個(gè)字符串整除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);}
}
方法二：枚舉優(yōu)化
class Solution {// 字符串最大公因子public String gcdOfStrings(String str1, String str2) {// 獲取兩個(gè)字符串長(zhǎng)度int len1 = str1.length(), len2 = str2.length();// 截取子串（截取到最大公因子）String T = str1.substring(0, gcd(len1, len2));// 檢測(cè)子串是否能被兩個(gè)字符串整除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;}
}
方法三：數(shù)學(xué)
class Solution {// 字符串最大公因子public String gcdOfStrings(String str1, String str2) {// 兩個(gè)字符串相連不相等，直接返回空串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. 反轉(zhuǎn)字符串中的元音字母（簡(jiǎn)單）
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. 反轉(zhuǎn)字符串中的單詞（中等）
10.1. 題目描述
10.2. 解題思路
方法一：使用語(yǔ)言特性
class Solution {public String reverseWords(String s) {// 除去開頭和末尾的空白字符s = s.trim();// 正則匹配連續(xù)的空白字符作為分隔符分割List<String> wordList = Arrays.asList(s.split("\\s+"));Collections.reverse(wordList);return String.join(" ", wordList);}
}
方法二：自行編寫對(duì)應(yīng)的函數(shù)
class Solution {public String reverseWords(String s) {StringBuilder sb = trimSpaces(s);// 翻轉(zhuǎn)字符串reverse(sb, 0, sb.length() - 1);// 翻轉(zhuǎn)每個(gè)單詞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) {// 循環(huán)至單詞的末尾while (end < n && sb.charAt(end) != ' ') {++end;}// 翻轉(zhuǎn)單詞reverse(sb, start, end - 1);// 更新start，去找下一個(gè)單詞start = end + 1;++end;}}
}
方法三：雙端隊(duì)列
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 到隊(duì)列的頭部d.offerFirst(word.toString());word.setLength(0);} else if (c != ' ') {word.append(c);}++left;}d.offerFirst(word.toString());return String.join(" ", d);}
}
11. 字符串變形（簡(jiǎn)單）
11.1. 題目描述
11.2. 解題思路
方法一：雙逆轉(zhuǎn)（推薦使用）
Java代碼實(shí)現(xiàn):
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++){//大小寫轉(zhuǎn)換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 //空格直接復(fù)制res.append(s.charAt(i)); } //翻轉(zhuǎn)整個(gè)字符串res = res.reverse();for (int i = 0; i < n; i++){int j = i;//以空格為界，二次翻轉(zhuǎn)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();}
}
方法二：分割字符串+棧（擴(kuò)展思路）
java代碼實(shí)現(xiàn)：
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++){//大小寫轉(zhuǎn)換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 //空格直接復(fù)制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++;//單詞進(jìn)棧temp.push((String)(res.substring(i, j))); i = j;}//排除結(jié)尾空格的特殊情況if(s.charAt(n - 1) == ' ') res = new StringBuffer(" ");elseres = new StringBuffer();//棧遵循先進(jìn)后廚，單詞順序是反的while(!temp.empty()){ res.append(temp.peek());temp.pop();if(!temp.empty())res.append(" ");}return res.toString();}
}
12. 最長(zhǎng)公共前綴
12.1. 題目描述
12.2. 解題思路
方法一：遍歷查找(推薦使用)
Java代碼實(shí)現(xiàn):
import java.util.*;
public class Solution {public String longestCommonPrefix (String[] strs) {int n = strs.length;//空字符串?dāng)?shù)組if(n == 0) return "";//遍歷第一個(gè)字符串的長(zhǎng)度f(wàn)or(int i = 0; i < strs[0].length(); i++){ char temp = strs[0].charAt(i); //遍歷后續(xù)的字符串for(int j = 1; j < n; j++) //比較每個(gè)字符串該位置是否和第一個(gè)相同if(i == strs[j].length() || strs[j].charAt(i) != temp) //不相同則結(jié)束return strs[0].substring(0, i); }//后續(xù)字符串有整個(gè)字一個(gè)字符串的前綴return strs[0]; }
}
13. 驗(yàn)證IP地址
13.1. 題目描述
13.2. 解題思路
方法一：分割字符串比較法（推薦使用）
java代碼實(shí)現(xiàn):
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++){//不可缺省，有一個(gè)分割為零，說(shuō)明兩個(gè)點(diǎn)相連if(s[i].length() == 0) return false;//比較數(shù)字位數(shù)及不為零時(shí)不能有前綴零if(s[i].length() < 0 || s[i].length() > 3 || (s[i].charAt(0)=='0' && s[i].length() != 1)) return false;int num = 0;//遍歷每個(gè)分割字符串，必須為數(shù)字for(int j = 0; j < s[i].length(); j++){ char c = s[i].charAt(j);if (c < '0' || c > '9') return false;//轉(zhuǎn)化為數(shù)字比較，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++){ //每個(gè)分割不能缺省，不能超過(guò)4位if(s[i].length() == 0 || s[i].length() > 4){ return false; }for(int j = 0; j < s[i].length(); j++){//不能出現(xiàn)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";}
}
方法二：正則表達(dá)式（擴(kuò)展思路）
Java代碼實(shí)現(xiàn):
import java.util.regex.Pattern;
public class Solution {String solve(String IP) {//正則表達(dá)式限制0-255 且沒(méi)有前綴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);//正則表達(dá)式限制出現(xiàn)8組，0-9a-fA-F的數(shù)，個(gè)數(shù)必須是1-4個(gè)String ipv6="([0-9a-fA-F]{1,4}\\:){7}[0-9a-fA-F]{1,4}";Pattern ipv6_pattern = Pattern.compile(ipv6);//調(diào)用正則匹配函數(shù)if (ipv4_pattern.matcher(IP).matches()) return "IPv4";else if (ipv6_pattern.matcher(IP).matches()) return "IPv6";else return "Neither";}
}
14. 大數(shù)加法
14.1. 題目描述
14.2. 解題思路
方法一：模擬法（建議使用）
Java代碼實(shí)現(xiàn):
import java.util.*;
public class Solution {public String solve (String s, String t) {//若是其中一個(gè)為空，返回另一個(gè)if(s.length()<=0)return t;if(t.length()<=0)return s;//讓s為較長(zhǎng)的，t為較短的if(s.length() < t.length()){ String temp = s;s = t;t = temp;}int carry = 0; //進(jìn)位標(biāo)志char[] res = new char[s.length()];//從后往前遍歷較長(zhǎng)的字符串for(int i = s.length() - 1; i >= 0; i--){ //轉(zhuǎn)數(shù)字加上進(jìn)位int temp = s.charAt(i) - '0' + carry; //轉(zhuǎn)較短的字符串相應(yīng)的從后往前的下標(biāo)int j = i - s.length() + t.length(); //如果較短字符串還有if(j >= 0) //轉(zhuǎn)數(shù)組相加temp += t.charAt(j) - '0'; //取進(jìn)位carry = temp / 10; //去十位temp = temp % 10; //修改結(jié)果res[i] = (char)(temp + '0'); }String output = String.valueOf(res);//最后的進(jìn)位if(carry == 1) output = '1' + output;return output;}
}
15. 無(wú)重復(fù)字符的最長(zhǎng)子串
15.1. 題目描述
15.2. 解題思路
方法一：滑動(dòng)窗口
class Solution {public int lengthOfLongestSubstring(String s) {// 哈希集合，記錄每個(gè)字符是否出現(xiàn)過(guò)Set<Character> occ = new HashSet<Character>();int n = s.length();// 右指針，初始值為 -1，相當(dāng)于我們?cè)谧址淖筮吔绲淖髠?cè)，還沒(méi)有開始移動(dòng)int rk = -1, ans = 0;for (int i = 0; i < n; ++i) {if (i != 0) {// 左指針向右移動(dòng)一格，移除一個(gè)字符occ.remove(s.charAt(i - 1));}while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {// 不斷地移動(dòng)右指針occ.add(s.charAt(rk + 1));++rk;}// 第 i 到 rk 個(gè)字符是一個(gè)極長(zhǎng)的無(wú)重復(fù)字符子串a(chǎn)ns = Math.max(ans, rk - i + 1);}return ans;}
}
16. 找到字符串中所有字母異位詞（中等）
16.1. 題目描述
16.2. 解題思路
方法一：滑動(dòng)窗口
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;}
}
方法二：優(yōu)化的滑動(dòng)窗口
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] 的數(shù)量與字符串 p 中的數(shù)量從不同變得相同--differ;} else if (count[s.charAt(i) - 'a'] == 0) { // 窗口中字母 s[i] 的數(shù)量與字符串 p 中的數(shù)量從相同變得不同++differ;}--count[s.charAt(i) - 'a'];if (count[s.charAt(i + pLen) - 'a'] == -1) { // 窗口中字母 s[i+pLen] 的數(shù)量與字符串 p 中的數(shù)量從不同變得相同--differ;} else if (count[s.charAt(i + pLen) - 'a'] == 0) { // 窗口中字母 s[i+pLen] 的數(shù)量與字符串 p 中的數(shù)量從相同變得不同++differ;}++count[s.charAt(i + pLen) - 'a'];if (differ == 0) {ans.add(i + 1);}}return ans;}
}
17. 定長(zhǎng)子串中元音的最大數(shù)目（中等）
17.1. 題目描述
17.2. 解題思路
方法一：滑動(dòng)窗口
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代碼實(shí)現(xiàn):
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;}
}
方法二：反轉(zhuǎn)字符串比較法（擴(kuò)展思路）
import java.util.*;
public class Solution {public boolean judge (String str) {StringBuffer temp = new StringBuffer(str);//反轉(zhuǎn)字符串String s = temp.reverse().toString();//比較字符串是否相等if(s.equals(str))return true;return false;}
}
19. 最小覆蓋子串（較難）
19.1. 題目描述
19.2. 解題思路
方法一：哈希表匹配（推薦使用）
Java代碼實(shí)現(xiàn)：
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;//記錄目標(biāo)字符串T的字符個(gè)數(shù)int[] hash = new int[128]; for(int i = 0; i < T.length(); i++)//初始化哈希表都為負(fù)數(shù)，找的時(shí)候再加為正hash[T.charAt(i)] -= 1; int slow = 0, fast = 0; //記錄左右區(qū)間int left = -1, right = -1; for(; fast < S.length(); fast++){char c = S.charAt(fast);//目標(biāo)字符匹配+1hash[c]++;//沒(méi)有小于0的說(shuō)明都覆蓋了，縮小窗口while(check(hash)){ //取最優(yōu)解if(cnt > fast - slow + 1){ cnt = fast - slow + 1; left = slow;right = fast;}c = S.charAt(slow);//縮小窗口的時(shí)候減1hash[c]--; //窗口縮小slow++; }}//找不到的情況if(left == -1) return "";return S.substring(left, right + 1);}
}
20. 反轉(zhuǎn)字符串（入門）
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);}
}解法三
直接調(diào)用庫(kù)函數(shù)
import java.util.*;
public class Solution {public String solve (String str) {StringBuffer sb =new StringBuffer(str);//此方法針對(duì)的是io流，不能針對(duì)字符串。return sb.reverse().toString();}
}