做题记录
题目1
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]] 输出：[[1,6],[8,10],[15,18]] 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]. 示例 2：
输入：intervals = [[1,4],[4,5]] 输出：[[1,5]] 解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
提示：
1 <= intervals.length <= 104 intervals[i].length == 2 0 <= starti <= endi <= 104
我的Attempt1
class Solution:
def merge(self, intervals) :
result_list = []
flag_list = [0]*len(intervals)
for temp1 in intervals:
for temp2 in intervals:
if temp1 != temp2:
if (temp2[0] <= temp1[1]) and (temp2[0] >= temp1[0]):
if temp2[1] > temp1[1]:
extended_list = [temp1[0],temp2[1]]
result_list.append(extended_list)
flag_list[intervals.index(temp1)] = 1
flag_list[intervals.index(temp2)] = 1
else:
extended_list = [temp1[0],temp1[1]]
result_list.append(extended_list)
flag_list[intervals.index(temp1)] = 1
flag_list[intervals.index(temp2)] = 1
for i in range(len(flag_list)):
if flag_list[i] == 0:
result_list.append(intervals[i])
result_list_sorted = []
for i in result_list:
if i not in result_list_sorted:
result_list_sorted.append(i)
return result_list_sorted
官方解法
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
intervals.sort(key=lambda x: x[0])
merged = []
for interval in intervals:
# 如果列表为空，或者当前区间与上一区间不重合，直接添加
if not merged or merged[-1][1] < interval[0]:
merged.append(interval)
else:
# 否则的话，我们就可以与上一区间进行合并
merged[-1][1] = max(merged[-1][1], interval[1])
return merged
看了官方解法没有看代码实现之后写的解法
这个要比官方解法慢个好多
class Solution:
def merge(self, intervals) :
intervals.sort(key = lambda x: x[0])
merged = []
merged.append(intervals[0])
for i in intervals:
if i[0]<= merged[-1][1]:
temp = [merged[-1][0],max(merged[-1][1],i[1])]
print(merged[-1][1])
print(i[1])
print(temp)
merged.pop(-1)
merged.append(temp)
else:
merged.append(i)
return merged
obj = Solution()
print(obj.merge([[1,3],[2,6],[8,10],[15,18]]))
学到的
1 遇到问题不要总是想着暴力解决，比如在这个题目中先排个序或许就会更好。
2 注意时间和空间消耗，尽量减少中间变量的出现。
题目2
给你一个由 ’1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例 1：
输入：grid = [ [“1”,”1”,”1”,”1”,”0”], [“1”,”1”,”0”,”1”,”0”], [“1”,”1”,”0”,”0”,”0”], [“0”,”0”,”0”,”0”,”0”] ] 输出：1 示例 2：
输入：grid = [ [“1”,”1”,”0”,”0”,”0”], [“1”,”1”,”0”,”0”,”0”], [“0”,”0”,”1”,”0”,”0”], [“0”,”0”,”0”,”1”,”1”] ] 输出：3
提示：
m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] 的值为 ‘0’ 或 ‘1’
官方解法
DFS
class Solution:
def dfs(self, grid, r, c):
grid[r][c] = 0
nr, nc = len(grid), len(grid[0])
for x, y in [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]:
if 0 <= x < nr and 0 <= y < nc and grid[x][y] == "1":
self.dfs(grid, x, y)
def numIslands(self, grid: List[List[str]]) -> int:
nr = len(grid)
if nr == 0:
return 0
nc = len(grid[0])
num_islands = 0
for r in range(nr):
for c in range(nc):
if grid[r][c] == "1":
num_islands += 1
self.dfs(grid, r, c)
return num_islands
本科的时候写代码写的太差现在做题遭报应了。 这个题目看了半天才能看懂，下一个感悟是在看不懂解题方法的时候可以通过使用测试用例跟着代码一步一步向下推进而进行。
这个解法可以看作当通过递归找到一片岛的时候，使用海水将这片岛给淹没，然后再去找下一片岛。
BFS
这个BFS的代码贴一下，但是我看起来反正和DFS是一样的。。
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
nr = len(grid)
if nr == 0:
return 0
nc = len(grid[0])
num_islands = 0
for r in range(nr):
for c in range(nc):
if grid[r][c] == "1":
num_islands += 1
grid[r][c] = "0"
neighbors = collections.deque([(r, c)])
while neighbors:
row, col = neighbors.popleft()
for x, y in [(row - 1, col), (row + 1, col), (row, col - 1), (row, col + 1)]:
if 0 <= x < nr and 0 <= y < nc and grid[x][y] == "1":
neighbors.append((x, y))
grid[x][y] = "0"
return num_islands
并查集
class UnionFind:
def __init__(self, grid):
m, n =len(grid),len(grid[0])
self.count = 0
self.parent = [-1]* (m*n)
self.rank = [0] *(m*n)
for i in range(m):
for j in range(n):
if grid[i][j] == "1":
self.parent[i*n+j] = i*n+j
self.count+=1
def find(self, i):
if self.parent[i] != i:
self.parent[i] = self.find(self.parent[i])
return self.parent[i]
def union(self, x, y):
rootx = self.find(x)
rooty = self.find(y)
if rootx != rooty:
if self.rank[rootx] < self.rank[rooty]:
rootx, rooty = rooty, rootx
self.parent[rooty] = rootx
if self.rank[rootx] == self.rank[rooty]:
rootx, rooty = rooty, rootx
self.parent[rooty] = rootx
def getCount(self):
return self.count
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
nr = len(grid)
if nr ==0:
return 0
nc = len(grid[0])
uf = UnionFind(grid)
num_islands = 0
for r in range(nr):
for c in range(nc):
if grid[r][c] == '1':
grid[r][c] = '0'
for x,y in [(r-1, c), (r + 1, c), (r, c - 1), (r, c + 1)]:
if 0 <= x < nr and 0 <=y < nc and grid[x][y] == "1":
uf.union(r*nc+c, x*nc+y)
其他内容
函数的声明方式
刚刚开始做题的时候一直搞不懂这个是啥意思，后来翻到了python的官方文档，在3.5版本之后有介绍。