200. 岛屿数量

https://leetcode-cn.com/problems/number-of-islands/
This question can be solved by DFS, BFS, Union-Find, I only practiced DFS and Union-Find
这道题也可以不用visited函数，在原来grid上修改，但是如果面试中，需要询问是否可以修改原数组

  1. class Solution:
  2.     def numIslands(self, grid: List[List[str]]) -> int:
  3.         rows = len(grid)
  4.         if rows==0:
  5.             return 0
  6.         cols = len(grid[0])
  7.         visited = [[False for _ in range(cols)] for _ in range(rows)]
  8.         DIRECTION = ((1,0),(-1,0),(0,1),(0,-1))
  9.         count = 0
  10.         def isArea(x,y):
  11.             return x>=0 and y>=0 and x<=rows-1 and y<=cols-1
  12.         def dfs(i,j):
  13.             visited[i][j] = True
  14.             for k in range(4):
  15.                 x = i + DIRECTION[k][0]
  16.                 y = j + DIRECTION[k][1]
  17.                 if isArea(x,y) and not visited[x][y] and grid[x][y]=='1':
  18.                     dfs(x,y)
  20.         for i in range(rows):
  21.             for j in range(cols):
  22.                 if not visited[i][j] and grid[i][j]=='1':
  23.                     dfs(i,j)
  24.                     count+=1
  25.         return count

BFS
主函数差不多，遍历函数用一个队列来维护了和当前岛屿连接的岛屿，注意DFS只需要向下或者向右，BFS需要把上下左右都加进来查看

  1. from collections import deque
  2. class Solution:
  3.     def numIslands(self, grid: List[List[str]]) -> int:
  4.         rows =len(grid)
  5.         cols =len(grid[0])
  6.         DIRECTION = ((1,0),(0,1),(-1,0),(0,-1))
  7.         count=0
  8.         def inArea(x,y):
  9.             return x>=0 and y>=0 and x<rows and y<cols
  10.         def bfs(x,y):
  11.             queue = deque()
  12.             queue.append([x,y])
  13.             while queue:
  14.                 i,j = queue.popleft()
  15.                 if inArea(i,j) and grid[i][j]=='1':
  16.                     grid[i][j]='0'
  17.                     for k in range(4):
  18.                         queue.append([i+DIRECTION[k][0],j+DIRECTION[k][1]])
  19.         for i in range(rows):
  20.             for j in range(cols):
  21.                 if grid[i][j]=='1':
  22.                     bfs(i,j)
  23.                     count+=1
  24.         return count

22. 括号生成

https://leetcode-cn.com/problems/generate-parentheses/
left和right从n开始递减，表示还剩多少个括号留下没用

  1.     def generateParenthesis(self, n: int) -> List[str]:
  2.         res = []
  3.         cur_str = ''
  4.         def dfs(cur_str, left, right):
  5.             '''
  6.             params:
  7.                 cur_str,  the string from root to leaf
  8.                 left,  how many left ( left
  9.                 right, how many right ) left
  10.             '''
  11.             if left==0 and right==0:
  12.                 res.append(cur_str)
  13.                 return
  14.             if right<left:
  15.                 return
  16.             if left > 0:
  17.                 dfs(cur_str+'(', left-1,right)
  18.             if right >0:
  19.                 dfs(cur_str+')', left, right-1)
  20.         dfs(cur_str, n,n)
  21.         return res

left和right从0开始，逐渐增加，注意判断条件变成了right要严格小于left，如果大于了就要return

  1.     def generateParenthesis(self, n: int) -> List[str]:
  2.         res = []
  3.         cur_str = ''
  4.         def dfs(cur_str, left, right):
  5.             '''
  6.             params:
  7.                 cur_str,  the string from root to leaf
  8.                 left,  how many left ( left
  9.                 right, how many right ) left
  10.             '''
  11.             if left==n and right==n:
  12.                 res.append(cur_str)
  13.                 return
  14.             if right>left:
  15.                 return
  16.             if left < n:
  17.                 dfs(cur_str+'(', left+1,right)
  18.             if right < n:
  19.                 dfs(cur_str+')', left, right+1)
  20.         dfs(cur_str, 0,0)
  21.         return res

剑指 Offer 12. 矩阵中的路径

https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof/

329. 矩阵中的最长递增路径

https://leetcode-cn.com/problems/longest-increasing-path-in-a-matrix/
拓扑排序， 课程表是为了找环，如果有环，说明无法学完全部课程，因为有的课程互为先决条件，导致有环出现。
这道题以数字大小来作为出度入度，是肯定没有环的，要计算的最长路径，那么就是每次把入度为0的作为一层，将这一层点挪去之后，还剩下的入度为0的点就是下一次，加入队列进入下一次循环， 经过多少次循环后再也没有入度为0的点就得到了最长递增路径

  1. from collections import deque
  2. class Solution:
  3.     def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
  4.         if not matrix:
  5.             return 0
  6.         rows, cols = len(matrix), len(matrix[0])
  7.         DIRECTION = ((1,0),(-1,0),(0,1),(0,-1))
  8.         # indegrees每个坐标上的值，是matrix对应坐标位置的入度
  9.         indegrees = [[0 for _ in range(cols)] for _ in range(rows)]
  10.         def inArea(x,y):
  11.             return x>=0 and y>=0 and x<rows and y<cols
  13.         # calculate the indegrees
  14.         for i in range(rows):
  15.             for j in range(cols):
  16.                 for k in range(4):
  17.                     new_x = i + DIRECTION[k][0]
  18.                     new_y = j + DIRECTION[k][1]
  19.                     if inArea(new_x, new_y) and matrix[i][j] > matrix[new_x][new_y]:
  20.                         indegrees[i][j]+=1
  22.         queue = deque()
  23.         # 入度为0的坐标进入队列
  24.         for i in range(rows):
  25.             for j in range(cols):
  26.                 if indegrees[i][j] == 0:
  27.                     queue.append((i,j))
  29.         res = 0
  30.         while queue:
  31.             # 每一层遍历 res+1
  32.             res += 1
  33.             for _ in range(len(queue)):
  34.                 x, y = queue.popleft()
  35.                 for k in range(4):
  36.                     new_x = x + DIRECTION[k][0]
  37.                     new_y = y + DIRECTION[k][1]
  38.                     if inArea(new_x,new_y) and matrix[x][y] < matrix[new_x][new_y]:
  39.                         indegrees[new_x][new_y] -= 1
  40.                         if indegrees[new_x][new_y] == 0:
  41.                             queue.append((new_x,new_y))
  42.         return res

