网站可以用什么语言开发做,软件开发工程师胜任力模型,用自己电脑做网站 dns,wordpress sql文件目录
一、1103. 分糖果 II
1.模拟
2.数学
二、312. 戳气球
1.递归-记忆化搜索
2.区间dp
三、2. 两数相加
1.迭代
2.递归-新建节点
3.递归-原节点
四、4. 寻找两个正序数组的中位数
1.堆
2.双指针二分
五、5. 最长回文子串
1.动态规划
2.中心扩展算法
六、6. Z…目录
一、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, val0, nextNone):
# 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, val0, nextNone):
# 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, val0, nextNone):
# 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
完
感谢你看到这里一起加油吧
