本文解决的问题: 按主题归纳 图论、回溯 相关高频题型与通用解法。
适用范围: LeetCode 中文站题目,示例主要使用 Java。
阅读建议: 先识别数据结构与不变量,再结合题目约束选择算法,不要只记忆代码。
图论
给你一个由 '1'(陆地)和 '0'(水)组成的的二维网格,请你计算网格中岛屿的数量。
岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外,你可以假设该网格的四条边均被水包围。
提示:
m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] 的值为 '0' 或 '1'
示例 1:
1 2 3 4 5 6 7
| 输入:grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ] 输出:1
|
示例 2:
1 2 3 4 5 6
| 输入:grid = [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"] ]
|
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
| class Solution { void dfs(char[][] grid, int r, int c) { int nr = grid.length; int nc = grid[0].length;
if (r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c] == '0') { return; }
grid[r][c] = '0'; dfs(grid, r - 1, c); dfs(grid, r + 1, c); dfs(grid, r, c - 1); dfs(grid, r, c + 1); }
public int numIslands(char[][] grid) { if (grid == null || grid.length == 0) { return 0; }
int nr = grid.length; int nc = grid[0].length; int num_islands = 0; for (int r = 0; r < nr; ++r) { for (int c = 0; c < nc; ++c) { if (grid[r][c] == '1') { ++num_islands; dfs(grid, r, c); } } }
return num_islands; } }
|
在给定的 m x n 网格 grid 中,每个单元格可以有以下三个值之一:
- 值
0 代表空单元格;
- 值
1 代表新鲜橘子;
- 值
2 代表腐烂的橘子。
每分钟,腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能,返回 -1 。
提示:
m == grid.length
n == grid[i].length
1 <= m, n <= 10
grid[i][j] 仅为 0、1 或 2
示例 1:

