String 作為最常見的編程語言類型之一，在算法面試中出現的頻率極高。
1. 驗證迴文串
題目來源於 LeetCode 第 125 號問題：驗證迴文串。這道題目是 初級程序員 在面試的時候經常遇到的一道算法題，而且面試官喜歡面試者手寫！
題目描述
給定一個字符串，驗證它是否是迴文串，只考慮字母和數字字符，可以忽略字母的大小寫。
說明：本題中，我們將空字符串定義為有效的迴文串。
示例 1:
輸入: "A man, a plan, a canal: Panama"
輸出: true
示例 2:
輸入: "race a car"
輸出: false
題目解析
先理解一個概念：所謂迴文，就是一個正讀和反讀都一樣的字符串。
先假設是驗證一個單詞 level 是否是迴文字符串，通過概念涉及到 正 與 反 ，那麼很容易想到使用雙指針，從字符的開頭和結尾處開始遍歷整個字符串，相同則繼續向前尋找，不同則直接返回 false。
而這裡與單獨驗證一個單詞是否是迴文字符串有所區別的是加入了 空格 與 非字母數字的字符，但實際上的做法一樣的：
一開始先建立兩個指針，left 和 right , 讓它們分別從字符的開頭和結尾處開始遍歷整個字符串。
如果遇到非字母數字的字符就跳過，繼續往下找，直到找到下一個字母數字或者結束遍歷，如果遇到大寫字母，就將其轉為小寫。
當左右指針都找到字母數字時，可以進行比較的時候，比較這兩個字符，如果相等，則兩個指針向它們的前進方向挪動，然後繼續比較下面兩個分別找到的字母數字，若不相等，直接返回 false。
動畫描述
動畫描述
代碼實現
注：isLetterOrDigit 方法確定指定的字符是否為字母或數字。
class Solution {
public boolean isPalindrome(String s) {
if(s.length() == 0)
return true;
int l = 0, r = s.length() - 1;
while(l < r){
//確定指定的字符是否為字母或數字
if(!Character.isLetterOrDigit(s.charAt(l))){
l++;
}else if(!Character.isLetterOrDigit(s.charAt(r))){
r--;
}else{
if(Character.toLowerCase(s.charAt(l)) != Character.toLowerCase(s.charAt(r)))
return false;
l++;
r--;
}
}
return true;
}
}
2. 分割回文串
題目來源於 LeetCode 第 131 號問題：分割回文串。
題目描述
給定一個字符串 s，將 s 分割成一些子串，使每個子串都是迴文串。
返回 s 所有可能的分割方案。
示例:
輸入: "aab"
輸出:
[
["aa","b"],
["a","a","b"]
]
題目解析
首先，對於一個字符串的分割，肯定需要將所有分割情況都遍歷完畢才能判斷是不是迴文數。不能因為 abba 是迴文串，就認為它的所有子串都是迴文的。
既然需要將所有的分割方法都找出來，那麼肯定需要用到DFS（深度優先搜索）或者BFS（廣度優先搜索）。
在分割的過程中對於每一個字符串而言都可以分為兩部分：左邊一個迴文串加右邊一個子串，比如 "abc" 可分為 "a" + "bc" 。 然後對"bc"分割仍然是同樣的方法，分為"b"+"c"。
在處理的時候去優先尋找更短的迴文串，然後回溯找稍微長一些的迴文串分割方法，不斷回溯，分割，直到找到所有的分割方法。
舉個：分割"aac"。
- 分割為 a + ac
- 分割為 a + a + c，分割後，得到一組結果，再回溯到 a + ac
- a + ac 中 ac 不是迴文串，繼續回溯，回溯到 aac
- 分割為稍長的迴文串，分割為 aa + c 分割完成得到一組結果，再回溯到 aac
- aac 不是迴文串，搜索結束
動畫描述
動畫描述
代碼實現
class Solution {
List<list>> res = new ArrayList<>();
public List<list>> partition(String s) {
if(s==null||s.length()==0)
return res;
dfs(s,new ArrayList<string>(),0);
return res;
}
public void dfs(String s,List<string> remain,int left){
if(left==s.length()){ //判斷終止條件
res.add(new ArrayList<string>(remain)); //添加到結果中
return;
}
for(int right=left;right<s.length>right是不是迴文串
if(isPalindroom(s,left,right)){ //判斷是否是迴文串
remain.add(s.substring(left,right+1)); //添加到當前迴文串到list中
dfs(s,remain,right+1); //從right+1開始繼續遞歸，尋找回文串
remain.remove(remain.size()-1); //回溯，從而尋找更長的迴文串
}
}
}
/**
* 判斷是否是迴文串
*/
public boolean isPalindroom(String s,int left,int right){
while(left<right> left++;
right--;
}
return left>=right;
}
}
/<right>/<s.length>/<string>/<string>/<string>/<list>/<list>3. 單詞拆分
題目來源於 LeetCode 第 139 號問題：單詞拆分。
題目描述
給定一個非空字符串 s 和一個包含非空單詞列表的字典 wordDict，判定 s 是否可以被空格拆分為一個或多個在字典中出現的單詞。
說明：
- 拆分時可以重複使用字典中的單詞。
- 你可以假設字典中沒有重複的單詞。
題目解析
與上面的第二題 分割回文串 有些類似，都是拆分，但是如果此題採取 深度優先搜索 的方法來解決的話，答案是超時的，不信的同學可以試一下~
為什麼會超時呢？
因為使用 深度優先搜索 會重複的計算了有些位的可拆分情況，這種情況的優化肯定是需要 動態規劃 來處理的。
如果不知道動態規劃的，可以看一下小吳之前的
萬字長文，比較詳細的介紹了動態規劃的概念。
在這裡，只需要去定義一個數組 boolean[] memo，其中第 i 位 memo[i] 表示待拆分字符串從第 0 位到第 i-1 位是否可以被成功地拆分。
然後分別計算每一位是否可以被成功地拆分。
代碼實現
class Solution {
public boolean wordBreak(String s, List<string> wordDict) {
int n = s.length();
int max_length=0;
for(String temp:wordDict){
max_length = temp.length() > max_length ? temp.length() : max_length;
}
// memo[i] 表示 s 中以 i - 1 結尾的字符串是否可被 wordDict 拆分
boolean[] memo = new boolean[n + 1];
memo[0] = true;
for (int i = 1; i <= n; i++) {
for (int j = i-1; j >= 0 && max_length >= i - j; j--) {
if (memo[j] && wordDict.contains(s.substring(j, i))) {
memo[i] = true;
break;
}
}
}
return memo[n];
}
}
/<string>4. 反轉字符串
題目來源於 LeetCode 第 344 號問題：反轉字符串。面試官最喜歡讓你手寫的一道算法題！
題目描述
編寫一個函數，其作用是將輸入的字符串反轉過來。輸入字符串以字符數組 char[] 的形式給出。
不要給另外的數組分配額外的空間，你必須原地修改輸入數組、使用 O(1) 的額外空間解決這一問題。
你可以假設數組中的所有字符都是 ASCII 碼錶中的可打印字符。
示例 1：
輸入：["h","e","l","l","o"]
輸出：["o","l","l","e","h"]
示例 2：
輸入：["H","a","n","n","a","h"]
輸出：["h","a","n","n","a","H"]
題目解析
這道題沒什麼難度，直接從兩頭往中間走，同時交換兩邊的字符。注意需要白板編程寫出來即可，也注意千萬別回答一句使用 reverse() 這種高級函數來解決。。。
動畫描述
動畫
代碼實現
class Solution {
public:
string reverseString(string s) {
int i = 0, j = s.size() - 1;
while (i < j){
swap(s[i],s[j]);
i++;
j--;
}
return s;
}
};
5. 把字符串轉換成整數
題目描述
將一個字符串轉換成一個整數，字符串不是一個合法的數值則返回 0，要求不能使用字符串轉換整數的庫函數。
題目解析
這道題要考慮全面，對異常值要做出處理。
對於這個題目，需要注意的要點有：
- 指針是否為空指針以及字符串是否為空字符串；
- 字符串對於正負號的處理；
- 輸入值是否為合法值，即小於等於'9'，大於等於'0'；
- int為32位，需要判斷是否溢出；
- 使用錯誤標誌，區分合法值0和非法值0。
代碼實現
public class Solution {
public int StrToInt(String str) {
if (str == null || str.length() == 0)
return 0;
boolean isNegative = str.charAt(0) == '-';
int ret = 0;
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
if (i == 0 && (c == '+' || c == '-')) /* 符號判定 */
continue;
if (c < '0' || c > '9') /* 非法輸入 */
return 0;
ret = ret * 10 + (c - '0');
}
return isNegative ? -ret : ret;
}
}
拜託，面試官別問我「布隆」了
數據結構與算法： 三十張圖弄懂「圖的兩種遍歷方式」
昨天，終於拿到了騰訊 offer
幾道和「二叉樹」有關的算法面試題
幾道和散列（哈希）表有關的面試題
一道看完答案你會覺得很沙雕的「動態規劃算法題」
幾道和「堆棧、隊列」有關的面試算法題
鏈表算法面試問題？看我就夠了！
閱讀更多 五分鐘學算法 的文章
