月度归档： 2025 年 11 月

目标

给你一个二进制字符串 s（仅由 '0' 和 '1' 组成的字符串）。

返回所有字符都为 1 的子字符串的数目。

由于答案可能很大，请你将它对 10^9 + 7 取模后返回。

示例 1：

输入：s = "0110111"
输出：9
解释：共有 9 个子字符串仅由 '1' 组成
"1" -> 5 次
"11" -> 3 次
"111" -> 1 次

示例 2：

输入：s = "101"
输出：2
解释：子字符串 "1" 在 s 中共出现 2 次

示例 3：

输入：s = "111111"
输出：21
解释：每个子字符串都仅由 '1' 组成

示例 4：

输入：s = "000"
输出：0

说明：

• s[i] == '0' 或 s[i] == '1'
• 1 <= s.length <= 10^5

思路

统计全一子串的个数。

根据等差数列求和公式计算即可。

代码

/**
 * @date 2025-11-16 22:17
 */
public class NumSub1513 {

    public int numSub(String s) {
        int mod = 1000000007;
        int n = s.length();
        int res = 0;
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '0') {
                continue;
            }
            int start = i;
            while (i < n && s.charAt(i) == '1'){
                i++;
            }
            int cnt = i - start;
            res += ((cnt + 1L) * cnt / 2) % mod;

        }
        return res;
    }

}

性能

目标

给你一个正整数 n ，表示最初有一个 n x n 、下标从 0 开始的整数矩阵 mat ，矩阵中填满了 0 。

另给你一个二维整数数组 queries 。针对每个查询 queries[i] = [row1i, col1i, row2i, col2i] ，请你执行下述操作：

• 找出 左上角 为 (row1i, col1i) 且 右下角 为 (row2i, col2i) 的子矩阵，将子矩阵中的 每个元素 加 1 。也就是给所有满足 row1i <= x <= row2i 和 col1i <= y <= col2i 的 mat[x][y] 加 1 。

返回执行完所有操作后得到的矩阵 mat 。

示例 1：

输入：n = 3, queries = [[1,1,2,2],[0,0,1,1]]
输出：[[1,1,0],[1,2,1],[0,1,1]]
解释：上图所展示的分别是：初始矩阵、执行完第一个操作后的矩阵、执行完第二个操作后的矩阵。
- 第一个操作：将左上角为 (1, 1) 且右下角为 (2, 2) 的子矩阵中的每个元素加 1 。 
- 第二个操作：将左上角为 (0, 0) 且右下角为 (1, 1) 的子矩阵中的每个元素加 1 。 

示例 2：

输入：n = 2, queries = [[0,0,1,1]]
输出：[[1,1],[1,1]]
解释：上图所展示的分别是：初始矩阵、执行完第一个操作后的矩阵。 
- 第一个操作：将矩阵中的每个元素加 1 。

说明：

• 1 <= n <= 500
• 1 <= queries.length <= 10^4
• 0 <= row1i <= row2i < n
• 0 <= col1i <= col2i < n

思路

有一个元素值为 0 的 n x n 矩阵 mat 和一系列由左上 (r1, c1) 右下 (r2, c2) 两个顶点表示的子矩阵，依次操作这些子矩阵，使其中的所有元素值加 1，返回最终得到的矩阵。

考察二维差分数组 以及 二维前缀和，这里直接当作多个一维差分处理了。

代码

/**
 * @date 2025-11-14 8:59
 */
public class RangeAddQueries2536 {

    public int[][] rangeAddQueries(int n, int[][] queries) {
        int[][] diff = new int[n][n + 1];
        for (int[] query : queries) {
            int row1 = query[0];
            int row2 = query[2];
            int col1 = query[1];
            int col2 = query[3];
            for (int j = row1; j <= row2; j++) {
                diff[j][col1]++;
                diff[j][col2 + 1]--;
            }
        }
        int[][] res = new int[n][n];
        for (int i = 0; i < n; i++) {
            int[] row = diff[i];
            res[i][0] = row[0];
            for (int j = 1; j < n; j++) {
                res[i][j] = res[i][j - 1] + row[j];
            }
        }
        return res;
    }

}

