标签： 数学

目标

矩形以列表 [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 的数组 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;
    }
}

性能

目标

给你一个下标从 0 开始的整数数组 nums 。

如果一个前缀 nums[0..i] 满足对于 1 <= j <= i 的所有元素都有 nums[j] = nums[j - 1] + 1 ，那么我们称这个前缀是一个 顺序前缀 。特殊情况是，只包含 nums[0] 的前缀也是一个 顺序前缀 。

请你返回 nums 中没有出现过的 最小 整数 x ，满足 x 大于等于 最长 顺序前缀的和。

示例 1：

输入：nums = [1,2,3,2,5]
输出：6
解释：nums 的最长顺序前缀是 [1,2,3] ，和为 6 ，6 不在数组中，所以 6 是大于等于最长顺序前缀和的最小整数。

示例 2：

输入：nums = [3,4,5,1,12,14,13]
输出：15
解释：nums 的最长顺序前缀是 [3,4,5] ，和为 12 ，12、13 和 14 都在数组中，但 15 不在，所以 15 是大于等于最长顺序前缀和的最小整数。

说明：

• 1 <= nums.length <= 50
• 1 <= nums[i] <= 50

思路

定义数组 nums 的顺序前缀是满足 1 <= j <= i, nums[j] = nums[j - 1] + 1 的前缀，返回大于等于数组顺序前缀和且没有出现在数组的最小整数。

使用哈希表保存数组所有元素，计算顺序前缀和 sum，从 sum 返回第一个不在哈希表中的整数即可。

代码

/**
 * @date 2026-08-11 8:58
 */
public class MissingInteger2996 {

    public int missingInteger(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return nums[0] + 1;
        }
        Set<Integer> set = Arrays.stream(nums).boxed().collect(Collectors.toSet());
        int sum = nums[0];
        for (int i = 1; i < n; i++) {
            if (nums[i] != nums[i - 1] + 1) {
                break;
            }
            sum += nums[i];
        }
        while (set.contains(sum)) {
            sum++;
        }
        return sum;
    }
}

性能

目标

给你一个字符串 word，由 不同 小写英文字母组成。

电话键盘上的按键与 不同 小写英文字母集合相映射，可以通过按压按键来组成单词。例如，按键 2 对应 ["a","b","c"]，我们需要按一次键来输入 "a"，按两次键来输入 "b"，按三次键来输入 "c"。

现在允许你将编号为 2 到 9 的按键重新映射到 不同 字母集合。每个按键可以映射到 任意数量 的字母，但每个字母 必须 恰好 映射到 一个 按键上。你需要找到输入字符串 word 所需的 最少 按键次数。

返回重新映射按键后输入 word 所需的 最少 按键次数。

下面给出了一种电话键盘上字母到按键的映射作为示例。注意 1，*，# 和 0 不 对应任何字母。

示例 1：

输入：word = "abcde"
输出：5
解释：图片中给出的重新映射方案的输入成本最小。
"a" -> 在按键 2 上按一次
"b" -> 在按键 3 上按一次
"c" -> 在按键 4 上按一次
"d" -> 在按键 5 上按一次
"e" -> 在按键 6 上按一次
总成本为 1 + 1 + 1 + 1 + 1 = 5 。
可以证明不存在其他成本更低的映射方案。

示例 2：

输入：word = "xycdefghij"
输出：12
解释：图片中给出的重新映射方案的输入成本最小。
"x" -> 在按键 2 上按一次
"y" -> 在按键 2 上按两次
"c" -> 在按键 3 上按一次
"d" -> 在按键 3 上按两次
"e" -> 在按键 4 上按一次
"f" -> 在按键 5 上按一次
"g" -> 在按键 6 上按一次
"h" -> 在按键 7 上按一次
"i" -> 在按键 8 上按一次
"j" -> 在按键 9 上按一次
总成本为 1 + 2 + 1 + 2 + 1 + 1 + 1 + 1 + 1 + 1 = 12 。
可以证明不存在其他成本更低的映射方案。

说明：

• 1 <= word.length <= 26
• word 仅由小写英文字母组成。
• word 中的所有字母互不相同。

思路