从最小的数字开始，遍历每个点附近的四个点， 取这四个点里（1.没有出界，2.值比当前点小）的当前路径最长的，然后这个点的路径就是那个附近最长路径+1， 如果附近四个点都比当前点大，那么这个点就是一个起始点，最长路径为1

  1. from collections import deque
  2. class Solution:
  3.     def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
  4.         if not matrix:
  5.             return 0
  6.         rows, cols = len(matrix), len(matrix[0])
  7.         DIRECTION = ((1,0),(-1,0),(0,1),(0,-1))
  8.         dp = [[0]*cols for _ in range(rows)]
  9.         def inArea(x,y):
  10.             return x>=0 and y>=0 and x<rows and y<cols
  11.         points = sorted([[matrix[i][j], (i,j)] for i in range(rows) for j in range(cols)])
  13.         res = 0
  14.         for point in points:
  15.             value = point[0]
  16.             x, y = point[1]
  17.             max_path = 0
  18.             for k in range(4):
  19.                 new_x = x + DIRECTION[k][0]
  20.                 new_y = y + DIRECTION[k][1]
  21.                 if inArea(new_x, new_y) and matrix[new_x][new_y] < value:
  22.                     max_path = max(max_path, dp[new_x][new_y])
  23.             dp[x][y] = max_path+1
  24.             res = max(res, dp[x][y])
  25.         return res

130. 被围绕的区域

https://leetcode-cn.com/problems/surrounded-regions/
和边界的O连接的o不变， 其他位置的o都是被围绕的，需要被设置为x
那么dfs bfs 和并查集都可以解决，思路是先处理边界位置的O， 把和边界相连的o都置为，比如#，结束遍历后再重新遍历一次board， 把#置为o，把o置为x
dfs是递归， bfs是用队列

  1. class Solution:
  2.     def solve(self, board: List[List[str]]) -> None:
  3.         """
  4.         Do not return anything, modify board in-place instead.
  5.         """
  6.         if not board:
  7.             return board
  8.         rows, cols = len(board), len(board[0])
  9.         DIRECTION = ((0,1),(1,0),(0,-1),(-1,0))
  10.         ans = []
  11.         def inArea(x, y):
  12.             return x >= 0 and y>=0 and x<rows and y<cols
  13.         def dfs(x, y):
  14.             board[x][y] = '#'
  15.             for k in range(4):
  16.                 new_x = x + DIRECTION[k][0]
  17.                 new_y = y + DIRECTION[k][1]
  18.                 if inArea(new_x, new_y) and board[new_x][new_y] == 'O':
  19.                     dfs(new_x, new_y)
  21.         # up&bottom boader
  22.         for j in range(cols):
  23.             if board[0][j] == 'O':
  24.                 dfs(0,j)
  25.             if board[rows-1][j] == 'O':
  26.                 dfs(rows-1, j)
  27.         # left&right boader
  28.         for i in range(rows):
  29.             if board[i][0] == 'O':
  30.                 dfs(i,0)
  31.             if board[i][cols-1] == 'O':
  32.                 dfs(i,cols-1)
  34.         for i in range(rows):
  35.             for j in range(cols):
  36.                 board[i][j] = 'O' if board[i][j] == '#' else 'X'
  37.         return board

778. 水位上升的泳池中游泳

https://leetcode-cn.com/problems/swim-in-rising-water/
优先队列, Python的实现是二叉堆. 相当于flood fill, 类似bfs的思维. 不是贪心只关注当前点周围可以去到的最低的点, 而是当前走过的点里面去找最低的点. 比如一个点如果选择过, 那么这个点的→和↓就会变为可接触的点,并且进入二叉堆heap, 每次我们都选择这些可接触点的最小值,也就是二叉堆的堆顶

  1. import heapq
  2. class Solution:
  3.     def swimInWater(self, grid: List[List[int]]) -> int:
  4.         if not grid:
  5.             return 0
  6.         rows, cols = len(grid), len(grid[0])
  7.         visited = [[False]*cols for _ in range(rows)]
  8.         heap = []
  9.         heapq.heappush(heap, (grid[0][0],(0,0)))
  10.         high = float('-inf')
  11.         DIRECTION = ((1,0), (0,1), (-1,0), (0,-1))
  12.         while heap:
  13.             height, loc = heapq.heappop(heap)
  14.             high = max(high, height)
  15.             x, y = loc
  16.             visited[x][y] = True
  17.             if x == rows-1 and y == cols-1:
  18.                 return high
  19.             for k in range(4):
  20.                 new_x = x + DIRECTION[k][0]
  21.                 new_y = y + DIRECTION[k][1]
  22.                 if 0<=new_x<rows and 0<=new_y<cols and not visited[new_x][new_y]:
  23.                     heapq.heappush(heap, (grid[new_x][new_y], (new_x, new_y)) )