标签： 数学

目标

给你两个 正 整数 num 和 sum。

如果一个正整数 n 满足以下两个条件，则称其为 好整数 ：

• n 的位数 恰好 为 num。
• n 的各位数字之和 恰好 为 sum。

一个 好整数 n 的 分数 定义为 n 的各位数字的平方和。

返回一个 字符串 ，表示能获得 最大分数 的 好整数 n。如果有多个可能的整数，返回 最大 的那个。如果不存在这样的整数，返回一个空字符串。

示例 1:

输入: num = 2, sum = 3
输出: "30"
解释:
有 3 个好整数：12、21 和 30。
12 的分数是 12 + 22 = 5。
21 的分数是 22 + 12 = 5。
30 的分数是 32 + 02 = 9。
最大分数是 9，由好整数 30 获得。因此，答案是 "30"。

示例 2:

输入: num = 2, sum = 17
输出: "98"
解释:
有两个好整数：89 和 98。
89 的分数是 82 + 92 = 145。
98 的分数是 92 + 82 = 145。
最大分数是 145。获得此分数的最大好整数是 98。因此，答案是 "98"。

示例 3:

输入: num = 1, sum = 10
输出: ""
解释:
不存在恰好有 1 位数字且各位数字之和为 10 的整数。因此，答案是 ""。

说明:

• 1 <= num <= 2 * 10^5
• 1 <= sum <= 2 * 10^6

思路

定义数位长度为 num，数位之和为 sum 的整数为好整数，好整数的分数定义为各位数字的平方和，返回分数最大的好整数，如果分数相同则返回整数值最大的，如果不存在返回空串。

贪心策略就是取当前位所能取的最大值，余下的补 0。

代码

/**
 * @date 2026-10-14 9:21
 */
public class MaxSumOfSquares3723 {

    public String maxSumOfSquares(int num, int sum) {
        StringBuilder sb = new StringBuilder();
        while (num > 0) {
            int d = Math.min(sum, 9);
            sum -= d;
            num--;
            sb.append(d);
        }
        return sum == 0 ? sb.toString() : "";
    }

}

性能

目标

给你一个由 正 整数组成的数组 nums，以及一个 正 整数 k。

你可以对 nums 执行 一次 操作，该操作中可以移除任意 不重叠 的前缀和后缀，使得 nums 仍然 非空 。

你需要找出 nums 的 x 值，即在执行操作后，剩余元素的 乘积 除以 k 后的 余数 为 x 的操作数量。

返回一个大小为 k 的数组 result，其中 result[x] 表示对于 0 <= x <= k - 1，nums 的 x 值。

数组的 前缀 指从数组起始位置开始到数组中任意位置的一段连续子数组。

数组的 后缀 是指从数组中任意位置开始到数组末尾的一段连续子数组。

子数组 是数组中一段连续的元素序列。

注意，在操作中选择的前缀和后缀可以是 空的 。

示例 1：

输入： nums = [1,2,3,4,5], k = 3
输出： [9,2,4]
解释：
对于 x = 0，可行的操作包括所有不会移除 nums[2] == 3 的前后缀移除方式。
对于 x = 1，可行操作包括：
    移除空前缀和后缀 [2, 3, 4, 5]，nums 变为 [1]。
    移除前缀 [1, 2, 3] 和后缀 [5]，nums 变为 [4]。
对于 x = 2，可行操作包括：
    移除空前缀和后缀 [3, 4, 5]，nums 变为 [1, 2]。
    移除前缀 [1] 和后缀 [3, 4, 5]，nums 变为 [2]。
    移除前缀 [1, 2, 3] 和空后缀，nums 变为 [4, 5]。
    移除前缀 [1, 2, 3, 4] 和空后缀，nums 变为 [5]。

示例 2：

输入： nums = [1,2,4,8,16,32], k = 4
输出： [18,1,2,0]
解释：
对于 x = 0，唯一 不 得到 x = 0 的操作有：
    移除空前缀和后缀 [4, 8, 16, 32]，nums 变为 [1, 2]。
    移除空前缀和后缀 [2, 4, 8, 16, 32]，nums 变为 [1]。
    移除前缀 [1] 和后缀 [4, 8, 16, 32]，nums 变为 [2]。
