标签： 前后缀分解

目标

给你一个下标从 0 开始、大小为 n m 的二维整数矩阵 grid ，定义一个下标从 0 开始、大小为 n m 的的二维矩阵 p。如果满足以下条件，则称 p 为 grid 的 乘积矩阵 ：

• 对于每个元素 p[i][j] ，它的值等于除了 grid[i][j] 外所有元素的乘积。乘积对 12345 取余数。

返回 grid 的乘积矩阵。

示例 1：

输入：grid = [[1,2],[3,4]]
输出：[[24,12],[8,6]]
解释：p[0][0] = grid[0][1] * grid[1][0] * grid[1][1] = 2 * 3 * 4 = 24
p[0][1] = grid[0][0] * grid[1][0] * grid[1][1] = 1 * 3 * 4 = 12
p[1][0] = grid[0][0] * grid[0][1] * grid[1][1] = 1 * 2 * 4 = 8
p[1][1] = grid[0][0] * grid[0][1] * grid[1][0] = 1 * 2 * 3 = 6
所以答案是 [[24,12],[8,6]] 。

示例 2：

输入：grid = [[12345],[2],[1]]
输出：[[2],[0],[0]]
解释：p[0][0] = grid[0][1] * grid[0][2] = 2 * 1 = 2
p[0][1] = grid[0][0] * grid[0][2] = 12345 * 1 = 12345. 12345 % 12345 = 0 ，所以 p[0][1] = 0
p[0][2] = grid[0][0] * grid[0][1] = 12345 * 2 = 24690. 24690 % 12345 = 0 ，所以 p[0][2] = 0
所以答案是 [[2],[0],[0]] 。

说明：

• 1 <= n == grid.length <= 10^5
• 1 <= m == grid[i].length <= 10^5
• 2 <= n * m <= 10^5
• 1 <= grid[i][j] <= 10^9

思路

已知 n x m 矩阵 grid，构造一个乘积矩阵 p 满足 p[i][j] 的值等于除了 grid[i][j] 外所有元素的乘积对 12345 取余。

计算所有元素的乘积会溢出，而保存取模后的乘积不支持除法。

---------
----X----
---------

实际上就是要快速计算出 - 的乘积。可以使用前后缀分解计算取模后的乘积。针对每一行进行前后缀分解，前缀的的最后一列以及后缀的第一列就是整行的乘积结果，对这 n 行整行的乘积再次进行前后缀分解。这样就可以快速求出 0 ~ i - 1 行的乘积，以及 i + 1 ~ n - 1 的乘积，然后对第 i 行，使用行的前后缀分解可以快速计算 grid[i][0 ~ j - 1] 以及 grid[i][j + 1 ~ m - 1] 的乘积。

代码

/**
 * @date 2026-03-24 8:57
 */
public class ConstructProductMatrix2906 {

    public int[][] constructProductMatrix(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int mod = 12345;
        int[][] prefix = new int[m][n + 1];
        int[][] suffix = new int[m][n + 1];
        for (int i = 0; i < m; i++) {
            prefix[i][0] = 1;
            suffix[i][n] = 1;
            for (int j = 0; j < n; j++) {
                prefix[i][j + 1] = (int) ((long) prefix[i][j] * grid[i][j] % mod);
                suffix[i][n - j - 1] = (int) ((long) suffix[i][n - j] * grid[i][n - j - 1] % mod);
            }
        }
        int[] rowPrefix = new int[m + 1];
        int[] rowSuffix = new int[m + 1];
        rowPrefix[0] = 1;
        rowSuffix[m] = 1;
        for (int i = 0; i < m; i++) {
            rowPrefix[i + 1] = (int) ((long) rowPrefix[i] * prefix[i][n] % mod);
            rowSuffix[m - i - 1] = (int) ((long) rowSuffix[m - i] * suffix[m - i - 1][0] % mod);
        }
        int[][] p = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                p[i][j] = (int) (((long) rowPrefix[i] * rowSuffix[i + 1] % mod) * ((long) prefix[i][j] * suffix[i][j + 1] % mod) % mod);
            }
        }
        return p;
    }

}

性能

目标

给你一个二进制字符串 s 。你可以按任意顺序执行以下两种操作任意次：

• 类型 1 ：删除 字符串 s 的第一个字符并将它 添加 到字符串结尾。
• 类型 2 ：选择 字符串 s 中任意一个字符并将该字符 反转 ，也就是如果值为 '0' ，则反转得到 '1' ，反之亦然。

请你返回使 s 变成 交替 字符串的前提下， 类型 2 的 最少 操作次数 。

我们称一个字符串是 交替 的，需要满足任意相邻字符都不同。

