前言:每天写这个的目的就是能够每天回忆一遍今天做过的题,如果哪里需要总结的单独拿出来
0X00 leetcode 做了 5 道
0X01 每道题的小小总结
动态规划是道难啃的题目,我感觉每天都要做一做
323. Number of Connected Components in an Undirected Graph
并查集模板题目
class UnionFind:
def __init__(self, n):
self.father = [i for i in range(n)]
self.count = n
def find(self, x):
if self.father[x] != x:
self.father[x] = self.find(self.father[x])
return self.father[x]
def union(self, x, y):
fx, fy = self.find(x), self.find(y)
if fx != fy:
self.count -= 1
self.father[fy] = fx
class Solution:
def countComponents(self, n: int, edges: List[List[int]]) -> int:
uf = UnionFind(n)
for x, y in edges:
uf.union(x, y)
return uf.count
261. Graph Valid Tree
也是动态规划的模板题,
坑的地方在: 不能有离散的点
class UnionFind:
def __init__(self, n):
self.fathers = [i for i in range(n)]
self.count = n
def find(self, x):
if self.fathers[x] != x:
self.fathers[x] = self.find(self.fathers[x])
return self.fathers[x]
def union(self, x, y):
fx, fy = self.find(x), self.find(y)
if fx == fy:
return False
self.fathers[fy] = fx
self.count -= 1
return True
class Solution:
def validTree(self, n: int, edges: List[List[int]]) -> bool:
uf = UnionFind(n)
for x, y in edges:
if not uf.union(x, y):
return False
return uf.count == 1
305. Number of Islands II
关键在于「集合合并」, 所以是并查集的题目,
不过是一个二维并查集
class UnionFind:
def __init__(self, m, n):
l = m * n
self.m = m
self.n = n
self.fathers = [i for i in range(l)]
def pos2idx(self, p):
x, y = p
return x * self.n + y
def find(self, idx):
if self.fathers[idx] != idx:
self.fathers[idx] = self.find(self.fathers[idx])
return self.fathers[idx]
def union(self, p1, p2):
idx1, idx2 = self.pos2idx(p1), self.pos2idx(p2)
f1, f2 = self.find(idx1), self.find(idx2)
if f1 == f2:
return False
self.fathers[f1] = self.fathers[f2]
return True
class Solution:
def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:
if len(positions) == 0: return [0]
lands = set()
res = []
uf = UnionFind(m, n)
count = 0
dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
for p in positions:
count += 1
idx = uf.pos2idx(p)
if idx in lands:
count -= 1
res.append(count)
continue
lands.add(idx)
x, y = p
for dx, dy in dirs:
x1, y1 = x + dx, y + dy
if x1 < 0 or y1 < 0 or x1 >= m or y1 >= n: continue
if uf.pos2idx((x1, y1)) not in lands: continue
# print("x1, y1 ", x1, y1)
if uf.union(p, (x1, y1)): count -= 1
# print("---------------")
res.append(count)
return res
关于并查集的一些小总结我都写到这里:
200. Number of Islands
标准网格型 dfs 题目,知道那个模板直接秒
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
if len(grid) == 0: return 0
m, n = len(grid), len(grid[0])
visited = [[False] * n for _ in range(m)]
count = 0
def dfs(x, y):
if x < 0 or x >= m or y < 0 or y >= n: return
if grid[x][y] == "0" or visited[x][y]: return
visited[x][y] = True
dirs = [(-1, 0), (0, 1), (1, 0), (0, -1)]
for dx, dy in dirs:
dfs(x + dx, y + dy)
for x in range(m):
for y in range(n):
if grid[x][y] == "1" and not visited[x][y]:
dfs(x, y)
count += 1
return c
300. Longest Increasing Subsequence
动态规划...每天来一道...
首先一个 O() 的做法
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
# 一维坐标型动态规划
# dp[x] 代表 包含 x 的最长子序列
# dp[x] = 从 0 ~ x -1 寻找一个比 nums[x] 小的,而且 dp 最大的
# 答案取最大值
if len(nums) == 0: return 0
m = len(nums)
dp = [1] * m
ans = 1
for i in range(1, m):
for j in range(i-1, -1, -1):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)
ans = max(ans, dp[i])
return ans
第二种解法,直接从这个序列里面找到最长上升子序列
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
if len(nums) == 0: return 0
# 维护一个最长子序列
m = len(nums)
record = [0] * m
# init
record[0] = nums[0]
ans = 1
for i in range(1, m):
left, right = 0, ans - 1
while left <= right:
mid = left + (right - left) // 2
if record[mid] == nums[i]:
left = mid
break
if record[mid] < nums[i]:
left = mid + 1
else:
right = mid - 1
record[left] = nums[i]
if left == ans:
ans += 1
return ans
record[i] 记录了 i+1 长度 的最小的那个值, 时间复杂度 O(nlogn)
这里还用到了二分查找的模板,我在这里复习一下
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left)
if nums[mid] == target:
left = mid
break
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
# 最后 left 是插入的位置
网友评论