2024.6.9刷题记录（6.10更新）

目录
一、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.考虑溢出问题-模拟一下（错误代码）
3.考虑溢出问题-正确代码

---

一、1103. 分糖果 II

1.模拟

1. class Solution:
2.     def distributeCandies(self, candies: int, num_people: int) -> List[int]:
3.         # 模拟
4.         ans = [0] * num_people
5.         num = 1
6.         while candies > 0:
7.             i = (num - 1) % num_people
8.             ans[i] += min(num, candies)
9.             candies -= num
10.             num += 1
11.         return ans

复制代码

2.数学

来自灵神题解（. - 力扣（LeetCode））。将添加利用分为“完整行”、“完整数”（最后一行中）、“不完整数”（最后一格）三个部门举行处置惩罚。

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

复制代码

二、312. 戳气球

1.递归-记忆化搜索

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

1. class Solution:
2.     def maxCoins(self, nums: List[int]) -> int:
3.         # 递归-记忆化搜索
4.         # 逆向思维，将搓破气球改为放入气球
5.         n = len(nums)
6.         val = [1] + nums + [1]
8.         @cache
9.         def solve(left: int, right: int) -> int:
10.             # 开区间，返回最大数量
11.             if left >= right - 1:
12.                 # 空区间
13.                 return 0
15.             best = 0
16.             for i in range(left + 1, right):
17.                 # 遍历区间值得最大值
18.                 total = val[left] * val[i] * val[right]
19.                 # 在区间内放入一个，左右都是固定的
20.                 total += solve(left, i) + solve(i, right)   # 在左右分别放入
21.                 best = max(best, total)
22.             return best
23.         
24.         return solve(0, n + 1)  # 现在是针对于val数组

复制代码

2.区间dp

来自官方题解。

1. class Solution:
2.     def maxCoins(self, nums: List[int]) -> int:
3.         # 区间dp
4.         # 使用二维数组表示区间
5.         n = len(nums)
6.         dp = [[0] * (n + 2) for _ in range(n + 2)]
7.         val = [1] + nums + [1]
9.         # dp要由小到大蔓延
10.         for i in range(n - 1, -1, -1):
11.             # 开区间, j - i > 1
12.             for j in range(i + 2, n + 2):
13.                 for k in range(i + 1, j):
14.                     total = val[i] * val[k] * val[j]
15.                     total += dp[i][k] + dp[k][j]
16.                     dp[i][j] = max(dp[i][j], total)
17.         return dp[0][n + 1]

复制代码

三、2. 两数相加

1.迭代

1. # Definition for singly-linked list.
2. # class ListNode:
3. #     def __init__(self, val=0, next=None):
4. #         self.val = val
5. #         self.next = next
6. class Solution:
7.     def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
8.         # 迭代
9.         carry = 0
10.         dummy = ListNode()
11.         cur = dummy
12.         while l1 or l2 or carry:
13.             if l1:
14.                 carry += l1.val
15.                 l1 = l1.next
16.             if l2:
17.                 carry += l2.val
18.                 l2 = l2.next
19.             cur.next = ListNode(val = carry % 10)
20.             cur = cur.next
21.             carry //= 10
22.         return dummy.next

复制代码

2.递归-新建节点

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

