数据结构与算法（Java）-前后缀分解题单

前后缀分解（力扣）

2909 元素和最小的山形三元组

2909. 元素和最小的山形三元组 II - 力扣（LeetCode）

给你一个下标从 0 开始的整数数组 nums 。

如果下标三元组 (i, j, k) 满足下述全部条件，则认为它是一个 山形三元组 ：

• i < j < k
• nums[i] < nums[j] 且 nums[k] < nums[j]

请你找出 nums 中 元素和最小 的山形三元组，并返回其 元素和 。如果不存在满足条件的三元组，返回 -1 。

示例 1：

输入：nums = [8,6,1,5,3]
输出：9
解释：三元组 (2, 3, 4) 是一个元素和等于 9 的山形三元组，因为： 
- 2 < 3 < 4
- nums[2] < nums[3] 且 nums[4] < nums[3]
这个三元组的元素和等于 nums[2] + nums[3] + nums[4] = 9 。可以证明不存在元素和小于 9 的山形三元组。
1
2
3
4
5
6

示例 2：

输入：nums = [5,4,8,7,10,2]
输出：13
解释：三元组 (1, 3, 5) 是一个元素和等于 13 的山形三元组，因为： 
- 1 < 3 < 5 
- nums[1] < nums[3] 且 nums[5] < nums[3]
这个三元组的元素和等于 nums[1] + nums[3] + nums[5] = 13 。可以证明不存在元素和小于 13 的山形三元组。
1
2
3
4
5
6

示例 3：

输入：nums = [6,5,4,3,4,5]
输出：-1
解释：可以证明 nums 中不存在山形三元组。
1
2
3

提示：

• 3 <= nums.length <= 105
• 1 <= nums[i] <= 108

class Solution {
    public int minimumSum(int[] nums) {
        int n = nums.length;
        int[] f = new int[n]; // f[i]表示nums[i]到nums[n-1]的后缀最小值
        f[n - 1] = nums[n - 1];
        for (int i = n - 2; i > 1; i--) {
            f[i] = Math.min(nums[i], f[i + 1]);
        }
        int pre = nums[0];
        int ans = Integer.MAX_VALUE;
        // 遍历中间山峰的值
        for (int i = 1; i < n - 1; i++) {
            if (nums[i] > pre && nums[i] > f[i + 1]) {
                ans = Math.min(ans, nums[i] + f[i + 1] + pre);
            }
            pre = Math.min(nums[i], pre);
        }
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

238 除自身以外数组的乘积

除自身以外数组的乘积

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

请 **不要使用除法，**且在 O(*n*) 时间复杂度内完成此题。

示例 1:

输入: nums = [1,2,3,4]
输出: [24,12,8,6]
1
2

示例 2:

输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]
1
2

提示：

• 2 <= nums.length <= 105
• -30 <= nums[i] <= 30
• 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内

**进阶：**你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组 不被视为 额外空间。）

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int left = 1, right = 1;
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            ans[i] = left;
            left = left * nums[i];
        }
        for (int i = n - 1; i >= 0; i--) {
            ans[i] = ans[i] * right;
            right = right * nums[i];
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2906 构造乘积矩阵

2906. 构造乘积矩阵 - 力扣（LeetCode）

给你一个下标从 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]] 。
1
2
3
4
5
6
7

示例 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
2
3
4
5
6

提示：

• 1 <= n == grid.length <= 105
• 1 <= m == grid[i].length <= 105
• 2 <= n * m <= 105
• 1 <= grid[i][j] <= 109

class Solution {
    public int[][] constructProductMatrix(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] p = new int[m][n];
        long suf = 1;
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                p[i][j] = (int) suf;
                suf = suf * grid[i][j] % 12345;
            }
        }
        long pre = 1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                p[i][j] = (int) (p[i][j] * pre % 12345);
                pre = pre * grid[i][j] % 12345;
            }
        }
        return p;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

2256 最小平均差

2256. 最小平均差 - 力扣（LeetCode）

给你一个下标从 0 开始长度为 n 的整数数组 nums 。

下标 i 处的 平均差 指的是 nums 中 前 i + 1 个元素平均值和 后 n - i - 1 个元素平均值的 绝对差 。两个平均值都需要 向下取整 到最近的整数。

