2024.6.9刷题记录

目录

一、1103. 分糖果 II

1.模拟

2.数学

二、312. 戳气球

1.递归-记忆化搜索

2.区间dp

三、2. 两数相加

1.迭代

2.递归-新建节点

3.递归-原节点

四、4. 寻找两个正序数组的中位数

1.堆

2.双指针+二分

五、5. 最长回文子串

1.动态规划

2.中心扩展算法

六、6. Z 字形变换

1.模拟-规律

2.巧设flag

七、7. 整数反转

1.模拟

2.考虑溢出问题-模拟一下（错误代码）

一、1103. 分糖果 II

1.模拟

class Solution:
    def distributeCandies(self, candies: int, num_people: int) -> List[int]:
        # 模拟
        ans = [0] * num_people
        num = 1
        while candies > 0:
            i = (num - 1) % num_people
            ans[i] += min(num, candies)
            candies -= num
            num += 1
        return ans

2.数学

来自灵神题解（. – 力扣（LeetCode））。将添加操作分为“完整行”、“完整数”（最后一行中）、“不完整数”（最后一格）三个部分进行处理。

class Solution:
    def distributeCandies(self, candies: int, num_people: int) -> List[int]:
        # 数学
        # m = sqrt(8 * candies + 1) - 1) // 2  # 是错误的，当被除数为浮点数时，整除结果还是为浮点数
        m = int((sqrt(8 * candies + 1) - 1) / 2)  # 前面完整的项数
        k, extra = divmod(m, num_people)
        ans = [(k - 1) * k * num_people // 2 + k * (i + 1) + \
                (k * num_people + i + 1 if i < extra else 0) \
                for i in range(num_people)]
        ans[extra] += candies - m * (m + 1) // 2
        return ans

二、312. 戳气球

1.递归-记忆化搜索

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

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        # 递归-记忆化搜索
        # 逆向思维，将搓破气球改为放入气球
        n = len(nums)
        val = [1] + nums + [1]

        @cache
        def solve(left: int, right: int) -> int:
            # 开区间，返回最大数量
            if left >= right - 1:
                # 空区间
                return 0

            best = 0
            for i in range(left + 1, right):
                # 遍历区间值得最大值
                total = val[left] * val[i] * val[right]
                # 在区间内放入一个，左右都是固定的
                total += solve(left, i) + solve(i, right)   # 在左右分别放入
                best = max(best, total)
            return best
        
        return solve(0, n + 1)  # 现在是针对于val数组

2.区间dp

来自官方题解。

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        # 区间dp
        # 使用二维数组表示区间
        n = len(nums)
        dp = [[0] * (n + 2) for _ in range(n + 2)]
        val = [1] + nums + [1]

        # dp要由小到大蔓延
        for i in range(n - 1, -1, -1):
            # 开区间, j - i > 1
            for j in range(i + 2, n + 2):
                for k in range(i + 1, j):
                    total = val[i] * val[k] * val[j]
                    total += dp[i][k] + dp[k][j]
                    dp[i][j] = max(dp[i][j], total)
        return dp[0][n + 1]

三、2. 两数相加

1.迭代

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        # 迭代
        carry = 0
        dummy = ListNode()
        cur = dummy
        while l1 or l2 or carry:
            if l1: 
                carry += l1.val
                l1 = l1.next
            if l2:
                carry += l2.val
                l2 = l2.next
            cur.next = ListNode(val = carry % 10)
            cur = cur.next
            carry //= 10
        return dummy.next

2.递归-新建节点

