分类： leetcode

目标

矩形以列表 [x1, y1, x2, y2] 的形式表示，其中 (x1, y1) 为左下角的坐标，(x2, y2) 是右上角的坐标。矩形的上下边平行于 x 轴，左右边平行于 y 轴。

如果相交的面积为 正 ，则称两矩形重叠。需要明确的是，只在角或边接触的两个矩形不构成重叠。

给出两个矩形 rec1 和 rec2 。如果它们重叠，返回 true；否则，返回 false 。

示例 1：

输入：rec1 = [0,0,2,2], rec2 = [1,1,3,3]
输出：true

示例 2：

输入：rec1 = [0,0,1,1], rec2 = [1,0,2,1]
输出：false

示例 3：

输入：rec1 = [0,0,1,1], rec2 = [2,2,3,3]
输出：false

说明：

• rect1.length == 4
• rect2.length == 4
• -10^9 <= rec1[i], rec2[i] <= 10^9
• rec1 和 rec2 表示一个面积不为零的有效矩形

思路

使用数组 [x1, y1, x2, y2] 表示一个矩形的 左下 (x1, y1) 与 右上 (x2, y2) 顶点。给出两个数组 rec1 与 rec2，判断它们是否重叠。

如果两个矩形重叠，那么两个矩形在两个坐标轴方向的投影区间都应该相交。

代码

/**
 * @date 2026-09-14 9:08
 */
public class IsRectangleOverlap836 {

    public boolean isRectangleOverlap(int[] rec1, int[] rec2) {
        int x1 = rec1[0], x3 = rec2[0];
        int y1 = rec1[1], y3 = rec2[1];
        int x2 = rec1[2], x4 = rec2[2];
        int y2 = rec1[3], y4 = rec2[3];
        return !(x2 <= x3 || x4 <= x1) && !(y2 <= y3 || y4 <= y1);
    }

}

性能

目标

给你一个数字数组 digits，你需要从中选择三个数字组成一个三位偶数，你的任务是求出 不同 三位偶数的数量。

注意：每个数字在三位偶数中都只能使用 一次 ，并且 不能 有前导零。

示例 1：

输入： digits = [1,2,3,4]
输出： 12
解释： 可以形成的 12 个不同的三位偶数是 124，132，134，142，214，234，312，314，324，342，412 和 432。注意，不能形成 222，因为数字 2 只有一个。

示例 2：

输入： digits = [0,2,2]
输出： 2
解释： 可以形成的三位偶数是 202 和 220。注意，数字 2 可以使用两次，因为数组中有两个 2 。

示例 3：

输入： digits = [6,6,6]
输出： 1
解释： 只能形成 666。

示例 4：

输入： digits = [1,3,5]
输出： 0
解释： 无法形成三位偶数。

说明：

• 3 <= digits.length <= 10
• 0 <= digits[i] <= 9

思路

有一个数字数组 digits，数组元素为 0 ~ 9 ，从中选择 3 个组成一个三位偶数，求不同的三位偶数的个数。

从结果来考虑，三位数 100 ~ 999，针对每个数字判断能否由数组中的数字构成即可。

从构造的角度考虑，需要保证个位是偶数，且百位不是 0，要求数字不同，需要维护可用的数字种类，需要知道每个数字的已使用次数，可以使用回溯。

代码

/**
 * @date 2026-09-11 8:56
 */
public class TotalNumbers3483 {

    public int totalNumbers(int[] digits) {
        int[] d = new int[10];
        for (int num : digits) {
            d[num]++;
        }
        int res = 0;
        for (int num = 100; num < 999; num += 2) {
            if (valid(num, d)) {
                res++;
            }
        }
        return res;
    }

    public boolean valid(int num, int[] d) {
        int[] tmp = new int[10];
        while (num > 0) {
            tmp[num % 10]++;
            num /= 10;
        }
        for (int i = 0; i < 10; i++) {
            if (d[i] < tmp[i]) {
                return false;
            }
        }
        return true;
    }

    public int totalNumbers_v0(int[] digits) {
        int[] d = new int[10];
        for (int num : digits) {
            d[num]++;
        }
        int res = 0;
        // 枚举百位
        for (int i = 1; i < d.length; i++) {
            if (d[i] == 0) {
                continue;
            }
            d[i]--;
            res += dfs(0, i, d);
            d[i]++;
        }

        return res;
    }

    int dfs(int index, int num, int[] d) {
        if (index == 2) {
            // 第三个数如果是偶数返回 1
            return num % 2 == 0 ? 1 : 0;
        }
        int res = 0;
        // 枚举十位
        for (int i = 0; i < d.length; i++) {
            if (d[i] == 0) {
                continue;
            }
            d[i]--;
            res += dfs(index + 1, i, d);
            d[i]++;
        }
        return res;
    }

}

性能

目标

给你一个整数 n。

返回将所有从 [1, n]（包含两端）范围内的整数以 标准 数字格式书写时所用到的 逗号总数。

在 标准 格式中：

• 从右边开始，每 三位 数字后插入一个逗号。
• 位数 少于四位 的数字不包含逗号。

示例 1：

输入： n = 1002
输出： 3
解释：
数字 "1,000"、"1,001" 和 "1,002" 每个都包含一个逗号，总计 3 个逗号。

示例 2：

输入： n = 998
输出： 0
解释：
从 1 到 998 的所有数字位数都少于四位，因此没有使用逗号。

