【Leetcode-200】
一、题目：岛屿数量
给你一个由 ‘1‘（陆地）和 ‘0‘（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
二、代码：
""" 代码1 """ def numIslands(self, grid: List[List[str]]) -> int: neibors = [[1, 0], [-1, 0], [0, 1], [0, -1]] m, n = len(grid), len(grid[0]) merged = [[False]*n for _ in range(m)] def dfs(i, j): merged[i][j] = True for x, y in neibors: new_x, new_y = x+i, y+j if 0 <= new_x < m and 0 <= new_y < n and not merged[new_x][new_y] and grid[new_x][new_y] == "1": dfs(new_x, new_y) num = 0 for i in range(m): for j in range(n): if not merged[i][j] and grid[i][j] == "1": num += 1 dfs(i, j) return num """ 代码2 """ def numIslands(self, grid: List[List[str]]) -> int: neibors = [[1, 0], [-1, 0], [0, 1], [0, -1]] m, n = len(grid), len(grid[0]) merged = [[False]*n for _ in range(m)] num = 0 for i in range(m): for j in range(n): if not merged[i][j] and grid[i][j] == "1": num += 1 que = [] merged[i][j] = True que.append((i, j)) while len(que) > 0: node = que.pop() for x, y in neibors: new_x, new_y = node[0]+x, node[1]+y if 0 <= new_x < m and 0 <= new_y < n and not merged[new_x][new_y] and grid[new_x][new_y] == "1": merged[new_x][new_y] = True que.append((new_x, new_y)) return num
【Leetcode-207】
一、题目：
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。
例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false。
二、代码：
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool: # 按出度入度表计算，把入度为0的结点放入，填充依赖它的项，全部节点出栈表示完成 visted = set() in_degree = [0]*numCourses # 表示依赖的结点个数 out_degree_list = [[] for i in range(numCourses)] # 可支撑的结点 for a, b in prerequisites: # a依赖b，b支撑a in_degree[a] += 1 out_degree_list[b].append(a) # 把无依赖的结点加入队列 que = [i for i, cnt in enumerate(in_degree) if cnt == 0] while len(que) > 0: node = que.pop(0) visted.add(node) # 已经解决的结点 # 尝试填充被依赖的结点 for item in out_degree_list[node]: in_degree[item] -= 1 if in_degree[item] == 0: # 全部依赖都满足 visted.add(item) que.append(item) if len(visted) == numCourses: return True else: return False
【Leetcode-207】
一、题目：除法求值
给你一个变量对数组 equations 和一个实数值数组 values 作为已知条件，其中 equations[i] = [Ai, Bi] 和 values[i] 共同表示等式 Ai / Bi = values[i] 。每个 Ai 或 Bi 是一个表示单个变量的字符串。
另有一些以数组 queries 表示的问题，其中 queries[j] = [Cj, Dj] 表示第 j 个问题，请你根据已知条件找出 Cj / Dj = ? 的结果作为答案。
返回 所有问题的答案 。如果存在某个无法确定的答案，则用 -1.0 替代这个答案。如果问题中出现了给定的已知条件中没有出现的字符串，也需要用 -1.0 替代这个答案。
注意：输入总是有效的。你可以假设除法运算中不会出现除数为 0 的情况，且不存在任何矛盾的结果。
二、代码：
def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]: """ dfs """ # 定义dfs def dfs(root, val, query): if root == query: return True, val visited.add(root) neibor_list = map_neibor[root] for neibor, v in neibor_list: if neibor not in visited: flag, final_v = dfs(neibor, val*v, query) if flag: return flag, final_v return False, None map_neibor = {} all_char = set() # 转换成临接表 for i in range(len(equations)): c1, c2 = equations[i] v = values[i] map_neibor.setdefault(c1, []).append((c2, v)) map_neibor.setdefault(c2, []).append((c1, 1/v)) all_char.add(c1) all_char.add(c2) # 调用 res = [] for item in queries: visited = set() x, y = item if x in all_char and y in all_char: if x == y: res.append(1) else: flag, v = dfs(x, 1, y) if flag: res.append(v) else: res.append(-1) else: res.append(-1) return res
原文：https://www.cnblogs.com/EstherLjy/p/14617879.html