热门标签
热门文章
- 1免费的 AI 视频生成工具 Moonvalley 厉害了！Moonvalley 怎么用（保姆级教程）_aigc视频生成工具
- 2后端架构师必知必会系列：代码质量与持续集成
- 3pta 习题集 5-2 找出不是两个数组共有的元素 (5分)
- 4【转】需要写英文简历的看过来，各种奖学金、社团、证书、竞赛奖项中英文对照，肯定用的上！！！_知行优秀奖学金 英文
- 5arm cortex-m架构 SVC指令详解以及SVC异常在freertos的应用_单片机 svc
- 6超简单白话文机器学习 - 支持向量机SVM（含算法讲解，公式全解，手写代码实现，调包实现）_支持向量机(svm)
- 7虚拟化技术——cpu虚拟化_硬件辅助虚拟化
- 8红黑树(一)之 原理和算法详细介绍
- 9二叉树系列
- 10resnet系列在imagenet上预训练的pytorch模型下载地址_resnet 18 权重下载
当前位置: article > 正文
leecode100题（自用）
作者：笔触狂放9 | 2024-06-07 11:42:27
赞
踩
code100题
每日刷题
- 简单题
- 中等题
- 2.两数相加
- 3.无重复字符的最长子串
- 5.最长回文子串
- 11.盛最多水的容器
- 15.三数之和
- 17.电话号码的字母组合
- 19.删除链表的倒数第n个结点
- 22.括号生成
- 31.下一个排列
- 33.搜索旋转排序数组
- 34.在排序数组中查找元素的第一个和最后一个位置
- 39.组合总和
- 46.全排列
- 48.旋转图像
- 49.字母异位词分组
- 55.跳跃游戏
- 56.合并区间
- 62.不同路径
- 64.最小路径和
- 75.颜色分类
- 78.子集
- 79.单词搜索
- 96.不同的二叉搜索树
- 98.验证二叉搜索树
- 102.二叉树的层序遍历
- 105.从前序与中序遍历序列构造二叉树
- 114.二叉树展开为链表
- 128.最长连续序列
- 139.单词拆分
- 142.环形链表2
- 146.LRU缓存
- 148.排序链表(分治法)
- 152.乘积最大子数组
- 198.打家劫舍
- 200.岛屿数量
- 207.课程表
- 208实现Trie（前缀树）
- 215.数组中的第K个最大元素
- 221.最大正方形
- 236.二叉树的最近公共祖先
- 238.除自身以外数组的乘积
- 240.搜索二维矩阵2
- 279.完全平方数
- 标题287.寻找重复数
- 300.最长递归子序列
- 309.最佳买卖股票时机含冷冻期
- 322.零钱兑换
- 337.打家劫舍3
- 347.前k个高频元素
刷题模板
背包问题
背包问题大体的解题模板是两层循环，分别遍历物品nums和背包容量
target，然后写转移方程， 根据背包的分类我们确定物品和容量遍历的先后顺序，根据问题的分类我们确定状态转移方程的写法首先是背包分类的模板：
1、0/1背包：外循环nums,内循环target,target倒序且target>=nums[i];
2、完全背包：外循环nums,内循环target,target正序且target>=nums[i];
3、组合背包(考虑顺序)：外循环target,内循环nums,target正序且target>=nums[i];
4、分组背包：这个比较特殊，需要三重循环：外循环背包bags,内部两层循环根据题目的要求转化为1,2,3三种背包类型的模板然后是问题分类的模板：
1、最值问题: dp[i] = max/min(dp[i], dp[i-nums]+1)或dp[i] = max/min(dp[i], dp[i-num]+nums);
2、存在问题(bool)：dp[i]=dp[i]||dp[i-num];
3、组合问题：dp[i]+=dp[i-num];
简单题
1.两数之和
#暴力枚举方法 先从列表中找到其中一个，再找到另外一个使之两个的和等于目标值，需要重复遍历两次，时间复杂度为n^2,空间复杂度为1 class Solution: def twoSum(self, nums，target): n = len(nums) for i in range(n): for j in range(i + 1,n): if nums[i] + nums[j] == target: return i,j #哈希表 #创建一个哈希表，对于每一个x，我们首先查询哈希表中是否存在target-x，然后将x插入到哈希表中，即可保证不会让x和自己匹配，时间复杂度n，空间复杂度n class Solution: def twoSum(self,nums,target): hashtable = dict() for i,num in enumerate(nums): #enumerate 用于遍历，同时列出数据和数据下标 if target - num in hashtable: return [hashtable[target - num],i] hashtable[nums[i]] = i return []
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
2.两数相加
#单向链表，模拟加法进位操作 class Solution: def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode: # 初始化个位节点，先不做进位 newPoint = ListNode(l1.val + l2.val) # rt用来作为最后return的节点，tp用来遍历节点 rt, tp = newPoint, newPoint # l1,l2只要后面还有节点，就继续往后遍历；或者新链表还需要继续往后进位 while (l1 and (l1.next != None)) or (l2 and (l2.next != None)) or (tp.val > 9): l1, l2 = l1.next if l1 else l1, l2.next if l2 else l2 tmpsum = (l1.val if l1 else 0) + (l2.val if l2 else 0) # 计算新链表下个节点的值（当前节点的进位+当前l1 l2的值之和），先不做进位 tp.next = ListNode(tp.val//10 + tmpsum) # 新链表当前节点的值取个位 tp.val %= 10 # 新链表往后便利一个节点 tp = tp.next return rt
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
70.爬楼梯（动态规划）
第n个台阶只能从第n-1或者第n-2个上来，到第n-1个台阶的走法+第n-2个台阶的走法=到第n个台阶的走法，已经知道了第1个和第2个台阶的走法，一路加上去
class Solution：
def climbstairs(self,n):
if n==1 or n==2:
return n
a = 1
b = 2 #a表示第n-1个台阶的走法，b表示第n-2个台阶的走法，传统迭代
count = 0
for i in range(3,n+1):
count = a + b #累加结果
#向下迭代
a = b #下次迭代的第n-2个台阶的走法等于上次迭代的n-1个台阶的走法
b = count #下次迭代的第n-1个台阶的走法等于上次迭代的第n个台阶走法
return count
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
94.二叉树的中序遍历
二叉树的中序遍历就是首先遍历左子树，然后访问当前节点，最后遍历右子树。
#递归做法：递归遍历左子树，访问根节点，递归遍历右子树 #非递归过程：先访问..最左子树..结点，再访问其父节点，再访问其兄弟 #中序遍历不忘“左链入栈” # Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None #迭代法 #https://www.bilibili.com/video/BV11P4y1L7in?from=search&seid=13963080210323760588&spm_id_from=333.337.0.0 class Solution: def inorderTraversal(self, root: TreeNode) -> List[int]: stack,ret = [],[] #创建空栈和结果集 cur = root #用cur代表当前的根节点 while stack or cur:#中序遍历需先判断当前的栈是否还有元素或者当前的栈是否为空，说明走完了退出当前循环 if cur: #若存在则将该节点放入栈中 stack.append(cur) cur = cur.left #再将当前结点设置为结点的左孩子 else: #这时候的当前结点已经是最左边的孩子了，左边儿没有了 cur = stack.pop()# 则取栈顶元素为cur ret.append(cur.val)#当且仅当栈空cur也为空，循环结束。 cur = cur.right return ret # 前序遍历-递归-LC144_二叉树的前序遍历 class Solution: def preorderTraversal(self, root: TreeNode) -> List[int]: # 保存结果 result = [] def traversal(root: TreeNode): if root == None: return result.append(root.val) # 前序 traversal(root.left) # 左 traversal(root.right) # 右 traversal(root) return result # 中序遍历-递归-LC94_二叉树的中序遍历 class Solution: def inorderTraversal(self, root: TreeNode) -> List[int]: result = [] def traversal(root: TreeNode): if root == None: return traversal(root.left) # 左 result.append(root.val) # 中序 traversal(root.right) # 右 traversal(root) return result # 后序遍历-递归-LC145_二叉树的后序遍历 class Solution: def postorderTraversal(self, root: TreeNode) -> List[int]: result = [] def traversal(root: TreeNode): if root == None: return traversal(root.left) # 左 traversal(root.right) # 右 result.append(root.val) # 后序 traversal(root) return result
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
101.对称二叉树
递归的难点在于：找到可以递归的点 为什么很多人觉得递归一看就会，一写就废。 或者说是自己写无法写出来，关键就是你对递归理解的深不深。
对于此题： 递归的点怎么找？从拿到题的第一时间开始，思路如下：
1.怎么判断一棵树是不是对称二叉树？ 答案：如果所给根节点，为空，那么是对称。如果不为空的话，当他的左子树与右子树对称时，他对称
2.那么怎么知道左子树与右子树对不对称呢？在这我直接叫为左树和右树 答案：如果左树的左孩子与右树的右孩子对称，左树的右孩子与右树的左孩子对称，那么这个左树和右树就对称。
仔细读这句话，是不是有点绕？怎么感觉有一个功能A我想实现，但我去实现A的时候又要用到A实现后的功能呢？
当你思考到这里的时候，递归点已经出现了： 递归点：我在尝试判断左树与右树对称的条件时，发现其跟两树的孩子的对称情况有关系。
想到这里，你不必有太多疑问，上手去按思路写代码，函数A（左树，右树）功能是返回是否对称
def 函数A（左树，右树）： 左树节点值等于右树节点值 且 函数A（左树的左子树，右树的右子树），函数A（左树的右子树，右树的左子树）均为真 才返回真
二叉树是否对称可以转化为左右子树是否镜像
class Solution(object): def isSymmetric(self, root): """ :type root: TreeNode :rtype: bool """ #递归 #创建一个函数：1.判断A的值和B的值是否相等 #2.A的左子树和B的右子树是否相等 与 A的右子树和B的左子树是否相等 def check(A,B): #判断数A和树B是否镜像 if not A and not B: return True elif not A or not B: return False if A.val != B.val: return False return check(A.left,B.right) and check(A.right,B.left) return check(root,root) #迭代:就是层序遍历，检查每一层是不是回文数组 class Solution(object): def isSymmetric(self, root): """ :type root: TreeNode :rtype: bool """ queue = [root] while(queue): next_queue = list() layer = list() for node in queue: if not node: layer.append(None) #空的补充null continue next_queue.append(node.left) next_queue.append(node.right) layer.append(node.val) if layer != layer[::-1]: #回文数前后判断 return False queue = next_queue return True
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
104二叉树的最大深度
第一种方法：BFS广度优先搜索，使用双端队列deque（因为性能比另外两种Queue好的多），在大循环内对二叉树的每个层做一次遍历，range(len(queue))使只遍历当前的层，每次大循环ans加1.由于每个节点仅访问一次，所以时间复杂度为O(n)
import collections class Solution: def maxDepth(self,root): if root is None: return 0 queue = collections.deque() queue.append(root) ans = 0 while queue: ans += 1 for _ in range(len(queue)): node = queue.popleft() if node.left: queue.append(node.left) if node.right: queue.append(node.right) return ans
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
第二种方法：DFS深度优先搜索，利用递归的栈，借助level标记当前层，由于每个节点仅访问一次，所以时间复杂度O（n）
class Solution:
def maxDepth(slef,root):
if not root:
return 0
self.ans = 0
self._dfs(root,0)
return self.ans
def _dfs(self,node,level):
if not node:
return
if self.ans < level + 1:
self.ans = level + 1
self._dfs(node.left,level + 1)
self._dfs(node.right,level + 1)
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
第三种方法迭代：DSF+分治，耗时
class Solution:
def maxDepth(self,root):
if not root:
return 0
return 1 + max(self.maxDepth(root.left),self.maxDepth(root.right))
- 1
- 2
- 3
- 4
- 5
121.买卖股票的最佳时机
动态规划：
前i天的最大收益 = max{前i-1天的最大收益，第i天的价格-第i-1天中的最小价格}
解题思路
到最后交易结束时，一共会有3种状态：
dp0：一直不买
dp1：只买了一次
dp2：买了一次，卖了一次
初始化3种状态：
dp0 = 0
dp1 = - prices[0]
dp2 = float("-inf")
因为第一天不可能会有dp2状态，因此将dp2置为负无穷
(Java中置为int的下边界)
对3种状态进行状态转移：
#一直为0
dp0 = 0
#前一天也是dp1状态，或者前一天是dp0状态，今天买入一笔变成dp1状态
dp1 = max(dp1, dp0 - prices[i])
#前一天也是dp2状态，或者前一天是dp1状态，今天卖出一笔变成dp2状态
dp2 = max(dp2, dp1 + prices[i])
最后一定是手里没有股票赚的钱最多，因此返回的是dp0，dp2的最大值
class Solution:
def maxProfit(self, prices: List[int]) -> int:
dp0 = 0 # 一直不买
dp1 = - prices[0] # 只买了一次
dp2 = float('-inf') # 买了一次，卖了一次
for i in range(1, len(prices)):
dp1 = max(dp1, dp0 - prices[i]) #存放最低的成本
dp2 = max(dp2, dp1 + prices[i]) #存放最大的利润
return max(dp0, dp2)
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
136.只出现一次的数字
不需要额外空间的方法，就往位运算上想
1.交换律：a ^ b ^ c<=>a ^ c ^ b
2.任何数与0异或为任何数0 ^ n => n
3.相同的数异或为0：n ^ n => 0
var a = [2,3,2,4,4]
2 ^ 3 ^ 2 ^ 4 ^ 4等价于 2 ^ 2 ^ 4 ^ 4 ^ 3 => 0 ^ 0 ^3 => 3
class Solution:
def singleNumber(self, nums: List[int]) -> int：
a = 0
for num in nums:
a = a ^ num
return a
- 1
- 2
- 3
- 4
- 5
- 6
141.环形链表(快慢指针)
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
if head is None:
return False
fast,slow = head,head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
155.最小栈（栈）
一个栈同时保存当前值和栈内最小值
思路：题目要求在常数时间内获得栈中的最小值，因此不能在 getMin() 的时候再去计算最小值，最好应该在 push 或者 pop 的时候就已经计算好了当前栈中的最小值。
可以用一个栈，这个栈同时保存的是每个数字 x 进栈的时候的值 与 插入该值后的栈内最小值。即每次新元素 x 入栈的时候保存一个元组：（当前值 x，栈内最小值）。
这个元组是一个整体，同时进栈和出栈。即栈顶同时有值和栈内最小值，top()函数是获取栈顶的当前值，即栈顶元组的第一个值； getMin() 函数是获取栈内最小值，即栈顶元组的第二个值；pop() 函数时删除栈顶的元组。
每次新元素入栈时，要求新的栈内最小值：比较当前新插入元素 x 和 当前栈内最小值（即栈顶元组的第二个值）的大小。
新元素入栈：当栈为空，保存元组 (x, x)；当栈不空，保存元组 (x, min(此前栈内最小值， x)))
出栈：删除栈顶的元组。
class MinStack: def __init__(self): self.stack = [] #放元组 def push(self, val: int) -> None: if self.stack is None: self.stack.append((val,val)) #为空，保存元祖 else： self.stack.append((val,min(val,self.stack[-1][1]))) #stack[-1]代表stack中倒数第一个元组，stack[-1][1]指的是元组中的第二个元素 def pop(self) -> None: self.stack.pop() def top(self) -> int: return self.stack[-1][0] def getMin(self) -> int: return self.stack[-1][1] # Your MinStack object will be instantiated and called as such: # obj = MinStack() # obj.push(val) # obj.pop() # param_3 = obj.top() # param_4 = obj.getMin()
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
160.相交链表（前后指针）
有交集的时候儿：
a+c+b=b+c+a
没有交集的时候儿：
第一个指针在a循环完了会循环b，第二个指针在b循环完了会去循环a，没有交点的话两个指针走的路程是一样的都是a+b，所以最后会同时走到最后一个节点，然后在next，就都到null了，相等，就会返回null
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
A, B = headA, headB
while A != B:
A = A.next if A else headB
B = B.next if B else headA
return A
- 1
- 2
- 3
- 4
- 5
- 6
- 7
169.多数元素
摩尔投票法（Boyer–Moore majority vote algorithm），也被称作「多数投票法」，算法解决的问题是：如何在任意多的候选人中（选票无序），选出获得票数最多的那个。
算法可以分为两个阶段：
对抗阶段：分属两个候选人的票数进行两两对抗抵消
计数阶段：计算对抗结果中最后留下的候选人票数是否有效
class Solution:
def majorityElement(self, nums: List[int]) -> int:
major = 0
count = 0
for n in nums:
if count == 0:
major = n
if major == n:
count += 1
else:
count -= 1
return major
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
169.多数元素
摩尔投票法（Boyer–Moore majority vote algorithm），也被称作「多数投票法」，算法解决的问题是：如何在任意多的候选人中（选票无序），选出获得票数最多的那个。
算法可以分为两个阶段：
对抗阶段：分属两个候选人的票数进行两两对抗抵消
计数阶段：计算对抗结果中最后留下的候选人票数是否有效
class Solution:
def majorityElement(self, nums: List[int]) -> int:
major = 0
count = 0
for n in nums:
if count == 0:
major = n
if major == n:
count += 1
else:
count -= 1
return major
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
206反转链表
前置条件：迭代指针：p = head、结果指针：res = none
以1->2->3->4->5为例：
过程：
res:None
第一层循环
res:1->2->3->4->5 res = p
res:1->None res.next = res
p:2->3->4->5 p = p.next
第二层循环
res:2->3->4->5 res = p
res:2->1->None res.next = res
p:3->4->5 p = p.next
第三层循环
res:3->4->5 res = p
res:3->2->1->None res.next = res
p:4->5 p = p.next
第四层循环
res:4->5 res = p
res:4->3->2->1->None res.next = res
p:5 p = p.next
第五层循环
res:5 res = p
res:5->4->3->2->1->None res.next = res
p:None p = p.next
end…
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
p, rev = head, None
while p:
rev, rev.next, p = p, rev, p.next
return rev
- 1
- 2
- 3
- 4
- 5
- 6
226翻转二叉树
class Solution:
def invertTree(self, root: TreeNode) -> TreeNode:
if root is None:
return None
root.left,root.right = root.right, root.left
self.invertTree(root.left)
self.invertTree(root.right)
#这时候儿左右节点都已经交换过了
return root
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
234回文链表
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
stack = []
cur = head
while cur:
stack.append(cur.val)
cur = cur.next
return stack == stack[::-1]
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
283移动零
class Solution: def moveZeroes(self, nums: List[int]) -> None: for n in range(nums.count(0)): nums.remove(0) nums.append(0) #快慢指针方法 class Solution: def moveZeroes(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ right = left = 0 while right < len(nums): if nums[right]: nums[right],nums[left] = nums[left],nums[right] left += 1 right += 1
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
338比特位计数
class Solution: def countBits(self, n): """ 1: 0001 3: 0011 0: 0000 2: 0010 6: 0110 1: 0001 4: 0100 12: 1100 2: 0010 8: 1000 24: 11000 3: 0011 16:10000 48: 110000 4: 0100 32:100000 96: 1100000 5: 0101 由上可见： 1、如果 i 为偶数，那么f(i) = f(i/2) ,因为 i/2 本质上是i的二进制左移一位，低位补零，所以1的数量不变。 2、如果 i 为奇数，那么f(i) = f(i - 1) + 1， 因为如果i为奇数，那么 i - 1必定为偶数，而偶数的二进制最低位一定是0， 那么该偶数 +1 后最低位变为1且不会进位，所以奇数比它上一个偶数bit上多一个1，即 f(i) = f(i - 1) + 1。 """ ret = [0] for i in range(1, n + 1): if i % 2 == 0: # 偶数 ret.append(ret[i//2]) #整除 else: # 奇数 ret.append(ret[i - 1] + 1) return ret
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
448.找到所有数组中消失的数字
counter = set(nums) #进行去重 N = len(nums) res = [] for i in range(1, N + 1): if i not in counter: res.append(i) return res #数组的原地操作 class Solution(object): def findDisappearedNumbers(self, nums): """ :type nums: List[int] :rtype: List[int] """ for i, num in enumerate(nums): if nums[abs(num) - 1] > 0: nums[abs(num) - 1] *= -1 res = [] for i in range(len(nums)): if nums[i] > 0: res.append(i + 1) return res
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
461.汉明距离
class Solution:
def hammingDistance(self, x: int, y: int) -> int:
return bin(x ^ y).count('1')
#bin把10进制数转化为二进制数，count（）计算字符串中指定字符个数
- 1
- 2
- 3
- 4
543.二叉树的直径
class Solution:
def diameterOfBinaryTree(self, root: TreeNode) -> int:
self.depth(root)
return self.max
def __init__(self):
self.max = 0
def depth(self,root):
if root is None:
return 0
l = self.depth(root.left)
r = self.depth(root.right)
'''每个结点都要去判断左子树+右子树的高度是否大于self.max，更新最大值'''
self.max = max(self.max,l + r)
# 返回的是高度
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
617.合并二叉树
#递归
class Solution:
def mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:
if root1 and root2:
root1.val += root2.val
root1.left = self.mergeTrees(root1.left,root2.left)
root1.right = self.mergeTrees(root1.right,root2.right)
return root1
return root1 or root2
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
中等题
2.两数相加
# 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: ListNode, l2: ListNode) -> ListNode: #生成一个值为0的链表作为表头 self.head = ListNode(0) #首尾为同一个节点 self.tail = self.head #记录单个位置是否进位的变量，初始为0，值应该在0,1之前切换 carry=0 while(l1 or l2): #循环条件，判断给的节点是否存在 # 接收l1节点value的变量，如果l1节点为空则值为0 x= l1.val if l1 else 0 # 接收l2节点value的变量，如果l2节点为空则值为0 y= l2.val if l2 else 0 #将进位值与两个节点value相加 s=carry+x+y #取本次节点相加进位值，决定下次循环时进位值 carry=s//10 #将目前节点的next（tail默认为None）改为计算后的个位数放入的节点 self.tail.next=ListNode(s%10) #将计算节点放入列表尾部 self.tail=self.tail.next #如果l1/l2存在，将next值传入l1/l2.节点存在才有next if l1:l1=l1.next if l2:l2=l2.next #如果最高位的计算仍然是2位数，将进位1作为节点出入最尾部 if(carry>0): self.tail.next=ListNode(1) #这里的self.head.next即指向了第二个节点，将我们生成的0节点排除 return self.head.next
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
3.无重复字符的最长子串
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
a = []
res = 0
for i in s:
if i in a:
a = a[a.index(i)+1:] #切片操作，从重复字符的位置切到当前元素
#后面的代码里a会append当前元素，最后得到的新a就是当前元素的最长不重复字串
a.append(i)
res = res if len(a)<res else len(a)
return res
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
5.最长回文子串
class Solution: def longestPalindrome(self, s: str) -> str: l = len(s) if l < 2: return s for i in range(l, 0, -1): for j in range(l-i+1): son_s = s[j:j+i] if son_s == son_s[::-1]: return son_s return '' #中心扩散法 class Solution: def longestPalindrome(self, s: str) -> str: n, m = 0, 0 for i in range(len(s)): left, right = i, i while left >= 0 and s[left] == s[i]: left -= 1 while right < len(s) and s[right] == s[i]: right += 1 while left >= 0 and right < len(s) and s[left] == s[right]: left -= 1 right += 1 if m - n + 1 < right - left - 1: n, m = left + 1, right - 1 return s[n:m+1]
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
11.盛最多水的容器
class Solution:
def maxArea(self, height: List[int]) -> int:
l, r = 0, len(height) - 1
ans = 0
while l < r:
area = min(height[l], height[r]) * (r - l)
ans = max(ans, area)
if height[l] <= height[r]: # 移动较小的那一端
l += 1
else:
r -= 1
return ans
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
15.三数之和
class Solution: def threeSum(self, nums: [int]) -> [[int]]: nums.sort()# 排序，nums变成递增数组 res, k = [], 0 for k in range(len(nums) - 2): #-2是为了保证后面还能存在两个数字 if nums[k] > 0: break # 若nums[k]大于0，则后面的数字也是大于零（排序后是递增的） if k > 0 and nums[k] == nums[k - 1]: continue #nums[k]值重复了，去重 i, j = k + 1, len(nums) - 1 #定义左右指针 while i < j: # 3. double pointer s = nums[k] + nums[i] + nums[j] if s < 0: i += 1 #左指针前进并去重 while i < j and nums[i] == nums[i - 1]: i += 1 elif s > 0: j -= 1 #右指针后退并去重 while i < j and nums[j] == nums[j + 1]: j -= 1 else: res.append([nums[k], nums[i], nums[j]]) i += 1 j -= 1 while i < j and nums[i] == nums[i - 1]: i += 1 #左指针前进并去重 while i < j and nums[j] == nums[j + 1]: j -= 1 #右指针后退并去重 return res
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
17.电话号码的字母组合
class Solution(object): def letterCombinations(self, digits): """ 动态规划 dp[i]: 前i个字母的所有组合 由于dp[i]只与dp[i-1]有关,可以使用变量代替列表存储降低空间复杂度 :type digits: str :rtype: List[str] """ if not digits: return [] d = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'} n = len(digits) dp = [[] for _ in range(n)] dp[0] = [x for x in d[digits[0]]] for i in range(1, n): dp[i] = [x + y for x in dp[i - 1] for y in d[digits[i]]] return dp[-1] def letterCombinations2(self, digits): """ 使用变量代替上面的列表 降低空间复杂度 :type digits: str :rtype: List[str] """ if not digits: return [] d = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'} n = len(digits) res = [''] for i in range(n): res = [x + y for x in res for y in d[digits[i]]] return res def letterCombinations3(self, digits): """ 递归 :param digits: :return: """ d = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'} if not digits: return [] if len(digits) == 1: return [x for x in d[digits[0]]] return [x + y for x in d[digits[0]] for y in self.letterCombinations3(digits[1:])]
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
19.删除链表的倒数第n个结点
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode: #双指针 a = head b = head for i in range(n): #距离为n，提前后移动n个节点 if a.next: a = a.next else: #移除的是首结点 return head.next while a.next:#当a到达链表尾，b指向要删除的节点的前一个节点 a = a.next b = b.next #因为已经保证了是待删除节点的前一个节点，直接删除即可 b.next = b.next.next #删除b指针所指节点后的节点 return head
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
22.括号生成
class Solution: def generateParenthesis(self, n: int) -> List[str]: result = {""} for i in range(n): temp = set() for s in result:#在上一次的结果的所有字符串的各个位置上插入“（）” for j in range(len(s) + 1): temp.add(s[:j] + "()" + s[j:]) result = temp return list(result) #回溯算法 class Solution: def generateParenthesis(self, n: int) -> List[str]: res = [] def backTracking(left, right, s): if len(s) == 2*n: res.append(s) return if left < n: backTracking(left+1, right, s+'(') if right < left: backTracking(left, right+1, s+')') backTracking(0,0,'') return res
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
31.下一个排列
class Solution: def nextPermutation(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ for i in range(len(nums)-1,0,-1): # 对应第3部，找到下标l的位置,这里 l == i-1 if nums[i-1] < nums[i]: for j in range(len(nums)-1,i-1,-1): #对应第4步找到下标r，这里 r == j #然后交换 下标l 与 下标r 的值 if nums[j] > nums[i-1]: nums[i-1],nums[j] = nums[j],nums[i-1] break # 对应第6步，反转下标l后的子序列 for j in range((len(nums)-i+1)//2): nums[i+j],nums[len(nums)-1-j] = nums[len(nums)-1-j] ,nums[i+j] return nums nums.reverse() return nums
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
33.搜索旋转排序数组
class Solution: def search(self, nums: List[int], target: int) -> int: try: a = nums.index(target) return a except: return -1 #二分法 class Solution: def search(self, nums, target): left, right = 0, len(nums) - 1 while left <= right: mid = (left + right) // 2 if nums[mid] == target: return mid elif nums[left] <= nums[mid]: if nums[left] <= target < nums[mid]: right = mid - 1 else: left = mid + 1 else: if nums[mid] < target <= nums[right]: left = mid + 1 else: right = mid - 1 return -1
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
34.在排序数组中查找元素的第一个和最后一个位置
class Solution: def combinationSum(self, candidates, target): candidates.sort() n = len(candidates) res = [] def backtrack(i, tmp_sum, tmp): for j in range(i, n): # 如果和超过了target值，停止遍历，返回上层函数 if tmp_sum + candidates[j] > target: break # 如果和等于target值，把结果添加进去，后面也没必要继续遍历了，停止遍历，返回上层函数 if tmp_sum + candidates[j] == target: res.append(tmp + [candidates[j]]) break backtrack(j, tmp_sum + candidates[j], tmp+[candidates[j]]) backtrack(0, 0, []) return res
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
39.组合总和
在这里插入代码片
- 1
46.全排列
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
res = []
def backtrack(nums, tmp):
if not nums:
res.append(tmp)
return
for i in range(len(nums)):
backtrack(nums[:i] + nums[i+1:], tmp + [nums[i]])
backtrack(nums, [])
return res
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
48.旋转图像
class Solution: def rotate(self, matrix: List[List[int]]) -> None: """ Do not return anything, modify matrix in-place instead. """ pos1,pos2 = 0,len(matrix)-1 while pos1<pos2: add = 0 while add<pos2-pos1: #左上角（0，0），右下角（3,3） #左上角为0块，右上角为1块，右下角为2块，左下角为3块 # temp = 3 temp = matrix[pos2-add][pos1] # 3 = 2 matrix[pos2-add][pos1] = matrix[pos2][pos2-add] # 2 = 1 matrix[pos2][pos2-add] = matrix[pos1+add][pos2] # 1 = 0 matrix[pos1+add][pos2] = matrix[pos1][pos1+add] # 0 = temp matrix[pos1][pos1+add] = temp add += 1 pos1 += 1 pos2 -= 1
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
49.字母异位词分组
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
dic = {}
for i in strs:
key = "".join(sorted(i))
if key not in dic:
dic[key] = [i]
else:
dic[key].append(i)
return list(dic.values())
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
55.跳跃游戏
class Solution:
def canJump(self, nums: List[int]) -> bool:
max_i = 0 #初始化当前能到达最远的位置
for i, jump in enumerate(nums):
#i为当前位置，jump是当前位置的跳数
if max_i>=i and i+jump>max_i:
#如果当前位置能到达，并且当前位置+跳数>最远位置
max_i = i+jump #更新最远能到达位置
return max_i>=i
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
56.合并区间
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
intervals.sort() #按首字母进行排序
res = [intervals[0]]
if not res: return []
for x,y in intervals[1:]:
if res[-1][1] < x:
res.append([x,y])
else:
res[-1][1] = max(y,res[-1][1])
return res
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
62.不同路径
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
def dp(i,j):
if 0 in (i,j):
return 1
return dp(i-1,j)+dp(i,j-1)#右下角=左边+上边
return dp(m-1,n-1)#减1就是说明横纵能走几步
#n行mm列说明最终路径里面一定会有n-1n−1个向下的步骤和m-1m−1个向右的步骤。
#意思就是在m+n-2m+n−2个步骤的路径上，选n-1n−1个位置来向下走，剩下的位置向右走即可，这个数据量直接调函数即可。
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
return comb(m + n - 2, n - 1)
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
64.最小路径和
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
for i in range(len(grid)):#行遍历
for j in range(len(grid[0])): #列遍历
if i==j==0:continue
elif i==0:grid[i][j]=grid[i][j-1]+grid[i][j]
elif j==0:grid[i][j]=grid[i-1][j]+grid[i][j]
else:grid[i][j]=min(grid[i][j-1],grid[i-1][j])+grid[i][j]
return grid[-1][-1]
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
75.颜色分类
class Solution:
def sortColors(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
p=0
for i in range(len(nums)):
if nums[i]==0:
nums[i],nums[p]=nums[p],nums[i]
p+=1
for i in range(p,len(nums)):
if nums[i]==1:
nums[i],nums[p]=nums[p],nums[i]
p+=1
return nums
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
78.子集
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
res = [[]]
for i in range(len(nums)):
for sub in res[:]:
res.append(sub+[nums[i]])
return res
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
79.单词搜索
class Solution: def exist(self, board: List[List[str]], word: str) -> bool: row = len(board) col = len(board[0]) def helper(i,j,k,visited): if k==len(word): return True for x,y in [(0,-1),(0,1),(-1,0),(1,0)]: #判断当前位置的上下左右的位置 tempi = i + x tempj = j + y if 0<=tempi<row and 0<=tempj<col and board[tempi][tempj]==word[k] and (tempi,tempj) not in visited: visited.add((tempi,tempj)) #把符合的位置添加进去 if helper(tempi,tempj,k+1,visited): return True visited.remove((tempi,tempj))#把上一个添加进去，但下一个不符合的移出来 return False for i in range(row): for j in range(col): if board[i][j]==word[0] and helper(i,j,1,{(i,j)}): return True return False
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
96.不同的二叉搜索树
class Solution:
def numTrees(self, n: int) -> int:
# 假设n个节点存在二叉排序树的个数是G(n)，令f(i)为以i为根的二叉搜索树的个数
# 即有:G(n) = f(1) + f(2) + f(3) + f(4) + ... + f(n)
# n为根节点，当i为根节点时，其左子树节点个数为[1,2,3,...,i-1]，右子树节点个数为[i+1,i+2,...n]，所以当i为根节点时，其左子树节点个数为i-1个，右子树节点为n-i，即f(i) = G(i-1)*G(n-i),
# 上面两式可得:G(n) = G(0)*G(n-1)+G(1)*(n-2)+...+G(n-1)*G(0)
dp = [0]*(n+1)#当为3时，[0,0,0,0]
dp[0] = 1 #初始状态
dp[1] = 1
for i in range(2,n+1):# n
for j in range(1,i+1):
dp[i]+=dp[j-1]*dp[i-j]
return dp[n]
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
98.验证二叉搜索树
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def isValidBST(self, root: TreeNode) -> bool: # 左子树的最大值**小于当前节点值，**右子树的最小值**大于当前节点值。而不是简单的左节点小于，右节点大于 #二叉搜索树中序遍历为递增的顺序。（二叉搜索树的重要性质） res = [] def helper(root): if not root: return helper(root.left) res.append(root.val) helper(root.right) helper(root) return res == sorted(res) and len(set(res)) == len(res)
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
102.二叉树的层序遍历
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def levelOrder(self, root: TreeNode) -> List[List[int]]: #BFS+递归 # if not root: # return [] # res = [] # level = [root] # while level: # tmp = [] # nextlevel = [] # for n in level: # tmp.append(n.val) # if n.left: # nextlevel.append(n.left) # if n.right: # nextlevel.append(n.right) # res.append(tmp) # level = nextlevel # return res # #BFS+回溯 res = [] def backtrack(root,depth): if not root:return if len(res)==depth: res.append([]) res[depth].append(root.val) backtrack(root.left,depth+1) backtrack(root.right,depth+1) backtrack(root,0) return res
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
105.从前序与中序遍历序列构造二叉树
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode: if len(inorder)==0: return None #前序遍历第一个节点为根节点 root = TreeNode(preorder[0]) #因为没有重复元素，找到中序遍历中根节点的位置，左边是左子树，右边是右子树 mid = inorder.index(preorder[0]) #构建左子树 root.left = self.buildTree(preorder[1:mid+1],inorder[:mid]) root.right = self.buildTree(preorder[mid+1:],inorder[mid+1:]) return root
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
114.二叉树展开为链表
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def flatten(self, root: TreeNode) -> None: """ Do not return anything, modify root in-place instead. """ if not root or (not root.left and not root.right): return root #先把左右子树捋直 self.flatten(root.left) self.flatten(root.right) tmp = root.right #把捋直的右子树备份一下 root.right = root.left #把捋直的左子树放到右边 root.left = None #记得把左子树置空 while(root.right): #找到现在右子树的最后一个node root = root.right root.right = tmp #把捋直的原来的右子树接上去
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
128.最长连续序列
class Solution: def longestConsecutive(self, nums: List[int]) -> int: nums = set(nums) res = 0 for num in nums: #判断第一个数字 if num-1 not in nums: tmp = 1 while num+1 in nums: num+=1 tmp+=1 res = max(tmp,res) return res #方法2 class Solution: def longestConsecutive(self, nums: List[int]) -> int: lookup = {} res = 0 for num in nums: if num not in lookup: # 判断左右是否可以连起来 left = lookup[num - 1] if num - 1 in lookup else 0 right = lookup[num + 1] if num + 1 in lookup else 0 # 记录长度 lookup[num] = left + right + 1 # 把头尾都设置为最长长度 lookup[num - left] = left + right + 1 lookup[num + right] = left + right + 1 res = max(res, left + right + 1) return res
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
139.单词拆分
class Solution:
def wordBreak(self, s: str, wordDict) -> bool:
n = len(s)
if not wordDict: return not s
dp = [False] * (n + 1)
dp[0] = True
for i in range(1, n + 1):
for j in range(i - 1, -1, -1):
if dp[j] and s[j:i] in wordDict: #从断的位置继续遍历下一个整体 宽度
dp[i] = True
break
return dp[-1]
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
142.环形链表2
环形解析 f=2s （快指针每次2步，路程刚好2倍） f = s + nb (相遇时，刚好多走了n圈） 推出：s = nb 从head结点走到入环点需要走 ： a + nb， 而slow已经走了nb，那么slow再走a步就是入环点了。 如何知道slow刚好走了a步？ 从head开始，和slow指针一起走，相遇时刚好就是a步 1.第一次相遇，slow = nb 2.a+nb = 入口点 3.slow再走a = 入口 = head走到入口 = a 4.由3得出，起始距离入口 = 第一次相遇位置 + a # Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def detectCycle(self, head: ListNode) -> ListNode: fast,slow = head,head while True: if not (fast and fast.next):return fast,slow = fast.next.next,slow.next if fast==slow:break fast = head while fast != slow: fast,slow = fast.next,slow.next return fast
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
146.LRU缓存
class ListNode: def __init__(self, key=None, value=None): self.key = key self.value = value self.prev = None self.next = None class LRUCache: def __init__(self, capacity: int): self.capacity = capacity self.hashmap = {} # 新建两个节点 head 和 tail self.head = ListNode() self.tail = ListNode() # 初始化链表为 head <-> tail self.head.next = self.tail self.tail.prev = self.head # 因为get与put操作都可能需要将双向链表中的某个节点移到末尾，所以定义一个方法 def move_node_to_tail(self, key): # 先将哈希表key指向的节点拎出来，为了简洁起名node # hashmap[key] hashmap[key] # | | # V --> V # prev <-> node <-> next pre <-> next ... node node = self.hashmap[key] node.prev.next = node.next node.next.prev = node.prev # 之后将node插入到尾节点前 # hashmap[key] hashmap[key] # | | # V --> V # prev <-> tail ... node prev <-> node <-> tail node.prev = self.tail.prev node.next = self.tail self.tail.prev.next = node self.tail.prev = node def get(self, key: int) -> int: if key in self.hashmap: # 如果已经在链表中了久把它移到末尾（变成最新访问的） self.move_node_to_tail(key) res = self.hashmap.get(key, -1) if res == -1: return res else: return res.value def put(self, key: int, value: int) -> None: if key in self.hashmap: # 如果key本身已经在哈希表中了就不需要在链表中加入新的节点 # 但是需要更新字典该值对应节点的value self.hashmap[key].value = value # 之后将该节点移到末尾 self.move_node_to_tail(key) else: if len(self.hashmap) == self.capacity: # 去掉哈希表对应项 self.hashmap.pop(self.head.next.key) # 去掉最久没有被访问过的节点，即头节点之后的节点 ，去除node这个结点 self.head.next = self.head.next.next self.head.next.prev = self.head # 如果不在的话就插入到尾节点前 new = ListNode(key, value) self.hashmap[key] = new new.prev = self.tail.prev new.next = self.tail self.tail.prev.next = new self.tail.prev = new
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
148.排序链表(分治法)
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]: if not head or not head.next: return head fast = head slow = head while fast.next and fast.next.next: slow = slow.next fast = fast.next.next #找到左右两部分，把左边的slow.next和右边的断开 mid = slow.next slow.next = None #递归下去，分到最小单位 # 递归下去 left = self.sortList(head) right = self.sortList(mid) # 合并 return self.merge(left, right) def merge(self,left,right): #创建一个头结点 h = ListNode(0) p = h while left and right: if left.val<right.val: p.next = left left = left.next p = p.next else: p.next = right right = right.next p = p.next if left: p.next = left if right: p.next = right return h.next
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
152.乘积最大子数组
# 我们只要记录前i的最小值, 和最大值, # 那么 dp[i] = max(nums[i] * pre_max, nums[i] * pre_min, nums[i]), #这里0 不需要单独考虑, 因为当相乘不管最大值和最小值,都会置0 class Solution: def maxProduct(self, nums: List[int]) -> int: if not nums: return res = nums[0] pre_max = nums[0] pre_min = nums[0] for num in nums[1:]: cur_max = max(pre_max * num, pre_min * num, num) cur_min = min(pre_max * num, pre_min * num, num) res = max(res, cur_max) pre_max = cur_max pre_min = cur_min return res
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
198.打家劫舍
在这里插入代码片
- 1
200.岛屿数量
#DFS #目标是找到矩阵中 “岛屿的数量” ，上下左右相连的 1 都被认为是连续岛屿。 # dfs方法： 设目前指针指向一个岛屿中的某一点 (i, j)，寻找包括此点的岛屿边界。 # 从 (i, j) 向此点的上下左右 (i+1,j),(i-1,j),(i,j+1),(i,j-1) 做深度搜索。 # 终止条件： # (i, j) 越过矩阵边界; # grid[i][j] == 0，代表此分支已越过岛屿边界。 # 搜索岛屿的同时，执行 grid[i][j] = '0'，即将岛屿所有节点删除，以免之后重复搜索相同岛屿。 # 主循环： # 遍历整个矩阵，当遇到 grid[i][j] == '1' 时，从此点开始做深度优先搜索 dfs，岛屿数 count + 1 且在深度优先搜索中删除此岛屿。 # 最终返回岛屿数 count 即可。 class Solution: def numIslands(self, grid: [[str]]) -> int: def dfs(grid, i, j): if not 0 <= i < len(grid) or not 0 <= j < len(grid[0]) or grid[i][j] == '0': return grid[i][j] = '0' dfs(grid, i + 1, j) dfs(grid, i, j + 1) dfs(grid, i - 1, j) dfs(grid, i, j - 1) count = 0 for i in range(len(grid)): for j in range(len(grid[0])): if grid[i][j] == '1': dfs(grid, i, j) count += 1 return count
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
207.课程表
class Solution: def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool: def dfs(i,behindclass,flags): if flags[i] == 1:return False #说明已经遍历过了，不需要在访问了 if flags[i] == -1:return True # flags[i] = 1 #只有这个标志位是干净的，别人还没有动过，我才能标记为1，说明本次dfs我遍历过它 for j in behindclass[i]:#遍历当前课程下（理解为后边的）课程 if not dfs(j,behindclass,flags): return False flags[i] = -1 #只有一次DFS完整结束了，才能执行到这一步，标记为-1，说明这条路没问题，再遇到不需要遍历了 return True behindclass = [[] for _ in range(numCourses)] #几个格子上下对应 flags = [0 for _ in range(numCourses)] #先开始的课程的状态 for cur, pre in prerequisites:# 把前后的课程放入behindclass behindclass[pre].append(cur) #把课程对应的分类 for i in range(numCourses): if not dfs(i,behindclass,flags):return False return True
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
208实现Trie（前缀树）
class Trie: #初始化前缀树对象 def __init__(self): self.root = {} def insert(self, word: str) -> None: #插入 tree = self.root for a in word: if not a in tree: tree[a] = {} tree = tree[a] tree["#"] = "#" def search(self, word: str) -> bool: #查找 tree = self.root for a in word: if a not in tree: return False tree = tree[a] if "#" in tree: return True return False def startsWith(self, prefix: str) -> bool: #看前缀 tree = self.root for a in prefix: if a not in tree: return False tree = tree[a] return True # Your Trie object will be instantiated and called as such: # obj = Trie() # obj.insert(word) # param_2 = obj.search(word) # param_3 = obj.startsWith(prefix)
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
215.数组中的第K个最大元素
#基于快排的所有TopK问题简单python模板 def partition(nums, left, right): pivot = nums[left]#初始化一个待比较数据 i,j = left, right while(i < j): while(i<j and nums[j]>=pivot): #从后往前查找，直到找到一个比pivot更小的数 j-=1 nums[i] = nums[j] #将更小的数放入左边 while(i<j and nums[i]<=pivot): #从前往后找，直到找到一个比pivot更大的数 i+=1 nums[j] = nums[i] #将更大的数放入右边 #循环结束，i与j相等 nums[i] = pivot #待比较数据放入最终位置 return i #返回待比较数据最终位置 #快速排序 def quicksort(nums, left, right): if left < right: index = partition(nums, left, right) quicksort(nums, left, index-1) quicksort(nums, index+1, right) arr = [1,3,2,2,0] quicksort(arr, 0, len(arr)-1) print(arr) def topk_split(nums, k, left, right): #topk切分 #将快速排序改成快速选择，即我们希望寻找到一个位置，这个位置左边是k个比这个#位置上的数更小的数，右边是n-k个比该位置上的数大的数，我将它命名为#topk_split，找到这个位置后停止迭代，完成了一次划分。 #寻找到第k个数停止递归，使得nums数组中index左边是前k个小的数，index右边是后面n-k个大的数 if (left<right): index = partition(nums, left, right) if index==k: return elif index < k: topk_split(nums, k, index+1, right) else: topk_split(nums, k, left, index-1) #接下来就依赖于上面这两个函数解决所有的topk问题 #获得前k小的数 #获得前k小的数 def topk_smalls(nums, k): topk_split(nums, k, 0, len(nums)-1) return nums[:k] arr = [1,3,2,3,0,-19] k = 2 print(topk_smalls(arr, k)) print(arr) #获得第k小的数 def topk_small(nums, k): topk_split(nums, k, 0, len(nums)-1) return nums[k-1] #右边是开区间，需要-1 arr = [1,3,2,3,0,-19] k = 3 print(topk_small(arr, k)) print(arr) #获得前k大的数 def topk_larges(nums, k): #parttion是按从小到大划分的，如果让index左边为前n-k个小的数，则index右边为前k个大的数 topk_split(nums, len(nums)-k, 0, len(nums)-1) #把k换成len(nums)-k return nums[len(nums)-k:] arr = [1,3,-2,3,0,-19] k = 3 print(topk_larges(arr, k)) print(arr) #获得第k大的数 def topk_large(nums, k): #parttion是按从小到大划分的，如果让index左边为前n-k个小的数，则index右边为前k个大的数 topk_split(nums, len(nums)-k, 0, len(nums)-1) #把k换成len(nums)-k return nums[len(nums)-k] arr = [1,3,-2,3,0,-19] k = 2 print(topk_large(arr, k)) print(arr) #只排序前k个小的数 #获得前k小的数O(n)，进行快排O(klogk) def topk_sort_left(nums, k): topk_split(nums, k, 0, len(nums)-1) topk = nums[:k] quicksort(topk, 0, len(topk)-1) return topk+nums[k:] #只排序前k个数字 arr = [0,0,1,3,4,5,0,7,6,7] k = 4 topk_sort_left(arr, k) #只排序后k个大的数 #获得前n-k小的数O(n)，进行快排O(klogk) def topk_sort_right(nums, k): topk_split(nums, len(nums)-k, 0, len(nums)-1) topk = nums[len(nums)-k:] quicksort(topk, 0, len(topk)-1) return nums[:len(nums)-k]+topk #只排序后k个数字 arr = [0,0,1,3,4,5,0,-7,6,7] k = 4 print(topk_sort_right(arr, k))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
221.最大正方形
class Solution:
def maximalSquare(self, matrix: List[List[str]]) -> int:
row = len(matrix)
col = len(matrix[0])
max_side = 0
dp = [[0]*(col+1) for _ in range(row+1)]
for i in range(row):
for j in range(col):
if matrix[i][j]=="1":
dp[i+1][j+1] = min(dp[i][j],dp[i+1][j],dp[i][j+1])+1
max_side = max(max_side,dp[i+1][j+1])
return max_side*max_side
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
236.二叉树的最近公共祖先
class Solution: def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode': if not root: return None # 边界条件，如果匹配到left或right就直接返回停止递归 if root.val == p.val or root.val == q.val: return root # 这两行代码可以无脑先写好！ # 因为是DFS算法，这个模板可以无脑套用，写上之后可能你思路就清晰很多 left = self.lowestCommonAncestor(root.left,p,q) right = self.lowestCommonAncestor(root.right,p,q) # 如果既在左子树找到，又在右子树找到，那么毫无疑问当前root就是公共节点 if left and right: return root # 只有左子树有，那么直接返回左子树匹配到的第一个节点 if left: return left if right: return right
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
238.除自身以外数组的乘积
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
# 原数组： [1 2 3 4]
# 左部分的乘积： 1 1 1*2 1*2*3
# 右部分的乘积： 2*3*4 3*4 4 1
# 结果： 1*2*3*4 1*3*4 1*2*4 1*2*3*1
res,p,q = [1],1,1
for i in range(len(nums)-1): #先把左半部分给算出来
p *= nums[i]
res.append(p)
for j in range(len(nums)-1,0,-1):#再从右边儿倒着过来乘起来
q *= nums[j]
res[j-1] *= q
return res
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
240.搜索二维矩阵2
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
#bfs的思路是按照一行一行的去遍历的，可以使右上角也可以是左下角
#按照右上角写
m,n = len(matrix),len(matrix[0])
i,j = 0,n-1
while i<m and j>=0:
if matrix[i][j]==target:
return True
elif matrix[i][j]>target:
j -= 1
else:
i += 1
return False
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
279.完全平方数
class Solution:
def numSquares(self, n: int) -> int:
# 组成和的完全平方数的最多个数，就是只用1构成
# 因此，dp[i] = i
dp = [i for i in range(n+1)]
# dp[0] = 0 无意义，只是为了方便记录特殊情况:
# n本身就是完全平方数，dp[n] = min(dp[n], dp[n - n] + 1) = 1
for i in range(1,n):#遍历物品
if i*i>n:
break
num = i*i
for j in range(num,n+1):#遍历背包
dp[j] = min(dp[j],dp[j-num]+1)
return dp[n]
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
标题287.寻找重复数
class Solution: def findDuplicate(self, nums: List[int]) -> int: # f=2s （快指针每次2步，路程刚好2倍） # f = s + nb (相遇时，刚好多走了n圈） # 推出：s = nb # 从head结点走到入环点需要走 ： a + nb， 而slow已经走了nb，那么slow再走a步就是入环点了。 # 如何知道slow刚好走了a步？ 从head开始，和slow指针一起走，相遇时刚好就是a步 # 1.第一次相遇，slow = nb # 2.a+nb = 入口点 # 3.slow再走a = 入口 = head走到入口 = a # 4.由3得出，起始距离入口 = 第一次相遇位置 + a fast,slow = 0,0 while True: slow = nums[slow] fast = nums[nums[fast]] if slow==fast: break find = 0 while True: find = nums[find] slow = nums[slow] if slow==find: return find
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
300.最长递归子序列
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
#用动态规划，设置一个同步的组，然后挨个遍历,之前的状态不变，变得话从之前最大的状态加1
if not nums:
return 0
dp = [1]*len(nums)
for i in range(len(nums)):
for j in range(i):
if nums[j]<nums[i]: #如果不是强点单调递增，有相等的情况，可以写成<=
dp[i] = max(dp[i],dp[j]+1)
return max(dp)
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
309.最佳买卖股票时机含冷冻期
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if len(prices)<2: return 0
dp0=0 # 手里没股票，没有处于冷冻期
dp1=float("-inf") # 手里没股票，并且处于冷冻期
dp2=- prices[0] # 手里有股票
for i in range(1, len(prices)):
new_dp0=max(dp0, dp1) #前一天是dp0/dp1（手里都没有股票，非冷冻期/冷冻期），今天变成dp0（手里没有股票，非冷冻期）
new_dp1=dp2+prices[i] #前一天的卖出，今天变成没有股票的冷冻期
new_dp2=max(dp2, dp0-prices[i]) #前一天是dp2（没有股票的冷冻期）/前一天解冻完后买入的dp0
dp0, dp1, dp2=new_dp0, new_dp1, new_dp2
return max(dp0, dp1)
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
322.零钱兑换
背包问题：
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。
# dp[j]代表含义：填满容量为j的背包最少需要多少硬币 # 初始化dp数组：因为硬币的数量一定不会超过amount，而amount <= 10^4 # ，因此初始化数组值为10001；dp[0] = 0 # 转移方程：dp[j] = min(dp[j], dp[j - coin] + 1) # 当前填满容量j最少需要的硬币 = min( 之前填满容量j最少需要的硬币, 填满容量 j - coin 需要的硬币 + 1个当前硬币） # 返回dp[amount]，如果dp[amount]的值为10001没有变过，说明找不到硬币组合，返回-1 coins = [1, 2, 5] amount = 11 class Solution: def coinChange(self, coins, amount): dp = [0] + [10001] * amount for coin in coins: for j in range(coin, amount + 1): dp[j] = min(dp[j], dp[j - coin] + 1) return dp[-1] if dp[-1] != 10001 else -1 a = Solution() print(a.coinChange(coins,amount))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
337.打家劫舍3
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def rob(self, root: TreeNode) -> int: def _rob(root): if not root: return 0, 0 # 偷，不偷 left = _rob(root.left) right = _rob(root.right) # 偷当前节点, 则左右子树都不能偷 v1 = root.val + left[1] + right[1] #left的第二个返回值，也就是不偷left的值 # 不偷当前节点, 则取左右子树中最大的值 v2 = max(left) + max(right) return v1, v2 #这个节点偷和不偷的受益同时返回。 return max(_rob(root))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
347.前k个高频元素
# Counter 是一个在collections包里的类，正如其名，是一个用于计数的工具。
# 我们可以用Counter(nums)这样的构造函数构造一个Counter类，其中nums是一个列表。
# 构造好的Counter实例可以看作一个字典，键是nums的每一项，值是它的出现次数。
# 如果上面的叙述让你感到很混乱的话，我不妨举个例子。
# 如果一个列表a = [1,1,3,4,3]，你想要统计每项的出现次数，那么你使用b = Counter(a)，那么这时候b就像一个这样的字典{1:2,3:2,4:1}，表示数字1出现了2次，数字3出现了2次，数字4出现了1次。
# 还是很好理解的吧？
# 可是题目里要我们输出的是最多的K项
# 这时候可以应用Counter的一个函数，most_common(k)
# 这个函数就是返回最多出现的K项
# 但是返回的形式是一个元祖列表，类似[(1,2),(3,2),(4,1)]的形式
# 我们只需要键也就是第一项，所以要使用列表生成式处理一下即可。
count = collections.Counter(nums)
return [item[0] for item in count.most_common(k)]
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/笔触狂放9/article/detail/685216
推荐阅读
相关标签
