1-10
605.种花问题
class Solution:
def canPlaceFlowers(self, f: List[int], n: int) -> bool:
f=[0]+f+[0,1]
ans,tmp=0,0
for i in f:
if i:
ans+=(tmp-1)//2 #整数除
tmp=0
else: tmp+=1
#print(ans)
return ans>=n
239.滑动窗口最大值⭐
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
n=len(nums)
q=collections.deque()
for i in range(k):
while q and nums[i]>=nums[q[-1]]:
q.pop()
q.append(i)
ans=[nums[q[0]]]
for i in range(k,n):
while q and nums[i]>=nums[q[-1]]:
q.pop()
q.append(i)
if q[0]==i-k: q.popleft()
ans.append(nums[q[0]])
return ans
# q 用于存放大值的索引
# nums[q[0]]总是当前窗口最大值，并且后面对应的num递减
#单调双端队列
#deque: 类似list的容器，实现了在两端快速append和pop
86.分隔链表
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def partition(self, head: ListNode, x: int) -> ListNode:
small,large=ListNode(),ListNode()
sp,lp,p=small,large,head
while p:
if p.val<x:
sp.next=p
sp=sp.next
else:
lp.next=p
lp=lp.next
p=p.next
sp.next=large.next
lp.next=None
return small.next
# 熟悉一下python中的链表
509.斐波那契数
class Solution:
#functools模块中的缓存
@lru_cache(None)
def fib(self, n: int) -> int:
if n<2: return n
return self.fib(n-1)+self.fib(n-2)
830.较大分组的位置
class Solution:
def largeGroupPositions(self, s: str) -> List[List[int]]:
left,right,n=0,0,len(s)
ans=[]
while right<n-1:
while right<n and s[right]==s[left]: #right<n的位置
#解决了后面是末尾的问题
right+=1
if right-left>=3: ans.append([left,right-1])
#print(left,right)
left=right
return ans
# 双指针
309.除法求值⭐
# 一、dfs做法
class Solution:
def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
dic=collections.defaultdict(dict) #值也为字典
for [a,b],val in zip(equations,values):
dic[a][b]=val
dic[b][a]=1/val
def dfs(a,b,visited):
if b in dic[a]: return dic[a][b]
for c in dic[a]: #开始遍历寻找
if c not in visited:
visited.add(c)
val=bt(c,b,visited)
if val!=-1: return dic[a][c]*val
return -1
ans=[]
for [a,b] in queries:
ans.append(dfs(a,b,set()))
return ans
# 二、带权并查集作法
class Solution:
def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
f = {} #记录每个结点的root
d = {} #记录每个结点到root的权
def find(x): #找到x的根节点并整理
f.setdefault(x, x)
d.setdefault(x,1)
if x != f[x]:
t = f[x]
f[x] = find(t)
d[x] *= d[t]
return f[x]
return x
def union(A, B, value):
a, b = find(A), find(B)
if a != b:
f[a] = b # a 的根结点是b
d[a] = d[B] / d[A] * value # a在b树上的权
def check(x, y):
if x not in f or y not in f:
return -1.0
a, b = find(x), find(y)
if a != b: return -1.0 #ab不在一棵树
return d[x] / d[y]
for i,nums in enumerate(equations):
union(nums[0],nums[1],values[i])
ans=[]
for x,y in queries:
ans.append(check(x,y))
return ans
#第一反应赋值，不行
#并查集是一种树型的数据结构，用于处理一些不相交集合（disjoint sets）的合并及查询问题。常常在使用中以森林来表示。
# dic.setdefault(key,default=None) 可类似于 dic.get()
# 如果键不存在于字典中，将会添加键并将值设为默认值。
# 并查集不懂
547.省份数量
class Solution:
def findCircleNum(self, isConnected: List[List[int]]) -> int:
dic=collections.defaultdict(set)
n=len(isConnected)
for i in range(n): #建立图
for j in range(n):
if i!=j and isConnected[i][j]==1:
dic[i].add(j)
dic[j].add(i)
visited=[]
ans=0
def dfs(i):
if i not in visited:
visited.append(i)
for j in dic[i]:
dfs(j)
for i in range(n): #查找省份
if i not in visited:
dfs(i)
ans+=1
#print(visited)
#print([i for i in dic.items()])
return ans
# hh~
189.旋转数组
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
k%=len(nums)
k*=-1
nums[:]=nums[k:]+nums[:k]
# nums[:]会指向新的内存空间，不能直接nums
123.买卖股票的最佳时机 III
一份股票，两次交易，求最大利润
https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/
class Solution(object):
def maxProfit(self, prices):
if not prices: return 0
n=len(prices)
dp=[[0]*n for _ in range(3)] #DP表为最大利润
for k in range(1,3):
pre_max=-prices[0]
for i in range(1,n):
pre_max=max(pre_max,dp[k-1][i-1]-prices[i])
dp[k][i]=max(dp[k][i-1],pre_max+prices[i])
return dp[-1][-1]
#这个DP的模板可以解决很多问题了
#pre_max=max(pre_max,dp[k-1][i-1]-prices[i])状态转移有些抽象啊
#[3,3,5,0,0,3,1,4]的DP表：
#[[0, 0, 0, 0, 0, 0, 0, 0],
# [0, 0, 2, 2, 2, 3, 3, 4],
# [0, 0, 2, 2, 2, 5, 5, 6]]
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n1, y1 = 0, -float("INF")
n2, y2 = 0, -float("INF")
for p in prices:
if y2 + p > n2:
n2 = y2 + p
if n1 - p > y2:
y2 = n1 - p
if y1 + p > n1:
n1 = y1 + p
if -p > y1:
y1 = -p
# y1, n1, y2, n2 = max(y1, -p), max(n1, y1 + p), max(y2, n1 - p), max(n2, y2 + p)
return max(n1, n2)
# copy
228.汇总区间
class Solution:
def summaryRanges(self, nums: List[int]) -> List[str]:
left,right,n=0,0,len(nums)
ans=[]
while right<n:
while right<n-1 and nums[right+1]-nums[right]==1:
right+=1
if right==left:
ans.append(str(nums[left]))
else:
ans.append(str(nums[left])+'->'+str(nums[right]))
right+=1
left=right
return ans
# （两个while）+（right指针放区间内的右侧），解决了：后面读不出来，或者list访问越界
11-20
1202.交换字符串中的元素⭐
给你一个字符串 s，以及该字符串中的一些「索引对」数组 pairs，其中 pairs[i] = [a, b] 表示字符串中的两个索引（编号从 0 开始）。
你可以 任意多次交换 在 pairs 中任意一对索引处的字符。
返回在经过若干次交换后，s 可以变成的按字典序最小的字符串。
class Solution:
def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
length=len(s)
p=[i for i in range(length)] #初始化，只记录根节点
def find(x):
while x!=p[x]:
p[x]=p[p[x]]
x=p[x]
return x
for a_id,b_id in pairs: #开始合并
roota = find(a_id)
rootb = find(b_id)
if roota == rootb:
continue
p[rootb] = roota
# tmp是相同根的容器
tmp=collections.defaultdict(list)
for i in range(length):
root=find(i)
tmp[root].append(i)
ans=list(s)
for same_idxs in tmp.values():
same_idxs.sort()
select_str=[s[i] for i in same_idxs]
select_str.sort()
for i,idx in enumerate(same_idxs):
ans[idx]=select_str[i]
return "".join(ans)
#关于本题：
#1.当成一个图问题
#2.索引对的交换具有传递性
#3.对于连通的索引直接排序，不连通的不能变动
#关于并查集：
#并查集解决一些元素分组问题，利用合并查询处理不相交的集合
#路径压缩：把节点的父节点设为根节点
#参考：https://zhuanlan.zhihu.com/p/93647900/
#暴力超时：
class Solution:
def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
q=deque([[i for i in s]])
ans=[]
while q:
tmp=q.popleft()
ans.append(tmp)
for i,j in pairs:
t=tmp.copy()
t[i],t[j]=t[j],t[i]
if t not in ans:
q.append(t)
return min([''.join(i) for i in ans])
684.冗余连接
class Solution:
def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
dic=collections.defaultdict(set)
for i in range(1,len(edges)+1):
dic[i].add(i) #并查集初始化
for x,y in edges:
if dic[x]!=dic[y]:
dic[x]|=dic[y] #合并集合
for z in dic[y]:
dic[z]=dic[x]
else: #x,y会形成闭环
return [x,y]
#无向图
803.打砖块
#并查集，或DFS
1232.缀点成线
class Solution:
def checkStraightLine(self, coordinates: List[List[int]]) -> bool:
x1,y1=coordinates[0][0],coordinates[0][1]
x2,y2=coordinates[1][0], coordinates[1][1]
for xi,yi in coordinates[2:]:
if (yi-y1)*(x2-x1)!=(y2-y1)*(xi-x1):
return False
return True
721.账户合并
#思路：建立并查集，将可以连接的account合并。
class Solution:
def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
f={}
def find(x):
f.setdefault(x,x) #不存在 key=x 就初始化
while f[x]!=x:
f[x]=f[f[x]]
x=f[x]
return x
def union(x,y):
f[find(x)]=find(y) #将x连到y的根上
visited={}
n=len(accounts)
for i,account in enumerate(accounts): #进行连接
name,email=account[0],account[1:]
for e in email:
if e in visited:
union(i,visited[e])
else:
visited[e]=i
disjointSet=collections.defaultdict(set)
for i in range(n):
root=find(i)
for es in accounts[i][1:]:
disjointSet[root].add(es)
#print(disjointSet)
return [[accounts[key][0]]+list(sorted(val)) for key,val in disjointSet.items()]
1584.连接所有点的最小费用⭐
给你一个 points 数组，表示 2D 平面上的一些点，其中 points[i] = [xi, yi] 。
连接点 [xi, yi] 和点 [xj, yj] 的费用为它们之间的 曼哈顿距离 ：|xi - xj| + |yi - yj| ，其中 |val| 表示 val 的绝对值。
请你返回将所有点连接的最小总费用。只有任意两点之间 有且仅有 一条简单路径时，才认为所有点都已连接。
#方法一：最小生成树prim算法
#每次迭代选择代价最小的边对应的点，加入到树中。
#算法从某一个顶点s开始，逐渐覆盖整个连通网的所有顶点。
class Solution:
def get_dist(self,a,b):
return abs(a[0]-b[0])+abs(a[1]-b[1])
def prim(self,points):
n=len(points)
dist=[float('inf')]*n
dist[0]=0
visited=[]
ans=0
for _ in range(n):
# 离集合最近的点
t = min([i for i in range(n) if not vis[i]], key = lambda x:(dist[x], x))
vis[t] = 1
ans += dist[t]
# 用离集合最近的点更新其他的点到集合的距离
for i in range(n):
if not vis[i]:
dist[i] = min(dist[i], self.get_dist(points[i], points[t]))
return ans
def minCostConnectPoints(self, points: List[List[int]]) -> int:
return self.prim(points)
#完全图：每对顶点都有边连接。
#方法二：最小生成树kruskal算法
#每迭代一次就选择一条满足条件的最小代价边，加入到最小生成树的边集合里。
class Solution:
def minCostConnectPoints(self, points: List[List[int]]) -> int:
def dist(a,b): #math中也有个dist函数
return abs(a[0]-b[0])+abs(a[1]-b[1])
n=len(points)
cost_list=[(dist(points[i],points[j]),i,j) for i in range(n-1) for j in range(i,n)]
cost_list.sort(key=lambda x:x[0])
f={} #记录每个点的根节点
def find(x): #仅find和初始化功能
f.setdefault(x,x)
while x!=f[x]:
f[x]=f[f[x]]
x=f[x]
return x
def union(x,y):
f[find(x)]=find(y)
ans=0
for cost,x,y in cost_list:
if find(x)==find(y): continue #两个点在树中
union(x,y)
ans+=cost
return ans
#会默写这段代码了，hh
628.三个数的最大乘积
class Solution(object):
def maximumProduct(self, nums):
nums.sort()
return max(nums[-1]*nums[-2]*nums[-3],nums[0]*nums[1]*nums[-1])
21-31
1489.关键边和伪关键边
给定n个点的带权无向连通图。
求关键边（每种最小生成树都有的边）
伪关键边（出现在最小生成树中，但不必全部出现）
# 并查集模板
class UnionFind:
def __init__(self, n: int):
self.parent = list(range(n))
self.size = [1] * n
self.n = n
# 当前连通分量数目
self.setCount = n
def findset(self, x: int) -> int:
if self.parent[x] == x:
return x
self.parent[x] = self.findset(self.parent[x])
return self.parent[x]
def unite(self, x: int, y: int) -> bool:
x, y = self.findset(x), self.findset(y)
if x == y:
return False
if self.size[x] < self.size[y]:
x, y = y, x
self.parent[y] = x
self.size[x] += self.size[y]
self.setCount -= 1
return True
def connected(self, x: int, y: int) -> bool:
x, y = self.findset(x), self.findset(y)
return x == y
# Tarjan 算法求桥边模版
class TarjanSCC:
def __init__(self, n: int, edges: List[List[int]], edgesId: List[List[int]]):
self.n = n
self.edges = edges
self.edgesId = edgesId
self.low = [-1] * n
self.dfn = [-1] * n
self.ans = list()
self.ts = -1
def getCuttingEdge(self) -> List[int]:
for i in range(self.n):
if self.dfn[i] == -1:
self.pGetCuttingEdge(i, -1)
return self.ans
def pGetCuttingEdge(self, u: int, parentEdgeId: int):
self.ts += 1
self.low[u] = self.dfn[u] = self.ts
for v, iden in zip(self.edges[u], self.edgesId[u]):
if self.dfn[v] == -1:
self.pGetCuttingEdge(v, iden)
self.low[u] = min(self.low[u], self.low[v])
if self.low[v] > self.dfn[u]:
self.ans.append(iden)
elif iden != parentEdgeId:
self.low[u] = min(self.low[u], self.dfn[v])
class Solution:
def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:
m = len(edges)
for i, edge in enumerate(edges):
edge.append(i)
edges.sort(key=lambda x: x[2])
uf = UnionFind(n)
ans0 = list()
label = [0] * m
i = 0
while i < m:
# 找出所有权值为 w 的边，下标范围为 [i, j)
w = edges[i][2]
j = i
while j < m and edges[j][2] == edges[i][2]:
j += 1
# 存储每个连通分量在图 G 中的编号
compToId = dict()
# 图 G 的节点数
gn = 0
for k in range(i, j):
x = uf.findset(edges[k][0])
y = uf.findset(edges[k][1])
if x != y:
if x not in compToId:
compToId[x] = gn
gn += 1
if y not in compToId:
compToId[y] = gn
gn += 1
else:
# 将自环边标记为 -1
label[edges[k][3]] = -1
# 图 G 的边
gm = collections.defaultdict(list)
gmid = collections.defaultdict(list)
for k in range(i, j):
x = uf.findset(edges[k][0])
y = uf.findset(edges[k][1])
if x != y:
idx, idy = compToId[x], compToId[y]
gm[idx].append(idy)
gmid[idx].append(edges[k][3])
gm[idy].append(idx)
gmid[idy].append(edges[k][3])
bridges = TarjanSCC(gn, gm, gmid).getCuttingEdge()
# 将桥边（关键边）标记为 1
ans0.extend(bridges)
for iden in bridges:
label[iden] = 1
for k in range(i, j):
uf.unite(edges[k][0], edges[k][1])
i = j
# 未标记的边即为非桥边（伪关键边）
ans1 = [i for i in range(m) if label[i] == 0]
return [ans0, ans1]
#copy,溜了溜了
989. 数组形式的整数加法
class Solution:
def addToArrayForm(self, A: List[int], K: int) -> List[int]:
sum=0
for num in A:
sum=sum*10+num
sum+=K
return [int(i) for i in str(sum)]
1319.连通网络的操作次数
class Solution:
def makeConnected(self, n: int, connections: List[List[int]]) -> int:
if len(connections)<n-1: return -1
f={}
def find(x):
f.setdefault(x,x)
while x!=f[x]:
f[x]=f[f[x]]
x=f[x]
return x
def union(x,y):
f[find(x)]=f[y]
n-=1 #需要n-1条边才能连通网络
for x,y in connections:
if find(x)==find(y):
continue
union(x,y)
n-=1 #需要的边减少了
return n
674.最长连续递增序列
class Solution:
def findLengthOfLCIS(self, nums: List[int]) -> int:
ans=0
start=0
for i in range(len(nums)):
if i and nums[i]<=nums[i-1]:
start=i
ans=max(ans,i-start+1)
return ans
959.由斜杠划分区域
class uf:
def __init__(self,n):
self.f={}
self.cnt=n
for i in range(n):
self.f[i]=i
def find(self,x):
while x!=self.f[x]:
self.f[x]=self.f[self.f[x]]
x=self.f[x]
return x
def union(self,x,y):
if not self.connect(x,y):
self.f[self.find(x)]=self.find(y) #将x根连到y的根节点
self.cnt-=1
def connect(self,x,y):
return self.find(x)==self.find(y)
class Solution:
def regionsBySlashes(self, grid: List[str]) -> int:
n=len(grid)
u=uf(n*n*4)
def get_pos(row,col,i):
return (row*n+col)*4+i
for row in range(n):
for col in range(n):
v=grid[row][col]
if col>0:
u.union(get_pos(row,col-1,1),get_pos(row,col,3))
if row>0:
u.union(get_pos(row-1,col,2),get_pos(row,col,0))
if v=='/':
u.union(get_pos(row,col,0),get_pos(row,col,3))
u.union(get_pos(row,col,1),get_pos(row,col,2))
elif v=='\\':
u.union(get_pos(row,col,0),get_pos(row,col,1))
u.union(get_pos(row,col,2),get_pos(row,col,3))
else:
u.union(get_pos(row,col,0),get_pos(row,col,1))
u.union(get_pos(row,col,2),get_pos(row,col,3))
u.union(get_pos(row,col,1),get_pos(row,col,2))
return u.cnt
# 万能的并查集...
1128.等价多米诺骨牌对的数量
class Solution:
def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:
tmp=Counter([a*10+b if a>=b else b*10+a for a,b in dominoes])
return sum(comb(k,2) for k in tmp.values())
#特定情况下，选取特征哈希键
1579.保证图的可完全遍历⭐
Alice 和 Bob 共有一个无向图，其中包含 n 个节点和 3 种类型的边，返回可以删除的最大边数，如果 Alice 和 Bob 无法完全遍历图，则返回 -1
class uf:
def __init__(self,n):
self.f={}
self.cnt=n
for i in range(n):
self.f[i]=i
def find(self,x):
while x!=self.f[x]:
self.f[x]=self.f[self.f[x]]
x=self.f[x]
return x
def union(self,x,y):
if not self.connect(x,y):
self.f[self.find(x)]=self.find(y)
self.cnt-=1
def connect(self,x,y):
return self.find(x)==self.find(y)
class Solution:
def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:
edges.sort(key=lambda x:x[0],reverse=True)
ua,ub=uf(n),uf(n)
ans=0
for t,x,y in edges:
x,y=x-1,y-1 #对上序号
if t==3:
if ua.connect(x,y): ans+=1
else:
ua.union(x,y)
ub.union(x,y)
elif t==2:
if ub.connect(x,y): ans+=1
else: ub.union(x,y)
else:
if ua.connect(x,y): ans+=1
else: ua.union(x,y)
if ua.cnt!=1 or ub.cnt!=1: return -1
return ans
# uf 666
724.寻找数组的中心索引
class Solution:
def pivotIndex(self, nums: List[int]) -> int:
total=sum(nums)
tmp=0
for i,num in enumerate(nums):
if tmp*2+num==total: return i
tmp+=num
return -1
1631.最小体力消耗路径⭐
class Solution:
def minimumEffortPath(self, heights: List[List[int]]) -> int:
rows, cols = len(heights), len(heights[0])
edges = []
for i in range(rows):
for j in range(cols):
idx = i*cols + j
if i:
edges.append([idx,idx-cols,abs(heights[i][j]-heights[i-1][j])])
if j:
edges.append([idx,idx-1,abs(heights[i][j]-heights[i][j-1])])
edges.sort(key = lambda x:x[2])
f = {}
def find(x):
f.setdefault(x, x)
while x != f[x]:
f[x] = f[f[x]]
x = f[x]
return x
def union(x, y):
f[find(x)] = find(y)
ans = 0
for x, y, w in edges:
if find(x)==find(y):
continue
union(x, y)
ans = max(ans, w)
if find(0) == find(rows*cols-1):
break
return ans
#并查集，连通
778.水位上升的泳池中游泳
class Solution:
def swimInWater(self, grid: List[List[int]]) -> int:
f={}
def find(x):
f.setdefault(x,x)
while x!=f[x]:
f[x]=f[f[x]]
x=f[x]
return x
def union(x,y):
f[find(x)]=find(y)
rows,cols=len(grid),len(grid[0])
edges=[]
for i in range(rows):
for j in range(cols):
idx=i*cols+j
if i: edges.append([idx,idx-cols,max(grid[i][j],grid[i-1][j])])
if j: edges.append([idx,idx-1,max(grid[i][j],grid[i][j-1])])
edges.sort(key=lambda x:x[2])
ans=0
for x,y,w in edges:
if find(x)==find(y): continue
union(x,y)
ans=max(ans,w)
if find(0)==find(rows*cols-1): break
return ans
# 激动，和昨天一个题。
839. 相似字符串组
class Solution:
def numSimilarGroups(self, strs: List[str]) -> int:
def check(x,y):
cnt=0
for a,b in zip(x,y):
if a!=b: cnt+=1
if cnt>2: return False #strs中所有单词长度相同
return True
f={}
def find(x):
f.setdefault(x,x)
while x!=f[x]:
f[x]=f[f[x]]
x=f[x]
return x
def union(x,y):
f[find(x)]=find(y)
n=len(strs)
for i in range(n):
for j in range(i+1,n):
if find(i)==find(j): continue
if check(strs[i],strs[j]):
#print(strs[i],strs[j])
union(i,j)
return sum(f[i]==i for i in range(n)) #连通分量个数
# 1月打卡完成
wuliao
3.无重复字符的最长子串
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
n=len(s)
q=collections.deque()
ans=0
for i in range(n):
if s[i] not in q:
q.append(s[i])
else:
while q[0]!=s[i]:
q.popleft()
q.popleft()
q.append(s[i])
ans=max(ans,len(q))
return ans
#参照239滑动窗口问题
29.整数相除
不用乘除，mod
class Solution:
def divide(self, dividend: int, divisor: int) -> int:
flag=dividend*divisor<0
dividend=abs(dividend)
divisor=abs(divisor)
def div(dividend, divisor):
if dividend<divisor: return 0
tmp=divisor
cnt=1
while tmp+tmp<dividend: #2倍法找邻值
tmp+=tmp
cnt+=cnt
return cnt+div(dividend-tmp,divisor)
ans=div(dividend,divisor)
if flag: ans*=-1
return ans if -(1<<31)<=ans<=(1<<31)-1 else (1<<31)-1 #题意溢出更改
删除链表中的结点
class Solution:
def deleteNode(self, node):
node.val=node.next.val
node.next=node.next.next
# 等效地删除了
链表倒数第k个结点
class Solution:
def kthToLast(self, head: ListNode, k: int) -> int:
slow,fast=head,head
for i in range(k-1):
fast=fast.next
while fast.next:
slow=slow.next
fast=fast.next
return slow.val
二叉树的直径
class Solution:
def diameterOfBinaryTree(self, root: TreeNode) -> int:
self.ans=1
def depth(node): #从下往上的计算
if not node: return 0
l=depth(node.left)
r=depth(node.right)
self.ans=max(self.ans,l+r+1)
return max(l,r)+1 #当前结点最大深度
depth(root)
return self.ans-1
二叉树镜像
class Solution:
def mirrorTree(self, root: TreeNode) -> TreeNode:
if not root: return
tmp=root.left
root.left=self.mirrorTree(root.right)
root.right=self.mirrorTree(tmp)
return root
混一下
class ParkingSystem:
def __init__(self, big: int, medium: int, small: int):
self.big=big
self.medium=medium
self.small=small
def addCar(self, carType: int) -> bool:
if carType==1:
self.big-=1
return self.big>=0
elif carType==2:
self.medium-=1
return self.medium>=0
else:
self.small-=1
return self.small>=0
#1.复习一下类...
#2.python str 还有replace()
#3.zip打包，一个for里多做点事
#4.col = [max(i) for i in zip(*matrix)]
75.颜色分类
一趟扫描，排序0，1，2
class Solution:
def sortColors(self, nums: List[int]) -> None:
p0, p2 = 0, len(nums) - 1
i = 0
while i <= p2:
while i <= p2 and nums[i] == 2:
nums[i], nums[p2] = nums[p2], nums[i]
p2 -= 1
if nums[i] == 0:
nums[i], nums[p0] = nums[p0], nums[i]
p0 += 1
i += 1
#快速排序
416.分割等和子集
class Solution:
def canPartition(self, nums: List[int]) -> bool:
n=len(nums)
if n<2: return False
total=sum(nums)
if total%2: return False
k=total//2
dp=[1]+[0]*k
for i, num in enumerate(nums):
for j in range(k, num - 1, -1):
if dp[j - num]: dp[j]=1
return True if dp[k] else False
#0-1背包