性能

目标

给你一个 二进制字符串 s。

你可以对这个字符串执行 任意次 下述操作：

• 选择字符串中的任一下标 i（ i + 1 < s.length ），该下标满足 s[i] == '1' 且 s[i + 1] == '0'。
• 将字符 s[i] 向 右移 直到它到达字符串的末端或另一个 '1'。例如，对于 s = "010010"，如果我们选择 i = 1，结果字符串将会是 s = "000110"。

返回你能执行的 最大 操作次数。

示例 1：

输入： s = "1001101"
输出： 4
解释：
可以执行以下操作：
选择下标 i = 0。结果字符串为 s = "0011101"。
选择下标 i = 4。结果字符串为 s = "0011011"。
选择下标 i = 3。结果字符串为 s = "0010111"。
选择下标 i = 2。结果字符串为 s = "0001111"。

示例 2：

输入： s = "00111"
输出： 0

说明：

• 1 <= s.length <= 10^5
• s[i] 为 '0' 或 '1'。

思路

有一个二进制字符串 s，每次操作可以选择一个下标 i，满足 s[i] == '1' 且 s[i + 1] == '0'，将 s[i] 向右移直到遇到另一个 1 或者到达末尾，返回可以执行的最大操作次数。

要使操作次数最大，每组相邻的 0 都要为其前面的 1 提供一次操作。换句话说操作尽量不要让右侧的 0 过早的合并，累加每组相邻的 0 前面 1 的个数即可。

计算前缀 1 个数，正序遍历，第一次遇到 0 时，就加上前面 1 的个数，跳过相邻的 0（因为每次操作都要移到最右侧，相邻的 0 对每个 1 只能贡献一次操作）。

代码

/**
 * @date 2025-11-13 8:44
 */
public class MaxOperations3228 {

    public int maxOperations(String s) {
        int n = s.length();
        char[] chars = s.toCharArray();
        int[] prefix = new int[n + 1];
        int res = 0;
        for (int i = 1; i <= n; i++) {
            prefix[i] = prefix[i - 1] + (chars[i - 1] - '0');
        }
        int i = 0;
        while (i < n) {
            if (chars[i] == '0') {
                res += prefix[i];
            }
            while (i < n && chars[i++] == '0') {
            }
        }
        return res;
    }

}

性能

目标

给你一个下标从 0 开始的 正 整数数组 nums 。你可以对数组执行以下操作 任意 次：

• 选择一个满足 0 <= i < n - 1 的下标 i ，将 nums[i] 或者 nums[i+1] 两者之一替换成它们的最大公约数。

请你返回使数组 nums 中所有元素都等于 1 的 最少 操作次数。如果无法让数组全部变成 1 ，请你返回 -1 。

两个正整数的最大公约数指的是能整除这两个数的最大正整数。

示例 1：

输入：nums = [2,6,3,4]
输出：4
解释：我们可以执行以下操作：
- 选择下标 i = 2 ，将 nums[2] 替换为 gcd(3,4) = 1 ，得到 nums = [2,6,1,4] 。
- 选择下标 i = 1 ，将 nums[1] 替换为 gcd(6,1) = 1 ，得到 nums = [2,1,1,4] 。
- 选择下标 i = 0 ，将 nums[0] 替换为 gcd(2,1) = 1 ，得到 nums = [1,1,1,4] 。
- 选择下标 i = 2 ，将 nums[3] 替换为 gcd(1,4) = 1 ，得到 nums = [1,1,1,1] 。

示例 2：

输入：nums = [2,10,6,14]
输出：-1
解释：无法将所有元素都变成 1 。

说明：

• 2 <= nums.length <= 50
• 1 <= nums[i] <= 10^6

思路

有一个正整数数组 nums，每次操作可以将 nums[i] 或者 nums[i + 1] 替换成它们的最大公约数。求将 nums 所有元素变为 1 的最小操作次数，如果无法完成，返回 -1。

显然只要存在相邻的互质元素，就可以将其中的一个设置为 1，然后就可以将左右的元素按顺序替换为 1，总共需要操作 n 次。目标是如何用最小的操作次数使得存在一对相邻元素互质。暴力枚举 子数组 的起点与终点，计算所有元素的最大公约数，记录最小的子数组长度。