1 2
| 输入:grid = [[2,1,1],[1,1,0],[0,1,1]] 输出:4
|
示例 2:
1 2 3
| 输入:grid = [[2,1,1],[0,1,1],[1,0,1]] 输出:-1 解释:左下角的橘子(第 2 行, 第 0 列)永远不会腐烂,因为腐烂只会发生在 4 个方向上。
|
示例 3:
1 2 3
| 输入:grid = [[0,2]] 输出:0 解释:因为 0 分钟时已经没有新鲜橘子了,所以答案就是 0 。
|
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
| class Solution { int[] dr = new int[]{-1, 0, 1, 0}; int[] dc = new int[]{0, -1, 0, 1};
public int orangesRotting(int[][] grid) { int R = grid.length, C = grid[0].length; Queue<Integer> queue = new ArrayDeque<Integer>(); Map<Integer, Integer> depth = new HashMap<Integer, Integer>(); for (int r = 0; r < R; ++r) { for (int c = 0; c < C; ++c) { if (grid[r][c] == 2) { int code = r * C + c; queue.add(code); depth.put(code, 0); } } } int ans = 0; while (!queue.isEmpty()) { int code = queue.remove(); int r = code / C, c = code % C; for (int k = 0; k < 4; ++k) { int nr = r + dr[k]; int nc = c + dc[k]; if (0 <= nr && nr < R && 0 <= nc && nc < C && grid[nr][nc] == 1) { grid[nr][nc] = 2; int ncode = nr * C + nc; queue.add(ncode); depth.put(ncode, depth.get(code) + 1); ans = depth.get(ncode); } } } for (int[] row: grid) { for (int v: row) { if (v == 1) { return -1; } } } return ans; } }
|
你这个学期必须选修 numCourses 门课程,记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出,其中 prerequisites[i] = [a_i, b_i] ,表示如果要学习课程 a_i 则 必须 先学习课程 b_i 。
- 例如,先修课程对
[0, 1] 表示:想要学习课程 0 ,你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习?如果可以,返回 true ;否则,返回 false 。
提示:
1 <= numCourses <= 2000
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
0 <= a_i, b_i < numCourses
prerequisites[i] 中的所有课程对 互不相同
示例 1:
1 2 3
| 输入:numCourses = 2, prerequisites = [[1,0]] 输出:true 解释:总共有 2 门课程。学习课程 1 之前,你需要完成课程 0 。这是可能的。
|
示例 2:
1 2 3
| 输入:numCourses = 2, prerequisites = [[1,0],[0,1]] 输出:false 解释:总共有 2 门课程。学习课程 1 之前,你需要先完成课程 0 ;并且学习课程 0 之前,你还应先完成课程 1 。这是不可能的
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39
| class Solution { List<List<Integer>> edges; int[] visited; boolean valid = true;
public boolean canFinish(int numCourses, int[][] prerequisites) { edges = new ArrayList<List<Integer>>(); for (int i = 0; i < numCourses; ++i) { edges.add(new ArrayList<Integer>()); } visited = new int[numCourses]; for (int[] info : prerequisites) { edges.get(info[1]).add(info[0]); } for (int i = 0; i < numCourses && valid; ++i) { if (visited[i] == 0) { dfs(i); } } return valid; }
public void dfs(int u) { visited[u] = 1; for (int v: edges.get(u)) { if (visited[v] == 0) { dfs(v); if (!valid) { return; } } else if (visited[v] == 1) { valid = false; return; } } visited[u] = 2; } }
|
Trie(发音类似 “try”)也叫前缀树,是一种用于高效存储和检索字符串键的树形数据结构,常用于自动补全和拼写检查。
请你实现 Trie 类:
Trie() 初始化前缀树对象。
void insert(String word) 向前缀树中插入字符串 word 。
boolean search(String word) 如果字符串 word 在前缀树中,返回 true(即,在检索之前已经插入);否则,返回 false 。
boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ,返回 true ;否则,返回 false 。
提示:
1 <= word.length, prefix.length <= 2000
word 和 prefix 仅由小写英文字母组成
insert、search 和 startsWith 调用次数 总计 不超过 3 * 10^4 次
示例:
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| 输入 ["Trie", "insert", "search", "search", "startsWith", "insert", "search"] [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]] 输出 [null, null, true, false, true, null, true]
解释 Trie trie = new Trie(); trie.insert("apple"); trie.search("apple"); // 返回 True trie.search("app"); // 返回 False trie.startsWith("app"); // 返回 True trie.insert("app"); trie.search("app"); // 返回 True
|
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
| class Trie { private Trie[] children; private boolean isEnd;
public Trie() { children = new Trie[26]; isEnd = false; } public void insert(String word) { Trie node = this; for (int i = 0; i < word.length(); i++) { char ch = word.charAt(i); int index = ch - 'a'; if (node.children[index] == null) { node.children[index] = new Trie(); } node = node.children[index]; } node.isEnd = true; } public boolean search(String word) { Trie node = searchPrefix(word); return node != null && node.isEnd; } public boolean startsWith(String prefix) { return searchPrefix(prefix) != null; }
private Trie searchPrefix(String prefix) { Trie node = this; for (int i = 0; i < prefix.length(); i++) { char ch = prefix.charAt(i); int index = ch - 'a'; if (node.children[index] == null) { return null; } node = node.children[index]; } return node; } }
|
回溯
给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
提示:
1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数 互不相同
示例 1:
1 2
| 输入:nums = [1,2,3] 输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
|
示例 2:
1 2
| 输入:nums = [0,1] 输出:[[0,1],[1,0]]
|
示例 3:
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
| public List<List<Integer>> permute(int[] nums) { List<List<Integer>> res = new ArrayList<List<Integer>>();
List<Integer> output = new ArrayList<Integer>(); for (int num : nums) { output.add(num); }
int n = nums.length; backtrack(n, output, res, 0); return res; }
public void backtrack(int n, List<Integer> output, List<List<Integer>> res, int first) { if (first == n) { res.add(new ArrayList<Integer>(output)); } for (int i = first; i < n; i++) { Collections.swap(output, first, i); backtrack(n, output, res, first + 1); Collections.swap(output, first, i); } }
|
给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1:
1 2
| 输入:nums = [1,2,3] 输出:[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
|
示例 2:
1 2
| 输入:nums = [0] 输出:[[],[0]]
|
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41
| class Solution { List<Integer> t = new ArrayList<Integer>(); List<List<Integer>> ans = new ArrayList<List<Integer>>();
public List<List<Integer>> subsets(int[] nums) { int n = nums.length; for (int mask = 0; mask < (1 << n); ++mask) { t.clear(); for (int i = 0; i < n; ++i) { if ((mask & (1 << i)) != 0) { t.add(nums[i]); } } ans.add(new ArrayList<Integer>(t)); } return ans; } }
class Solution { List<Integer> t = new ArrayList<Integer>(); List<List<Integer>> ans = new ArrayList<List<Integer>>();
public List<List<Integer>> subsets(int[] nums) { dfs(0, nums); return ans; }
public void dfs(int cur, int[] nums) { if (cur == nums.length) { ans.add(new ArrayList<Integer>(t)); return; } t.add(nums[cur]); dfs(cur + 1, nums); t.remove(t.size() - 1); dfs(cur + 1, nums); } }
|
给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。

提示:
0 <= digits.length <= 4
digits[i] 是范围 ['2', '9'] 的一个数字。
示例 1:
1 2
| 输入:digits = "23" 输出:["ad","ae","af","bd","be","bf","cd","ce","cf"]
|
示例 2:
示例 3:
1 2
| 输入:digits = "2" 输出:["a","b","c"]
|
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
| class Solution { public List<String> letterCombinations(String digits) { List<String> combinations = new ArrayList<String>(); if (digits.length() == 0) { return combinations; } Map<Character, String> phoneMap = new HashMap<Character, String>() {{ put('2', "abc"); put('3', "def"); put('4', "ghi"); put('5', "jkl"); put('6', "mno"); put('7', "pqrs"); put('8', "tuv"); put('9', "wxyz"); }}; backtrack(combinations, phoneMap, digits, 0, new StringBuffer()); return combinations; }
public void backtrack(List<String> combinations, Map<Character, String> phoneMap, String digits, int index, StringBuffer combination) { if (index == digits.length()) { combinations.add(combination.toString()); } else { char digit = digits.charAt(index); String letters = phoneMap.get(digit); int lettersCount = letters.length(); for (int i = 0; i < lettersCount; i++) { combination.append(letters.charAt(i)); backtrack(combinations, phoneMap, digits, index + 1, combination); combination.deleteCharAt(index); } } } }
|
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ,找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ,并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同,则两种组合是不同的。
对于给定的输入,保证和为 target 的不同组合数少于 150 个。
提示:
1 <= candidates.length <= 30
2 <= candidates[i] <= 40
candidates 的所有元素 互不相同
1 <= target <= 40
示例 1:
1 2 3 4 5 6
| 输入:candidates = [2,3,6,7], target = 7 输出:[[2,2,3],[7]] 解释: 2 和 3 可以形成一组候选,2 + 2 + 3 = 7 。注意 2 可以使用多次。 7 也是一个候选, 7 = 7 。 仅有这两种组合。
|
示例 2:
1 2
| 输入: candidates = [2,3,5], target = 8 输出: [[2,2,2,2],[2,3,3],[3,5]]
|
示例 3:
1 2
| 输入: candidates = [2], target = 1 输出: []
|
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
| class Solution { public List<List<Integer>> combinationSum(int[] candidates, int target) { List<List<Integer>> ans = new ArrayList<List<Integer>>(); List<Integer> combine = new ArrayList<Integer>(); dfs(candidates, target, ans, combine, 0); return ans; }
public void dfs(int[] candidates, int target, List<List<Integer>> ans, List<Integer> combine, int idx) { if (idx == candidates.length) { return; } if (target == 0) { ans.add(new ArrayList<Integer>(combine)); return; } dfs(candidates, target, ans, combine, idx + 1); if (target - candidates[idx] >= 0) { combine.add(candidates[idx]); dfs(candidates, target - candidates[idx], ans, combine, idx); combine.remove(combine.size() - 1); } } }
|
数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 **有效的 **括号组合。
提示:
示例 1:
1 2
| 输入:n = 3 输出:["((()))","(()())","(())()","()(())","()()()"]
|
示例 2:
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
| class Solution { public List<String> generateParenthesis(int n) { List<String> ans = new ArrayList<String>(); backtrack(ans, new StringBuilder(), 0, 0, n); return ans; }
public void backtrack(List<String> ans, StringBuilder cur, int open, int close, int max) { if (cur.length() == max * 2) { ans.add(cur.toString()); return; } if (open < max) { cur.append('('); backtrack(ans, cur, open + 1, close, max); cur.deleteCharAt(cur.length() - 1); } if (close < open) { cur.append(')'); backtrack(ans, cur, open, close + 1, max); cur.deleteCharAt(cur.length() - 1); } } }
|
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中,返回 true ;否则,返回 false 。
单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
提示:
m == board.length
n = board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
board 和 word 仅由大小写英文字母组成
进阶: 你可以使用搜索剪枝的技术来优化解决方案,使其在 board 更大的情况下可以更快解决问题?
示例 1:

1 2
| 输入:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED" 输出:true
|
示例 2:

1 2
| 输入:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE" 输出:true
|
示例 3:

1 2
| 输入:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB" 输出:false
|
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
| class Solution { public boolean exist(char[][] board, String word) { boolean[][] visited = new boolean[board.length][board[0].length]; for (int i = 0; i < board.length; i++) { for (int j = 0; j < board[i].length; j++) { if (dfsChecker(board, visited, i, j, 0, word)) { return true; } } } return false; }
private boolean dfsChecker(char[][] board, boolean[][] visited, int i, int j, int k, String word) { if (board[i][j] != word.charAt(k)) { return false; } if (k == word.length() - 1) { return true; } visited[i][j] = true; int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; boolean flag = false; for (int[] direction : directions) { int newI = i + direction[0], newJ = j + direction[1]; if (newI >= 0 && newI < board.length && newJ >= 0 && newJ < board[0].length && !visited[newI][newJ]) { boolean checker = dfsChecker(board, visited, newI, newJ, k + 1, word); if (checker) { flag = true; break; } } } visited[i][j] = false; return flag; } }
|
给你一个字符串 s,请你将 s 分割成一些 子串,使每个子串都是 回文串 。返回 s 所有可能的分割方案。
提示:
1 <= s.length <= 16
s 仅由小写英文字母组成
示例 1:
1 2
| 输入:s = "aab" 输出:[["a","a","b"],["aa","b"]]
|
示例 2:
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37
| class Solution { boolean[][] f; List<List<String>> ret = new ArrayList<List<String>>(); List<String> ans = new ArrayList<String>(); int n;
public List<List<String>> partition(String s) { n = s.length(); f = new boolean[n][n]; for (int i = 0; i < n; ++i) { Arrays.fill(f[i], true); }
for (int i = n - 1; i >= 0; --i) { for (int j = i + 1; j < n; ++j) { f[i][j] = (s.charAt(i) == s.charAt(j)) && f[i + 1][j - 1]; } }
dfs(s, 0); return ret; }
public void dfs(String s, int i) { if (i == n) { ret.add(new ArrayList<String>(ans)); return; } for (int j = i; j < n; ++j) { if (f[i][j]) { ans.add(s.substring(i, j + 1)); dfs(s, j + 1); ans.remove(ans.size() - 1); } } } }
|
按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。
给你一个整数 n ,返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案,该方案中 'Q' 和 '.' 分别代表了皇后和空位。
提示:
示例 1:

1 2 3
| 输入:n = 4 输出:[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]] 解释:如上图所示,4 皇后问题存在两个不同的解法。
|
示例 2:
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53
| class Solution { public List<List<String>> solveNQueens(int n) { List<List<String>> solutions = new ArrayList<List<String>>(); int[] queens = new int[n]; Arrays.fill(queens, -1); Set<Integer> columns = new HashSet<Integer>(); Set<Integer> diagonals1 = new HashSet<Integer>(); Set<Integer> diagonals2 = new HashSet<Integer>(); backtrack(solutions, queens, n, 0, columns, diagonals1, diagonals2); return solutions; }
public void backtrack(List<List<String>> solutions, int[] queens, int n, int row, Set<Integer> columns, Set<Integer> diagonals1, Set<Integer> diagonals2) { if (row == n) { List<String> board = generateBoard(queens, n); solutions.add(board); } else { for (int i = 0; i < n; i++) { if (columns.contains(i)) { continue; } int diagonal1 = row - i; if (diagonals1.contains(diagonal1)) { continue; } int diagonal2 = row + i; if (diagonals2.contains(diagonal2)) { continue; } queens[row] = i; columns.add(i); diagonals1.add(diagonal1); diagonals2.add(diagonal2); backtrack(solutions, queens, n, row + 1, columns, diagonals1, diagonals2); queens[row] = -1; columns.remove(i); diagonals1.remove(diagonal1); diagonals2.remove(diagonal2); } } }
public List<String> generateBoard(int[] queens, int n) { List<String> board = new ArrayList<String>(); for (int i = 0; i < n; i++) { char[] row = new char[n]; Arrays.fill(row, '.'); row[queens[i]] = 'Q'; board.add(new String(row)); } return board; } }
|
参考资料