对于 x = 1，唯一的操作是：
    移除空前缀和后缀 [2, 4, 8, 16, 32]，nums 变为 [1]。
对于 x = 2，可行操作包括：
    移除空前缀和后缀 [4, 8, 16, 32]，nums 变为 [1, 2]。
    移除前缀 [1] 和后缀 [4, 8, 16, 32]，nums 变为 [2]。
对于 x = 3，没有可行的操作。

示例 3：

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

说明：

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

思路

有一个正整数数组 nums 和一个正整数 k，每次操作可以移除数组不重叠的前缀与后缀，即保留中间非空的子数组。求子数组元素乘积模 k 的余数为 x 的操作数量。

定义 dp[i][j] 表示 [0, i] 中以 i 为右端点的子数组中模 k 余 j 的个数。使用刷表法更新 dp[i][nums[i] % k]++, dp[i][nums[i] * j % k] += dp[i - 1][j]。

代码

/**
 * @date 2026-09-21 15:19
 */
public class ResultArray3524 {

    public long[] resultArray(int[] nums, int k) {
        int n = nums.length;
        long[][] dp = new long[n][k];
        dp[0][nums[0] % k] = 1;
        long[] res = new long[k];
        res[nums[0] % k]++;
        for (int i = 1; i < n; i++) {
            int rem = nums[i] % k;
            dp[i][rem]++;
            for (int j = 0; j < k; j++) {
                dp[i][(int) ((long) nums[i] * j % k)] += dp[i - 1][j];
            }
            for (int j = 0; j < k; j++) {
                res[j] += dp[i][j];
            }
        }
        return res;
    }

}

性能

目标

给你一个以 (radius, xCenter, yCenter) 表示的圆和一个与坐标轴平行的矩形 (x1, y1, x2, y2) ，其中 (x1, y1) 是矩形左下角的坐标，而 (x2, y2) 是右上角的坐标。

如果圆和矩形有重叠的部分，请你返回 true ，否则返回 false 。

换句话说，请你检测是否 存在 点 (xi, yi) ，它既在圆上也在矩形上（两者都包括点落在边界上的情况）。

示例 1 ：

输入：radius = 1, xCenter = 0, yCenter = 0, x1 = 1, y1 = -1, x2 = 3, y2 = 1
输出：true
解释：圆和矩形存在公共点 (1,0) 。

示例 2 ：

输入：radius = 1, xCenter = 1, yCenter = 1, x1 = 1, y1 = -3, x2 = 2, y2 = -1
输出：false

示例 3 ：

输入：radius = 1, xCenter = 0, yCenter = 0, x1 = -1, y1 = 0, x2 = 0, y2 = 1
输出：true

说明：

• 1 <= radius <= 2000
• -10^4 <= xCenter, yCenter <= 10^4
• -10^4 <= x1 < x2 <= 10^4
• -10^4 <= y1 < y2 <= 10^4

思路

平面坐标中有一个圆 (radius, xCenter, yCenter) 和一个平行于坐标轴的矩形 (x1, y1, x2, y2)，判断圆和矩形是否重叠。

求出圆心到矩形的最短距离，然后判断最短距离与圆的半径关系。最短距离为 dx^2 + dy^2 = (x - xCenter)^2 + (y - yCenter)^2，要使距离最小，分别使 |dx| 与 |dy| 最小即可。

要使 x1 <= x <= x2 与 xCenter 的距离最小，

• 当 x1 <= xCenter <= x2 时，取 x = xCenter；
• 当 xCenter < x1 时，取 x = x1；
• 当 xCenter > x2 时，取 x = x2；

可简化为 x = Math.max(x1, Math.min(xCenter, x2))，同理 y = Math.max(y1, Math.min(yCenter, y2))。

代码

/**
 * @date 2026-09-22 10:18
 */
public class CheckOverlap1401 {

