shelterofly

目标

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

说明：

为什么返回数值是整数，但输出的答案是数组呢？

请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

示例 1：

输入：nums = [1,1,1,2,2,3]
输出：5, nums = [1,1,2,2,3]
解释：函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3。 不需要考虑数组中超出新长度后面的元素。

示例 2：

输入：nums = [0,0,1,1,1,1,2,3,3]
输出：7, nums = [0,0,1,1,2,3,3]
解释：函数应返回新长度 length = 7, 并且原数组的前七个元素被修改为 0, 0, 1, 1, 2, 3, 3。不需要考虑数组中超出新长度后面的元素。

说明：

• 1 <= nums.length <= 3 * 10^4
• -10^4 <= nums[i] <= 10^4
• nums 已按升序排列

思路

原地删除有序数组中重复元素超过两个的元素，返回删除后的数组长度。

使用双指针，一个指针指向重复元素的第三个元素或者第一个不重复元素，另一个指向第一个不重复元素，然后将后者的值赋给前者即可。

代码

/**
 * @date 2024-03-07 10:52
 */
public class RemoveDuplicatesII80 {

    public int removeDuplicates(int[] nums) {
        int n = nums.length;
        int i = 1;
        int res = 1;
        while (i < n) {
            int cnt = 1;
            while (i < n && nums[i] == nums[i - 1]) {
                if (cnt < 2) {
                    nums[res++] = nums[i];
                }
                i++;
                cnt++;
            }
            if (i < n) {
                nums[res++] = nums[i++];
            }
        }
        return res;
    }

}

性能

目标

给定一个 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;
        }
    }

}

性能