共计 2217 个字符，预计需要花费 6 分钟才能阅读完成。
第一题 验证回文串
题目信息
给定一个字符串，验证它是否是回文串，只思考字母和数字字符，能够疏忽字母的大小写。
阐明：本题中，咱们将空字符串定义为无效的回文串。
示例 1:
输出: “A man, a plan, a canal: Panama”
输入: true
解释：”amanaplanacanalpanama” 是回文串
示例 2:
输出: “race a car”
输入: false
解释：”raceacar” 不是回文串
提醒：
1 <= s.length <= 2 * 105
字符串 s 由 ASCII 字符组成
解题思路
依据示例显然，验证是否是回文串之前，因为
只思考字母和数字字符，能够疏忽字母的大小写所以对于给定的字符串，咱们应该
提取出字符串中属于字符和数字的局部
疏忽其余的符号而后咱们只需验证提取出的字符串是否是回文串就行了
代码
func isPalindrome(s string) bool {if len(s)==1{return true}
var ss []byte
for i, n := range s {
if n <= 'Z' && n >= 'A' {ss = append(ss, s[i]+32)
}
if n >= 'a' && n <= 'z' || n >= '0' && n <= '9' {ss = append(ss, s[i])
}
}
if ss==nil {return true}
for i := 0; i <= len(ss)/2; i++ {if ss[i] != ss[len(ss)-i-1] {return false}
}
return true
}复杂度剖析
工夫复杂度：O(∣s∣)，其中 ∣s∣ 是字符串 ss 的长度。
空间复杂度：O(∣s∣)。因为咱们须要将所有的字母和数字字符寄存在另一个字符串中，在最坏状况下，新的字符串与原字符串 s 完全相同，因而须要应用 O(∣s∣) 的空间。
优化
借鉴官网解析第二个办法
能够应用双指针间接在原数组上进行操作，将空间复杂度优化为常数级别
代码如下
func isPalindrome(s string) bool {s = strings.ToLower(s)
left, right := 0, len(s) - 1
for left < right {for left < right && !isalnum(s[left]) {left++}
for left < right && !isalnum(s[right]) {right--}
if left < right {if s[left] != s[right] {return false}
left++
right--
}
}
return true
}
func isalnum(ch byte) bool {return (ch >= 'A' && ch <= 'Z') || (ch >= 'a' && ch <= 'z') || (ch >= '0' && ch <= '9')
}
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/valid-palindrome/solution/yan-zheng-hui-wen-chuan-by-leetcode-solution/
起源：力扣（LeetCode）著作权归作者所有。商业转载请分割作者取得受权，非商业转载请注明出处。第二题
题目信息
请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（相似 C/C++ 中的 atoi 函数）。
函数 myAtoi(string s) 的算法如下：
读入字符串并抛弃无用的前导空格
查看下一个字符（假如还未到字符开端）为正还是负号，读取该字符（如果有）。确定最终后果是正数还是负数。如果两者都不存在，则假设后果为正。
读入下一个字符，直到达到下一个非数字字符或达到输出的结尾。字符串的其余部分将被疏忽。
将后面步骤读入的这些数字转换为整数（即，”123″ -> 123，“0032” -> 32）。如果没有读入数字，则整数为 0。必要时更改符号（从步骤 2 开始）。
如果整数数超过 32 位有符号整数范畴 [−231, 231 − 1]，须要截断这个整数，使其放弃在这个范畴内。具体来说，小于 −231 的整数应该被固定为 −231，大于 231 − 1 的整数应该被固定为 231 − 1。
返回整数作为最终后果。
留神：
本题中的空白字符只包含空格字符 ‘ ‘。
除前导空格或数字后的其余字符串外，请勿疏忽 任何其余字符。
解题思路
1，须要去掉前导空格；
2，须要判断第 1 个字符为 + 和 – 的状况，因而，能够设计一个变量 sign，初始化的时候为 1，如果遇到 –，将 sign 修改为 -1；
3，判断是否是数字，能够应用字符的 ASCII 码数值进行比拟，即 0 <= c <= ‘9’；
4，在遇到第 1 个不是数字的字符的状况下，转换进行，退出循环；
5，如果转换当前的数字超过了 int 类型的范畴，须要截取。
代码
func myAtoi(s string) int {num, sign, i, n := 0, 1, 0, len(s)
for i < n && s[i] == ' ' {i++}
if i < n {if s[i] == '-' {
sign = -1
i++
} else if s[i] == '+' {
sign = 1
i++
}
}
for i < n && s[i] >= '0' && s[i] <= '9' {num = 10*num + int(s[i]-'0')
if sign*num < math.MinInt32 {return math.MinInt32} else if sign*num > math.MaxInt32 {return math.MaxInt32}
i++
}
return sign * num
}
复杂度剖析
工夫复杂度：O（n）
空间复杂度：O（1）
