目录
一、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[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] < nums2[m2 - 1]: # check
- left = m1 + 1
- else:
- right = m1 - 1
- m1 = left
- m2 = 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 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 < 2:
- return s
-
- max_len = 1
- begin = 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 = L
- j = L + i - 1
- # 右边界越界
- if j >= n:
- break
- if s[i] != s[j]:
- dp[i][j] = False
- else:
- if j - i < 3:
- dp[i][j] = True
- else:
- dp[i][j] = dp[i + 1][j - 1] # 内串是否为回文串
- # 更新
- if dp[i][j] and j - i + 1 > 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 < len(s) and s[left] == s[right]:
- 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[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
复制代码 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企服之家,中国第一个企服评测及商务社交产业平台。 |