• 比方说，字符串 "010" 和 "1010" 都是交替的，但是字符串 "0100" 不是。

示例 1：

输入：s = "111000"
输出：2
解释：执行第一种操作两次，得到 s = "100011" 。
然后对第三个和第六个字符执行第二种操作，得到 s = "101010" 。

示例 2：

输入：s = "010"
输出：0
解释：字符串已经是交替的。

示例 3：

输入：s = "1110"
输出：1
解释：对第二个字符执行第二种操作，得到 s = "1010" 。

说明：

• 1 <= s.length <= 10^5
• s[i] 要么是 '0' ，要么是 '1' 。

思路

有一个二进制字符串 s，每次操作：1.可以将首字母移动到末尾；2.或者将任意字符反转，求将 s 变为交替字符串所需的最小反转次数，即最少的操作 2 次数。

由于不考虑首尾移动的次数，可以将首尾相接，考虑字符串 s + s。交替字符串就两种，可以使用长度为 s.length 的滑动窗口计算反转的最小次数。

可以只考虑交替字符串 010101...，假设所需的反转次数为 k，那么 10101010... 所需的反转次数为 n - k，参考 1758.生成交替二进制字符串的最少操作数。

010101... 这种交替字符串可以用下标的奇偶性来表示。移出窗口时，如果下标的奇偶性与元素值的奇偶性不同，说明差异个数减一。移入窗口同理，操作次数加一。

代码

/**
 * @date 2026-03-09 11:42
 */
public class MinFlips1888 {

    public int minFlips(String s) {
        int n = s.length();
        char[] chars = s.toCharArray();
        int ops = 0;
        for (int i = 0; i < n; ++i) {
            ops += (chars[i] ^ i) & 1;
        }
        int res = Math.min(ops, n - ops);
        if ((n & 1) == 0) {
            // 如果长度为偶数，操作1不会改变下标的奇偶性，比如 i，i + n 的奇偶性相同，后面循环中 ops 并不会发生变化
            return res;
        }
        for (int i = 0; i < n; ++i) {
            ops -= (chars[i] ^ i) & 1;
            ops += (chars[i] ^ (n + i)) & 1;
            res = Math.min(res, Math.min(ops, n - ops));
        }
        return res;
    }

}

性能

目标

给你一个字符串 s ，它仅包含字符 'a' 和 'b' 。

你可以删除 s 中任意数目的字符，使得 s 平衡 。当不存在下标对 (i,j) 满足 i < j ，且 s[i] = 'b' 的同时 s[j]= 'a' ，此时认为 s 是 平衡 的。

请你返回使 s 平衡 的 最少 删除次数。

示例 1：

输入：s = "aababbab"
输出：2
解释：你可以选择以下任意一种方案：
下标从 0 开始，删除第 2 和第 6 个字符（"aababbab" -> "aaabbb"），
下标从 0 开始，删除第 3 和第 6 个字符（"aababbab" -> "aabbbb"）。

示例 2：

输入：s = "bbaaaaabb"
输出：2
解释：唯一的最优解是删除最前面两个字符。

说明：

• 1 <= s.length <= 10^5
• s[i] 要么是 'a' 要么是 'b'​ 。​

思路

有一个仅包含 a, b 两个字符的字符串 s，如果 a 的左边没有 b，b 的右边没有 a 则认为 s 是平衡的。求使得 s 平衡需要删除的最少次数。

可以枚举分割线，分割线左侧的 b 都要删除，右侧的 a 也要删除，取最小值即可。可以使用前后缀分解来解决。

也可也使用动态规划，定义 dp[i] 表示前 i 个字符平衡需要删除的最小次数。

• 当 i 是 b 时，dp[i] = dp[i - 1]
• 当 i 时 a 时，dp[i] = min(dp[i - 1] + 1, cntB)，其中 cntB 表示 i 前面的 b 的个数

代码

/**
 * @date 2026-02-09 11:31
 */
public class MinimumDeletions1653 {

    public int minimumDeletions(String s) {
        int n = s.length();
        int[] prefixB = new int[n + 1];
        char[] chars = s.toCharArray();
        for (int i = 0; i < n; i++) {
            int c = chars[i] - 'a';
            prefixB[i + 1] = prefixB[i] + c;
        }
        int deletedA = 0;
        int res = Integer.MAX_VALUE;
        for (int i = n - 1; i > 0; i--) {
            int c = chars[i] - 'a';
            if (c == 0) {
                res = Math.min(res, prefixB[i] + deletedA);
                deletedA++;
            }
        }
        res = Math.min(res, deletedA);
        return res;
    }

}

性能