Leetcode - 周赛433

一、3427. 变长子数组求和

题目链接

暴力模拟或者前缀和，代码如下：

//O(n^2) - 暴力模拟
class Solution {
    public int subarraySum(int[] nums) {
        int ans = 0;
        int n = nums.length;
        for(int i=0; i<n; i++){
            for(int j=Math.max(0, i-nums[i]); j<=i; j++){
                ans += nums[j];
            }
        }
        return ans;
    }
}
//O(n) - 前缀和做法
class Solution {
    public int subarraySum(int[] nums) {
        int n = nums.length;
        int[] pre = new int[n+1];
        for(int i=0; i<n; i++){
            pre[i+1] = pre[i] + nums[i];
        }
        int ans = 0;
        for(int i=0; i<n; i++){
            int x = nums[i];
            ans += pre[i+1] - pre[Math.max(0, i-x)];
        }
        return ans;
    }
}

二、3428. 最多 K 个元素的子序列的最值之和

题目链接

本题求所有子序列中最大值和最小值的和，虽然是子序列，但是本题实际上对于 $nums$ 数组的排列顺序没有任何约束，所以可以先对该数组进行排序。

和这周双周赛 $T4$ 一样，本题也无法枚举所有子序列，求其中最大值和最小值的和，这时可以反过来想，能不能枚举最大值或最小值，求它们出现过的次数，将它们一乘，同样可以算出答案。这就是所谓的贡献法。

假设求以 $x=nums[i]$ 为最大值的子序列的个数：

• 除去 $x$，前面还有 $i$ 个数，题目还要求子序列的长度最多为 $k$ 个，所以在 $[0,i-1]$ 可以取 { 0 , 1 , . . . , m i n ( k − 1 , i ) } \left \{ 0,1,...,min(k-1,i) \right \} {0,1,...,min(k−1,i)} 个元素形成子序列，令 $mn=min(k-1,i)$，总个数实际上是 $S=\left(\genfrac{}{}{0ex}{}{i}{0}\right)+\left(\genfrac{}{}{0ex}{}{i}{1}\right)+\left(\genfrac{}{}{0ex}{}{i}{2}\right)+...+\left(\genfrac{}{}{0ex}{}{i}{mn}\right)$。以 $x$ 为最大值的子序列共有 $S$ 个，$ans=ans+x\ast S$

最小值的算法也是同理，但是实际上，根据对称性，我们求出的以 $x=nums[i]$ 为最大值的子序列的个数 $S$，它也是以 $y=nums[n-i-1]$ 为最小值的子序列的个数，不需要再重复计算。

代码如下：

class Solution {
    private static final int MOD = 1_000_000_007;
    private static final int MX = 100_001;
    private static final long[] f = new long[MX];
    private static final long[] inv_f = new long[MX];
    static{
        f[0] = 1;
        for(int i=1; i<MX; i++){
            f[i] = f[i-1] * i % MOD;
        }
        // 费马小定理！
    	// 1 / b % MOD = b ^ (MOD-2) % MOD 注：MOD必须为质数才成立
    	// 1 / (a*b*c) % p = pow(a*b*c, p - 2) % p
    	// 1 / (a*b) % p = pow(a*b, p-2) % p
    	// 1 / (a*b) % p = 1 / (a*b*c) * c % p
    	// 得到：inv_f[i-1] = inv_f[i] * i % p
        inv_f[MX-1] = pow(f[MX-1], MOD-2);
        for(int i=MX-1; i>0; i--){
            inv_f[i-1] = inv_f[i] * i % MOD;
        }
    }
    //快速幂O(logy): x^y
    static long pow(long x, long y){
        long res = 1;
        for(; y>0; y/=2){
            if(y%2 > 0) 
                res = res * x % MOD;
            x = x * x % MOD;
        }
        return res;
    }
    long comb(int n, int m){
        return f[n] * inv_f[m] % MOD * inv_f[n-m] % MOD;
    }
    public int minMaxSums(int[] nums, int k) {
        int n = nums.length;
        Arrays.sort(nums);
        long ans = 0;
        for(int i=0; i<n; i++){
            long s = 0;
            for(int j=0; j<Math.min(k, i+1); j++){
                s += comb(i, j);
            }
            ans = (ans + s % MOD * (nums[i] + nums[n-1-i]) % MOD) % MOD;
        }
        return (int)ans;
    }
}

