2024.6.10刷题记录

目录

一、881. 救生艇

贪心-排序-双指针

二、8. 字符串转换整数 (atoi)

1.模拟-未考虑溢出

2.考虑溢出问题

三、9. 回文数

1.双指针-字符串

2.数字翻转

3.数字翻转-只翻转一半

一、881. 救生艇

贪心-排序-双指针

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        # 贪心-排序-双指针
        n = len(people)
        people.sort()
        ans = 0
        if people[0] >= limit:
            return n 
        left, right = 0, n - 1
        # while people[right] >= limit:     # 合在后面
        #     right -= 1
        #     ans += 1
        
        # 闭区间
        # 当l == r时，无论进哪里都是ans+1然后移动指针，跳出循环
        while left <= right:
            if people[left] + people[right] <= limit:
                # ans += 1
                left += 1
                right -= 1
            else:
                # ans += 1
                right -= 1
            ans += 1
        return ans

二、8. 字符串转换整数 (atoi)

1.模拟-未考虑溢出

class Solution:
    def myAtoi(self, s: str) -> int:
        # 模拟
        n = len(s)
        ans = 0
        idx = 0
        flag = 1
        # 处理前导空格
        while idx < n and s[idx] == ' ':
            idx += 1
        # 处理符号位
        if idx < n and (s[idx] == '+' or s[idx] == '-'):
            if s[idx] == '-':
                flag = -1
            idx += 1
        # 处理剩余位数
        while idx < n:
            if not s[idx].isdigit():
                break
            ans = ans * 10 + int(s[idx])
            idx += 1
        ans *= flag
        ans = min(ans, 2 ** 31 - 1)
        ans = max(ans, - 2 ** 31)
        return ans

2.考虑溢出问题

来自题解（. - 力扣（LeetCode）），优雅。

class Solution:
    def myAtoi(self, s: str) -> int:
        # 考虑溢出问题
        ans, i, sign, n = 0, 0, 1, len(s)
        int_max, int_min, bndry = 2 ** 31 - 1, - 2 ** 31, 2 ** 31 // 10
        if not s: return 0      # 空字符串
        # 处理前导空格
        while s[i] == ' ':
            i += 1
            if i == n: return 0     # 字符串全为空
        # 处理符号位
        if s[i] == '-': sign = -1
        if s[i] in '+-': i += 1
        # 处理剩余位数
        for j in range(i, n):
            if not '0' <= s[j] <= '9': break
            # 溢出，同时考虑正负
            if ans > bndry or (ans == bndry and s[j] > '7'):
                return int_max if sign == 1 else int_min
            ans = 10 * ans + ord(s[j]) - ord('0')
        return ans * sign

三、9. 回文数

1.双指针-字符串

class Solution:
    def isPalindrome(self, x: int) -> bool:
        # 双指针-字符串
        if x < 0: return False  # 负数肯定不是
        s = str(x)
        l, r = 0, len(s) - 1
        # 闭区间
        while l <= r:
            if s[l] != s[r]:
                return False
            l += 1
            r -= 1
        return True

2.数字翻转

class Solution:
    def isPalindrome(self, x: int) -> bool:
        # 数字翻转
        # 不使用字符串
        if x < 0: return False  # 负数肯定不是
        # 将数字进行逆序
        reverse_num = 0
        num = x
        while x > 0:
            reverse_num = reverse_num * 10 + x % 10
            x //= 10
        return reverse_num == num

3.数字翻转-只翻转一半

来自官方题解（. - 力扣（LeetCode））。

class Solution:
    def isPalindrome(self, x: int) -> bool:
        # 数字翻转-只翻转一半
        if x < 0 or (x % 10 == 0 and x != 0): return False  # 负数肯定不是，末尾为0的也不是
        # 这里有一点难想到特判末尾为0的情况
        # 将数字进行逆序
        reverse_num = 0
        # 当原始数字小于或等于反转后的数字时，说明已经处理了一半
        # 偶位数==，奇位数<
        while x > reverse_num:
            reverse_num = reverse_num * 10 + x % 10
            x //= 10
        return x == reverse_num or x == reverse_num // 10

完

感谢你看到这里！一起加油吧！