LeetCode 31下一个排列、LeetCode 64最小路径和、LeetCode 62不同路径、LeetCode 78子集

Top1：LeetCode 31下一个排列

题目描述：
以数字序列 [1,2,3][1,2,3] 为例，其排列按照字典序依次为：

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

这样，排列 [2,3,1][2,3,1] 的下一个排列即为 [3,1,2][3,1,2]。特别的，最大的排列 [3,2,1][3,2,1] 的下一个排列为最小的排列 [1,2,3][1,2,3]。
整数数组的下一个排列是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的下一个排列就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。
给你一个整数数组 nums ，找出 nums 的下一个排列。
必须原地修改，只允许使用额外常数空间。
示例 1：
输入：nums = [1,2,3]
输出：[1,3,2]

示例 2：
输入：nums = [3,2,1]
输出：[1,2,3]

示例 3：
输入：nums = [1,1,5]
输出：[1,5,1]

一、注意到下一个排列总是比当前排列要大，除非该排列已经是最大的排列。若要满足需要变大的幅度尽可能小，需要从右往左找到一个左边的【较小数】和从右往左找右边的【较大数】，之后将较大数右边的数使用刷给你指针反转区间【其实也是按照升序重新排列】

以排列 [4,5,2,6,3,1][4,5,2,6,3,1] 为例：

我们能找到的符合条件的一对「较小数」与「较大数」的组合为 22 与 33，满足「较小数」尽量靠右，而「较大数」尽可能小。
当我们完成交换后排列变为 [4,5,3,6,2,1][4,5,3,6,2,1]，此时我们可以重排「较小数」右边的序列，序列变为 [4,5,3,1,2,6][4,5,3,1,2,6]。

可通过完整代码：

public void nextPermutation(int[] nums) {
    int i = nums.length - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) i--;   // 找到为【较小数】的i，一定要>=不能>，因为要找到较小数nums[i] < nums[i+1]
    if (i >= 0) {   // 如果已经是最大的了，i=-1，此时不满足这个；将会执行最后的reverse
        int j = nums.length - 1;
        while (j >= 0 && nums[i] >= nums[j]) j--;   // 找到为【较大数】的j，一定要有=，因为较大的数一定满足nums[j] > nums[i]
        swap(nums, i, j);   // 交换
    }
    reverse(nums, i + 1);   // 反转较小数的后面
}

private void reverse(int[] nums, int startIndex) {
    int left = startIndex, right = nums.length - 1;   // 从两头开始交换（偶数正好满足，奇数中间的那个不用交换）
    while (left < right) {
        swap(nums, left, right);
        left ++;
        right--;
    }
}

private void swap(int[] nums, int i, int j) {
    int tem = nums[i];
    nums[i] = nums[j];
    nums[j] = tem;
}

Top2：LeetCode 64最小路径和（动态规划）

题目描述：
给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例 1：

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

示例 2：
输入：grid = [[1,2,3],[4,5,6]]
输出：12

一、【动态规划构造最小路径和的数组，dp[i][j]表示从左上角出发到位置[i][j]的最小路径和】

二、对于在第一列和第一行上的元素直接初始化dp[0][0]后初始化完，不在第一行和第一列的元素使用两个for循环从1到

可通过完整代码：

public int minPathSum(int[][] grid) {
    if (grid == null || grid.length == 0 || grid[0].length == 0) {
        return 0;
    }
    int rows = grid.length, cols = grid[0].length;
    int[][] dp = new int[rows][cols];
    dp[0][0] = grid[0][0];   // 初始化左上角第一个元素
    for (int i = 1; i < rows; i++) {   // 填dp矩阵的第一列，从下标1开始
        dp[i][0] = dp[i - 1][0] + grid[i][0];
    }
    for (int j = 1; j < cols; j++) {   // 填dp矩阵的第一行，从下标1开始
        dp[0][j] = dp[0][j - 1] + grid[0][j];
    }
    for (int i = 1; i < rows; i++) {   // 一行一行的填剩余的地方
        for (int j = 1; j < cols; j++) {
            dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
        }
    }
    return dp[rows - 1][cols - 1];
}

