1-10
1337. 矩阵中战斗力最弱的 K 行
1. 练习一下 functools 中的 cmp_to_key
class Solution:
def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:
n = len(mat)
ans = [i for i in range(n)]
def func(x,y):
if sum(mat[x])>sum(mat[y]):
return 1
elif sum(mat[x])<sum(mat[y]):
return -1
else:
return x>y
ans.sort(key=cmp_to_key(lambda x,y:func(x,y)))
return ans[:k]
2. 二分查找+堆，参考官方
class Solution:
def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:
m, n = len(mat[0]), len(mat)
power = []
for i in range(n):
l, r = 0, m-1
while l <= r:
mid = (l+r)//2
if mat[i][mid]==0:
r = mid - 1
else:
l = mid + 1
power.append((l, i))
#print(power)
heapq.heapify(power)
ans = []
for i in range(k):
ans.append(heapq.heappop(power)[1])
return ans
743. 网络延迟时间
从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1 。
0. 海象运算符
3.8版本新增的语法 := 可在表达式内部为变量赋值
例 1 ：
age = 20
if age > 18:
print("")
if (age := 20) > 18:
print("")
例 2 ：
while (block := f.read(256)) != '':
process(block)
1. Dijkstra，枚举
class Solution:
def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
# 邻接矩阵
g = [[float('inf')] * n for _ in range(n)]
for x, y, time in times:
g[x - 1][y - 1] = time
# 距离数组
dist = [float('inf')] * n
dist[k - 1] = 0
# 标记数组
used = [False] * n
for _ in range(n):
# 找到未标记最近的点, 从 k 点开始
x = -1
for y, u in enumerate(used):
if not u and (x == -1 or dist[y] < dist[x]):
x = y
# 更新
used[x] = True
for y, time in enumerate(g[x]):
dist[y] = min(dist[y], dist[x] + time)
ans = max(dist)
return ans if ans < float('inf') else -1
2. Dijkstra，堆
class Solution:
def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
g = [[] for _ in range(n)]
for x, y, time in times:
g[x-1].append((y-1, time))
dist = [float('inf')] * n
dist[k-1] = 0
q = [(0, k-1)]
while q:
time, x = heapq.heappop(q)
if dist[x] < time:
continue
for y, time in g[x]:
if (d := dist[x]+time) < dist[y]:
dist[y] = d
heapq.heappush(q,(d,y))
ans = max(dist)
return ans if ans <float('inf') else -1
581. 最短无序连续子数组
找出最短的需要排序的子数组，使整个数组升序排列
1. 双指针
class Solution:
def findUnsortedSubarray(self, nums: List[int]) -> int:
n = len(nums)
maxn, minn = float('-inf'), float('inf')
l, r = -1, -1
for i in range(n):
if maxn > nums[i]:
r = i
else:
maxn = nums[i]
if minn < nums[n-i-1]:
l = n-i-1
else:
minn = nums[n-i-1]
return 0 if r==-1 else r-l+1
611. 有效三角形的个数
统计数组中可构成三角形的三元组个数。
1. 排序 + 二分查找
class Solution:
def triangleNumber(self, nums: List[int]) -> int:
n = len(nums)
nums.sort()
ans = 0
for i in range(n):
for j in range(i+1,n):
l, r, k = j+1, n-1, j
while l<=r:
mid = (l+r)//2
if nums[mid] < nums[i] + nums[j]:
l = mid + 1
k = mid
else:
r = mid - 1
ans += k-j
#print(k,j)
return ans
#时间复杂度：n2logn
2. 排序 + 双指针
class Solution:
def triangleNumber(self, nums: List[int]) -> int:
n = len(nums)
nums.sort()
ans = 0
for i in range(n-2):
if nums[i] == 0: continue
k = i + 1 # k 仅在第一层循环初始化
for j in range(i+1, n-1):
while k < n and nums[i]+nums[j] > nums[k]:
k += 1 # 对于每个i, 该语句最多执行(<n)次
ans += k-j-1
return ans
#时间复杂度：n2
802. 找到最终的安全状态
判断环
1. dfs + 标记
class Solution:
def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
# 0：该节点尚未被访问；
# 1：该节点位于递归栈中，或者在某个环上；
# 2：该节点搜索完毕，是一个安全节点。
n = len(graph)
color = [0] * n
def dfs(x): #判断 safe 的函数
if color[x] > 0: return color[x] == 2
color[x] = 1
for y in graph[x]:
if not dfs(y):
return False
color[x] = 2
return True
return [i for i in range(n) if dfs(i)]
2. 拓扑排序
class Solution:
def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
n = len(graph)
out = [0]*n
edges = defaultdict(list)
for i, nodes in enumerate(graph):
for node in nodes:
edges[node].append(i)
out[i] += 1
q = deque([]) #两端更快pop，属于collections
for i in range(n):
if out[i] == 0:
q.append(i) #出度为0，绝对安全的结点
while q:
node = q.popleft()
for x in edges[node]:
out[x] -= 1 #该节点的一条出边，安全
if not out[x]:
q.append(x)
return [i for i in range(n) if out[i]==0]
847. 访问所有节点的最短路径⭐
无向连通图，从任一节点开始访问所有结点的最短路径。
1. 状态压缩 + bfs
class Solution:
def shortestPathLength(self, graph: List[List[int]]) -> int:
n = len(graph)
q = deque((i, 1<<i, 0) for i in range(n)) # (编号，状态，走过距离)
seen = {(i, 1<<i) for i in range(n)}
# bfs，通常通过队列实现
while q:
u, mask, dist = q.popleft()
if mask == (1<<n) - 1: #所有节点已访问，mask 全为1
return dist
for v in graph[u]:
mask_v = mask | (1<<v) # 将 状态 第v位 置1
if (v, mask_v) not in seen:
q.append((v, mask_v, dist+1))
seen.add((v, mask_v))
return ans
状态压缩
用一个变量来表示当前状态，比较常用的方式是利用一个 n 位 k 进制数 mask 表示当前 n 个节点的所处的 k 个不同状态。对于本题而言，某个节点只需要记录是否遍历过，所以利用二进制即可。
666，将状态压缩的mask作为bfs队列的参数，能解决这种类似旅行商问题
457. 环形数组是否存在循环
1. 快慢指针
class Solution:
def circularArrayLoop(self, nums: List[int]) -> bool:
n = len(nums)
def next(x):
return (x+nums[x])%n
for i,num in enumerate(nums):
if num == 0: continue
l, r = i, next(i)
while nums[l]*nums[r]>0 and nums[l]*nums[next(r)]>0:
if l == r:
if l == next(l):
break
return True
l = next(l)
r = next(next(r))
#将访问过的结点置0
vis = i
while nums[vis] * nums[next(vis)] > 0:
nums[vis] = 0
vis = next(vis)
return False
1137. 第 N 个泰波那契数
T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2
1. 三个变量
class Solution:
def tribonacci(self, n: int) -> int:
a, b, c = 0, 1, 1
for i in range(n) :
a, b, c = b, c, a+b+c
return a
2. 缓存
class Solution:
def tribonacci(self, n: int) -> int:
a = [0, 1, 1]
@lru_cache(None)
def tb(n):
if n<3:
return a[n]
else:
return tb(n-1)+tb(n-2)+tb(n-3)
return tb(n)
313. 超级丑数⭐
丑数：只包含质因数 primes 的正整数。
1. 最小堆
from heapq import *
class Solution:
def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:
seen = {1}
heap = [1]
for i in range(n):
ugly = heappop(heap)
for p in primes:
if (x := p*ugly) not in seen:
seen.add(x)
heappush(heap, x)
return ugly
2. 动态规划, k指针
class Solution:
def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:
dp =[0]*(n+1)
dp[1] = 1
m = len(primes)
p = [1]*m #表示每个质因数指向dp表的指标
for i in range(2,n+1):
min_num = min(dp[p[j]]*primes[j] for j in range(m))
dp[i] = min_num
for j in range(m):
if dp[p[j]]*primes[j]==min_num:
p[j] += 1 #指针右移，已选定下一项丑数
return dp[n]
413. 等差数列划分
class Solution:
def numberOfArithmeticSlices(self, nums: List[int]) -> int:
n = len(nums)
if n<3: return 0
ans = 0
arr = [nums[i]-nums[i-1] for i in range(1,n)]
l = 0
for r in range(n-1):
if arr[l] != arr[r]:
ans += sum([i for i in range(1,r-l) if r-l>1])
l = r
ans += sum([i for i in range(1,r-l+1) if r>l])
return ans
11-20
446. 等差数列划分 II - 子序列
1. 动态规划 + 哈希表
class Solution:
def numberOfArithmeticSlices(self, nums: List[int]) -> int:
n = len(nums)
ans = 0
d =[defaultdict(int) for i in range(n)]
for i in range(1, n):
for j in range(i):
delta = nums[i]-nums[j]
d[i][delta] += 1
d[i][delta] += d[j][delta]
ans += d[j][delta] #注释1
return ans
#当3个等差变为4个时，子序列多了3个，同理类推
516. 最长回文子序列
1. 动态规划
# 动态规划核心：dp表，状态转移方程
# 最终结果出现在 dp表 右上角
class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
n = len(s)
dp = [[0]*n for i in range(n)]
for i in range(n-1,-1,-1):
dp[i][i] = 1
for j in range(i+1,n):
if s[i] == s[j]:
dp[i][j] = dp[i+1][j-1] + 2
else:
dp[i][j] = max(dp[i+1][j],dp[i][j-1])
return dp[0][n-1]
233. 数字 1 的个数
给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。
1. 数学
#个位：每 10 个数 1 个一
#十位：每 100 个数 10 个一
#百位：每 1000 个数 100 个一
class Solution:
def countDigitOne(self, n: int) -> int:
ans = 0
k = 1
while n >= k:
s, m = n//(k*10), n%(k*10)
ans += s*k + min(k, max(m-k+1, 0))
k *= 10
return ans
1583. 统计不开心的朋友
1. 模拟
class Solution:
def unhappyFriends(self, n: int, preferences: List[List[int]], pairs: List[List[int]]) -> int:
h = {}
for x, y in pairs:
h[x] = y
h[y] = x
# order[x][y] 表示y在x的朋友列表中的亲近程度下标，0最大
order = [[0]*n for _ in range(n)]
for i in range(n):
for j in range(n-1):
order[i][preferences[i][j]] = j
ans = 0
for x in range(n):
y = h[x]
index = order[x][y]
for i in range(index):
u = preferences[x][i]
v = h[u]
if order[u][x] < order[u][v]:
ans += 1
break
return ans
576. 出界的路径数
1. 动态规划
class Solution:
def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:
dp = [defaultdict(int) for _ in range(maxMove+1)]
dp[0][(startRow,startColumn)] = 1
ans = 0
for step in range(maxMove):
for i, j in dp[step]:
cnt = dp[step][(i,j)]
for x, y in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:
if 0<=x<m and 0<=y<n:
dp[step+1][(x,y)] += cnt
else:
ans += cnt
return ans % (10**9 +7)
# dp 表：第 step 步到达 {位置：路径数} 的表
526. 优美的排列
1. 回溯
class Solution:
def countArrangement(self, n: int) -> int:
h = defaultdict(list)
for i in range(1,n+1):
for j in range(1,n+1):
if i%j==0 or j%i==0:
h[i].append(j)
ans = 0
vis = set()
def bk(i):
if i == n+1:
nonlocal ans
ans += 1
return
for x in h[i]:
if x not in vis:
vis.add(x)
bk(i+1)
vis.discard(x)
bk(1)
return ans
# global 将变量声明为全局变量
# nonlocal 将变量声明为外层变量（外层函数的局部变量，不能是全局变量）
551. 学生出勤记录 I
class Solution:
def checkRecord(self, s: str) -> bool:
return (s.count('A')<2 and "LLL" not in s)
552. 学生出勤记录 II⭐
先画出 状态转移图，编译原理课上学过…
#本题求的是所有可能的数量
#状态a: 缺勤(A)0，末尾的迟到(L)0
#状态b: 缺勤(A)0，末尾的迟到(L)1
#状态c: 缺勤(A)0，末尾的迟到(L)2
#状态d: 缺勤(A)1，末尾的迟到(L)0
#状态e: 缺勤(A)1，末尾的迟到(L)1
#状态f: 缺勤(A)1，末尾的迟到(L)2
MOD = 10**9+7
class Solution:
def checkRecord(self, n: int) -> int:
a,b,c,d,e,f = 1,0,0,0,0,0
for i in range(n):
a,b,c,d,e,f = a+b+c,a,b,a+b+c+d+e+f,d,e
a %= MOD
b %= MOD
c %= MOD
d %= MOD
e %= MOD
f %= MOD
#print(i,a,b,c,d,e,f)
return (a+b+c+d+e+f)%MOD
345. 反转字符串中的元音字母
1. 双指针
class Solution:
def reverseVowels(self, s: str) -> str:
def check(c):
return c not in "aeiouAEIOU"
n = len(s)
s = list(s)
l, r = 0, n-1
while l < r:
while l<n and check(s[l]):
l += 1
while r>0 and check(s[r]):
r -= 1
if l < r:
s[l],s[r] = s[r], s[l]
l += 1
r -= 1
return "".join(s)
541. 反转字符串 II
给定一个字符串 s 和一个整数 k，从字符串开头算起，每 2k 个字符反转前 k 个字符。
- 如果剩余字符少于
k个，则将剩余字符全部反转。 - 如果剩余字符小于
2k但大于或等于k个，则反转前k个字符，其余字符保持原样。
1. 双指针
class Solution:
def reverseStr(self, s: str, k: int) -> str:
l, r = 0, 0
s = list(s)
n = len(s)
while r <= n:
if r - l == 2*k:
s[l:l+k] = s[l:l+k][::-1]
l = r
r += 1
if l!=n:
if n-l<k:
s[l:] = s[l:][::-1]
else:
s[l:l+k] = s[l:l+k][::-1]
return "".join(s)
2. 模拟
class Solution:
def reverseStr(self, s: str, k: int) -> str:
s = list(s)
for i in range(0,len(s),2*k):
l[i:i+k] = l[i:i+k][::-1]
return "".join(s)
21-31
443. 压缩字符串
class Solution:
def compress(self, chars: List[str]) -> int:
n = len(chars)
l, r = 0, 0
p = 0
while l < n:
while r < n and chars[l] == chars[r]:
r += 1
chars[p] = chars[l]
p += 1
if r-l>1:
for c in str(r-l):
chars[p] = c
p += 1
l = r
return p
789. 逃脱阻碍者
class Solution:
def escapeGhosts(self, ghosts: List[List[int]], target: List[int]) -> bool:
d = abs(target[0]) + abs(target[1])
for x,y in ghosts:
if d >= abs(target[0]-x)+abs(target[1]-y):
return False
return True
1646. 获取生成数组中的最大值
class Solution:
def getMaximumGenerated(self, n: int) -> int:
if not n: return 0
arr = [0, 1]
for i in range(2,n+1):
if i%2:
arr.append(arr[i//2]+arr[i//2+1])
else:
arr.append(arr[i//2])
return max(arr)
787. K 站中转内最便宜的航班⭐
1. 动态规划
class Solution:
def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
dp = [float('inf') for i in range(n)]
dp[src] = 0
for i in range(k+1):
tmp = dp[:]
for u,v,w in flights:
dp[v] = min (dp[v],tmp[u]+w)
return dp[dst] if dp[dst] != float('inf') else -1
2. DFS
超时
class Solution:
def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
res = []
@lru_cache(None)
def dfs(k,v,cur):
if k==-1:
return
if cur == dst:
res.append(v)
for a,b,w in flights:
if a == cur:
dfs(k-1,v+w,b)
dfs(k+1, 0, src)
return -1 if not res else min(res)
3. BFS + 堆
超时
from heapq import *
from collections import defaultdict
class Solution:
def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
if src == dst: return 0
g = defaultdict(dict)
for u,v,w in flights:
g[u][v] = w
q = [(0,0,src)]
while q:
cost, step, cur = heappop(q)
if step>k+1:
continue
if cur == dst:
return cost
for key, val in g[cur].items():
heappush(q,(cost+val,step+1,key))
return -1
797. 所有可能的路径
本题：有向无环图，2 <= n <= 15，求出所有可能
而上题 1 <= n <= 100，求的是最值，动态规划最优
1. DFS
class Solution:
def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
n = len(graph)
res = []
def dfs(arr,cur):
if cur == n-1:
res.append(arr[:])
return
for x in graph[cur]:
dfs(arr+[x],x)
dfs([0], 0)
return res
2. BFS
class Solution:
def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
n = len(graph)
q = deque([[0]])
res = []
while q:
path = q.popleft()
if path[-1] == n-1:
res.append(path)
continue
for nxt in graph[path[-1]]:
q.append(path+[nxt])
return res
881. 救生艇
1. 双指针
class Solution:
def numRescueBoats(self, people: List[int], limit: int) -> int:
people.sort()
l, r = 0, len(people)-1
res = 0
while l <= r:
if people[l]+people[r] > limit:
r -= 1
else:
r -= 1
l += 1
res += 1
return res
295. 数据流的中位数
1. 普通做法
from bisect import insort_left
class MedianFinder:
def __init__(self):
self.arr = []
self.n = 0
def addNum(self, num: int) -> None:
insort_left(self.arr,num)
self.n += 1
def findMedian(self) -> float:
if self.n%2:
return self.arr[self.n//2]
else:
return (self.arr[self.n//2]+self.arr[self.n//2-1])/2
2. 堆
from heapq import *
class MedianFinder:
def __init__(self):
self.A = [] # 较大的一半，先放入，A[0] 总为最小
self.B = [] # 较小的一半，后放入，-B[0]总为最大
def addNum(self, num: int) -> None:
if len(self.A) != len(self.B):
heappush(self.B, -heappushpop(self.A, num))
else:
heappush(self.A, -heappushpop(self.B, -num))
def findMedian(self) -> float:
return self.A[0] if len(self.A) != len(self.B) else (self.A[0] - self.B[0]) / 2.0
1480. 一维数组的动态和
class Solution:
def runningSum(self, nums: List[int]) -> List[int]:
pre = 0
res = []
for num in nums:
pre += num
res.append(pre)
return res
class Solution:
def runningSum(self, nums: List[int]) -> List[int]:
return itertools.accumulate(nums)
1588. 所有奇数长度子数组的和
class Solution:
def sumOddLengthSubarrays(self, arr: List[int]) -> int:
n = len(arr)
ans = 0
for i in range(1,n+1,2):
for l in range(n-i+1):
ans += sum(arr[l:l+i])
return ans
528. 按权重随机选择
线段 + 二分
class Solution:
def __init__(self, w: List[int]):
self.a = list(accumulate(w))
self.s = self.a[-1]
def pickIndex(self) -> int:
x = randint(1, self.s)
return bisect_left(self.a, x)
# random.randint(x,y) 产生的随机数包括 x 和 y
1109. 航班预订统计⭐
记得清的差分只有两道题… 今天，昨天，相关标签：数组，前缀和
class Solution:
def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:
nums = [0]*n
for l,r,v in bookings:
nums[l-1] += v
if r < n:
nums[r] -= v
return list(accumulate(nums))
前缀和666，用哈希表硬暴力会超时
