目錄

轉換成小寫字母

字符串轉化為整數

反轉相關的問題

反轉字符串

k個一組反轉

僅僅反轉字母

反轉字符串里的單詞

驗證回文串

判斷是否互為字符重排

最長公共前綴

字符串壓縮問題

---

轉換成小寫字母

給你一個字符串 s ，將該字符串中的大寫字母轉換成相同的小寫字母，返回新的字符串。

每個字母都是有確定的 ASCII的，因此我們可以根據 碼表操作字符串即可。

常見ASCII范圍是：

• a-z：97-122

• A-Z：65-90

• 0-9：48-57

public static String toLowerCase(String s) {int n = s.length();char[] chars = s.toCharArray();for (int i = 0; i < n; ++i) {if (chars[i] >= 65 && chars[i] <= 90) {chars[i] += 32;}}String str = new String(chars);return str;
}

字符串轉化為整數

請你來實現一個 myAtoi(string s) 函數，使其能將字符串轉換成一個 32 位有符號整數

函數 myAtoi(string s) 的算法如下：

1. 空格：讀入字符串并丟棄無用的前導空格（" "）

2. 符號：檢查下一個字符（假設還未到字符末尾）為 '-' 還是 '+'。如果兩者都不存在，則假定結果為正。

3. 轉換：通過跳過前置零來讀取該整數，直到遇到非數字字符或到達字符串的結尾。如果沒有讀取數字，則結果為0。

4. 舍入：如果整數數超過 32 位有符號整數范圍 [?2(31), 2(31 )? 1] ，需要截斷這個整數，使其保持在這個范圍內。具體來說，小于 ?2(31) 的整數應該被舍入為 ?2(31) ，大于 2(31 )? 1 的整數應該被舍入為 2(31 )? 1 。

返回整數作為最終結果。

public static int myAtoi(String str) {int len = str.length();char[] charArray = str.toCharArray();// 1、去除前導空格int index = 0;while (index < len && charArray[index] == ' ') {index++;}// 2、如果已經遍歷完成（針對極端用例 "      "）if (index == len) {return 0;}// 3、如果出現符號字符，僅第 1 個有效，并記錄正負int sign = 1;char firstChar = charArray[index];if (firstChar == '+') {index++;} else if (firstChar == '-') {index++;sign = -1;}// 4、將后續出現的數字字符進行轉換// 不能使用 long 類型，這是題目說的int res = 0;while (index < len) {char currChar = charArray[index];// 4.1 先判斷不合法的情況if (currChar > '9' || currChar < '0') {break;}// 這是解決溢出問題的經典處理方式。if (res > Integer.MAX_VALUE / 10 || (res == Integer.MAX_VALUE / 10 && (currChar - '0') > Integer.MAX_VALUE % 10)) {return Integer.MAX_VALUE;}if (res < Integer.MIN_VALUE / 10 || (res == Integer.MIN_VALUE / 10 && (currChar - '0') > -(Integer.MIN_VALUE % 10))) {return Integer.MIN_VALUE;}// 合法的情況下，才考慮轉換，每一步都把符號位乘進去// 想想這里為什么要帶著sign乘res = res * 10 + sign * (currChar - '0');index++;}return res;
}

反轉相關的問題

反轉字符串

編寫一個函數，其作用是將輸入的字符串反轉過來。輸入字符串以字符數組 s 的形式給出。

不要給另外的數組分配額外的空間，你必須原地修改輸入數組、使用 O(1) 的額外空間解決這一問題。

• 一看就是雙指針問題！太經典了！

public void reverseString(char[] s) {if (s == null || s.length() == 0) {return ;}int n = s.length;for (int left = 0, right = n - 1; left < right; ++left, --right) {char tmp = s[left];s[left] = s[right];s[right] = tmp;}}

k個一組反轉

給定一個字符串 s 和一個整數 k，從字符串開頭算起，每計數至 2k 個字符，就反轉這 2k 字符中的前 k 個字符。

• 如果剩余字符少于 k 個，則將剩余字符全部反轉。

• 如果剩余字符小于 2k 但大于或等于 k 個，則反轉前 k 個字符，其余字符保持原樣。

反轉每個下標從 2k的倍數開始的，長度為 k的子串。若該子串長度不足 k，則反轉整個子串。

public String reverseStr(String s, int k) {if (s == null || s.length() == 0) {return s;}int n = s.length();char[] arr = s.toCharArray();for (int i = 0; i < n; i += 2 * k) {reverse(arr, i, Math.min(i + k, n) - 1);}return new String(arr);}public void reverse(char[] arr, int left, int right) {while (left < right) {char temp = arr[left];arr[left] = arr[right];arr[right] = temp;left++;right--;}}

僅僅反轉字母

