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_peoplenum = 1while candies > 0:i = (num - 1) % num_peopleans[i] += min(num, candies)candies -= numnum += 1return 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) // 2return ans

二、312. 戳气球

1.递归-记忆化搜索

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

class Solution:def maxCoins(self, nums: List[int]) -> int:# 递归-记忆化搜索# 逆向思维，将搓破气球改为放入气球n = len(nums)val = [1] + nums + [1]@cachedef solve(left: int, right: int) -> int:# 开区间，返回最大数量if left >= right - 1:# 空区间return 0best = 0for 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 bestreturn 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 > 1for 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 = 0dummy = ListNode()cur = dummywhile l1 or l2 or carry:if l1: carry += l1.vall1 = l1.nextif l2:carry += l2.vall2 = l2.nextcur.next = ListNode(val = carry % 10)cur = cur.nextcarry //= 10return 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 Nonecarry += (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:# 这里是关键，一定还得记得Nonereturn ListNode(val = carry) if carry else Noneif not l1:l1, l2 = l2, l1carry += l1.val + (l2.val if l2 else 0)l1.val = carry % 10l1.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 + nums2heapq.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) // 2left = 0right = n1 - 1# 二分留在左边的nums1的个数while left <= right:# 闭区间m1 = (left + right) // 2m2 = k - m1     # 留在左边的nums2的个数# 当nums2划分多了的时候，左边的nums2最后一位是大于右边nums1的第一位if nums1[m1] < nums2[m2 - 1]:   # checkleft = m1 + 1else:right = m1 - 1m1 = leftm2 = k - m1# 左边最大值# m1是个数，m1 - 1是下标# 注意，划分个数是确定了，但是大小没有确定c1 = max(nums1[m1 - 1] if m1 > 0 else float("-inf"), nums2[m2 - 1] if m2 > 0 else float("-inf"))if (n1 + n2) % 2 == 1:return c1c2 = 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 < 2:return smax_len = 1begin = 0# dp[i][j] 表示 s[i..j] 是否是回文串dp = [[False] * n for _ in range(n)]# 记得初始化for i in range(n):# 长度为1是回文dp[i][i] = True# 递推# 先枚举子串长度，从小到大for L in range(2, n + 1):# 枚举左边界for i in range(n):# 右边界j - i + 1 = Lj = L + i - 1# 右边界越界if j >= n:breakif s[i] != s[j]:dp[i][j] = Falseelse:if j - i < 3:dp[i][j] = Trueelse:dp[i][j] = dp[i + 1][j - 1]     # 内串是否为回文串# 更新if dp[i][j] and j - i + 1 > max_len:max_len = j - i + 1begin = i   # 记录起始位置，方便返回return s[begin: begin + max_len]

2.中心扩展算法

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

六、6. Z 字形变换

1.模拟-规律

class Solution:def convert(self, s: str, numRows: int) -> str:# 模拟-规律# 将每一条竖线（斜线）分开看# 第一行和最后一行为重叠部分if numRows == 1:return sans = []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 sans = ["" for _ in range(numRows)]i, flag = 0, -1     # flag代表增减ifor c in s:ans[i] += c# 边界处转换if i == 0 or i == numRows - 1: flag = -flagi += flagreturn ''.join(ans)

七、7. 整数反转

1.模拟

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

class Solution:def reverse(self, x: int) -> int:# 模拟x, flag = (x, 1) if x >= 0 else (-x, -1)ans = 0while x > 0:ans *= 10   # 进位ans += x % 10x //= 10return 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 ** 31ans = 0while x != 0:pop = x % 10if ans > INT_MAX_VALUE // 10 or (ans == INT_MAX_VALUE // 10 and pop > 7):return 0if ans < INT_MIN_VALUE // 10 or (ans == INT_MIN_VALUE // 10 and pop < -8):return 0ans = ans * 10 + popx //= 10return ans

完

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