可以将 26 个字母映射到 2 ~ 9 按键上，比如将 abc 映射到 2，那么输入 b 需要按两下 2，输入 c 需要按三下 2。给定一个由 不同字母 组成的单词 word，返回输入该字符所需的最少按键次数。

字母出现的频次都是 1，先将所有按键的第一个位置填满，然后是第二个、第三个。

录入单词所需的按键次数为 8 * (1 + 2 + …… + k) + (n % 8) * (k + 1) = 8 * (1 + k) * k / 2 + (n % 8) * (k + 1) = 4 * k * (k + 1) + (n % 8) * (k + 1) = (4 * k + n % 8) * (k + 1)。

代码

/**
 * @date 2026-07-30 9:10
 */
public class MinimumPushes3014 {

    public int minimumPushes_v1(String word) {
        int n = word.length();
        int k = n / 8;
        return (4 * k + n % 8) * (k + 1);
    }
}

性能

目标

给你一个整型数组 nums ，在数组中找出由三个数组成的最大乘积，并输出这个乘积。

示例 1：

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

示例 2：

输入：nums = [1,2,3,4]
输出：24

示例 3：

输入：nums = [-1,-2,-3]
输出：-6

说明：

• 3 <= nums.length <= 10^4
• -1000 <= nums[i] <= 1000

思路

从数组中取三个不同的下标，返回其乘积的最大值。

由于存在负数，分情况讨论，定义 max1、max2、max3 分别为前三大元素，min1、min2 分别是前二小元素：

• 如果 max1 < 0, 乘积只能为负，要使乘积最大，那么其绝对值应该最小，因此取 max1 * max2 * max3
• 如果 max2 < 0, 最大乘积可以为正，取最小的两个负数相乘，乘积最大，取 max1 * min1 * min2
• 如果 max3 < 0，乘积可能为正也可能为负（只有三个元素），不论那种情况，都可取 max1 * min1 * min2
• 如果 max3 > 0, 最大值可能是 max1 * max2 * max3 或者 max1 * min1 * min2

代码

/**
 * @date 2026-07-27 16:37
 */
public class MaximumProduct628 {

    public int maximumProduct_v1(int[] nums) {
        int max1 = -1001, max2 = -1001, max3 = -1001;
        int min1 = 1001, min2 = 1001;
        for (int num : nums) {
            if (num > max1) {
                max3 = max2;
                max2 = max1;
                max1 = num;
            } else if (num > max2) {
                max3 = max2;
                max2 = num;
            } else if (num > max3) {
                max3 = num;
            }
            if (num < min1) {
                min2 = min1;
                min1 = num;
            } else if (num < min2) {
                min2 = num;
            }
        }
        return Math.max(max1 * max2 * max3, max1 * min1 * min2);
    }

}

性能

目标

给定一个正整数 n。

返回 任意两位数字 相乘所得的 最大 乘积。

注意：如果某个数字在 n 中出现多次，你可以多次使用该数字。

示例 1：

输入： n = 31
输出： 3
解释：
n 的数字是 [3, 1]。
任意两位数字相乘的结果为：3 * 1 = 3。
最大乘积为 3。

示例 2：

输入： n = 22
输出： 4
解释：
n 的数字是 [2, 2]。
任意两位数字相乘的结果为：2 * 2 = 4。
最大乘积为 4。

示例 3：

输入： n = 124
输出： 8
解释：
n 的数字是 [1, 2, 4]。
任意两位数字相乘的结果为：1 * 2 = 2, 1 * 4 = 4, 2 * 4 = 8。
最大乘积为 8。

说明：

• 10 <= n <= 10^9

思路

给定一个数字 n，选择数位中的两个数字相乘，返回乘积的最大值。

找到最大的两个数字相乘即可。

代码

/**
 * @date 2026-07-27 14:22
 */
public class MaxProduct3536 {

    public int maxProduct(int n) {
        int max = 0;
        int preMax = 0;
        int res = 0;
        while (n > 0) {
            int d = n % 10;
            if (d >= preMax) {
                preMax = Math.min(max, d);
                max = Math.max(max, d);
                res = Math.max(res, max * preMax);
            }
            n /= 10;
        }
        return res;
    }

}

性能