代码

/**
 * @date 2025-11-12 9:07
 */
public class MinOperations2654 {

    public int minOperations(int[] nums) {
        int n = nums.length;
        int res = Integer.MAX_VALUE;
        int oneCnt = 0;
        int gcdAll = nums[0];
        for (int num : nums) {
            if (num == 1) {
                oneCnt++;
            }
            gcdAll = gcd(gcdAll, num);
        }
        if (gcdAll > 1) {
            return -1;
        }
        if (oneCnt > 0) {
            return n - oneCnt;
        }
        for (int i = 0; i < n; i++) {
            int g = nums[i];
            for (int j = i; j < n; j++) {
                g = gcd(g, nums[j]);
                if (g == 1) {
                    res = Math.min(res, j - i + 1);
                    break;
                }
            }
        }
        return res - 2 + n;
    }

    public int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }

}

性能

目标

给你一个大小为 n 的 非负 整数数组 nums 。你的任务是对该数组执行若干次（可能为 0 次）操作，使得 所有 元素都变为 0。

在一次操作中，你可以选择一个子数组 [i, j]（其中 0 <= i <= j < n），将该子数组中所有 最小的非负整数 的设为 0。

返回使整个数组变为 0 所需的最少操作次数。

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

示例 1：

输入: nums = [0,2]
输出: 1
解释:
选择子数组 [1,1]（即 [2]），其中最小的非负整数是 2。将所有 2 设为 0，结果为 [0,0]。
因此，所需的最少操作次数为 1。

示例 2：

输入: nums = [3,1,2,1]
输出: 3
解释:
选择子数组 [1,3]（即 [1,2,1]），最小非负整数是 1。将所有 1 设为 0，结果为 [3,0,2,0]。
选择子数组 [2,2]（即 [2]），将 2 设为 0，结果为 [3,0,0,0]。
选择子数组 [0,0]（即 [3]），将 3 设为 0，结果为 [0,0,0,0]。
因此，最少操作次数为 3。

示例 3：

输入: nums = [1,2,1,2,1,2]
输出: 4
解释:
选择子数组 [0,5]（即 [1,2,1,2,1,2]），最小非负整数是 1。将所有 1 设为 0，结果为 [0,2,0,2,0,2]。
选择子数组 [1,1]（即 [2]），将 2 设为 0，结果为 [0,0,0,2,0,2]。
选择子数组 [3,3]（即 [2]），将 2 设为 0，结果为 [0,0,0,0,0,2]。
选择子数组 [5,5]（即 [2]），将 2 设为 0，结果为 [0,0,0,0,0,0]。
因此，最少操作次数为 4。

说明:

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

思路

有一个非负整数数组 nums，每一次操作可以任选一个子数组，将子数组的最小非负整数设为 0，求将整个数组变为 0 所需的最小操作次数。

保存元素值与下标的映射，同时记录已经变为 0 的元素下标，按照元素值从小到大的顺序枚举对应的下标，同时判断该下标后面是否有已变为 0 的下标。

代码

/**
 * @date 2025-11-10 8:53
 */
public class MinOperations3542 {

    public int minOperations(int[] nums) {
        TreeMap<Integer, List<Integer>> map = new TreeMap<>();
        TreeSet<Integer> zeros = new TreeSet<>();
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            int v = nums[i];
            if (v == 0) {
                zeros.add(i);
                continue;
            }
            map.putIfAbsent(v, new ArrayList<>());
            map.get(v).add(i);
        }
        int res = 0;
        for (Map.Entry<Integer, List<Integer>> entry : map.entrySet()) {
            if (zeros.size() == 0) {
                res++;
                zeros.addAll(entry.getValue());
                continue;
            }
            Integer right = null;
            for (Integer index : entry.getValue()) {
                if (right != null && index < right) {
                    continue;
                }
                res++;
                right = zeros.higher(index);
                if (right == null) {
                    break;
                }
            }
            zeros.addAll(entry.getValue());
        }
        return res;
    }

}

性能