給定一個字符串 S，返回 “反轉后的” 字符串，其中不是字母的字符都保留在原地，而所有字母的位置發生反轉。

示例1：

輸入："ab-cd"

輸出："dc-ba"

示例2：

輸入："a-bC-dEf-ghIj"

輸出："j-Ih-gfE-dCba"

示例3：

輸入："Test1ng-Leet=code-Q!"

輸出："Qedo1ct-eeLg=ntse-T!"

• 棧：將 s 中的所有字母單獨存入棧中，所以出棧等價于對字母反序操作。（或者可以用數組存儲字母并反序數組）然后，遍歷 s 的所有字符，如果是字母我們就選擇棧頂元素輸出。

• 雙指針：一個接一個輸出 s 的所有字符。當遇到一個字母時，我們希望找到逆序遍歷字符串的下一個字母。所以我們這么做：維護一個指針 j 從后往前遍歷字符串，當需要字母時就使用它。

class Solution {public String reverseOnlyLetters(String S) {Stack<Character> letters = new Stack();for (char c: S.toCharArray())if (Character.isLetter(c))letters.push(c);StringBuilder ans = new StringBuilder();for (char c: S.toCharArray()) {if (Character.isLetter(c))ans.append(letters.pop());elseans.append(c);}return ans.toString();}
}

class Solution {public String reverseOnlyLetters(String S) {if (S == null || S.length() == 0) {return S;}StringBuilder ans = new StringBuilder();int j = S.length() - 1;for (int i = 0; i < S.length(); ++i) {if (Character.isLetter(S.charAt(i))) {while (!Character.isLetter(S.charAt(j)))j--;ans.append(S.charAt(j--));} else {ans.append(S.charAt(i));}}return ans.toString();}
}

反轉字符串里的單詞

給你一個字符串 s ，逐個反轉字符串中的所有 單詞 。

單詞 是由非空格字符組成的字符串。s 中使用至少一個空格將字符串中的 單詞 分隔開。

請你返回一個反轉 s 中單詞順序并用單個空格相連的字符串。

說明：

• 輸入字符串 s 可以在前面、后面或者單詞間包含多余的空格。

• 反轉后單詞間應當僅用一個空格分隔。

• 反轉后的字符串中不應包含額外的空格。

示例1：

輸入：s = "the sky is blue"

輸出："blue is sky the"

示例2：

輸入：s = "hello world"

輸出："world hello"

解釋：輸入字符串可以在前面或者后面包含多余的空格，但是反轉后的字符不能包括。

public String reverseWords(String s) {if (s == null || s.length() == 0) {return 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;}}
}

驗證回文串

給定一個字符串，找到它的第一個不重復的字符，并返回它的索引。如果不存在，則返回 -1。

• 在第一次遍歷時，我們使用哈希映射統計出字符串中每個字符出現的次數。在第二次遍歷時，我們只要遍歷到了一個只出現一次的字符，那么就返回它的索引，否則在遍歷結束后返回 -1。

public int firstUniqChar(String s) {if (s == null || s.length() == 0) {return 0;}Map<Character, Integer> frequency = new HashMap<Character, Integer>();for (int i = 0; i < s.length(); ++i) {char ch = s.charAt(i);frequency.put(ch, frequency.getOrDefault(ch, 0) + 1);}for (int i = 0; i < s.length(); ++i) {if (frequency.get(s.charAt(i)) == 1) {return i;}}return -1;}

判斷是否互為字符重排

給定兩個字符串 s1 和 s2，請編寫一個程序，確定其中一個字符串的字符重新排列后，能否變成另一個字符串。

• 將兩個字符串全部從小到大或者從大到小排列，然后再逐個位置比較

• 我們可以記錄出現的次數，如果一個字符串經過重新排列后，能夠變成另外一個字符串，那么它們的每個不同字符的出現次數是相同的。如果出現次數不同，那么表示兩個字符串不能夠經過重新排列得到。

