力扣初級演算法（二）【字串】
字串問題在面試中出現頻率很高，你極有可能在面試中遇到，
我們推薦以下題目：反轉字串，字串中第一個唯一字符，字串轉整數（atoi）和 實作 strStr() ，
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"]
解題思路
-
樸素的想法是，反向遍歷陣列，然后進行拷貝即可，
但是對于本題來說，要求原地操作 ，我們可以使用雙指標來交換陣列中首尾的值，實作反轉，
-
讓左右指標分別向中間移動，同時交換對應的值即可，
-
在C#語言當中，可以利用元組直接交換兩個元素值，
方法一：雙指標
public void ReverseString(char[] s) {
for (int left = 0, right = s.Length - 1; left < right; left++, right--)
(s[left], s[right]) = (s[right], s[left]);
}
387. 字串中的第一個唯一字符
難度：簡單
給定一個字串，找到它的第一個不重復的字符，并回傳它的索引，如果不存在，則回傳 -1，
示例：
s = "leetcode" 回傳 0 s = "loveleetcode" 回傳 2提示：你可以假定該字串只包含小寫字母，
解題思路
-
樸素的想法是，遍歷字串并統計各個字符的出現次數，
-
然后再次遍歷該字串，如果某個字符的出現次數為一，就回傳這個字符的下標，
-
這里可以考慮用哈希表來統計出現次數，因為只包含小寫字母，所以也可以用陣列來統計，
這里給出LINQ的解法，
方法一：統計數量
public int FirstUniqChar(string s)
{
var res = s.GroupBy(x => x).Where(y => y.Count() == 1).FirstOrDefault();
return res is null ? -1 : s.IndexOf(res.First());
}
8. 字串轉換整數 (atoi)
難度：中等
請你來實作一個
atoi函式，使其能將字串轉換成整數，首先，該函式會根據需要丟棄無用的開頭空格字符，直到尋找到第一個非空格的字符為止，接下來的轉化規則如下：
- 如果第一個非空字符為正或者負號時，則將該符號與之后面盡可能多的連續數字字符組合起來，形成一個有符號整數，
- 假如第一個非空字符是數字，則直接將其與之后連續的數字字符組合起來，形成一個整數，
- 該字串在有效的整數部分之后也可能會存在多余的字符，那么這些字符可以被忽略，它們對函式不應該造成影響，
注意：假如該字串中的第一個非空格字符不是一個有效整數字符、字串為慷訓字串僅包含空白字符時，則你的函式不需要進行轉換，即無法進行有效轉換，
在任何情況下，若函式不能進行有效的轉換時，請回傳 0 ，
提示：
- 本題中的空白字符只包括空格字符
' '，- 假設我們的環境只能存盤 32 位大小的有符號整數，如果數值超過這個范圍，請回傳 INT_MAX 或 INT_MIN ，
示例 1:
輸入: "42" 輸出: 42示例 2:
輸入: " -42" 輸出: -42 解釋: 第一個非空白字符為 '-', 它是一個負號， 我們盡可能將負號與后面所有連續出現的數字組合起來，最后得到 -42 ，示例 3:
輸入: "4193 with words" 輸出: 4193 解釋: 轉換截止于數字 '3' ，因為它的下一個字符不為數字，示例 4:
輸入: "words and 987" 輸出: 0 解釋: 第一個非空字符是 'w', 但它不是數字或正、負號， 因此無法執行有效的轉換，示例 5:
輸入: "-91283472332" 輸出: -2147483648 解釋: 數字 "-91283472332" 超過 32 位有符號整數范圍， 因此回傳 INT_MIN，
解題思路
-
樸素的想法是，掃描的給定的字串，對讀到到的不同字符做不同處理，
-
想法很簡單，但是實作起來就稍有一些麻煩了，顯然我們要做出的處理不止一種，
這里肯定需要根據讀到的不同字符做不同的判斷，
-
這里我們對不同的情況稍加分析，大抵上可以歸類為以下幾種情況：
- 整數前面的空白符
- '+' '-'號
- 數字
- 其他字符
-
我們應該做出如下的處理
- 對于整數前面的空白符，直接跳過即可
- 對于'+' '-'號，如果出現在數字前，視為正負數識別符號，如果出現在數字后，視為其他字符
- 對于數字，視為數字，
- 對于其他字符，做讀取結束處理
-
其中，較為復雜的部分在于空白符和正負號出現的位置，這很難直接用if陳述句或switch陳述句判斷，此時，我們可以考慮再引入一個狀態標記，用于標記當前讀取的字串處于什么狀態，
- 如果還未讀取到任何數字，那么讀取到空白符和正負號都是合法的
- 如果已經讀取到數字，再讀取到任意其他字符都是非法的，
-
這里我們定義了三種狀態，分別是起始狀態、數字狀態、以及結束狀態用來終止讀取，
-
在不同的狀態下，我們再對讀取到的字符做不同處理，這樣就簡單多了，
方法一：狀態機
enum MyState
{
NONE,
DIGIT,
FINISH,
}
public int MyAtoi(string s)
{
var state = new MyState();
var sb = new StringBuilder();
foreach (var item in s.TrimStart())
{
switch (state)
{
case MyState.NONE:
if (item.Equals('-') || item.Equals('+') || Char.IsDigit(item))
{
state = MyState.DIGIT;
sb.Append(item);
}
else
{
state = MyState.FINISH;
}
break;
case MyState.DIGIT:
if (Char.IsDigit(item))
{
sb.Append(item);
}
else
{
state = MyState.FINISH;
}
break;
default:
break;
}
if (state.Equals(MyState.FINISH)) break;
}
try
{
return int.Parse(sb.ToString());
}
catch (OverflowException)
{
return sb[0].Equals('-') ? int.MinValue : int.MaxValue;
}
catch (FormatException)
{
return 0;
}
}
思考
- 對于狀態位的定義，可以為符號位單獨定義一個狀態，也可以為不合法的資料定義一個失敗的狀態，這些留給讀者自行嘗試，
- 除此之外，你還可以考慮不使用庫函式來自行判斷是否為數字，是否溢位等，
28. 實作 strStr()
難度：簡單
實作 strStr() 函式，
給定一個 haystack 字串和一個 needle 字串，在 haystack 字串中找出 needle 字串出現的第一個位置 (從0開始)，如果不存在，則回傳 -1，
示例 1:
輸入: haystack = "hello", needle = "ll" 輸出: 2示例 2:
輸入: haystack = "aaaaa", needle = "bba" 輸出: -1說明:
當
needle是空字串時，我們應當回傳什么值呢？這是一個在面試中很好的問題，對于本題而言，當
needle是空字串時我們應當回傳 0 ，這與C語言的 strstr() 以及 Java的 indexOf() 定義相符，
解題思路
- 樸素的想法是，遍歷給定的字串，看看能否從某一個字符開始，和給定的子串完全匹配，
方法一：暴力列舉
public int StrStr(string haystack, string needle)
{
for (int i = 0; i <= haystack.Length - needle.Length; i++)
if (FindP(i)) return i;
return -1;
bool FindP(int start)
{
for (int i = 0; i < needle.Length; i++, start++)
if (!haystack[start].Equals(needle[i])) return false;
return true;
}
}
-
上面這種解法是最容易想到的，
不過除此之外，還可以考慮使用字串匹配的一個經典演算法，KMP演算法，
-
這里給出一個講解的很好的KMP演算法視頻，感興趣的讀者可以深入了解一下，
方法二：KMP演算法
public int StrStr(string haystack, string needle)
{
// dp[i] 表示 i 前面的都匹配成功時的相同前后綴長度
var dp = new int[needle.Length];
// 填表
for (int l = 0, r = 1; r < needle.Length - 1;)
if (needle[l].Equals(needle[r]))
{
dp[++r] = ++l;
}
else if (l == 0)
{
dp[++r] = 0;
}
else
{
l = dp[l];
}
// 字串匹配
for (int i = 0, j = 0; i - j <= haystack.Length - needle.Length;
i += j == 0 ? 1 : 0, j = dp[j])
{
for (; j < needle.Length; j++, i++)
if (!haystack[i].Equals(needle[j])) break;
if (j == needle.Length) return i - needle.Length;
}
return -1;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/173165.html
標籤：其他
下一篇：Java 集合看這一篇就夠了