说明：

• 1 <= n <= 10^5

思路

返回 [1, n] 之间所有整数的标准写法中总共有多少逗号。所谓标准写法指从右开始每 3 个数字插入一个逗号，且逗号不能位于开头。

只需判断 1 ~ n 之间有多少个数字在 1,000 ~ 100,000 之间，返回 max(0, n - 999) 即可。

代码

/**
 * @date 2026-09-08 9:04
 */
public class CountCommas3870 {

    public int countCommas(int n) {
        return Math.max(0, n - 999);
    }
}

性能

目标

给你一个长度为 n 的整数数组 nums 和一个整数 k。

对于每个下标 i，定义它的 不稳定值 为 max(nums[0..i]) - min(nums[i..n - 1])。

换句话说：

• max(nums[0..i]) 表示从下标 0 到下标 i 的元素中的 最大值 。
• min(nums[i..n - 1]) 表示从下标 i 到下标 n - 1 的元素中的 最小值 。

如果某个下标 i 的不稳定值 小于等于 k，则称该下标为 稳定下标 。

返回 最小 的稳定下标。如果不存在这样的下标，则返回 -1。

示例 1：

输入： nums = [5,0,1,4], k = 3
输出： 3
解释：
在下标 0 处：[5] 中的最大值是 5，[5, 0, 1, 4] 中的最小值是 0，因此不稳定值为 5 - 0 = 5。
在下标 1 处：[5, 0] 中的最大值是 5，[0, 1, 4] 中的最小值是 0，因此不稳定值为 5 - 0 = 5。
在下标 2 处：[5, 0, 1] 中的最大值是 5，[1, 4] 中的最小值是 1，因此不稳定值为 5 - 1 = 4。
在下标 3 处：[5, 0, 1, 4] 中的最大值是 5，[4] 中的最小值是 4，因此不稳定值为 5 - 4 = 1。
这是第一个不稳定值小于等于 k = 3 的下标，因此答案是 3。

示例 2：

输入： nums = [3,2,1], k = 1
输出： -1
解释：
在下标 0 处，不稳定值为 3 - 1 = 2。
在下标 1 处，不稳定值为 3 - 1 = 2。
在下标 2 处，不稳定值为 3 - 1 = 2。
这些值都不小于等于 k = 1，因此答案是 -1。

示例 3：

输入： nums = [0], k = 0
输出： 0
解释：
在下标 0 处，不稳定值为 0 - 0 = 0，它小于等于 k = 0。因此答案是 0。

说明：

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 10^9
• 0 <= k <= 10^9

思路

定义下标 i 的不稳定值为 max(nums[0..i]) - min(nums[i..n - 1])，如果该值小于等于 k 则称 i 为稳定下标。返回最小的稳定下标。

前后缀分解，计算后缀最小值，从左到右枚举，记录前缀最大值，如果满足条件直接返回，否则返回 -1。

代码

/**
 * @date 2026-09-04 9:14
 */
public class FirstStableIndex3903 {

    public int firstStableIndex(int[] nums, int k) {
        int n = nums.length;
        int[] suffix = new int[n + 1];
        Arrays.fill(suffix, Integer.MAX_VALUE);
        for (int i = n - 1; i >= 0; i--) {
            suffix[i] = Math.min(suffix[i + 1], nums[i]);
        }
        int max = 0;
        for (int i = 0; i < n; i++) {
            max = Math.max(max, nums[i]);
            if (max - suffix[i] <= k) {
                return i;
            }
        }
        return -1;
    }

}

性能

目标

给你一个长度为 n 的数组 nums1，其中包含 互不相同 的整数。

你需要构造另一个长度为 n 的数组 nums2，使得 nums2 中的元素要么全部为 奇数，要么全部为 偶数。

对于每个下标 i，你必须从以下两种选择中 任选其一（顺序不限）：

• nums2[i] = nums1[i]
• nums2[i] = nums1[i] - nums1[j]，其中 j != i

如果能够构造出满足条件的数组，则返回 true；否则，返回 false。

示例 1：

输入： nums1 = [2,3]
输出： true
解释：
    选择 nums2[0] = nums1[0] - nums1[1] = 2 - 3 = -1。
    选择 nums2[1] = nums1[1] = 3。
    nums2 = [-1, 3]，两个元素均为奇数。因此答案为 true。

示例 2：

输入： nums1 = [4,6]
输出： true
解释：​​​​​​​
    选择 nums2[0] = nums1[0] = 4。
    选择 nums2[1] = nums1[1] = 6。
    nums2 = [4, 6]，两个元素均为偶数。因此答案为 true。

说明：

• 1 <= n == nums1.length <= 100
• 1 <= nums1[i] <= 100
• nums1 中的所有整数互不相同。

思路

有一个元素互不相同的整数数组 nums1，问能否构造另一个相同长度的数组 nums2，nums2[i] = nums1[i] 或者 nums2[i] = nums1[i] - nums1[j]，其中 j != i。使得 nums2 中的元素全为 奇数 或 偶数。

如果数组元素均为奇数/偶数直接满足条件，否则，可以将偶数减去任意奇数，使得整个数组变为奇数。直接返回 true 即可。

代码

/**
 * @date 2026-09-02 9:17
 */
public class UniformArray3875 {

    public boolean uniformArray(int[] nums1) {
        return true;
    }
}

性能