【Leetcode-17】
一、题目：电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
二、代码：
def letterCombinations(self, digits: str) -> List[str]: res_all = [] if len(digits) == 0: return res_all def back_up(pre, arr): if len(arr) == 0: res_all.append(pre) return # 不加入 # back_up(pre, arr[1:]) # 加入 letters = list(look_up[arr[0]]) for i in range(len(letters)): letters[0], letters[i] = letters[i], letters[0] back_up(pre+letters[0], arr[1:]) letters[i], letters[0] = letters[0], letters[i] look_up = { "2": "abc", "3": "def", "4": "ghi", "5": "jkl", "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz" } back_up(‘‘, digits) return res_all
【Leetcode-22】
一、题目：括号生成
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
二、代码
def generateParenthesis(self, n: int) -> List[str]: res = [] def back_up(pre, left, right): if left == 0 and right == 0: res.append(pre) if left > 0: back_up(pre+‘(‘, left-1, right) if left < right: # 左放的多，可放右 back_up(pre+‘)‘, left, right-1) back_up(‘‘, n, n) return res
【Leetcode-46】
一、题目：全排列
给定一个 没有重复 数字的序列，返回其所有可能的全排列。
二、代码：
def permute(self, nums: List[int]) -> List[List[int]]: res = [] if len(nums) == 0: return res def back(pre, arr): if len(arr) == 0: res.append(pre[:]) for i in range(len(arr)): arr[i], arr[0] = arr[0], arr[i] pre.append(arr[0]) back(pre, arr[1:]) pre.pop() arr[0], arr[i] = arr[i], arr[0] back([], nums) return res
【Leetcode-39】
一、题目：组合总数
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
二、代码：
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: n = len(candidates) res = [] if n == 0: return res def back(pre, arr, t): if len(arr) == 0 or t < 0: # 放完了 if len(arr) == 0 and t == 0: res.append(pre[:]) return # 不放 back(pre, arr[1:], t) # 放 if t-arr[0] >= 0: pre.append(arr[0]) back(pre, arr, t-arr[0]) pre.pop() back([], candidates, target) return res
【Leetcode-78】
一、题目：子集
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
二、代码：
def subsets(self, nums: List[int]) -> List[List[int]]: res = [] n = len(nums) if n == 0: return [[]] def back(pre, arr): if len(arr) == 0: res.append(pre[:]) return # 放 pre.append(arr[0]) back(pre, arr[1:]) pre.pop() # 不放 back(pre, arr[1:]) back([], nums) return res
【Leetcode-79】
一、题目：单词搜索
给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
二、代码：
def exist(self, board: List[List[str]], word: str) -> bool: neibors = [[-1, 0], [1, 0], [0, -1], [0, 1]] m, n = len(board), len(board[0]) flag = [[True]*n for _ in range(m)] def dfs(i, j, k): if board[i][j] != word[k]: return False if k == len(word) - 1: return True flag[i][j] = False matched = False for pos in neibors: x, y = pos new_i, new_j = x + i, j + y if 0 <= new_i < m and 0 <= new_j < n and flag[new_i][new_j]: if dfs(new_i, new_j, k+1): matched = True break flag[i][j] = True return matched for i in range(m): for j in range(n): if dfs(i, j, 0): return True return False
【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
原文：https://www.cnblogs.com/EstherLjy/p/14608373.html