力扣中級演算法（一）【陣列和字串】
本文中的題目均來自力扣，代碼默認以C#實作，偽代碼僅用來幫助描述，不嚴格遵循某種語言的語法，
- 可前往GitHub下載Markdown 筆記
陣列和字串問題在面試中出現頻率很高，你極有可能在面試中遇到，
我們推薦以下題目：字母異位詞分組，無重復字符的最長子串 和 最長回文子串，
目錄
- 力扣中級演算法（一）【陣列和字串】
- 49. 字母異位詞分組
- 解題思路
- 方法一：哈希表
- 解題思路
- 3. 無重復字符的最長子串
- 解題思路
- 方法一：暴力列舉
- 方法二：滑動視窗
- 解題思路
- 5. 最長回文子串
- 解題思路
- 方法一：暴力列舉
- 方法二：動態規劃
- 解題思路
- 49. 字母異位詞分組
49. 字母異位詞分組
難度：中等
給定一個字串陣列，將字母異位詞組合在一起，字母異位詞指字母相同，但排列不同的字串，
示例:
輸入: ["eat", "tea", "tan", "ate", "nat", "bat"] 輸出: [ ["ate","eat","tea"], ["nat","tan"], ["bat"] ]說明：
- 所有輸入均為小寫字母，
- 不考慮答案輸出的順序，
解題思路
- 樸素的想法是，遍歷整個字串陣列，把異位詞放到同一個串列中，那么如何判斷異位詞呢？
- 我們可以重新定義每個單詞的哈希規則，讓異位詞映射到同一個哈希值上，這有一些困難，我們也可以對每個單詞按照統一規則排序，那么異位詞在排序后必然是相同的，
- 以排序后的單詞作為哈希表的鍵，不失為一種方法，
方法一：哈希表
public IList<IList<string>> GroupAnagrams(string[] strs)
{
var dict = new Dictionary<string, IList<string>>();
foreach (var item in strs)
{
var key = new string(item.OrderBy(x=>x).ToArray());
if (dict.ContainsKey(key))
{
dict[key].Add(item);
}
else
{
dict[key] = new List<string> { item };
}
}
return dict.Values.ToList();
}
3. 無重復字符的最長子串
難度：中等
給定一個字串，請你找出其中不含有重復字符的 最長子串 的長度，
示例 1:
輸入: "abcabcbb" 輸出: 3 解釋: 因為無重復字符的最長子串是 "abc"，所以其長度為 3，示例 2:
輸入: "bbbbb" 輸出: 1 解釋: 因為無重復字符的最長子串是 "b"，所以其長度為 1，示例 3:
輸入: "pwwkew" 輸出: 3 解釋: 因為無重復字符的最長子串是 "wke"，所以其長度為 3， 請注意，你的答案必須是 子串 的長度，"pwke" 是一個子序列，不是子串，
解題思路
-
樸素的想法是，遍歷整個字串，從每個字符開始，向右進行試探，直到找到第一個重復的字符，
-
然后，回傳所有可能的無重復字符子串中的最大的一個
方法一：暴力列舉
public int LengthOfLongestSubstring(string s)
{
var set = new HashSet<char>();
var res = 0;
for (int i = 0; i < s.Length; i++)
{
for (int j = i; j < s.Length; j++)
if (!set.Add(s[j])) break;
res = Math.Max(set.Count, res);
set.Clear();
}
return res;
}
- 在上面的方法中，我們每次探測到一個無重復子串的時候都重新回到
i + 1的位置，再次進行試探， - 稍加思考，我們就會發現，這樣的操作是完全沒有必要的，原因如下：
- 如果第
i個字符不是重復的，那么再次探測的結果一定小于剛剛探測的結果， - 如果第
i個字符是重復的，那么再次探測的結果才可能大于剛剛探測的結果，
- 如果第
- 所以，我們完全可以避免一部分重復的計算，這也是我們優化演算法一直以來的思路，
- 我們可以直接移動多次
i指標，直到與j指標指向的字符相同，
方法二：滑動視窗
public int LengthOfLongestSubstring(string s)
{
var set = new HashSet<char>();
var res = 0;
for (int i = 0, j = 0; j < s.Length; i++)
{
while (j < s.Length && set.Add(s[j])) { j++; }
res = Math.Max(set.Count, res);
set.Remove(s[i]);
}
return res;
}
5. 最長回文子串
難度：中等
給定一個字串
s，找到s中最長的回文子串，你可以假設s的最大長度為 1000，示例 1：
輸入: "babad" 輸出: "bab" 注意: "aba" 也是一個有效答案，示例 2：
輸入: "cbbd" 輸出: "bb"
解題思路
-
樸素的想法是，窮舉所有的可能，對于每一個子串，我們都判斷一下它是不是回文串，
-
顯然，這并不是一個很好的辦法，不過我們可以再次基礎上看看有沒有優化的空間，
- 首先，我們可以從大到小的搜索子串，這樣一旦找到某個符合條件的子串，我們就可以停止接下來的搜索，跳到下一層繼續搜索，
- 其次，我們可以判斷一下要搜索的子串長度有沒有超過當前解，如果沒有超過，就說明不存在更優解，也沒有必要搜索，
方法一：暴力列舉
public string LongestPalindrome(string s)
{
var res = "";
for (int i = 0, j = s.Length - 1; j - i + 1 > res.Length; i++) // 判斷有無更優解
{
for (int k = j; k - i + 1 > res.Length; k--) // 一旦找到就停止了搜索
if (IsP(i, k)) res = s.Substring(i, k - i + 1);
}
return res;
// 判斷是否為質數，
bool IsP(int start, int end)
{
for (int i = start, j = end; i < j; i++, j--)
if (!s[i].Equals(s[j])) return false;
return true;
}
}
- 除了剪枝之外，我們能不能考慮別的優化方案呢？
- 稍加思考，我們發現，在判斷一個子串是否為回文串的程序中，我們存在大量的重復計算，
- 我們不難得出這樣的判斷，如果一個字串是回文串，那么去掉首尾兩個字符，依然是回文串，例如：
ababa => bab => a
-
假如現在有一個字串是這樣的
abcdefdcba，我們在用雙指標判斷回文串的時候，雖然abcd四個字符前后都相等，但ef兩個字符并不相等，如果再次基礎上，我們又掃描到了aabcdefdcbaa子串，這顯然是一種不必要的重復計算， -
我們可以用
DP[i][j]來記錄i-j的子串是否是回文串，不難得出DP[i][j] = DP[i+1][j-1] and (s[i] == s[j]) -
最后，考慮一下我們要從哪里開始填充我們的DP，長度為4的子串是根據長度為2的子串的情況得到的，長度為3的子串是根據長度為1的子串得到的，
-
所以，我們應該讓長度從小到大的填充DP，并且，對于長度1和長度2的子串，進行初值處理，
方法二：動態規劃
public string LongestPalindrome(string s)
{
var res = "";
var dp = new bool[s.Length, s.Length]; // dp[i,j] 表示 i-j 的子串是否為回文串，
for (int l = 0; l < s.Length; l++) // 從長度為1的子串開始填充
{
for (int i = 0; i + l < s.Length; i++)
{
var j = i + l;
switch (l)
{
case 0:
dp[i, j] = true;
break;
case 1:
dp[i, j] = s[i] == s[j];
break;
default:
dp[i, j] = dp[i + 1, j - 1] && (s[i] == s[j]);
break;
}
if (dp[i, j] && (l + 1 > res.Length)) res = s.Substring(i, l + 1);
}
}
return res;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/188900.html
標籤：其他
上一篇：力扣初級演算法（零）【開篇詞】
下一篇：圓圈中最后剩下的數