public boolean checkPermutation(String s1, String s2) {// 將字符串轉換成字符數組char[] s1Chars = s1.toCharArray();char[] s2Chars = s2.toCharArray();// 對字符數組進行排序Arrays.sort(s1Chars);Arrays.sort(s2Chars);// 再將字符數組轉換成字符串，比較是否相等return new String(s1Chars).equals(new String(s2Chars));}

public boolean checkPermutation(String s1, String s2) {if (s1.length() != s2.length()) {return false;}char[] s1Chars = s1.toCharArray();Map<Character, Integer> s1Map = getMap(s1);Map<Character, Integer> s2Map = getMap(s2);for (char s1Char : s1Chars) {if (!s2Map.containsKey(s1Char) || (int)s2Map.get(s1Char) != (int)s1Map.get(s1Char)) {return false;}}return true;}// 統計指定字符串str中各字符的出現次數，并以Map的形式返回private Map<Character, Integer> getMap(String str) {Map<Character, Integer> map = new HashMap<>();char[] chars = str.toCharArray();for (char aChar : chars) {map.put(aChar, map.getOrDefault(aChar, 0) + 1);}return map;}

最長公共前綴

編寫一個函數來查找字符串數組中的最長公共前綴。如果不存在公共前綴，返回空字符串 ""。

示例1：

輸入：strs = ["flower","flow","flight"]

輸出："fl"

示例2：

輸入：strs = ["dog","racecar","car"]

輸出：""

解釋：輸入不存在公共前綴。

• 豎著比較，每前進一個位置就比較各個串，看是不是都是相等的，只要在某一輪遇到一個不相等的，那么就結束。

• 橫著比較，借鑒歸并的思想，先兩兩一組找fix，然后將找到的fix再兩兩歸并。依次遍歷字符串數組中的每個字符串，對于每個遍歷到的字符串，更新最長公共前綴（其實就是看是否要縮短，一定不會變長），當遍歷完所有的字符串以后，即可得到字符串數組中的最長公共前綴。如果在尚未遍歷完所有的字符串時，最長公共前綴已經是空串，則最長公共前綴一定是空串，因此不需要繼續遍歷剩下的字符串，直接返回空串即可。

public String longestCommonPrefix(String[] strs) {if (strs == null || strs.length == 0) {return "";}int length = strs[0].length();int count = strs.length;for (int i = 0; i < length; i++) {char c = strs[0].charAt(i);for (int j = 1; j < count; j++) {if (i == strs[j].length() || strs[j].charAt(i) != c) {return strs[0].substring(0, i);}}}return strs[0];

public String longestCommonPrefix(String[] strs) {if (strs == null || strs.length == 0) {return "";}String prefix = strs[0];int count = strs.length;for (int i = 1; i < count; i++) {prefix = longestCommonPrefix(prefix, strs[i]);if (prefix.length() == 0) {break;}}return prefix;
}public String longestCommonPrefix(String str1, String str2) {int length = Math.min(str1.length(), str2.length());int index = 0;while (index < length && str1.charAt(index) == str2.charAt(index)) {index++;}return str1.substring(0, index);
}

字符串壓縮問題

給你一個字符數組 chars ，請使用下述算法壓縮：

從一個空字符串 s 開始。對于 chars 中的每組 連續重復字符 ：

• 如果這一組長度為 1 ，則將字符追加到 s 中。

• 否則，需要向 s 追加字符，后跟這一組的長度。壓縮后得到的字符串 s 不應該直接返回 ，需要轉儲到字符數組 chars 中。需要注意的是，如果組長度為 10 或 10 以上，則在 chars 數組中會被拆分為多個字符。

請在 修改完輸入數組后 ，返回該數組的新長度。你必須設計并實現一個只使用常量額外空間的算法來解決此問題。

示例1：
輸入：chars = ["a","a","b","b","c","c","c"]
輸出：返回 6 ，輸入數組的前 6 個字符應該是：["a","2","b","2","c","3"]
解釋：
"aa" 被 "a2" 替代。"bb" 被 "b2" 替代。"ccc" 被 "c3" 替代。示例2：
輸入：chars = ["a"]
輸出：返回 1 ，輸入數組的前 1 個字符應該是：["a"]
解釋：
沒有任何字符串被替代。示例3：
輸入：chars = ["a","b","b","b","b","b","b","b","b","b","b","b","b"]
輸出：返回 4 ，輸入數組的前 4 個字符應該是：["a","b","1","2"]。
解釋：
由于字符 "a" 不重復，所以不會被壓縮。"bbbbbbbbbbbb" 被 “b12” 替代。
注意每個數字在數組中都有它自己的位置。

• 可以使用兩個指針分別標志我們在字符串中讀和寫的位置，還要一個指針left用來標記重復字段的開始位置。read指針不斷向前讀取，每次當讀指針 read 移動到某一段連續相同子串的最右側，我們就在寫指針 write 處依次寫入該子串對應的字符和子串長度即可。當讀指針read 位于字符串的末尾，或讀指針read 指向的字符不同于下一個字符時，我們就認為讀指針read 位于某一段連續相同子串的最右側。該子串對應的字符即為讀指針 read 指向的字符串。我們使用變量 left 記錄該子串的最左側的位置，這樣子串長度即為 read?left+1。這里還有一個問題，就是長度可能超過10，因此還要實現將數字轉化為字符串寫入到原字符串的功能。這里我們采用短除法將子串長度倒序寫入原字符串中，然后再將其反轉即可。

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--;}}
}