月度归档： 2025 年 2 月

目标

给定一个 m x n 的整数数组 grid。一个机器人初始位于 左上角（即 grid[0][0]）。机器人尝试移动到 右下角（即 grid[m - 1][n - 1]）。机器人每次只能向下或者向右移动一步。

网格中的障碍物和空位置分别用 1 和 0 来表示。机器人的移动路径中不能包含 任何 有障碍物的方格。

返回机器人能够到达右下角的不同路径数量。

测试用例保证答案小于等于 2 * 109。

示例 1：

输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

示例 2：

输入：obstacleGrid = [[0,1],[0,0]]
输出：1

说明：

• m == obstacleGrid.length
• n == obstacleGrid[i].length
• 1 <= m, n <= 100
• obstacleGrid[i][j] 为 0 或 1

思路

有一个 m x n 的二进制矩阵，0 代表空位，1 代表有障碍物。有一个机器人可以向右或向下移动，求从 (0,0) 到 (m - 1, n - 1) 的路径有多少。

定义 dp[i][j] 表示到达坐标 (i - 1, j - 1) 的不同路径数。这样定义可以省去单独初始化第一行第一列。状态转移方程为 当 obstacleGrid[i][j] == 0 时, dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，初值为 dp[0][1] = 1，可以视为从 (-1, 0) 到 (0, 0) 的路径数量，如果 (0, 0) 有障碍物则为 0，否则为 1。

代码

/**
 * @date 2025-02-01 20:05
 */
public class UniquePathsWithObstacles63 {

     public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] dp = new int[m + 1][n + 1];
        dp[0][1] = 1;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (obstacleGrid[i - 1][j - 1] == 0){
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[m][n];
    }

}

性能

目标

给你一个正整数 n ，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

示例 1：

输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]

示例 2：

输入：n = 1
输出：[[1]]

说明：

1 <= n <= 20

思路

生成一个 n x n 的正方形矩阵，元素值 1 ~ n^2 按顺时针螺旋顺序排列。

定义 4 个方向，用 direction[i] 表示沿着 i 方向前进的坐标变化量。首先从 (0, 0) 开始向右遍历，预先计算下一步的坐标，如果越界或者已经设置过值则转向。这种解法需要标记已经设置过值的数组，由于填充的元素值都大于 0，数组初值无需特殊处理，只需判断元素是否大于 0 即可。

代码

/**
 * @date 2025-02-07 0:11
 */
public class GenerateMatrix59 {

    public int[][] generateMatrix(int n) {
        int[][] matrix = new int[n][n];
        int[][] direction = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int x = 0, y = 0, num = 1, d = 0;
        for (int i = 0; i < n * n; i++) {
            matrix[x][y] = num++;
            int xNext = x + direction[d][0];
            int yNext = y + direction[d][1];
            if (xNext == n || yNext < 0 || yNext == n || matrix[xNext][yNext] != 0) {
                d = (d + 1) % 4;
            }
            x += direction[d][0];
            y += direction[d][1];
        }
        return matrix;
    }

}

性能

目标

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例 1：

输入：nums = [1,1,2]
输出：
[[1,1,2],
 [1,2,1],
 [2,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]]

说明：

• 1 <= nums.length <= 8
• -10 <= nums[i] <= 10

思路

返回数组不重复的全排列。

依次枚举第 i 个位置的可选元素，不含重复元素的全排列个数为 n!，收集结果复杂度为 O(n)。重复排列的处理与 与 90.子集II 类似，先排序数组，在每个位置枚举元素时，直接跳过后续相同的元素。

代码

/**
 * @date 2025-02-06 8:41
 */
public class PermuteUnique47 {

    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        int n = nums.length;
        boolean[] visited = new boolean[n];
        List<Integer> path = Arrays.asList(new Integer[n]);
        dfs(0, nums, visited, path, res);
        return res;
    }

    public void dfs(int index, int[] nums, boolean[] visited, List<Integer> path, List<List<Integer>> res) {
        int n = nums.length;
        if (index == n) {
            List<Integer> permute = new ArrayList<>(path);
            res.add(permute);
            return;
        }
        for (int i = 0; i < n; i++) {
            if (visited[i] || (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1])) {
                continue;
            }
            visited[i] = true;
            path.set(index, nums[i]);
            dfs(index + 1, nums, visited, path, res);
            visited[i] = false;
        }
    }

}

性能

目标

已知存在一个按非降序排列的整数数组 nums ，数组中的值不必互不相同。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转 ，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。

给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。

你必须尽可能减少整个操作步骤。

示例 1：

输入：nums = [2,5,6,0,0,1,2], target = 0
输出：true

示例 2：

输入：nums = [2,5,6,0,0,1,2], target = 3
输出：false

说明：

• 1 <= nums.length <= 5000
• -10^4 <= nums[i] <= 10^4
• 题目数据保证 nums 在预先未知的某个下标上进行了旋转
• -10^4 <= target <= 10^4

进阶：

此题与 33.搜索旋转排序数组 相似，但本题中的 nums 可能包含 重复 元素。这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？

思路

将 有序数组 划分为两个子数组，交换子数组的顺序得到旋转数组 nums，判断旋转数组中是否存在 target。

根据题意可知，原来的有序数组被划分成两部分，第一部分的所有元素均大于 等于 第二部分的所有元素。

此题与 33.搜索旋转排序数组 相似，但本题中的 nums 可能包含 重复 元素。如果当前元素恰好与切点的元素值相同，那么我们无法判断该搜索哪一部分。

例如，如果当前元素值大于 target，但是恰好与第一个元素相同：

• 如果当前元素就是位于第一部分，那么我们应该将 left 左移，以便到达第二部分搜索。
• 如果当前元素已经位于第二部分，那么我们应该将 right 右移，以便找到更小的target。

最简单的处理方法是缩小右边界，因为这种情况只会出现在切点刚好在连续相同元素中间，这时最左侧的元素一定与最右侧的元素相同，我们可以提前将 right 移到第一个与 left 不同的位置。这样当前元素属于哪一部分就确定了，不会影响判断。

代码

/**
 * @date 2025-02-01 14:33
 */
public class Search81 {

    public boolean search(int[] nums, int target) {
        int n = nums.length;
        int left = 0, right = n - 1;
        while (right > 0 && nums[left] == nums[right]) {
            right--;
        }
        int mid = left + (right - left) / 2;
        while (left <= right) {
            if (check(nums[mid], nums[0], target)) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
            mid = left + (right - left) / 2;
        }
        if (left >= 0 && left < n) {
            return nums[left] == target;
        }
        return false;
    }

    public boolean check(int midValue, int firstValue, int target) {
        if (target < firstValue) {
            if (midValue >= firstValue) {
                return true;
            } else {
                return midValue < target;
            }
        } else {
            if (midValue >= firstValue) {
                return midValue < target;
            } else {
                return false;
            }
        }
    }

}

性能