三、3429. 粉刷房子 IV

题目链接

这道题第一想法是暴力枚举每一个房屋的颜色，一看数据范围肯定超时，再看为什么不能记忆化，因为题目约定了对称的颜色不能相同，也就是说不管从前往后还是从后往前枚举，它都会影响到后面枚举的房屋的颜色，那么能否同时枚举对称房屋（ $i$ 和 $n-i-1$ ）的颜色呢？

换一种状态定义，$dfs(i,l,r)$：前后各 $i+1$ 个房子的最低涂色成本，且第 $i-1$ 个房子的颜色为 $l$，第 $n-i-2$ 个房子的颜色为 $r$。

• 对于 $dfs(i,l,r)$，枚举第 $i$ 个和第 $n-i-1$ 个房子的颜色 $a、b$，要求 $a!=b$ & $a!=l$ & $b!=r$，即 $dfs(i,l,r)=min(dfs(i-1,a,b)+cost[i][a]+cost[n-i-1][b])$

代码如下：

class Solution {
    public long minCost(int n, int[][] cost) {
        memo = new long[n/2][4][4];
        for(long[][] x : memo){
            for(long[] y : x){
                Arrays.fill(y, -1);
            }
        }
        return dfs(n/2-1, 3, 3, cost);
    }
    long[][][] memo;
    long dfs(int i, int l, int r, int[][] cost){
        if(i < 0) return 0;
        if(memo[i][l][r] != -1) return memo[i][l][r];
        long res = Long.MAX_VALUE;
        int n = cost.length;
        for(int a=0; a<3; a++){
            for(int b=0; b<3; b++){
                if(a!=b && a!=l && b!=r){
                    res = Math.min(res, dfs(i-1, a, b, cost) + cost[i][a] + cost[n-i-1][b]);
                }
            }
        }
        return memo[i][l][r] = res;
    }
}
//递推写法
class Solution {
    public long minCost(int n, int[][] cost) {
        //(i,n-i-1) (i, i+1)不同
        //(1,2,3) 3种颜色
        long[][][] f = new long[n/2+1][4][4];
        for(long[][] x : f){
            for(long[] y : x){
                Arrays.fill(y, Long.MAX_VALUE);
            }
        }
        for(int i=0; i<3; i++){
            Arrays.fill(f[0][i], 0);
        }
        long ans = Long.MAX_VALUE;
        for(int i=0; i<n/2; i++){
            for(int l=0; l<3; l++){
                for(int r=0; r<3; r++){
                    for(int a=0; a<3; a++){
                        for(int b=0; b<3; b++){
                            if(a==b || l==a || r==b) continue;
                            f[i+1][l][r] = Math.min(f[i+1][l][r], f[i][a][b] + cost[i][a] + cost[n-1-i][b]);
                            if(i+1==n/2) ans = Math.min(ans, f[i+1][l][r]);
                        }
                    }
                }
            }
            
        }
        return ans;
    }
}

四、3430. 最多 K 个元素的子数组的最值之和

题目链接

本题是 $T2$ 的升级版——求长度至多为 $k$ 的所有子数组的最大值和最小值的和，本题的思路与 $T2$ 基本相同，求以 $x=nums[i]$ 为最大值或最小值的子数组数量，将其相乘，得到答案。

本题的难点在于如何计算以 $x=nums[i]$ 为最大值或最小值的子数组数量。假设求以 $x=nums[i]$ 为最小值的子数组数量，那么就需要知道 $nums[i]$ 的边界 $(l,r)$，$l:$ $nums[i]$ 左边第一个小于它的元素下标，$r:$ $nums[i]$ 右边第一个小于它的元素下标。

如何快速计算 $nums$ 数组中每个元素为最小值的 $(l,r)$，使用单调栈（栈内存储的是下标），遍历 $nums$ 数组：

• 初始化 $pre$ 数组为 $-1$，$suf$ 数组为 $n$。

• 当 $while(!que.isEmpty()$ && $nums[que.peekLast()]>=x)$ 时，说明对于 $nums[que.peekLast()]$ 来说，$nums[i]$ 就是它右边第一个小于等于它的元素，$suf[que.pollLast()]=i$，赋值的同时排出顶层的元素。