1. # Definition for singly-linked list.
2. # class ListNode:
3. #     def __init__(self, val=0, next=None):
4. #         self.val = val
5. #         self.next = next
6. class Solution:
7.     def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
8.         # 递归-新建节点
9.         def addTwo(l1, l2, carry = 0):
10.             if not l1 and not l2:
11.                 return ListNode(val = carry) if carry else None
12.             carry += (l1.val if l1 else 0) + (l2.val if l2 else 0)
13.             nxt = addTwo(l1.next if l1 else None, l2.next if l2 else None, carry // 10)
14.             return ListNode(val = carry % 10, next = nxt)
15.         return addTwo(l1, l2)

复制代码

3.递归-原节点

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

1. # Definition for singly-linked list.
2. # class ListNode:
3. #     def __init__(self, val=0, next=None):
4. #         self.val = val
5. #         self.next = next
6. class Solution:
7.     def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode], carry = 0) -> Optional[ListNode]:
8.         # 递归-原节点
9.         # 均在l1表的基础上修改
10.         if not l1 and not l2:
11.             # 这里是关键，一定还得记得None
12.             return ListNode(val = carry) if carry else None
13.         if not l1:
14.             l1, l2 = l2, l1
15.         carry += l1.val + (l2.val if l2 else 0)
16.         l1.val = carry % 10
17.         l1.next = self.addTwoNumbers(l1.next, l2.next if l2 else None, carry // 10)
18.         return l1

复制代码

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

1.堆

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

1. class Solution:
2.     def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
3.         # 堆
4.         # 时复O(m + n), 空复O(m + n)
5.         m, n = len(nums1), len(nums2)
6.         q = nums1 + nums2
7.         heapq.heapify(q)    # 原地堆化
8.         for _ in range((m + n - 1) // 2):
9.             heapq.heappop(q)
10.         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））。题解作者使用的是左闭右开区间，博主本人二分习惯使用闭区间，所以改为了闭区间写法。

1. class Solution:
2.     def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
3.         # 双指针+二分
4.         # 时复O(log(min(m,n)))，空复O(1)
5.         n1 = len(nums1)
6.         n2 = len(nums2)
7.         if n1 > n2:
8.             # 使查找较短数组
9.             return self.findMedianSortedArrays(nums2, nums1)
10.         k = (n1 + n2 + 1) // 2
11.         left = 0
12.         right = n1 - 1
13.         # 二分留在左边的nums1的个数
14.         while left <= right:
15.             # 闭区间
16.             m1 = (left + right) // 2
17.             m2 = k - m1     # 留在左边的nums2的个数
18.             # 当nums2划分多了的时候，左边的nums2最后一位是大于右边nums1的第一位
19.             if nums1[m1] < nums2[m2 - 1]:   # check
20.                 left = m1 + 1
21.             else:
22.                 right = m1 - 1
23.         m1 = left
24.         m2 = k - m1
25.         # 左边最大值
26.         # m1是个数，m1 - 1是下标
27.         # 注意，划分个数是确定了，但是大小没有确定
28.         c1 = max(nums1[m1 - 1] if m1 > 0 else float("-inf"), nums2[m2 - 1] if m2 > 0 else float("-inf"))
29.         if (n1 + n2) % 2 == 1:
30.             return c1
31.         c2 = min(nums1[m1] if m1 < n1 else float("inf"), nums2[m2] if m2 < n2 else float("inf"))
32.         return (c1 + c2) / 2

复制代码

五、5. 最长回文子串

不会，均来自官方题解（. - 力扣（LeetCode））。
1.动态规划

1. class Solution:
2.     def longestPalindrome(self, s: str) -> str:
3.         # 动态规划
4.         n = len(s)
5.         if n < 2:
6.             return s
7.         
8.         max_len = 1
9.         begin = 0
10.         
11.         # dp[i][j] 表示 s[i..j] 是否是回文串
12.         dp = [[False] * n for _ in range(n)]
13.         # 记得初始化
14.         for i in range(n):
15.             # 长度为1是回文
16.             dp[i][i] = True
18.         # 递推
19.         # 先枚举子串长度，从小到大
20.         for L in range(2, n + 1):
21.             # 枚举左边界
22.             for i in range(n):
23.                 # 右边界j - i + 1 = L
24.                 j = L + i - 1
25.                 # 右边界越界
26.                 if j >= n:
27.                     break
29.                 if s[i] != s[j]:
30.                     dp[i][j] = False
31.                 else:
32.                     if j - i < 3:
33.                         dp[i][j] = True
34.                     else:
35.                         dp[i][j] = dp[i + 1][j - 1]     # 内串是否为回文串
37.                 # 更新
38.                 if dp[i][j] and j - i + 1 > max_len:
39.                     max_len = j - i + 1
40.                     begin = i   # 记录起始位置，方便返回
41.         return s[begin: begin + max_len]

复制代码

2.中央扩展算法

1. class Solution:
2.     def expandAroundCenter(self, s: str, left: int, right: int):
3.         # 中心扩展算法
4.         while left >= 0 and right < len(s) and s[left] == s[right]:
5.             left -= 1
6.             right += 1
7.         return left + 1, right - 1      # 符号条件的
9.     def longestPalindrome(self, s: str) -> str:
10.         # 中心扩展算法
11.         start, end = 0, 0
12.         for i in range(len(s)):
13.             # 边界条件1，初始中心串长度为1
14.             left1, right1 = self.expandAroundCenter(s, i, i)
15.             # 边界条件2，初始中心串长度为2
16.             left2, right2 = self.expandAroundCenter(s, i, i + 1)
17.             if right1 - left1 > end - start:
18.                 start, end = left1, right1
19.             if right2 - left2 > end - start:
20.                 start, end = left2, right2
21.         return s[start: end + 1]

复制代码

六、6. Z 字形变更

1.模拟-规律

1. class Solution:
2.     def convert(self, s: str, numRows: int) -> str:
3.         # 模拟-规律
4.         # 将每一条竖线（斜线）分开看
5.         # 第一行和最后一行为重叠部分
6.         if numRows == 1:
7.             return s
8.         ans = []
9.         n = len(s)
10.         for row in range(numRows):
11.             if row != 0 and row != numRows - 1:
12.                 # 普通竖线（斜线）
13.                 for j in range(row, n, (numRows - 1)* 2):
14.                     # 竖线
15.                     ans.append(s[j])
16.                     # 斜线
17.                     idx = j + 2 * (numRows - 1 - row)
18.                     if idx < n:
19.                         ans.append(s[idx])
20.             else:
21.                 # 第一行和最后一行，重叠部分，特判
22.                 for j in range(row, n, (numRows - 1)* 2):
23.                     ans.append(s[j])
24.         return ''.join(ans)

复制代码

2.巧设flag

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

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

复制代码

七、7. 整数反转

1.模拟

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

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

复制代码

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

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

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

复制代码

2024.6.10续：
博主重要知道错在那里了！！！
3.考虑溢出问题-正确代码

负数受取模运算的影响（负数取模为正），为正确处置惩罚，将其全部转化为正数再处置惩罚就没问题了。

1. class Solution:
2.     def reverse(self, x: int) -> int:
3.         # 考虑溢出问题
4.         INT_MAX_VALUE = 2 ** 31 - 1
5.         sign = 1 if x >= 0 else -1
6.         x = abs(x)
7.         
8.         ans = 0
9.         while x > 0:
10.             pop = x % 10
11.             if ans > INT_MAX_VALUE // 10 or (ans == INT_MAX_VALUE // 10 and pop > 7):
12.                 return 0
13.             ans = ans * 10 + pop
14.             x //= 10
15.         return ans*sign

复制代码

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

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。