- A+
力扣初级算法（二）【字符串】
字符串问题在面试中出现频率很高，你极有可能在面试中遇到。
我们推荐以下题目：反转字符串，字符串中第一个唯一字符，字符串转整数（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; } 
