LeetCode --- 446 周赛

题目列表

3522. 执行指令后的得分
3523. 非递减数组的最大长度
3524. 求出数组的 X 值 I
3525. 求出数组的 X 值 II

一、执行指令后的得分

照着题目要求进行模拟即可，代码如下

// C++
class Solution {
public:
    long long calculateScore(vector<string>& instructions, vector<int>& values) {
        long long ans = 0;
        int n = values.size();
        vector<bool> vis(n);
        for(int i = 0; i >= 0 && i < n;){
            if(vis[i]) break;
            vis[i] = true;
            if(instructions[i][0] == 'a'){
                ans += values[i++];
            }else{
                i = i + values[i];
            }
        }
        return ans;
    }
};

# Python
class Solution:
    def calculateScore(self, instructions: List[str], values: List[int]) -> int:
        n = len(values)
        i = 0
        ans = 0
        vis = [False] * n
        while 0 <= i < n:
            if vis[i]:
                break
            vis[i] = True
            if instructions[i][0] == 'a':
                ans += values[i]
                i += 1
            else:
                i += values[i]
        return ans

二、非递减数组的最大长度

根据题目的操作方式，我们会得到以下性质：

• 最大的元素一定会被保留
• 最大的元素后面的元素一定会被删除
• 去掉最大元素，我们考虑剩下元素，依旧有上诉的性质
• 如此循环，直到没有元素可以选择

在上述过程中找最大值的操作需要 O(n) 的时间，会超时，但其实，如果我们逆着看思考过程，就会发现找最大值的操作就是在找前缀最大值，判断一个元素是否能保留，就是看他是否是前缀最大值，代码如下

// C++
class Solution {
public:
    int maximumPossibleSize(vector<int>& nums) {
        int ans = 0, mx = 0;
        for(int x : nums){
            mx = max(mx, x);
            if(x == mx)
                ans++;
        }
        return ans;
    }
};

# Python
class Solution:
    def maximumPossibleSize(self, nums: List[int]) -> int:
        mx = 0
        ans = 0
        for x in nums:
            mx = max(mx, x)
            if x == mx:
                ans += 1
        return ans

三、求出数组的 X 值 I

对于这类子数组问题，我们可以用 53. 最大子数组和 的动态规划想法来思考

• 设 $f[i][j]$ 表示以 $i$ 为右端点的乘积除以 $k$ 后余数为 $j$ 的子数组的个数
• 如果和以 $i-1$ 为右端点的子数组连起来，则 $f[i][(j\ast x)\%k]+$$=f[i-1][j]$，其中 $x=nums[i]、j\in [0,k)$
• 如果 $i$ 单独作为一个子数组，则 $f[i][x\%k]+$$=1$

代码如下

// C++
class Solution {
public:
    vector<long long> resultArray(vector<int>& nums, int k) {
        int n = nums.size();
        vector f(n + 1, vector<long long>(k));
        vector<long long> res(k);
        for(int i = 0; i < n; i++){
            int x = nums[i] % k;
            for(int j = 0; j < k; j++){
                f[i+1][j*x%k] += f[i][j];
            }
            f[i+1][x % k]++;
            for(int j = 0; j < k; j++){
                res[j] += f[i+1][j];
            }
        }
        return res;
    }
};

// 空间优化
class Solution {
public:
    vector<long long> resultArray(vector<int>& nums, int k) {
        int n = nums.size();
        vector<long long> f(k);
        vector<long long> res(k);
        for(int i = 0; i < n; i++){
            int x = nums[i] % k;
            vector<long long> tmp(k);
            for(int j = 0; j < k; j++){
                tmp[j*x%k] += f[j];
            }
            tmp[x % k]++;
            f = tmp;
            for(int j = 0; j < k; j++){
                res[j] += f[j];
            }
        }
        return res;
    }
};

# Python
class Solution:
    def resultArray(self, nums: List[int], k: int) -> List[int]:
        res = [0] * k
        f = [0] * k
        
        for num in nums:
            m = num % k
            tmp = [0] * k
            tmp[m] += 1
            
            for x in range(k): 
                tmp[(x * m) % k] += f[x]
            
            f = tmp
            for x in range(k):
                res[x] += f[x]
        
        return res

四、求出数组的 X 值 II

(注意：本题的题面和上一题不一样，请仔细阅读)

通过题目，我们不难看出查询的几个经典特征：单点修改+区间查询，很容易想到用 线段树 来维护，关键是如何进行维护，或者说线段树的结点应该保留哪些值？

• mul表示整个区间的乘积 %k 后的值，为了方便后面计算

• array<int,5>res，res[i] 表示 [l,r]中以 l 为左端点的元素乘积 %k = i 的子数组个数，这里直接开 5 个 int 是因为 k 最大为 5

• 合并区间时

  • cur.mul = left.mul * right.mul % k
  • cur.res = left.res && cur.res[left.mul * i % k] += right.res[i]，因为都要以 l 为左端点

// C++
struct Node{
    long long mul;
    array<int, 5> res;
};
class SegTree{    
public:
    SegTree(int n, int K):t(n << 2), k(K){}
    void maintain(int o){
        t[o].mul = (t[o<<1].mul * t[o<<1|1].mul) % k;
        t[o].res = t[o<<1].res;
        for(int i = 0; i < k; i++){
            t[o].res[t[o<<1].mul * i % k] += t[o<<1|1].res[i];
        }
    }
    void build(int o, int l, int r, const vector<int> & a){
        if(l == r){
            t[o].mul = a[l] % k;
            t[o].res[a[l] % k] = 1;
            return;
        }
        int mid = l + (r - l) / 2;
        build(o << 1, l, mid, a);
        build(o << 1 | 1, mid + 1, r, a);
        maintain(o);
    }
    void update(int o, int l, int r, int i, int val){
        if(l == r){
            t[o].mul = val % k;
            for(int i = 0; i < k; i++)
                t[o].res[i] = 0;
            t[o].res[val % k] = 1;
            return;
        }
        int mid = l + (r - l) / 2;
        if(i <= mid) update(o << 1, l, mid, i, val);
        else update(o << 1 | 1, mid + 1, r, i, val);
        maintain(o);
    }
    Node query(int o, int l, int r, int L, int R){
        if(L <= l && r <= R){
            return t[o];
        }
        int mid = l + (r - l) / 2;
        if(L <= mid){
            auto left = query(o << 1, l, mid, L, R);
            if(mid < R){
                auto right = query(o << 1 | 1, mid + 1, r, L, R);
                Node ret;
                ret.mul = left.mul * right.mul % k;
                ret.res = left.res;
                for(int i = 0; i < k; i++){
                    ret.res[left.mul*i % k] += right.res[i];
                }
                return ret;
            }
            return left;
        }
        return query(o << 1 | 1, mid + 1, r, L, R);
    }
private:
    vector<Node> t;
    int k;
};
class Solution {
public:
    vector<int> resultArray(vector<int>& nums, int k, vector<vector<int>>& queries) {
        int n = nums.size();
        SegTree t(n, k);
        t.build(1, 0, n - 1, nums);
        vector<int> res;
        for(auto& q : queries){
            t.update(1, 0, n - 1, q[0], q[1]);
            res.push_back(t.query(1, 0, n - 1, q[2], n - 1).res[q[3]]);
        }
        return res;
    }
};