作者： admin

目标

给你一个整数数组 nums ，返回全部为 0 的 子数组 数目。

子数组 是一个数组中一段连续非空元素组成的序列。

示例 1：

输入：nums = [1,3,0,0,2,0,0,4]
输出：6
解释：
子数组 [0] 出现了 4 次。
子数组 [0,0] 出现了 2 次。
不存在长度大于 2 的全 0 子数组，所以我们返回 6 。

示例 2：

输入：nums = [0,0,0,2,0,0]
输出：9
解释：
子数组 [0] 出现了 5 次。
子数组 [0,0] 出现了 3 次。
子数组 [0,0,0] 出现了 1 次。
不存在长度大于 3 的全 0 子数组，所以我们返回 9 。

示例 3：

输入：nums = [2,10,2019]
输出：0
解释：没有全 0 子数组，所以我们返回 0 。

说明：

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

思路

返回数组的全 0 子数组个数。

长度为 k 的子数组个数为 (1 + k) * k / 2。可以使用贪心策略，如果当前元素是 0 找到以它为起点的最长连续 0 数组，计算子数组个数。

代码

/**
 * @date 2025-08-19 8:54
 */
public class ZeroFilledSubarray2348 {

    public long zeroFilledSubarray(int[] nums) {
        long res = 0L;
        int n = nums.length;
        int i = 0;
        while (i < n){
            if (nums[i] != 0){
                i++;
                continue;
            }
            int start = i;
            while (i < n && nums[i] == 0){
                i++;
            }
            int cnt = i - start;
            res += (1L + cnt) * cnt / 2;
        }

        return res;
    }
}

性能

目标

给你一个正整数 n ，你需要找到一个下标从 0 开始的数组 powers ，它包含 最少 数目的 2 的幂，且它们的和为 n 。powers 数组是 非递减 顺序的。根据前面描述，构造 powers 数组的方法是唯一的。

同时给你一个下标从 0 开始的二维整数数组 queries ，其中 queries[i] = [lefti, righti] ，其中 queries[i] 表示请你求出满足 lefti <= j <= righti 的所有 powers[j] 的乘积。

请你返回一个数组 answers ，长度与 queries 的长度相同，其中 answers[i]是第 i 个查询的答案。由于查询的结果可能非常大，请你将每个 answers[i] 都对 10^9 + 7 取余 。

示例 1：

输入：n = 15, queries = [[0,1],[2,2],[0,3]]
输出：[2,4,64]
解释：
对于 n = 15 ，得到 powers = [1,2,4,8] 。没法得到元素数目更少的数组。
第 1 个查询的答案：powers[0] * powers[1] = 1 * 2 = 2 。
第 2 个查询的答案：powers[2] = 4 。
第 3 个查询的答案：powers[0] * powers[1] * powers[2] * powers[3] = 1 * 2 * 4 * 8 = 64 。
每个答案对 10^9 + 7 得到的结果都相同，所以返回 [2,4,64] 。

示例 2：

输入：n = 2, queries = [[0,0]]
输出：[2]
解释：
对于 n = 2, powers = [2] 。
唯一一个查询的答案是 powers[0] = 2 。答案对 10^9 + 7 取余后结果相同，所以返回 [2] 。

说明：

• 1 <= n <= 10^9
• 1 <= queries.length <= 10^5
• 0 <= starti <= endi < powers.length

思路

给定一个正整数，将其拆分成最少数目的 2 的幂，即二进制表示中每一个 1 所表示的 2 的幂，按照从小到大的顺序放入 nums。有一个查询数组 queries，queries[i] = [from, to] 表示查询 nums 从 from 到 to 的乘积，返回对应的结果数组。

由于 nums 长度最大 31，因此可以提前预处理所有子数组的乘积，或值直接暴力计算查询范围内的元素乘积。

注意不能计算前缀乘积，为了防止溢出存的是余数，相除后取余并不满足分配律。或者换一种思路计算幂次的前缀和，然后再计算 2 的幂对 mod 取余。

代码

/**
 * @date 2025-08-11 9:52
 */
public class ProductQueries2438 {

    public int[] productQueries(int n, int[][] queries) {
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < 31; i++) {
            int p = 1 << i;
            if ((n & p) == p) {
                list.add(p);
            }
        }
        int mod = 1000000007;
        int[] res = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int from = queries[i][0];
            int to = queries[i][1];
            res[i] = 1;
            for (int j = from; j <= to; j++) {
                res[i] = (int) ((long) res[i] * list.get(j) % mod);
            }
        }
        return res;
    }

}

性能

目标

给定正整数 n ，我们按任何顺序（包括原始顺序）将数字重新排序，注意其前导数字不能为零。

如果我们可以通过上述方式得到 2 的幂，返回 true；否则，返回 false。

示例 1：

输入：n = 1
输出：true

示例 2：

输入：n = 10
输出：false

说明：

• 1 <= n <= 10^9

思路

判断数字重新排列后能否变成 2 的幂。

统计所有数位上数字的出现次数，如果与 2 的幂完全相同则返回 true。

代码

/**
 * @date 2025-08-10 13:49
 */
public class ReorderedPowerOf2_869 {

    public static int[][] nums = new int[31][10];

    static {
        for (int i = 0; i < 31; i++) {
            int num = 1 << i;
            while (num > 0) {
                int d = num % 10;
                nums[i][d]++;
                num /= 10;
            }
        }
    }

    public boolean reorderedPowerOf2(int n) {
        int[] digits = new int[10];
        while (n > 0) {
            int d = n % 10;
            digits[d]++;
            n /= 10;
        }
        here:
        for (int[] num : nums) {
            for (int i = 0; i < num.length; i++) {
                if (num[i] != digits[i]) {
                    continue here;
                }
            }
            return true;
        }
        return false;
    }

}

性能