算法练习5

今日完成 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 ListListInteger permute(int[] nums) { ListListInteger result new ArrayList(); boolean[] used new boolean[nums.length]; backtrack(nums, used, new ArrayList(), result); return result; } private void backtrack( int[] nums, boolean[] used, ListInteger path, ListListInteger 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 ListListInteger combinationSum(int[] candidates, int target) { ListListInteger result new ArrayList(); backtrack(candidates, target, 0, new ArrayList(), result); return result; } private void backtrack( int[] candidates, int remaining, int start, ListInteger path, ListListInteger 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); } }为什么递归传ibacktrack(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] 结果2n 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)。