请你返回产生 最小平均差 的下标。如果有多个下标最小平均差相等，请你返回 最小 的一个下标。

注意：

• 两个数的 绝对差 是两者差的绝对值。
• n 个元素的平均值是 n 个元素之 和 除以（整数除法） n 。
• 0 个元素的平均值视为 0 。

示例 1：

输入：nums = [2,5,3,9,5,3]
输出：3
解释：
- 下标 0 处的平均差为：|2 / 1 - (5 + 3 + 9 + 5 + 3) / 5| = |2 / 1 - 25 / 5| = |2 - 5| = 3 。
- 下标 1 处的平均差为：|(2 + 5) / 2 - (3 + 9 + 5 + 3) / 4| = |7 / 2 - 20 / 4| = |3 - 5| = 2 。
- 下标 2 处的平均差为：|(2 + 5 + 3) / 3 - (9 + 5 + 3) / 3| = |10 / 3 - 17 / 3| = |3 - 5| = 2 。
- 下标 3 处的平均差为：|(2 + 5 + 3 + 9) / 4 - (5 + 3) / 2| = |19 / 4 - 8 / 2| = |4 - 4| = 0 。 
- 下标 4 处的平均差为：|(2 + 5 + 3 + 9 + 5) / 5 - 3 / 1| = |24 / 5 - 3 / 1| = |4 - 3| = 1 。
- 下标 5 处的平均差为：|(2 + 5 + 3 + 9 + 5 + 3) / 6 - 0| = |27 / 6 - 0| = |4 - 0| = 4 。
下标 3 处的平均差为最小平均差，所以返回 3 。
1
2
3
4
5
6
7
8
9
10

示例 2：

输入：nums = [0]
输出：0
解释：
唯一的下标是 0 ，所以我们返回 0 。
下标 0 处的平均差为：|0 / 1 - 0| = |0 - 0| = 0 。
1
2
3
4
5

提示：

• 1 <= nums.length <= 105
• 0 <= nums[i] <= 105

