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

2024-01-10 07:49:11

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

文章来源:https://blog.csdn.net/Jack199274/article/details/135493411
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。