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 + aca + ac 中 ac 不是迴文串,繼續回溯,回溯到 aac分割為稍長的迴文串,分割為 aa + c 分割完成得到一組結果,再回溯到 aacaac 不是迴文串,搜索結束動畫描述
動畫描述
代碼實現
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
幾道和「二叉樹」有關的算法面試題
幾道和散列(哈希)表有關的面試題
一道看完答案你會覺得很沙雕的「動態規劃算法題」
幾道和「堆棧、隊列」有關的面試算法題
鏈表算法面試問題?看我就夠了!