class Solution {
    public int minimumAverageDifference(int[] nums) {
        long suf = 0, pre = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            suf += nums[i];
        }
        int res = -1;
        long minAns = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            pre += nums[i];
            suf -= nums[i];
            long l = pre / (i + 1);
            //防止除以0
            long r = i != n - 1 ? suf / (n - i - 1) : 0;
            long x = Math.abs(l - r);
            if (x < minAns) {
                //更新最小值及下标
                minAns = x;
                res = i;
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

2483 商店的最小代价

2483. 商店的最少代价 - 力扣（LeetCode）

给你一个顾客访问商店的日志，用一个下标从 0 开始且只包含字符 'N' 和 'Y' 的字符串 customers 表示：

• 如果第 i 个字符是 'Y' ，它表示第 i 小时有顾客到达。
• 如果第 i 个字符是 'N' ，它表示第 i 小时没有顾客到达。

如果商店在第 j 小时关门（0 <= j <= n），代价按如下方式计算：

• 在开门期间，如果某一个小时没有顾客到达，代价增加 1 。
• 在关门期间，如果某一个小时有顾客到达，代价增加 1 。

请你返回在确保代价 最小 的前提下，商店的 最早 关门时间。

注意，商店在第 j 小时关门表示在第 j 小时以及之后商店处于关门状态。

示例 1：

输入：customers = "YYNY"
输出：2
解释：
- 第 0 小时关门，总共 1+1+0+1 = 3 代价。
- 第 1 小时关门，总共 0+1+0+1 = 2 代价。
- 第 2 小时关门，总共 0+0+0+1 = 1 代价。
- 第 3 小时关门，总共 0+0+1+1 = 2 代价。
- 第 4 小时关门，总共 0+0+1+0 = 1 代价。
在第 2 或第 4 小时关门代价都最小。由于第 2 小时更早，所以最优关门时间是 2 。
1
2
3
4
5
6
7
8
9

示例 2：

输入：customers = "NNNNN"
输出：0
解释：最优关门时间是 0 ，因为自始至终没有顾客到达。
1
2
3

示例 3：

输入：customers = "YYYY"
输出：4
解释：最优关门时间是 4 ，因为每一小时均有顾客到达。
1
2
3

提示：

• 1 <= customers.length <= 105
• customers 只包含字符 'Y' 和 'N' 。

class Solution {
    public int bestClosingTime(String customers) {
        char[] cust = customers.toCharArray();
        int res = -1;
        int cost = Integer.MAX_VALUE;
        int n = cust.length;
        int[] suf = new int[n + 1];
        int[] pre = new int[n + 1];
        suf[n] = 0;
        pre[0] = 0;
        // 0 1 1 2 3 -> 3 2 1 1 0
        for (int i = n - 1; i >= 0; i--) {
            suf[i] = cust[i] == 'Y' ? suf[i + 1] + 1 : suf[i + 1];
        }
        // 0 0 0 1 1
        for (int i = 1; i < n + 1; i++) {
            pre[i] = cust[i - 1] == 'N' ? pre[i - 1] + 1 : pre[i - 1];
        }
        for (int i = n; i >= 0; i--) {
            if (cost >= suf[i] + pre[i]) {
                cost = suf[i] + pre[i];
                res = i;
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

优化

class Solution {
    public int bestClosingTime(String customers) {
        int res = 0;
        int bal = 0;
        int i = 1;
        char[] cust = customers.toCharArray();
        for (char c : cust) {
            if (c == 'N') {
                bal++;
            } else {
                bal--;
                if (bal < 0) {
                    res = i;
                    bal = 0;
                }
            }
            i++;
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

2420 找到所有好下标

2420. 找到所有好下标 - 力扣（LeetCode）

给你一个大小为 n 下标从 0 开始的整数数组 nums 和一个正整数 k 。

对于 k <= i < n - k 之间的一个下标 i ，如果它满足以下条件，我们就称它为一个 好 下标：

• 下标 i 之前 的 k 个元素是 非递增的 。
• 下标 i 之后 的 k 个元素是 非递减的 。

按 升序 返回所有好下标。

示例 1：

输入：nums = [2,1,1,1,3,4,1], k = 2
输出：[2,3]
解释：数组中有两个好下标：
- 下标 2 。子数组 [2,1] 是非递增的，子数组 [1,3] 是非递减的。
- 下标 3 。子数组 [1,1] 是非递增的，子数组 [3,4] 是非递减的。
注意，下标 4 不是好下标，因为 [4,1] 不是非递减的。
1
2
3
4
5
6

示例 2：

输入：nums = [2,1,1,2], k = 2
输出：[]
解释：数组中没有好下标。
1
2
3

提示：

• n == nums.length
• 3 <= n <= 105
• 1 <= nums[i] <= 106
• 1 <= k <= n / 2

class Solution {
    // i之前 >= i之后 <=
    //左边用一个变量统计长度 右边用一个数组统计长度
    public List<Integer> goodIndices(int[] nums, int k) {
        int n = nums.length;
        List<Integer> ans = new ArrayList<>();
        int[] R = new int[n];// R[i]为i之后非递减的长度
        Arrays.fill(R,1);// 初始化为1
        for (int i = n - 2; i >= 1; i--) {
            if (nums[i] <= nums[i + 1]) {
                R[i] = R[i + 1] + 1;
            }
        }
        int leftLen = 1;
        for (int i = 1; i < n - 1; i++) {
            if (leftLen >= k && R[i + 1] >= k) {
                ans.add(i);
            }
            if (nums[i - 1] >= nums[i]) {
                leftLen++;
            } else {
                leftLen = 1;
            }
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

2167移除所有载有违禁货物车厢所需的最小时间（DP思想）

2167. 移除所有载有违禁货物车厢所需的最少时间 - 力扣（LeetCode）

给你一个下标从 0 开始的二进制字符串 s ，表示一个列车车厢序列。s[i] = '0' 表示第 i 节车厢 不 含违禁货物，而 s[i] = '1' 表示第 i 节车厢含违禁货物。

作为列车长，你需要清理掉所有载有违禁货物的车厢。你可以不限次数执行下述三种操作中的任意一个：

1. 从列车 左 端移除一节车厢（即移除 s[0]），用去 1 单位时间。
2. 从列车 右 端移除一节车厢（即移除 s[s.length - 1]），用去 1 单位时间。
3. 从列车车厢序列的 任意位置 移除一节车厢，用去 2 单位时间。

返回移除所有载有违禁货物车厢所需要的 最少 单位时间数。

注意，空的列车车厢序列视为没有车厢含违禁货物。

示例 1：

输入：s = "1100101"
输出：5
解释：
一种从序列中移除所有载有违禁货物的车厢的方法是：
- 从左端移除一节车厢 2 次。所用时间是 2 * 1 = 2 。
- 从右端移除一节车厢 1 次。所用时间是 1 。
- 移除序列中间位置载有违禁货物的车厢。所用时间是 2 。
总时间是 2 + 1 + 2 = 5 。

一种替代方法是：
- 从左端移除一节车厢 2 次。所用时间是 2 * 1 = 2 。
- 从右端移除一节车厢 3 次。所用时间是 3 * 1 = 3 。
总时间也是 2 + 3 = 5 。

5 是移除所有载有违禁货物的车厢所需要的最少单位时间数。
没有其他方法能够用更少的时间移除这些车厢。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

示例 2：

输入：s = "0010"
输出：2
解释：
一种从序列中移除所有载有违禁货物的车厢的方法是：
- 从左端移除一节车厢 3 次。所用时间是 3 * 1 = 3 。
总时间是 3.

另一种从序列中移除所有载有违禁货物的车厢的方法是：
- 移除序列中间位置载有违禁货物的车厢。所用时间是 2 。
总时间是 2.

另一种从序列中移除所有载有违禁货物的车厢的方法是：
- 从右端移除一节车厢 2 次。所用时间是 2 * 1 = 2 。
总时间是 2.

2 是移除所有载有违禁货物的车厢所需要的最少单位时间数。
没有其他方法能够用更少的时间移除这些车厢。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

提示：

• 1 <= s.length <= 2 * 105
• s[i] 为 '0' 或 '1'

常规做法：

class Solution {
    public int minimumTime(String s) {
        char[] str = s.toCharArray();
        int n = str.length;
        //pre[i]表示pre[0]到pre[i]的最少时间
        //s[i]='0' pre[i]=pre[i - 1] s[i]='1' pre[i]=min(pre[i - 1] + 2, i + 1) 
        int[] pre = new int[n];
        //suf[i]表示suf[i]到suf[n - 1]的最少时间
        //s[i]='0' suf[i]=suf[i + 1] s[i]='1' suf[i]=min(suf[i + 1] + 2, n - i)
        int[] suf = new int[n];
        pre[0] = (str[0] == '1') ? 1 : 0;
        suf[n - 1] = (str[n - 1] == '1') ? 1 : 0;
        for (int i = 1; i < n; i++) {
            pre[i] = (str[i] == '1') ? Math.min(pre[i - 1] + 2, i + 1) : pre[i - 1];
        }
        for (int i = n - 2; i >= 0; i--) {
            suf[i] = (str[i] == '1') ? Math.min(suf[i + 1] + 2, n - i) : suf[i + 1];
        }
        //初始化为后缀和的第一项
        int res = suf[0];
        //    1 1 0 0 1 0 1
        //pre 1 2 2 2 4 4 6
        //suf 7 5 3 3 3 1 1
        for(int i = 0; i < n; i++) {
            res = Math.min(res, pre[i] + suf[i]);
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

优化：

class Solution {
    public int minimumTime(String s) {
        //优化1：先计算suf，再计算pre
        //优化2：pre仅与上一个状态有关，可用滚动数组（一个变量）保存
        //优化3：s[i]='0' pre[i]和suf[i]值不会变化 仅仅需要考虑s[i]='1'的情况
        char[] str = s.toCharArray();
        int n = str.length;
        int[] suf = new int[n];
        suf[n - 1] = (str[n - 1] == '1') ? 1 : 0;
        for (int i = n - 2; i >= 0; i--) {
            suf[i] = (str[i] == '1') ? Math.min(suf[i + 1] + 2, n - i) : suf[i + 1];
        }
        int res = suf[0];
        int pre = 0;
        for (int i = 0; i < n; i++) {
            if (str[i] == '1') {
                pre = Math.min(pre + 2, i + 1);
            }
            res = Math.min(res, suf[i] + pre);
        } 
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

进一步优化+一次遍历

class Solution {
    public int minimumTime(String s) {
        //将移除前面的车厢和移除后面的车厢合并
        // 移除前缀+移除分割线左侧某些车厢+(分割线)+移除分割线右侧某些车厢+移除后缀
        // ->移除前缀 + 移除分割线左侧某些车厢 + (分割线) + 移除后缀
        char[] str = s.toCharArray();
        int n = str.length;
        int pre = 0;
        int res = n;
        for (int i = 0; i < n; i++) {
            if (str[i] == '1') {
                pre = Math.min(pre + 2, i + 1);
            }
            res = Math.min(res, pre + n - i - 1);
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2484 统计回文子序列数目（灵神笔记）

2484. 统计回文子序列数目 - 力扣（LeetCode）

参考：2484. 统计回文子序列数目 - 力扣（LeetCode）

视频：【力扣双周赛 92】前后缀分解_哔哩哔哩_bilibili

给你数字字符串 s ，请你返回 s 中长度为 5 的 回文子序列 数目。由于答案可能很大，请你将答案对 109 + 7 取余 后返回。

提示：

• 如果一个字符串从前往后和从后往前读相同，那么它是 回文字符串 。
• 子序列是一个字符串中删除若干个字符后，不改变字符顺序，剩余字符构成的字符串。

示例 1：

输入：s = "103301"
输出：2
解释：
总共有 6 长度为 5 的子序列："10330" ，"10331" ，"10301" ，"10301" ，"13301" ，"03301" 。
它们中有两个（都是 "10301"）是回文的。
1
2
3
4
5

示例 2：

输入：s = "0000000"
输出：21
解释：所有 21 个长度为 5 的子序列都是 "00000" ，都是回文的。
1
2
3

示例 3：

输入：s = "9999900000"
输出：2
解释：仅有的两个回文子序列是 "99999" 和 "00000" 。
1
2
3

提示：

• 1 <= s.length <= 104
• s 只包含数字字符。

class Solution {
    private static final long MOD = (long) 1e9 + 7;
    // 将子序列分成三段 pre2[a][0...9] suf2[a][0...9] 前两个字符一部分 枚举中间字符 后两个字符一部分
    public int countPalindromes(String s) {
        char[] str = s.toCharArray();
        int[] pre = new int[10], suf = new int[10];// 前后缀中d的个数
        int[][] pre2 = new int[10][10], suf2 = new int[10][10]; //(d1,d2)的个数
        for (int i = str.length - 1; i >= 0; i--) {
            int d = str[i] - '0';// 转化为int
            for (int j = 0; j < 10; j++) {
                //枚举后面两个字符
                suf2[d][j] += suf[j];
            }
            // 循环结束++，防止一个字符选两次
            suf[d]++;
        }
        // 最坏情况（所有字符相同） 答案为C(n,5)
        long res = 0;
        for (char d : str) {
            d -= '0';
            suf[d]--;// 枚举五个中的中间一个，后缀不能包含d，要撤销一步
            for (int j = 0; j < 10; j++) {
                suf2[d][j] -= suf[j];
            }
            // 得到了左右两侧的(d1,d2)个数
            for (int j = 0; j < 10; j++) {
                for (int k = 0; k < 10; k++) {
                    res += (long) pre2[j][k] * suf2[j][k];// 枚举所有字母组合
                }
            }
            for (int j = 0; j < 10; j++) {
                pre2[d][j] += pre[j];
            }
            pre[d]++;
        }
        return (int) (res % MOD);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

2565 最少得分子序列（灵神笔记）

2565. 最少得分子序列 - 力扣（LeetCode）

参考：2565. 最少得分子序列 - 力扣（LeetCode）

视频：前后缀分解【力扣周赛 332】_哔哩哔哩_bilibili

给你两个字符串 s 和 t 。

你可以从字符串 t 中删除任意数目的字符。

如果没有从字符串 t 中删除字符，那么得分为 0 ，否则：

• 令 left 为删除字符中的最小下标。
• 令 right 为删除字符中的最大下标。

字符串的得分为 right - left + 1 。

请你返回使 t 成为 s 子序列的最小得分。

一个字符串的 子序列 是从原字符串中删除一些字符后（也可以一个也不删除），剩余字符不改变顺序得到的字符串。（比方说 "ace" 是 "***a\***b***c\***d***e\***" 的子序列，但是 "aec" 不是）。

示例 1：

输入：s = "abacaba", t = "bzaa"
输出：1
解释：这个例子中，我们删除下标 1 处的字符 "z" （下标从 0 开始）。
字符串 t 变为 "baa" ，它是字符串 "abacaba" 的子序列，得分为 1 - 1 + 1 = 1 。
1 是能得到的最小得分。
1
2
3
4
5

示例 2：

输入：s = "cde", t = "xyz"
输出：3
解释：这个例子中，我们将下标为 0， 1 和 2 处的字符 "x" ，"y" 和 "z" 删除（下标从 0 开始）。
字符串变成 "" ，它是字符串 "cde" 的子序列，得分为 2 - 0 + 1 = 3 。
3 是能得到的最小得分。
1
2
3
4
5

提示：

• 1 <= s.length, t.length <= 105
• s 和 t 都只包含小写英文字母。

常规解法：

class Solution {
    public int minimumScore(String S, String T) {
        char[] s = S.toCharArray(), t = T.toCharArray();
        int n = s.length, m = t.length;
        //计算后缀和 suf[i]为s[:i]对应的t最长前缀开始下标
        int[] suf = new int[n + 1];
        suf[n] = m;
        for (int i = n - 1, j = m - 1; i >=0; i--) {
            if (j >= 0 && s[i] == t[j]) {
                j--;
            }
            suf[i] = j + 1;
        }
        //计算前缀和 pre[i]为s[i:]对应的t最长后缀开始下标
        int[] pre = new int[n + 1];
        pre[0] = 0;
        for (int i = 0, j = 0; i < n; i++) {
            if (j < m && s[i] == t[j]) {
                j++;
            }
            pre[i] = j - 1;
        }
        int res = suf[0];
        if (res == 0) {
            return 0;
        }
        //在s两个字符之间插入一个板子 枚举所有的板子
        for (int i = 0, j = 0; i <= n; i++) {
            // 保证t前后缀没有交集
            int r = (i < n) ? suf[i] : m;
            int l = (i > 0) ? pre[i - 1] : -1;
            res = Math.min(res, r - l - 1);
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

优化：

class Solution {
    public int minimumScore(String S, String T) {
        char[] s = S.toCharArray(), t = T.toCharArray();
        int n = s.length, m = t.length;
        //计算后缀和 suf[i]为s[:i]对应的t最长前缀开始下标
        int[] suf = new int[n + 1];
        suf[n] = m;
        for (int i = n - 1, j = m - 1; i >=0; i--) {
            if (j >= 0 && s[i] == t[j]) {
                j--;
            }
            suf[i] = j + 1;
        }
        int res = suf[0];
        if (res == 0) {
            return 0;
        }
        //在s两个字符之间插入一个板子 枚举所有的板子
        for (int i = 0, j = 0; i < n; i++) {
            //j不会等于m res=suf[0]>0说明t不是s的子序列
            if (s[i] == t[j]) {
                res = Math.min(res, suf[i + 1] - ++j);//删除t[j:suf[i+1]]
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

2552 统计上升四元组（灵神笔记）

2552. 统计上升四元组 - 力扣（LeetCode）

有了前面的经验，不难发现，与子序列一类题目一样，我们可以枚举中间的j和k，在k右侧统计比nums[j]大的数，在j左侧统计比nums[k]小的数，最后根据乘法原理，从左边选一个i，从右边选一个l，答案就是前缀*后缀

参考视频：转化思路 前后缀分解【力扣周赛 330】_哔哩哔哩_bilibili

给你一个长度为 n 下标从 0 开始的整数数组 nums ，它包含 1 到 n 的所有数字，请你返回上升四元组的数目。

如果一个四元组 (i, j, k, l) 满足以下条件，我们称它是上升的：

• 0 <= i < j < k < l < n 且
• nums[i] < nums[k] < nums[j] < nums[l] 。

示例 1：

输入：nums = [1,3,2,4,5]
输出：2
解释：
- 当 i = 0 ，j = 1 ，k = 2 且 l = 3 时，有 nums[i] < nums[k] < nums[j] < nums[l] 。
- 当 i = 0 ，j = 1 ，k = 2 且 l = 4 时，有 nums[i] < nums[k] < nums[j] < nums[l] 。
没有其他的四元组，所以我们返回 2 。
1
2
3
4
5
6

示例 2：

输入：nums = [1,2,3,4]
输出：0
解释：只存在一个四元组 i = 0 ，j = 1 ，k = 2 ，l = 3 ，但是 nums[j] < nums[k] ，所以我们返回 0 。
1
2
3

提示：

• 4 <= nums.length <= 4000
• 1 <= nums[i] <= nums.length
• nums 中所有数字 互不相同 ，nums 是一个排列。

常规解法：

class Solution {
    public long countQuadruplets(int[] nums) {
        int n = nums.length;
        //在k右侧比nums[j]大的元素个数为great[k][nums[j]]
        int[][] great = new int[n][n + 1];
        for (int k = n - 2; k >= 2; k--) {
            great[k] = great[k + 1].clone();
            for (int x = nums[k + 1] - 1; x > 0; x--) {
                great[k][x]++;
            }
        }
        //在j左侧比nums[k]小的元素个数为less[j][nums[k]]
        int[][] less = new int[n][n + 1];
        for (int j = 1; j < n - 2; j++) {
            less[j] = less[j - 1].clone();
            for (int x = nums[j - 1] + 1; x < n + 1; x++) {
                less[j][x]++;
            }
        }
        long res = 0;
        for (int j = 1; j < n - 2; j++) {
            for (int k = j + 1; k < n - 1; k++) {
                if (nums[j] > nums[k]) {
                    res += less[j][nums[k]] * great[k][nums[j]];
                }
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

前缀优化成一维数组：

class Solution {
    public long countQuadruplets(int[] nums) {
        int n = nums.length;
        int[][] great = new int[n][n + 1];
        for (int k = n - 2; k >= 2; k--) {
            great[k] = great[k + 1].clone();
            for (int x = nums[k + 1] - 1; x > 0; x--) {
                great[k][x]++;
            }
        }
        long res = 0;
        int[] less = new int[n + 1];
        for (int j = 1; j < n - 2; j++) {
            for (int x = nums[j - 1] + 1; x <= n; x++) {
                less[x]++;
            }
            for (int k = j + 1; k < n - 1; k++) {
                if (nums[j] > nums[k]) {
                    res += less[nums[k]] * great[k][nums[j]];
                }
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

前缀优化成变量：

class Solution {
    public long countQuadruplets(int[] nums) {
        int n = nums.length;
        //在k右侧比nums[j]大的元素个数为great[k][nums[j]]
        //在j左侧比nums[k]小的元素个数为less[j][nums[k]]
        int[][] great = new int[n][n + 1];
        //注意 k最小为1
        for (int k = n - 2; k > 0; k--) {
            great[k] = great[k + 1].clone();
            for (int x = nums[k + 1] - 1; x > 0; x--) {
                great[k][x]++;
            }
        }
        long res = 0;
        for (int j = 1; j < n - 2; j++) {
            for (int k = j + 1; k < n - 1; k++) {
                //j右边比nums[k]小的个数为右边的个数(n-1-j)减去j右侧比nums[k]大的个数
                //总共有nums[k]个不超过nums[k]的数
                int r_less = n - 1 - j - great[j][nums[k]];
                int l_less = nums[k] - r_less;
                if (nums[j] > nums[k]) {
                    res += l_less * great[k][nums[j]];
                }
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

great [k] [x] x 为什么是从 nums [k+1]-1 开始，而不是从 nums [k+1]?

对于比 nums [k+1]小的的数 x 来说，nums [k+1] 的出现使得 x 的右边多了一个比 x 大的数。所以更新的是比 nums [k+1] 小的数。