本文正在参加「金石计划 . 分割6万现金大奖」
题一：验证回文串
假如在将一切大写字符转化为小写字符、并移除一切非字母数字字符之后，短语正着读和反着读都相同。则能够认为该短语是一个 回文串
字母和数字都归于字母数字字符
给你一个字符串 s，假如它是 回文串 ，回来 true ；否则，回来 false。
示例 1：
输入: s = "A man, a plan, a canal: Panama"
输出：true
解说："amanaplanacanalpanama" 是回文串。
示例 2：
输入：s = "race a car"
输出：false
解说："raceacar" 不是回文串。
示例 3：
输入：s = " "
输出：true
解说：在移除非字母数字字符之后，s 是一个空字符串 "" 。
由于空字符串正着反着读都相同，所以是回文串。
解题思路：双指针、Reversed
回文串：字符对称呈现； 根据这个特性，咱们能够有两种做法：
- 运用双指针判别前后持平。
- 颠倒字符串判别是否持平；
解法一：双指针
双指针 i（➡️）， j = n-i-1（⬅️）
判别两个指针指向的字符是否相同；
假如相同，则一起移动方位，i++、j--；假如不相同，则当即跳出循环；
在判别相同之前，还需求处理字符的合法性，假如哪一个指针的字符不合法，则需求持续移位，直到找到合法的字符为止。
时刻复杂度：O(n)
空间复杂度：O(1)
代码
func isPalindrome(_ s: String) -> Bool {
let sList = Array(s)
var res = true
guard sList.count > 0 else { return res }
var leftIndex = 0
var rightIndex = sList.count - 1
while leftIndex < rightIndex {
while leftIndex < rightIndex {
let lChar = sList[leftIndex]
if String(lChar).isAlphanumeric { break }
leftIndex += 1
}
while leftIndex < rightIndex {
let rChar = sList[rightIndex]
if String(rChar).isAlphanumeric { break }
rightIndex -= 1
}
if sList[leftIndex].lowercased() != sList[rightIndex].lowercased() {
res = false
return res
}
leftIndex += 1
rightIndex -= 1
}
return res
}
解法二：挑选 + 双指针
根据上一种解法，咱们知道在判别字符串之前还需求验证字符串。假如字符串中的其他的字符（除字母和数字以外）比较多的话，那么解法一会在验证字符串上耗时较长。
所以解法二采用先挑选合法的字符串，再运用双指针遍历。
时刻复杂度：O(n) n取决于s的长度
空间复杂度：O(n)
代码
func isPalindrome(_ s: String) -> Bool {
var res = true
guard s.count > 0 else { return res }
var list = [String]()
for char in s {
if String(char).isAlphanumeric {
list.append(String(char))
}
}
var leftIndex = 0
var rightIndex = list.count - 1
while leftIndex < rightIndex {
if list[leftIndex].lowercased() != list[rightIndex].lowercased() {
res = false
return res
}
leftIndex += 1
rightIndex -= 1
}
return res
}
解法三：Reversed
有种用魔法打败魔法的感觉。
代码
func isPalindrome3(_ s: String) -> Bool {
var res = true
guard s.count > 0 else { return res }
let str = s.matchAlphanumeric()
let tempStr = String(str.reversed())
if str != tempStr {
res = false
}
return res
}
题二：字符串转化整数 (atoi)
请你来完成一个 myAtoi(string s) 函数，使其能将字符串转化成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。
函数 myAtoi(string s) 的算法如下：
读入字符串并丢掉无用的前导空格
检查下一个字符（假设还未到字符末尾）为正仍是负号，读取该字符（假如有）。 确认终究成果是负数仍是正数。 假如两者都不存在，则假定成果为正。
读入下一个字符，直到抵达下一个非数字字符或抵达输入的结尾。字符串的其余部分将被疏忽。
将前面过程读入的这些数字转化为整数（即，”123″ -> 123， “0032” -> 32）。假如没有读入数字，则整数为 0 。必要时更改符号（从过程 2 开端）。
假如整数数超过 32 位有符号整数范围 [−2^31^, 2^31^ − 1] ，需求截断这个整数，使其保持在这个范围内。具体来说，小于 −2^31^ 的整数应该被固定为 −2^31^ ，大于 2^31^ − 1 的整数应该被固定为 2^31^ − 1 。
回来整数作为终究成果。
示例 1：
输入：s = "42"
输出：42
示例 2：
输入：s = " -42"
输出：-42
示例 3：
输入：s = "4193 with words"
输出：4193
解题思路：数学计算(考虑溢出）
字符串转化整数需求考虑到以下三点：
- 先过滤空格
- 识别 +、—
- 过滤>9,<0的符号，以及数字溢出的处理；
代码
func myAtoi(_ s: String) -> Int {
guard s.count > 0 else { return 0 }
var res: Int = 0
var index = 0
var sign = 1
let array = Array(s)
/// 第一步
while index < s.count, array[index] == " " {
index+=1
}
if index == array.count { return Int(res) }
/// 第二步
if array[index] == "+" {
index+=1
} else if array[index] == "-"{
sign = 0
index+=1
}
/// 第三步
while index < s.count {
let char = array[index]
if char > "9" || char < "0" {
break
}
let charNum = (char.asciiValue ?? 0) - (Character("0").asciiValue ?? 0)
if res > Int32.max / 10 || (res == Int32.max / 10 && charNum > Int32.max % 10) {
res = Int(Int32.max)
break
}
if res < Int32.min / 10 || (res == Int32.min / 10 && charNum > -(Int32.min % 10)) {
res = Int(Int32.min)
break
}
res = res * 10 + Int(charNum) * (sign == 1 ? 1 : -1)
index+=1
}
return Int(res)
}
题三：完成 strStr()
给你两个字符串haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开端）。假如needle 不是 haystack 的一部分，则回来 -1 。
示例 1：
输入：haystack = "sadbutsad", needle = "sad"
输出：0
解说："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以回来 0 。
示例 2：
输入：haystack = "leetcode", needle = "leeto"
输出：-1
解说："leeto" 没有在 "leetcode" 中呈现，所以回来 -1 。
解题思路： 匹配字符串
匹配字符串浅显来讲便是找到字串，而找字串的话，最简略的做法便是从两个字符串开头开端匹配，假如两个字符相同，则持续往后匹配，假如两个字符不匹配，则回溯持续找。
这种解法中，因为有回溯的过程，所以有一定的时刻上的耗时。尽管能够简略的完成，但不是最优解。
假如 h[i] == n[j], i++, j++;
假如 h[i] != n[j], i=i-j+1, j=0;
代码
func strStr(_ haystack: String, _ needle: String) -> Int {
let h = Array(haystack)
let n = Array(needle)
var res = -1
var i = 0, j = 0
while i < h.count && j < n.count {
if h[i] == n[j] {
i+=1; j+=1
} else {
i = i-j+1; j=0
}
if j == n.count {
res = i-j
break
}
}
return res
}
题四：外观数列
给定一个正整数 n ，输出外观数列的第 n 项。
「外观数列」是一个整数序列，从数字 1 开端，序列中的每一项都是对前一项的描绘。
你能够将其视作是由递归公式界说的数字字符串序列：
countAndSay(1) = "1"
countAndSay(n) 是对 countAndSay(n-1) 的描绘，然后转化成另一个数字字符串。
前五项如下：
1. 1
2. 11
3. 21
4. 1211
5. 111221
第一项是数字 1
描绘前一项，这个数是 1 即 “ 一 个 1 ”，记作 "11"
描绘前一项，这个数是 11 即 “ 二 个 1 ” ，记作 "21"
描绘前一项，这个数是 21 即 “ 一 个 2 + 一 个 1 ” ，记作 "1211"
描绘前一项，这个数是 1211 即 “ 一 个 1 + 一 个 2 + 二 个 1 ” ，记作 "111221"
解题思路：递归法
当后一项需求依靠前一项的成果时，能够运用递归法。思路其实便是先压栈，然后再顺次出栈。
掌握了这个思路，将一切项都顺次进栈，f(n)、f(n-1)、f(n-2)、...、f(1)，描绘完前一项之后，顺次出栈f(1)、f(2)、f(3)、...、f(n)。
入栈：
f(n) -> f(n-1) -> f(n-2) -> ... -> f(1)
描绘：
前项描绘 + \(count)\(item)
出栈：
f(n) <- f(n-1) <- f(n-2) <- ... <- f(1)
代码
func countAndSay(_ n: Int) -> String {
if n == 1 { return "1" }
let s = countAndSay(n-1)
var count = 1
var string = ""
var item = s[s.index(s.startIndex, offsetBy: 0)]
for i in 1..<s.count {
let startIndex = s.index(s.startIndex, offsetBy: i)
let char: Character = s[startIndex]
if char == item {
count += 1
} else {
string += ("\(count)\(item)")
count = 1
item = char
}
}
return string + "\(count)\(item)"
}
题五：最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。 假如不存在公共前缀，回来空字符串””。
示例 1：
输入： strs = ["flower","flow","flight"]
输出： "fl"
示例 2：
输入： strs = ["dog","racecar","car"]
输出： ""
解说： 输入不存在公共前缀。
解题思路：横向查找、纵向查找
解法一：横向查找
横向查找是指顺次遍历每个字符串，更新最长公共前缀。
代码
func longestCommonPrefix(_ strs: [String]) -> String {
guard strs.count > 0 else { return "" }
var str = strs[0]
for i in 1..<strs.count {
str = commonPrefix(str,strs[i])
if str.count == 0 { break }
}
return str
}
func commonPrefix(_ str1: String, _ str2: String) -> String {
let length = min(str1.count, str2.count)
var index = 0
while index < length {
let char1 = str1[str1.index(str1.startIndex, offsetBy: index)]
let char2 = str2[str2.index(str2.startIndex, offsetBy: index)]
if char1 != char2 {
break
}
index+=1
}
return String(str1[str1.startIndex..<str1.index(str1.startIndex, offsetBy: index)])
}
解法二：纵向查找
纵向查找是指从前往后遍历一切字符串的每一列，比较相同列上的字符是否相同，假如相同则持续对下一列进行比较，假如不相同则当前列不再归于公共前缀，当前列之前的部分为最长公共前缀。
代码
func longestCommonPrefix(_ strs: [String]) -> String {
guard strs.count > 0 else { return "" }
var str = strs[0]
for i in 0..<str.count {
var char = str[str.index(str.startIndex, offsetBy: i)]
for j in 1..<strs.count {
let subStrs = Array(strs[j])
if i == subStrs.count || subStrs[i] != char {
return String(str[str.startIndex..<str.index(str.startIndex, offsetBy: i)])
}
}
}
return strs[0]
}
小结
字符串篇的初级算法看看你们都学会了吗？总结下来，匹配字符串、反转字符串、转化数字、找子串、寻觅前后缀等。针对不同的题型，咱们能够运用不同的方法，频率呈现较多的是双指针、哈希表。
大多时候，能够运用哈希表判别重复字符，运用双指针减少时刻复杂带来的耗时。对于依靠前项的这种数列，能够运用递归法。
字符串：双指针、哈希表、集合、递归、横向查找、纵向查找