• 出了上述循环，就说明如果栈不为空的话，$nums[que.peekLast()]>nums[i]$，对于 $nums[i]$ 来说，$nums[que.peekLast()]$ 就是左边第一个小于 $nums[i]$ 的元素，$pre[i]=que.peekLast()$

• 最后将 $i$ 加入栈中，$que.addLast(i)$

• PS：如果使用两次单调栈分别计算 $pre、suf$ 数组的话，题目中可能会出现 $[1,3,5,4,3,2]$ 的情况，就不能同时使用 $while(!que.isEmpty()$ && $nums[que.peekLast()]>=x)$，因为这样两个元素 3 算出来的区间 $(l,r)$ 都是 $(0,5)$，会重复计算 $[3,5,4,3]$ 的情况，所以其中必须有一个$>$，有一个$>=$。如果计算 $pre$ 数组用$>=$，那么前一个 3 就不包含 $[3,5,4,3]$，反之就是后一个 3 不包含 $[3,5,4,3]$。

计算出每个 $nums[i]$ 的左右区间$(l,r)$后，剩下的就是计算能形成多少以 $nums[i]$ 为最小值的子数组了，分情况讨论：

• $r-l-1⩽k$ 时，没有 $k$ 的限制，左边有选 $i-l$ 种选法，右边有 $r-i$ 种选法，左右组合，共有 $(i-l)(r-i)$ 种选法。

• $r-l-1>k$ 时，有 $k$ 的限制，对于左端点 $l$ 来说，由于最多选 $k$ 个数，所以 $l$ 必须大于等于 $i-k$，否则就取不到 $nums[i]$ 了。 $l=max(l,i-k)$，同理 $r=min(r,i+k)$，分情况讨论：

  • $l>r-k$ 时，此时和情况一相同，没有 $k$ 的限制，左边有选 $i-(r-k)$ 种选法，右边有 $r-i$ 种选法，左右组合，共有 $(i-(r-k))(r-i)$ 种选法。
  • $l⩽r-k$ 时，
    • 以 $l+1$ 为左端点的子数组有 $l+k-i+1$ 个，
    • 以 $l+2$ 为左端点的子数组有 $l+k-i+2$ 个，
    • 以 $l+3$ 为左端点的子数组有 $l+k-i+3$ 个，
    • …
    • 以 $r-k$ 为左端点的子数组有 $r-i$ 个，
    • 可以发现它其实是一个等差数列，使用求和公式可以得到 $(l+k-i+r-i+1)(r-k-(l+1)+1)/2$

这是计算以 $nums[i]$ 为最小值的子数组的数目，计算最大值其实可以将 $nums$ 数组中的每个元素变成相反数，这样最大值就可以复用最小值的代码，最终返回的是一个负值，只要减去就行。

代码如下：

class Solution {
    public long minMaxSubarraySum(int[] nums, int k) {
        long ans = sumMinMAX(nums, k);
        int n = nums.length;
        for(int i=0; i<n; i++){
            nums[i] = -nums[i];
        }
        return ans - sumMinMAX(nums, k);
    }
    long sumMinMAX(int[] nums, int k){
        int n = nums.length;
        int[] pre = new int[n];
        int[] suf = new int[n];
        Arrays.fill(suf, n);
        Arrays.fill(pre,-1);
        Deque<Integer> que = new ArrayDeque<>();
        for(int i=0; i<n; i++){
            int x = nums[i];
            //nums=[1,3,5,4,3,2],前一个3不包含[3,5,4,3],后一个3包含[3,5,4,3]
            while(que.size() > 0 && nums[que.peekLast()] >= x){
                suf[que.pollLast()] = i;
            }
            if(que.size() > 0)
                pre[i] = que.peekLast();
            que.addLast(i);
        }
        long ans = 0;
        for(int i=0; i<n; i++){
            int x = nums[i];
            int l = pre[i], r = suf[i];
            if(r-l-1 <= k){
                ans += (long)(r-i)*(i-l)*x;
            }else{
                l = Math.max(l, i-k);
                r = Math.min(r, i+k);
                //l>r-k
                ans += (long)(r-i)*(i-(r-k))*x;
                //l<=r-k
                ans += (long)(r+l+k-2*i+1)*(r-k-l)/2*x;
            }
        }
        return ans;
    }
}