Grind75第5天 | 409.最长回文串、3.无重复字符的最长子串、8.字符串转换整数

409.最长回文串

题目链接：https://leetcode.com/problems/longest-palindrome

解法：

我们发现，回文串如果是偶数长度，那么所有字符的个数为偶数个，回文串如果是奇数长度，那么除了中间的子串为一个奇数长度的单字符外，其他字符都是偶数个。

那么对字符串中的每个字符都统计个数，然后进行遍历：

• 如果某个字符的个数为偶数，那么直接可以作为回文串的一部分；
• 如果好几个字符的个数都为奇数（个数 > 1），那么每个字符的个数都先移除掉一个，就都可以作为回文串的一部分了，再把最后一个遍历到的字符填入回文串中间即可。

参考题解：最长回文串

边界条件：无

时间复杂度：O(n)

空间复杂度：O(1)，因为字符串只包含大写和小写字母，所以hashmap的空间为常数空间。

class Solution:
    def longestPalindrome(self, s: str) -> int:
        count = dict()
        for c in s:
            count[c] = count.get(c, 0) + 1
        
        even = 0
        odd = 0
        for v in count.values():
            # 如果是奇数，则移除一个字符变成偶数，先构造为回文串
            if v % 2:
                even += v - 1
                odd = 1
            else:
                even += v
        # 奇数的字符可能有多个，但最后只拿一个填入字符串中间
        return even + odd

3.无重复字符的最长子串

题目链接：https://leetcode.com/problems/longest-substring-without-repeating-characters

解法：

这道题用滑动窗口，代码量不大，但是中间的思维链还比较长，需要用具体的例子才能理解一些关键步骤。

其中，最关键的是更新左指针：left = max(left, pos[c]+1)。

看题解即可，参考题解：无重复字符的最长子串

边界条件：无

时间复杂度：O(n)

空间复杂度：O(128)，本题中没有明确说明字符集，因此可以默认为所有 ASCII 码在?[0,128)?内的字符

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # 记录每个字符的索引位置
        pos = {}
        left = 0
        max_len = 0
        for i in range(len(s)):
            c = s[i]
            if c in pos:
                left = max(left, pos[c]+1)
            pos[c] = i
            # 等left更新后，再更新最大长度
            max_len = max(max_len, i - left + 1)
        return max_len

8.字符串转换整数

题目链接：https://leetcode.com/problems/string-to-integer-atoi

解法：

这个题去除空格、取正负号的操作算是比较常规，没有什么技巧。

关键在于数字不能溢出，即范围在 [-2**31, 2**31-1]，如果溢出需要截断。那么如果乘以10要溢出了，那么在这之前就要预先判断，进行截断。

容易错的地方是，python对负数求商和余数时，得到的结果非常反常识，比如 divmod(-128, 10) 得到的是 -13 和 2，这个结果与 -128 // 10, -128 % 10 得到的是一样的。因此判断是否溢出负数范围时，需要特殊处理，商也不是简单的加1，因为 -130 // 10 = -13。那么可以用 (INT_MIN + 8) // 10 来得到向零取整的商。

为了把这个问题简化，也可以先把这个整数看成是正的，用 INT_MAX 去判断是否越界，最后返回结果时再乘以正负号。具体实现看代码。

参考题解：字符串转换整数

边界条件：无

时间复杂度：O(n)

空间复杂度：O(1)

class Solution:
    def myAtoi(self, s: str) -> int:
        INT_MAX = 2 ** 31 - 1
        INT_MIN = - 2 ** 31
        i, length = 0, len(s)

        # 1.去掉空格
        while i < length and s[i] == ' ':
            i += 1
        
        if i == length:
            return 0
        
        # 2.记录正号或负号
        sign = 1
        # 如果不是正负号，就不用操作
        if s[i] == '-':
            sign = -1
            i += 1
        elif s[i] == '+':
            i += 1
        
        # 3. 对字符转换位数字
        res = 0
        while i < length:
            if not s[i].isdigit():
                break
            
            digit = int(s[i])
            
            # 提前预判是否在乘以10以后会越界
            if res > INT_MAX // 10 or (res == INT_MAX // 10 and digit > 7):
                return INT_MAX
            # 在Python中，整数除法 // 的行为是向下取整, -128 // 10 得到是-13
            if res < (INT_MIN + 8) // 10 or (res == (INT_MIN + 8) // 10 and digit > 8):
                return INT_MIN

            res = res * 10 + sign * digit
            i += 1

        return res

class Solution:
    def myAtoi(self, s: str) -> int:
        INT_MAX = 2 ** 31 - 1
        INT_MIN = - 2 ** 31
        i, length = 0, len(s)

        # 1.去掉空格
        while i < length and s[i] == ' ':
            i += 1
        
        if i == length:
            return 0
        
        # 2.记录正号或负号
        sign = 1
        # 如果不是正负号，就不用操作
        if s[i] == '-':
            sign = -1
            i += 1
        elif s[i] == '+':
            i += 1
        
        # 3. 对字符转换位数字
        res = 0
        while i < length:
            if not s[i].isdigit():
                break
            
            digit = int(s[i])
            # 考虑到负数的时候不好处理，可以同一先当做正数处理
            if res > (INT_MAX - digit) // 10:
                return INT_MAX if sign == 1 else INT_MIN

            res = res * 10 + digit
            i += 1

        return sign * res