上一篇：献芹奏曝-Python面试题
开篇的话：本文目的是收集和归纳力扣上的算法题，希望用python语言，竭我所能做到思路最清奇、代码最简洁、方法最广泛、性能最高效，了解常见题目，找到最利于记忆的答案，更加从容的应对面试。希望广思集益，共同进步。
深度优先搜索（DFS）与广度优先搜索（BFS）
一、岛屿篇
-
200. 岛屿数量（难度系数✯）
class Solution: def set_grid(self,grid,i,j): if i<0 or j<0 or i>=len(grid) or j>=len(grid[i]) or grid[i][j] == "0": return grid[i][j] = "0" self.set_grid(grid,i,j-1) #左 self.set_grid(grid,i,j+1) #右 self.set_grid(grid,i-1,j) #上 self.set_grid(grid,i+1,j) #下 def numIslands(self, grid: List[List[str]]) -> int: # 边界条件 if not grid: return 0 # 统计岛屿个数 count = 0 # 双层for 遍历每个格子 for i in range(len(grid)): for j in range(len(grid[i])): if grid[i][j] == "1": count += 1 self.set_grid(grid,i,j) return countDFS运行结果：1：耗时超过58%。2：内存超过59%
知识点/技巧:1：访问相邻结点（上、下、左、右）。2：判断base case（是否过界、是否为0）
class Solution: def set_grid(self,grid,i,j): # 设置队列 que = [] que.append((i,j)) while que: i,j=que.pop(0) grid[i][j] = "0" # 上 （i-1,j） if i>0 and grid[i-1][j] == "1": grid[i-1][j] = "0" que.append((i-1,j)) # 下 （i+1,j） if i+1<len(grid) and grid[i+1][j] == "1": grid[i+1][j] = "0" que.append((i+1,j)) # 左 （i,j-1） if j>0 and grid[i][j-1] == "1": grid[i][j-1] = "0" que.append((i,j-1)) # 右 （i,j+1） if j+1<len(grid[i]) and grid[i][j+1] == "1": grid[i][j+1] = "0" que.append((i,j+1)) def numIslands(self, grid: List[List[str]]) -> int: # 边界条件 if not grid: return 0 # 统计岛屿个数 count = 0 # 双层for 遍历每个格子 for i in range(len(grid)): for j in range(len(grid[i])): if grid[i][j] == "1": count += 1 self.set_grid(grid,i,j) return countBFS运行结果：1：耗时超过97%。2：内存超过94%
知识点/技巧:1：通过队列实现广度优先搜索
-
463. 岛屿的周长（难度系数✯）
class Solution: def islandPerimeter(self, grid: List[List[int]]) -> int: # 普通方法，看周边情况， count = 0 for i in range(len(grid)): for j in range(len(grid[i])): if grid[i][j] == 1: count += self.get_count(grid,i,j) return count def get_count(self,grid,i,j): _count = 0 # 上 if i-1<0 or grid[i-1][j]==0: _count += 1 # 下 if i+1==len(grid) or grid[i+1][j]==0: _count += 1 # 左 if j-1<0 or grid[i][j-1]==0: _count += 1 # 右 if j+1==len(grid[i]) or grid[i][j+1]==0: _count += 1 return _count直接法运行结果：1：耗时超过65%。2：内存超过78%
知识点/技巧:1：访问相邻结点（上、下、左、右）。2：如果相邻结点是0或者边 周长+1
class Solution: count = 0 def islandPerimeter(self, grid: List[List[int]]) -> int: # DFS方法，看周边情况， for i in range(len(grid)): for j in range(len(grid[i])): if grid[i][j] == 1: self.dfs(grid,i,j) return self.count def dfs(self,grid,i,j): if i<0 or j<0 or i>=len(grid) or j>=len(grid[i]) or grid[i][j] == 2 or grid[i][j] == 0: return grid[i][j] = 2 self.get_count(grid,i,j) self.dfs(grid,i,j-1) #左 self.dfs(grid,i,j+1) #右 self.dfs(grid,i-1,j) #上 self.dfs(grid,i+1,j) #下 def get_count(self,grid,i,j): # 上 if i-1<0 or grid[i-1][j]==0: self.count += 1 # 下 if i+1==len(grid) or grid[i+1][j]==0: self.count += 1 # 左 if j-1<0 or grid[i][j-1]==0: self.count += 1 # 右 if j+1==len(grid[i]) or grid[i][j+1]==0: self.count += 1DFS运行结果：1：耗时超过8%。2：内存超过14%
知识点/技巧:1：DFS
class Solution: count = 0 def islandPerimeter(self, grid: List[List[int]]) -> int: # DFS方法，看周边情况， for i in range(len(grid)): for j in range(len(grid[i])): if grid[i][j] == 1: self.dfs(grid,i,j) return self.count def dfs(self,grid,i,j): if i<0 or j<0 or i>=len(grid) or j>=len(grid[i]) or grid[i][j] == 2 or grid[i][j] == 0: return grid[i][j] = 2 result = self.get_count(grid,i,j) if "左" not in result: self.dfs(grid,i,j-1) if "右" not in result: self.dfs(grid,i,j+1) if "上" not in result: self.dfs(grid,i-1,j) if "下" not in result: self.dfs(grid,i+1,j) def get_count(self,grid,i,j): result = [] if i-1<0 or grid[i-1][j]==0: self.count += 1 result.append("上") if i+1==len(grid) or grid[i+1][j]==0: self.count += 1 result.append("下") if j-1<0 or grid[i][j-1]==0: self.count += 1 result.append("左") if j+1==len(grid[i]) or grid[i][j+1]==0: self.count += 1 result.append("右") return resultDFS 优化版运行结果：1：耗时超过12%。2：内存超过15%
知识点/技巧:1：DFS 递归调用时进行优化。
class Solution: count = 0 def islandPerimeter(self, grid: List[List[int]]) -> int: # BFS方法，看周边情况， for i in range(len(grid)): for j in range(len(grid[i])): if grid[i][j] == 1: self.bfs(grid,i,j) return self.count def bfs(self,grid,i,j): # 设置队列 que = [] que.append((i,j)) while que: i,j = que.pop(0) grid[i][j] = 2 # 上 if i-1<0 : self.count += 1 elif grid[i-1][j]==0: self.count += 1 elif grid[i-1][j]==1: grid[i-1][j]==2 if (i-1,j) not in que: que.append((i-1,j)) # 下 if i+1==len(grid) : self.count += 1 elif grid[i+1][j]==0: self.count += 1 elif grid[i+1][j]==1: grid[i+1][j]==2 if (i+1,j) not in que: que.append((i+1,j)) # 左 if j-1<0 : self.count += 1 elif grid[i][j-1]==0: self.count += 1 elif grid[i][j-1]==1: grid[i][j-1]==2 if (i,j-1) not in que: que.append((i,j-1)) # 右 if j+1==len(grid[i]): self.count += 1 elif grid[i][j+1]==0: self.count += 1 elif grid[i][j+1]==1: grid[i][j+1]==2 if (i,j+1) not in que: que.append((i,j+1))BFS运行结果：1：耗时超过8%。2：内存超过44%
知识点/技巧:1：BFS
-
695. 岛屿的最大面积 （难度系数✯✯）
-
827. 最大人工岛 （难度系数✯✯✯）
