标签： medium

目标

给你一个 m * n 的矩阵，矩阵中的元素不是 0 就是 1，请你统计并返回其中完全由 1 组成的 正方形 子矩阵的个数。

示例 1：

输入：matrix =
[
  [0,1,1,1],
  [1,1,1,1],
  [0,1,1,1]
]
输出：15
解释： 
边长为 1 的正方形有 10 个。
边长为 2 的正方形有 4 个。
边长为 3 的正方形有 1 个。
正方形的总数 = 10 + 4 + 1 = 15.

示例 2：

输入：matrix = 
[
  [1,0,1],
  [1,1,0],
  [1,1,0]
]
输出：7
解释：
边长为 1 的正方形有 6 个。 
边长为 2 的正方形有 1 个。
正方形的总数 = 6 + 1 = 7.

说明：

• 1 <= arr.length <= 300
• 1 <= arr[0].length <= 300
• 0 <= arr[i][j] <= 1

思路

统计 m x n 矩阵中 全是 1 的正方形子矩阵个数。

遍历的逻辑是枚举长度，以左上顶点为圆心，长度为半径进行遍历。

代码

/**
 * @date 2025-08-20 8:44
 */
public class CountSquares1277 {

    public int countSquares(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int res = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] != 1) {
                    continue;
                }
                int max = Math.min(m - i, n - j);
                int l = 1;
                here:
                for (; l < max; l++) {
                    for (int y = i + l; y >= i; y--) {
                        if (matrix[y][j + l] == 0) {
                            break here;
                        }
                    }
                    for (int x = j + l; x >= j; x--) {
                        if (matrix[i + l][x] == 0) {
                            break here;
                        }
                    }
                }
                res += l;
            }
        }
        return res;
    }

}

性能

目标

给你一个整数数组 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;
    }

}

性能

目标

给你两个长度为 n 的整数数组，fruits 和 baskets，其中 fruits[i] 表示第 i 种水果的 数量，baskets[j] 表示第 j 个篮子的 容量。

你需要对 fruits 数组从左到右按照以下规则放置水果：

• 每种水果必须放入第一个 容量大于等于 该水果数量的 最左侧可用篮子 中。
• 每个篮子只能装 一种 水果。
• 如果一种水果 无法放入 任何篮子，它将保持 未放置。

返回所有可能分配完成后，剩余未放置的水果种类的数量。

示例 1

输入： fruits = [4,2,5], baskets = [3,5,4]
输出： 1
解释：
fruits[0] = 4 放入 baskets[1] = 5。
fruits[1] = 2 放入 baskets[0] = 3。
fruits[2] = 5 无法放入 baskets[2] = 4。
由于有一种水果未放置，我们返回 1。

示例 2

输入： fruits = [3,6,1], baskets = [6,4,7]
输出： 0
解释：
fruits[0] = 3 放入 baskets[0] = 6。
fruits[1] = 6 无法放入 baskets[1] = 4（容量不足），但可以放入下一个可用的篮子 baskets[2] = 7。
fruits[2] = 1 放入 baskets[1] = 4。
由于所有水果都已成功放置，我们返回 0。

说明：

• n == fruits.length == baskets.length
• 1 <= n <= 10^5
• 1 <= fruits[i], baskets[i] <= 10^9

思路

有水果 fruits 与 篮子 baskets 两个数组，fruits[i] 表示下标为 i 的水果数量，baskets[i] 表示下标为 i 位置上篮子的容量。现在需要按 fruits 的顺序从左往右将其放入篮子中，放置的位置是第一个能够容下水果的篮子，每个篮子只能放一种水果，如果没有位置能放下则保持未放置状态，求剩余未放置的水果种类。

暴力解法是枚举每种水果数量，然后枚举篮子，标记第一个能放下的篮子，时间复杂度为 O(n^2)。由于 basket 是无序的，没办法使用二分查找，并且排序会影响最终结果。因为未排序前，数量小的水果可能占据了大的篮子，导致数量多的水果无法放置。

考虑将 basket 分块，记录每一块的最大值，然后找到块内第一个大于 fruits[i] 的元素，然后将其置零。

代码

/**
 * @date 2025-08-05 15:20
 */
public class NumOfUnplacedFruits3479 {

    public int numOfUnplacedFruits(int[] fruits, int[] baskets) {
        int n = fruits.length;
        int blockSize = (int) Math.ceil(Math.sqrt(n));
        int m = (int) Math.ceil((double) n / blockSize);
        int[] block = new int[m];
        int bi = 0;
        while (bi < m) {
            int start = bi * blockSize;
            int max = 0;
            for (int j = start; j < start + blockSize && j < n; j++) {
                max = Math.max(max, baskets[j]);
            }
            block[bi++] = max;
        }
        int res = n;
        for (int fruit : fruits) {
            int i = 0;
            for (; i < m; i++) {
                if (fruit <= block[i]) {
                    res--;
                    break;
                }
            }
            int start = i * blockSize;
            int newMax = 0;
            for (int j = start; j < start + blockSize && j < n; j++) {
                if (baskets[j] >= fruit) {
                    if (baskets[j] == block[i]) {
                        for (int k = j + 1; k < start + blockSize && k < n; k++) {
                            newMax = Math.max(newMax, baskets[k]);
                        }
                        block[i] = newMax;
                    }
                    baskets[j] = 0;
                    break;
                } else {
                    newMax = Math.max(newMax, baskets[j]);
                }
            }
        }
        return res;
    }

}

性能

目标

你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类 。

你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：

• 你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
• 你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
• 一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。

给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。

示例 1：

输入：fruits = [1,2,1]
输出：3
解释：可以采摘全部 3 棵树。

示例 2：

输入：fruits = [0,1,2,2]
输出：3
解释：可以采摘 [1,2,2] 这三棵树。
如果从第一棵树开始采摘，则只能采摘 [0,1] 这两棵树。

示例 3：

输入：fruits = [1,2,3,2,2]
输出：4
解释：可以采摘 [2,3,2,2] 这四棵树。
如果从第一棵树开始采摘，则只能采摘 [1,2] 这两棵树。

示例 4：

输入：fruits = [3,3,3,1,2,1,1,2,3,3,4]
输出：5
解释：可以采摘 [1,2,1,1,2] 这五棵树。

说明：

• 1 <= fruits.length <= 10^5
• 0 <= fruits[i] < fruits.length

思路

求满足条件的子数组的最大长度，要求子数组最多包含两个不同的元素。

滑动窗口。

代码

/**
 * @date 2025-08-04 8:51
 */
public class TotalFruit904 {

    public int totalFruit(int[] fruits) {
        int n = fruits.length;
        int res = 0;
        Map<Integer, Integer> map = new HashMap<>();
        int l = 0;
        for (int i = 0; i < n; i++) {
            map.merge(fruits[i], 1, Integer::sum);
            while (map.size() > 2) {
                map.merge(fruits[l], -1, Integer::sum);
                if (map.get(fruits[l]) == 0) {
                    map.remove(fruits[l]);
                }
                l++;
            }
            res = Math.max(res, i - l + 1);
        }
        return res;
    }

}

性能