判断边界的时候只想着有carry的情况，而没有返回无carry的情况（None）导致运行超时，修改后运行通过。我当时还以为我递归写错了，参考了灵神的递归才发现问题。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        # 递归-新建节点
        def addTwo(l1, l2, carry = 0):
            if not l1 and not l2:
                return ListNode(val = carry) if carry else None
            carry += (l1.val if l1 else 0) + (l2.val if l2 else 0)
            nxt = addTwo(l1.next if l1 else None, l2.next if l2 else None, carry // 10)
            return ListNode(val = carry % 10, next = nxt)
        return addTwo(l1, l2)

3.递归-原节点

来自灵神题解（. – 力扣（LeetCode））。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode], carry = 0) -> Optional[ListNode]:
        # 递归-原节点
        # 均在l1表的基础上修改
        if not l1 and not l2:
            # 这里是关键，一定还得记得None
            return ListNode(val = carry) if carry else None
        if not l1:
            l1, l2 = l2, l1
        carry += l1.val + (l2.val if l2 else 0)
        l1.val = carry % 10
        l1.next = self.addTwoNumbers(l1.next, l2.next if l2 else None, carry // 10)
        return l1

四、4. 寻找两个正序数组的中位数

1.堆

时复O(m + n), 空复O(m + n)。但是堆没有运用到本身已经有序的这一特点。

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        # 堆
        # 时复O(m + n), 空复O(m + n)
        m, n = len(nums1), len(nums2)
        q = nums1 + nums2
        heapq.heapify(q)    # 原地堆化
        for _ in range((m + n - 1) // 2):
            heapq.heappop(q)
        return (heapq.heappop(q) + heapq.heappop(q)) / 2 if (m + n) % 2 == 0 else heapq.heappop(q)

2.双指针+二分

时复O(log(min(m,n)))，空复O(1)。来自题解（. – 力扣（LeetCode））。题解作者使用的是左闭右开区间，博主本人二分习惯使用闭区间，所以改为了闭区间写法。

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        # 双指针+二分
        # 时复O(log(min(m,n)))，空复O(1)
        n1 = len(nums1)
        n2 = len(nums2)
        if n1 > n2:
            # 使查找较短数组
            return self.findMedianSortedArrays(nums2, nums1)
        k = (n1 + n2 + 1) // 2
        left = 0
        right = n1 - 1
        # 二分留在左边的nums1的个数
        while left <= right:
            # 闭区间
            m1 = (left + right) // 2
            m2 = k - m1     # 留在左边的nums2的个数
            # 当nums2划分多了的时候，左边的nums2最后一位是大于右边nums1的第一位
            if nums1[m1]  0 else float("-inf"), nums2[m2 - 1] if m2 > 0 else float("-inf"))
        if (n1 + n2) % 2 == 1:
            return c1
        c2 = min(nums1[m1] if m1 < n1 else float("inf"), nums2[m2] if m2 < n2 else float("inf"))
        return (c1 + c2) / 2

五、5. 最长回文子串

不会，均来自官方题解（. – 力扣（LeetCode））。

1.动态规划

class Solution:
    def longestPalindrome(self, s: str) -> str:
        # 动态规划
        n = len(s)
        if n = n:
                    break

                if s[i] != s[j]:
                    dp[i][j] = False
                else:
                    if j - i  max_len:
                    max_len = j - i + 1
                    begin = i   # 记录起始位置，方便返回
        return s[begin: begin + max_len]

2.中心扩展算法

class Solution:
    def expandAroundCenter(self, s: str, left: int, right: int):
        # 中心扩展算法
        while left >= 0 and right  str:
        # 中心扩展算法
        start, end = 0, 0
        for i in range(len(s)):
            # 边界条件1，初始中心串长度为1
            left1, right1 = self.expandAroundCenter(s, i, i)
            # 边界条件2，初始中心串长度为2
            left2, right2 = self.expandAroundCenter(s, i, i + 1)
            if right1 - left1 > end - start:
                start, end = left1, right1
            if right2 - left2 > end - start:
                start, end = left2, right2
        return s[start: end + 1]

六、6. Z 字形变换

1.模拟-规律

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        # 模拟-规律
        # 将每一条竖线（斜线）分开看
        # 第一行和最后一行为重叠部分
        if numRows == 1:
            return s
        ans = []
        n = len(s)
        for row in range(numRows):
            if row != 0 and row != numRows - 1:
                # 普通竖线（斜线）
                for j in range(row, n, (numRows - 1)* 2):
                    # 竖线
                    ans.append(s[j])
                    # 斜线
                    idx = j + 2 * (numRows - 1 - row)
                    if idx < n:
                        ans.append(s[idx])
            else:
                # 第一行和最后一行，重叠部分，特判
                for j in range(row, n, (numRows - 1)* 2):
                    ans.append(s[j])
        return ''.join(ans)

2.巧设flag

来自题解（. – 力扣（LeetCode））。很妙！

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        # 巧设flag
        # 行数先增后减，使用flag模拟
        if numRows < 2:
            return s
        ans = ["" for _ in range(numRows)]
        i, flag = 0, -1     # flag代表增减i
        for c in s:
            ans[i] += c
            # 边界处转换
            if i == 0 or i == numRows - 1: flag = -flag
            i += flag
        return ''.join(ans)

七、7. 整数反转

1.模拟

python一般不会出现溢出的问题，所以实际上并没有受到限制，题主也就并没有答到考点。

class Solution:
    def reverse(self, x: int) -> int:
        # 模拟
        x, flag = (x, 1) if x >= 0 else (-x, -1)
        ans = 0
        while x > 0:
            ans *= 10   # 进位
            ans += x % 10
            x //= 10
        return flag * ans if - 2 ** 31 <= flag * ans <= 2 ** 31 - 1 else 0

2.考虑溢出问题-模拟一下（错误代码）

来自题解（. – 力扣（LeetCode）），讲解非常通俗易懂。虽然python不用考虑，但是还是应该学习一下。

class Solution:
    def reverse(self, x: int) -> int:
        # 考虑溢出问题-模拟一下（错误代码）
        # 由于python的自动转换机制，并不能实现
        # 该代码是运行错误的
        INT_MAX_VALUE = 2 * 31 - 1      # 错误问题出在这里
        INT_MIN_VALUE = - 2 ** 31
        ans = 0
        while x != 0:
            pop = x % 10
            if ans > INT_MAX_VALUE // 10 or (ans == INT_MAX_VALUE // 10 and pop > 7):
                return 0
            if ans < INT_MIN_VALUE // 10 or (ans == INT_MIN_VALUE // 10 and pop < -8):
                return 0
            ans = ans * 10 + pop
            x //= 10
        return ans

完

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