shelterofly

目标

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

}

性能

目标

给你一个整数 c，表示 c 个电站，每个电站有一个唯一标识符 id，从 1 到 c 编号。

这些电站通过 n 条 双向 电缆互相连接，表示为一个二维数组 connections，其中每个元素 connections[i] = [ui, vi] 表示电站 ui 和电站 vi 之间的连接。直接或间接连接的电站组成了一个 电网 。

最初，所有 电站均处于在线（正常运行）状态。

另给你一个二维数组 queries，其中每个查询属于以下 两种类型之一 ：

• [1, x]：请求对电站 x 进行维护检查。如果电站 x 在线，则它自行解决检查。如果电站 x 已离线，则检查由与 x 同一 电网 中 编号最小 的在线电站解决。如果该电网中 不存在 任何 在线 电站，则返回 -1。
• [2, x]：电站 x 离线（即变为非运行状态）。

返回一个整数数组，表示按照查询中出现的顺序，所有类型为 [1, x] 的查询结果。

注意：电网的结构是固定的；离线（非运行）的节点仍然属于其所在的电网，且离线操作不会改变电网的连接性。

示例 1：

输入： c = 5, connections = [[1,2],[2,3],[3,4],[4,5]], queries = [[1,3],[2,1],[1,1],[2,2],[1,2]]
输出： [3,2,3]
解释：
最初，所有电站 {1, 2, 3, 4, 5} 都在线，并组成一个电网。
查询 [1,3]：电站 3 在线，因此维护检查由电站 3 自行解决。
查询 [2,1]：电站 1 离线。剩余在线电站为 {2, 3, 4, 5}。
查询 [1,1]：电站 1 离线，因此检查由电网中编号最小的在线电站解决，即电站 2。
查询 [2,2]：电站 2 离线。剩余在线电站为 {3, 4, 5}。
查询 [1,2]：电站 2 离线，因此检查由电网中编号最小的在线电站解决，即电站 3。

示例 2：

输入： c = 3, connections = [], queries = [[1,1],[2,1],[1,1]]
输出： [1,-1]
解释：
没有连接，因此每个电站是一个独立的电网。
查询 [1,1]：电站 1 在线，且属于其独立电网，因此维护检查由电站 1 自行解决。
查询 [2,1]：电站 1 离线。
查询 [1,1]：电站 1 离线，且其电网中没有其他电站，因此结果为 -1。

说明：

• 1 <= c <= 10^5
• 0 <= n == connections.length <= min(10^5, c * (c - 1) / 2)
• connections[i].length == 2
• 1 <= ui, vi <= c
• ui != vi
• 1 <= queries.length <= 2 * 10^5
• queries[i].length == 2
• queries[i][0] 为 1 或 2。
• 1 <= queries[i][1] <= c

思路

有 c 个电站，编号为 1 ~ c，connections[i] = [ui, vi] 表示电站 ui 与 vi 相连，所有连通的电站组成了一个电网。查询 queries[i] = [operation, x]，如果 operation 为 2 表示将电站 x 离线，如果 operation 为 1 并且 x 在线，返回 x，否则返回 x 所在电网中在线电站的最小编号，如果没有在线电站返回 -1。

使用 有序集合 数组 维护不同电网的在线电站。如果离线就将其从有序集合中删掉 O(logn)，否则先判断集合是否为空，如果集合为空返回 -1，再判断电站是否在集合中 O(logn)，如果在则直接返回查询电站编号，否则取集合最小的编号。

代码

/**
 * @date 2025-11-06 9:03
 */
public class ProcessQueries3607 {

    private class UnionFind {
        private int[] fa;

        public UnionFind() {
        }

        public UnionFind(int n) {
            this.fa = new int[n];
            Arrays.setAll(this.fa, i -> i);
        }

        public int find(int x) {
            if (fa[x] != x) {
                fa[x] = find(fa[x]);
            }
            return fa[x];
        }

        public void merge(int x, int y) {
            int a = find(x);
            int b = find(y);
            if (a != b) {
                fa[b] = a;
            }
        }

    }

    public int[] processQueries(int c, int[][] connections, int[][] queries) {
        UnionFind uf = new UnionFind(c + 1);
        for (int[] connection : connections) {
            uf.merge(connection[0], connection[1]);
        }
        TreeSet<Integer>[] set = new TreeSet[c + 1];
        Arrays.setAll(set, i -> new TreeSet<>());
        for (int i = 1; i <= c; i++) {
            set[uf.find(i)].add(i);
        }
        List<Integer> list = new ArrayList<>();
        boolean[] off = new boolean[c + 1];
        for (int[] query : queries) {
            int operation = query[0];
            int node = query[1];
            int network = uf.find(node);
            if (operation == 1) {
                if (set[network].size() > 0) {
                    if (off[node]) {
                        list.add(set[network].first());
                    } else {
                        list.add(node);
                    }
                } else {
                    list.add(-1);
                }
            } else {
                off[node] = true;
                set[network].remove(node);
            }
        }
        return list.stream().mapToInt(i -> i).toArray();
    }
}

性能