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.模拟
class Solution:
def distributeCandies(self, candies: int, num_people: int) -> List:
# 模拟
ans = * num_people
num = 1
while candies > 0:
i = (num - 1) % num_people
ans += min(num, candies)
candies -= num
num += 1
return ans 2.数学
来自灵神题解（. - 力扣（LeetCode））。将添加利用分为“完整行”、“完整数”（最后一行中）、“不完整数”（最后一格）三个部门举行处置惩罚。
class Solution:
def distributeCandies(self, candies: int, num_people: int) -> List:
# 数学
# 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 += candies - m * (m + 1) // 2
return ans 二、312. 戳气球
1.递归-记忆化搜索
来自官方题解（. - 力扣（LeetCode））。
class Solution:
def maxCoins(self, nums: List) -> int:
# 递归-记忆化搜索
# 逆向思维，将搓破气球改为放入气球
n = len(nums)
val = + nums +
@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 * val * val
# 在区间内放入一个，左右都是固定的
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:
# 区间dp
# 使用二维数组表示区间
n = len(nums)
dp = [ * (n + 2) for _ in range(n + 2)]
val = + nums +
# 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 * val * val
total += dp + dp
dp = max(dp, total)
return dp 三、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, l2: Optional) -> Optional:
# 迭代
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, l2: Optional) -> Optional:
# 递归-新建节点
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, l2: Optional, carry = 0) -> Optional:
# 递归-原节点
# 均在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, nums2: List) -> 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, nums2: List) -> 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 < nums2: # check
left = m1 + 1
else:
right = m1 - 1
m1 = left
m2 = k - m1
# 左边最大值
# m1是个数，m1 - 1是下标
# 注意，划分个数是确定了，但是大小没有确定
c1 = max(nums1 if m1 > 0 else float("-inf"), nums2 if m2 > 0 else float("-inf"))
if (n1 + n2) % 2 == 1:
return c1
c2 = min(nums1 if m1 < n1 else float("inf"), nums2 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 < 2:
return s
max_len = 1
begin = 0
# dp 表示 s 是否是回文串
dp = [ * n for _ in range(n)]
# 记得初始化
for i in range(n):
# 长度为1是回文
dp = True
# 递推
# 先枚举子串长度，从小到大
for L in range(2, n + 1):
# 枚举左边界
for i in range(n):
# 右边界j - i + 1 = L
j = L + i - 1
# 右边界越界
if j >= n:
break
if s != s:
dp = False
else:
if j - i < 3:
dp = True
else:
dp = dp # 内串是否为回文串
# 更新
if dp and j - i + 1 > max_len:
max_len = j - i + 1
begin = i # 记录起始位置，方便返回
return s 2.中央扩展算法
class Solution:
def expandAroundCenter(self, s: str, left: int, right: int):
# 中心扩展算法
while left >= 0 and right < len(s) and s == s:
left -= 1
right += 1
return left + 1, right - 1 # 符号条件的
def longestPalindrome(self, s: str) -> 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 六、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)
# 斜线
idx = j + 2 * (numRows - 1 - row)
if idx < n:
ans.append(s)
else:
# 第一行和最后一行，重叠部分，特判
for j in range(row, n, (numRows - 1)* 2):
ans.append(s)
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 += 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 2024.6.10续：
博主重要知道错在那里了！！！
3.考虑溢出问题-正确代码
负数受取模运算的影响（负数取模为正），为正确处置惩罚，将其全部转化为正数再处置惩罚就没问题了。
class Solution:
def reverse(self, x: int) -> int:
# 考虑溢出问题
INT_MAX_VALUE = 2 ** 31 - 1
sign = 1 if x >= 0 else -1
x = abs(x)
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
ans = ans * 10 + pop
x //= 10
return ans*sign 完
感谢你看到这里！一起加油吧！
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]