    public boolean checkOverlap(int radius, int xCenter, int yCenter, int x1, int y1, int x2, int y2) {
        int dx = Math.max(x1, Math.min(xCenter, x2)) - xCenter;
        int dy = Math.max(y1, Math.min(yCenter, y2)) - yCenter;
        return dx * dx + dy * dy <= radius * radius;
    }
}

性能

目标

给你一维空间的 n 个点，其中第 i 个点（编号从 0 到 n-1）位于 x = i 处，请你找到 恰好 k 个不重叠 线段且每个线段至少覆盖两个点的方案数。线段的两个端点必须都是 整数坐标 。这 k 个线段不需要全部覆盖全部 n 个点，且它们的端点 可以 重合。

请你返回 k 个不重叠线段的方案数。由于答案可能很大，请将结果对 10^9 + 7 取余 后返回。

示例 1：

输入：n = 4, k = 2
输出：5
解释：
如图所示，两个线段分别用红色和蓝色标出。
上图展示了 5 种不同的方案 {(0,2),(2,3)}，{(0,1),(1,3)}，{(0,1),(2,3)}，{(1,2),(2,3)}，{(0,1),(1,2)} 。

示例 2：

输入：n = 3, k = 1
输出：3
解释：总共有 3 种不同的方案 {(0,1)}, {(0,2)}, {(1,2)} 。

示例 3：

输入：n = 30, k = 7
输出：796297179
解释：画 7 条线段的总方案数为 3796297200 种。将这个数对 10^9 + 7 取余得到 796297179 。

示例 4：

输入：n = 5, k = 3
输出：7

示例 5：

输入：n = 3, k = 2
输出：1

说明：

• 2 <= n <= 1000
• 1 <= k <= n-1

思路

数轴上有 n 个点，编号为 0 ~ n - 1，求从中选择 k 个不重叠线段（至少覆盖两个点）的方案数。线段 [a, b] 与 [c, d] 不重叠指 b <=c 或 d <= a。

定义 dp[i][k] 表示 [0, i] 中恰好 k 个不重叠线段的方案数。根据选或者不选 i 考虑状态转移方程，如果不选 i，方案数等于前面的方案数，如果选，需要枚举前面所有的 p ∈ [0, i - 1]，累加 dp[p][j - 1]。

• dp[i][j] = (dp[i - 1][j] + sum) % mod，sum = Σdp[p][j - 1], p ∈ [0, i - 1]

代码

/**
 * @date 2026-09-17 15:31
 */
public class NumberOfSets1621 {

    public int numberOfSets(int n, int k) {
        int mod = 1000000007;
        int[][] dp = new int[n][k + 1];
        dp[0][0] = 1;
        int[] prefix = new int[k + 1];
        for (int i = 1; i < n; i++) {
            for (int j = 1; j <= k; j++) {
                prefix[j] = (prefix[j] + dp[i - 1][j - 1]) % mod;
                dp[i][j] = (dp[i - 1][j] + prefix[j]) % mod;
            }
        }
        int res = 0;
        for (int i = 0; i < n; i++) {
            res = (res + dp[i][k]) % mod;
        }
        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^15

思路

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

• 1,000 ~ 999,999 之间的数字有 1 个逗号
• 1,000,000 ~ 999,999,999 之间的数字有 2 个逗号
• 1,000,000,000 ~ 999,999,999,999 之间的数字有 3 个逗号
• 1,000,000,000,000 ~ 999,999,999,999,999 之间的数字有 4 个逗号
• 1,000,000,000,000,000 有 5 个逗号

返回 max(0, n - 999) + max(0, n - 999999) + max(0, n - 999999999) + max(0, n - 999999999999) + max(0, n - 999999999999999)。

可以写成循环的形式，for (long i = 1000; i <= n; i *= 1000) { res += n - i + 1; }。

代码

/**
 * @date 2026-09-08 9:15
 */
public class CountCommas3871 {

    public long countCommas(long n) {
        long res = 0;
        for (long i = 1000; i <= n; i *= 1000) {
            res += n - i + 1;
        }
        return res;
    }
}

性能