企业官网建设流程全解析

今日完成 4 道高频算法题，覆盖回溯、动态规划、二维网格 DFS 三个重要专题。

回溯：选择 -> 递归 -> 撤销选择 动态规划：定义状态 -> 推导状态转移 -> 优化空间 网格 DFS：遍历格子 -> 发现连通块 -> 标记已访问

1. 全排列

题目：给定一个不包含重复元素的数组nums，返回所有可能的全排列。

示例：

nums = [1, 2, 3] 结果： [ [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1] ]

思路

全排列要求每个位置都从尚未使用过的元素中选择一个。

第一个位置：可以选 1、2、3 第二个位置：从剩余元素中选 第三个位置：只能选择最后一个剩余元素

需要使用：

path：当前正在构造的排列 used：记录每个元素是否已经被使用 result：保存所有完整排列

当路径长度等于数组长度时，说明得到一个完整排列：

if (path.size() == nums.length) { result.add(new ArrayList<>(path)); return; }

Java 实现

public List<List<Integer>> permute(int[] nums) { List<List<Integer>> result = new ArrayList<>(); boolean[] used = new boolean[nums.length]; backtrack(nums, used, new ArrayList<>(), result); return result; } private void backtrack( int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> result) { if (path.size() == nums.length) { result.add(new ArrayList<>(path)); return; } for (int i = 0; i < nums.length; i++) { if (used[i]) { continue; } used[i] = true; path.add(nums[i]); backtrack(nums, used, path, result); path.remove(path.size() - 1); used[i] = false; } }

回溯核心模板

做选择; 递归进入下一层; 撤销选择;

对应代码：

used[i] = true; path.add(nums[i]); backtrack(nums, used, path, result); path.remove(path.size() - 1); used[i] = false;

其中：

result.add(new ArrayList<>(path));

必须创建副本。因为path会在回溯时不断增删；若直接保存path，所有结果都会引用同一个列表对象。

复杂度

时间复杂度：O(n * n!) 空间复杂度：O(n)

排列总数为n!，复制每个排列需要O(n)。

2. 组合总和

题目：给定无重复正整数数组candidates和目标值target，找出所有和为target的不同组合。

要求：

同一个数字可以重复选择。 组合元素顺序不同，视为同一个组合。

示例：

candidates = [2, 3, 6, 7] target = 7 结果： [[2, 2, 3], [7]]

与全排列的区别

全排列： 每个元素最多选择一次； 使用 used[] 标记； [1, 2] 和 [2, 1] 是不同答案。 组合总和： 元素可以重复选择； 不使用 used[]； [2, 2, 3] 与 [3, 2, 2] 是同一个组合。

核心参数

remaining：距离 target 还差多少。 start：当前层从哪个下标开始选择。 path：当前组合。 result：所有符合条件的组合。

结束条件与剪枝

if (remaining == 0) { result.add(new ArrayList<>(path)); return; } if (remaining < 0) { return; }

含义：

remaining == 0：当前组合和恰好等于 target。 remaining < 0：当前组合和超过 target，后续数字均为正数，不可能回到 target，可以停止。

Java 实现

public List<List<Integer>> combinationSum(int[] candidates, int target) { List<List<Integer>> result = new ArrayList<>(); backtrack(candidates, target, 0, new ArrayList<>(), result); return result; } private void backtrack( int[] candidates, int remaining, int start, List<Integer> path, List<List<Integer>> result) { if (remaining == 0) { result.add(new ArrayList<>(path)); return; } if (remaining < 0) { return; } for (int i = start; i < candidates.length; i++) { path.add(candidates[i]); backtrack( candidates, remaining - candidates[i], i, path, result ); path.remove(path.size() - 1); } }

为什么递归传i

backtrack(candidates, remaining - candidates[i], i, path, result);

传入i，代表下一层仍可以选择当前数字：

选择 2 后，下一层仍可选择 2。 [2] -> [2, 2] -> [2, 2, 3]

如果传入i + 1，当前数字只能选一次，题目就会变成另一类问题。

为什么不从0重新开始

若每层都从下标0开始，会产生顺序重复：

[2, 2, 3] [2, 3, 2] [3, 2, 2]

通过start限制下标不倒退：

只生成 [2, 2, 3]； 不会生成 [3, 2, 2]。

3. 爬楼梯

题目：需要爬到第n阶，每次可以走1阶或2阶，求不同走法数量。

示例：

n = 2 [1 + 1] [2] 结果：2

n = 3 [1 + 1 + 1] [1 + 2] [2 + 1] 结果：3

状态转移

到达第n阶时，最后一步只有两种来源：

从第 n - 1 阶走 1 步； 从第 n - 2 阶走 2 步。

因此：

dp[n] = dp[n - 1] + dp[n - 2]

基础状态：

dp[1] = 1 dp[2] = 2

常数空间优化

每次只依赖前两个状态，不需要完整dp数组：

public int climbStairs(int n) { if (n <= 2) { return n; } int previousPrevious = 1; int previous = 2; for (int step = 3; step <= n; step++) { int current = previousPrevious + previous; previousPrevious = previous; previous = current; } return previous; }

变量含义：

previousPrevious：到第 i - 2 阶的方法数。 previous：到第 i - 1 阶的方法数。 current：到第 i 阶的方法数。

例如n = 5：

第 1 阶：1 第 2 阶：2 第 3 阶：3 第 4 阶：5 第 5 阶：8

复杂度

时间复杂度：O(n) 空间复杂度：O(1)

本题本质是斐波那契数列变形：

dp[i] = dp[i - 1] + dp[i - 2]

4. 岛屿数量

题目：给定由'1'（陆地）和'0'（水）组成的二维网格，计算岛屿数量。

规则：

上下左右相邻的陆地属于同一座岛。 对角线相邻不连通。

示例：

grid = [ ['1', '1', '0', '0', '0'], ['1', '1', '0', '0', '0'], ['0', '0', '1', '0', '0'], ['0', '0', '0', '1', '1'] ] 结果：3

网格转图

二维网格可以看作图：

每个 '1' 是一个节点； 上下左右相邻的 '1' 之间存在边； 一片相连的陆地就是一个连通块，也就是一座岛。

DFS 思路

双重循环扫描每一个格子： 遇到 '0'：跳过。 遇到 '1'： 发现一座新岛，count 加 1； 从当前位置开始 DFS； 将该岛所有相连的 '1' 全部改为 '0'。

将'1'改成'0'的作用：

标记该陆地已经访问； 避免同一个岛被重复统计； 避免 DFS 在相邻格子间反复递归。

Java 实现

public int numIslands(char[][] grid) { int count = 0; for (int row = 0; row < grid.length; row++) { for (int col = 0; col < grid[0].length; col++) { if (grid[row][col] == '1') { dfs(grid, row, col); count++; } } } return count; } private void dfs(char[][] grid, int row, int col) { if (row < 0 || row >= grid.length || col < 0 || col >= grid[0].length || grid[row][col] == '0') { return; } grid[row][col] = '0'; dfs(grid, row - 1, col); dfs(grid, row + 1, col); dfs(grid, row, col - 1); dfs(grid, row, col + 1); }

DFS 四个方向

上：row - 1, col 下：row + 1, col 左：row, col - 1 右：row, col + 1

复杂度

时间复杂度：O(m * n) 空间复杂度：O(m * n)

其中：

m：网格行数 n：网格列数

每个格子最多被访问一次。最坏情况下网格全为陆地，递归调用栈可能达到O(m * n)。