Top3：LeetCode 62不同路径

题目描述：
一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？
示例1：

输入：m = 3, n = 7
输出：28

示例 2：
输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。

向右 -> 向下 -> 向下
向下 -> 向下 -> 向右
向下 -> 向右 -> 向下

示例 3：
输入：m = 7, n = 3
输出：28

示例 4：
输入：m = 3, n = 3
输出：6

一、动态规划：因为机器人每次都只能往下or往右，所以第一行和第一列都初始化为1【反证—>多一个下和多一个右都回不去上一行和前一列】，其他的i j=i-1（从上一行往下）+j-1（从前一列往右）【如果都是1，则=1+1=2，就相当于有两条不同路径】

时间复杂度O(mn)：两个for循环m * n
空间复杂度O(mn)：新建了dp数组来存储不同路径数组的各个数量

可通过完整代码：

public int uniquePaths(int m, int n) {
    int[][] dp = new int[m][n];
    for (int i = 0; i < m; i++) {   // 按行i++填满第一列
        dp[i][0] = 1;
    }
    for (int j = 0; j < n; j++) {   // 按列j++填满第一行
        dp[0][j] = 1;
    }
    for (int i = 1; i < m; i++) {   // 按i++开始逐列填dp次数矩阵
        for (int j = 1; j < n; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];   // 除了第一行和第一列的[i][j]位置有可能从i-1下移，或者j-1右移动【因为机器人每次只能右移或下移】
        }
    }
    return dp[m - 1][n - 1];
}

方法II 组合数学方法：

从左上角到右下角的过程中，我们需要移动 m+n-2 次，其中有 m-1 次向下移动，n-1 次向右移动。因此路径的总数，就等于从 m+n-2 次移动中选择 m-1 次向下移动的方案数【因为每一种组合都可以将n-1次向右移动匹配到】，即组合数：

消去分母(n-1)!：

递推

我们直接计算出这个组合数即可得到不同路径数。

时间复杂度O(m)
空间复杂度O(1)

将long类型转变为int，且for循环终止条件：因为每一回合x y都会增加，所以可以写一个终止条件yreturn (int) ans;

for (int x = n, y = 1; y < m; x++, y++){}

！！！Division result is truncated to integer警告⚠

猜测此处是因为使用 *= 符号之后，先计算右边int/int了，所以会报除法结果被切断为integer，尽量不同类型的时候不使用 *= 这种符号【使用将会造成奇怪的错误】

可通过完整代码

public int uniquePaths2(int m, int n) {
    long ans = 1;
    for (int x = n, y = 1; y < m; x++, y++) {
//            ans *= x / y;
        ans = ans * x / y;
    }
    return (int) ans;
}

Top4：LeetCode 78子集（数组中数据互不相同）

题目描述：
给你一个整数数组 nums ，数组中的元素互不相同 color{red}{互不相同} 互不相同。返回该数组所有可能的子集（幂集）。
解集不能包含重复的子集。你可以按任意顺序返回解集。
示例 1：
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：
输入：nums = [0]
输出：[[],[0]]

一、使用dfs，其中为选择当前位置然后index+1继续下一次，和不选择当前位置remove（sub.size()-1），继续dfs；当index==n-1的时候添加答案进去，return

看下图递归树就可知，要按照代码顺序从右往左输出，所以remove(sub.size()-1)

可通过完整代码：

List> ans = new ArrayList<>();
List sub = new ArrayList<>();
public List> subsets(int[] nums) {
    dfs(0, nums);
    return ans;
}

private void dfs(int index, int[] nums) {
    if (index == nums.length) {   // 当其执行完sub.add()后进入dfs就会输出
        ans.add(new ArrayList<>(sub));
        return;
    }
    sub.add(nums[index]);
    dfs(index + 1, nums);
    sub.remove(sub.size() - 1);   // remove掉sub.size() - 1更保险一些，移除的是前面行添加的nums[index]
    dfs(index + 1, nums);
}

LeetCode 31下一个排列、LeetCode 64最小路径和、LeetCode 62不同路径、LeetCode 78子集

C/C++/C#相关栏目本月热门文章