LeetCode --- 441周赛

题目列表

3487. 删除后的最大子数组元素和
3488. 距离最小相等元素查询
3489. 零数组变换 IV
3490. 统计美丽整数的数目

一、删除后的最大子数组元素和

题目要求我们去掉一些元素使得数组之和最大，即只取数组中 $\ge 0$ 的数字，同时数组中不能包含重复元素，可以通过哈希表去重，注意数组不能为空，也就是说，当数组全为负的时候，此时，我们应该取一个最大的负数。

代码如下

// C++
class Solution {
public:
    int maxSum(vector<int>& nums) {
        unordered_set<int> st;
        int mx = INT_MIN, sum = 0;
        for(auto x : nums){
            if(x >= 0 && !st.contains(x)){
                st.insert(x);
                sum += x;
            }else{
                mx = max(mx, x);
            }
        }
        return st.empty() ? mx : sum;
    }
};

# Python
class Solution:
    def maxSum(self, nums: List[int]) -> int:
        st = set(x for x in nums if x >= 0)
        return sum(st) if st else max(nums)

二、距离最小相等元素查询

本题的关键是如何快速的计算出与 $nums[query[i]]$ 相同的元素 $nums[j]$，其中 $j!=query[i]$，且 $|query[i]-j|$ 最小，返回所有查询的 $|query[i]-j|$，如果不存在这样的 $j$，返回 $-1$

• 对于任意一个元素 $nums[i]$，我们只要知道它左右两边的与之相同的数字下标 $l,r$，就能直接算出答案，为 $min(i-l,r-i)$

如何计算出 $nums[i]$ 左边的与之相同数字下标 $l？$，用 $left[i]$ 记录下标

• 在从左往右遍历 $nums$ 数组的同时，维护 $mp[x]$，表示 $x$ 最近一次出现的下标
• 对于 $nums[i]$，它的 $left[i]=mp[nums[i]]$
• 注意：题目中给的是循环数组，也就是说 $left[0]$ 需要看最后一个与 $nums[0]$ 相同的下标 $j$，同时，为了方便计算，我们可以将其下标进行 $j-n$ 的操作，这样我们在计算 $i-l$ 时，就能算出正确的结果
• 右边也是同理

代码如下

// C++
class Solution {
public:
    vector<int> solveQueries(vector<int>& nums, vector<int>& queries) {
        int n = nums.size(), m = queries.size();
        vector<int> left(n), right(n);
        unordered_map<int,int> mp;
        for(int i = -n; i < n; i++){
            if(i >= 0)
                left[i] = mp[nums[i]];
            mp[nums[(i+n)%n]] = i;
        }
        mp.clear();
        for(int i = 2*n-1; i >= 0; i--){
            if(i < n)
                right[i] = mp[nums[i]];
            mp[nums[i%n]] = i;
        }
        vector<int> ans(m);
        for(int i = 0; i < m; i++){
            int j = queries[i];
            ans[i] = min(j - left[j], right[j] - j);
            if(ans[i] == n) // 说明这个数字只出现了一次
                ans[i] = -1; 
        }
        return ans;
    }
};

# Python
class Solution:
    def solveQueries(self, nums: List[int], queries: List[int]) -> List[int]:
        n, m = len(nums), len(queries)
        mp = {}
        left = [0] * n
        right = [0] * n
        for i in range(-n, n):
            if i >= 0:
                left[i] = mp[nums[i]]
            mp[nums[i]] = i
        mp.clear()
        for i in range(2*n-1, -1, -1):
            if i < n:
                right[i] = mp[nums[i]]
            mp[nums[i%n]] = i
        ans = [0] * m
        for i, x in enumerate(queries):
            ans[i] = min(x - left[x], right[x] - x)
            if ans[i] == n:
                ans[i] = -1
        return ans

三、零数组变换 IV

题目求最少需要经过前多少个 $queries$ 才能让 $nums$ 数组全为 $0$

假设需要前 $k$ 个查询，则对于任意一个 $nums[i]$ 来说，会有一个集合 { v a l j } \{val_j\} {valj​} ，其中 $0\le j\le k，l_j\le i\le r_j$，只要能从该集合中选出一些数字让它们的元素之和等于 $nums[i]$，则 $nums[i]$ 能变成 $0$，而这是一个标准的 $01背包$ 问题。并且每一个 $01背包$ 都是独立的。我们只要同时计算这 $n$ 个 $01背包$ 即可。

$01背包：能否从数组nums中选出一些数字使得它们的和等于target$
$设f[i][j]表示是否能从前i个元素中选出一些元素，使得它们的和等于j$
$1、如果不选nums[i]，那么f[i][j]=f[i-1][j]$
$2、如果选择nums[i]，那么f[i][j]=f[i-1][j-nums[i]]，此时j>=nums[i]$
$故f[i][j]=f[i-1][j]||f[i-1][j-nums[i]]，f[0][0]=true$
$也可以进行空间优化，去掉第一个维度，此时对于j，我们需要倒着遍历$
$f[j]=f[j]||f[j-nums[i],f[0]=true$

代码如下

// C++
class Solution {
public:
    int minZeroArray(vector<int>& nums, vector<vector<int>>& queries) {
        if(ranges::all_of(nums, [](int x){return x == 0;}))
            return 0;
        int n = nums.size();
        vector<vector<bool>> f(n); // n 个 01背包
        for(int i = 0; i < n; i++){
            f[i].resize(nums[i] + 1);
            f[i][0] = true;
        } 
        for(int k = 0; k < queries.size(); k++){
            auto & q = queries[k];
            for(int i = q[0]; i <= q[1]; i++){ // 对于在此区间内的01背包都多了一个q[2]可选
                if(f[i][nums[i]]) continue; // 如果已经能组成 nums[i] 就没必要再计算了
                for(int j = nums[i]; j >= q[2]; j--){
                    f[i][j] = f[i][j] || f[i][j-q[2]];
                }
            }
            bool ok = true;
            for(auto & fi : f){
                if(!fi.back()){
                    ok = false;
                    break;
                }
            }
            if(ok) return k + 1;
        }
        return -1;
    }
};

# Python
class Solution:
    def minZeroArray(self, nums: List[int], queries: List[List[int]]) -> int:
        if sum(nums) == 0:
            return 0
        n = len(nums)
        f = [[True] + [False] * nums[i] for i in range(n)]
        for k, q in enumerate(queries):
            for i in range(q[0], q[1] + 1):
	            if f[i][nums[i]]:
                    continue
                for j in range(nums[i],q[2]-1,-1):
                    f[i][j] = f[i][j] or f[i][j-q[2]]
            for i in range(n):
                if f[i][nums[i]] == False:
                    break
            else:
                return k + 1
        return -1

四、统计美丽整数的数目

对于这类求区间范围内符合某种条件的数字的个数的题，可以用 $数位DP$ 来做

• $数位DP思想：去构造一个数字，在构造的同时维护数字的某些特殊信息，从而判断我们构造的数字是否符合条件$

代码如下

// C++
class Solution {
public:
    int beautifulNumbers(int l, int r) {
        string sl = to_string(l), sr = to_string(r);
        int n = sr.size();
        int diff = n - sl.size();
        unordered_map<long long, int> mp;
        // | mul   | sum  | i    |
        // | 9^9   | 81   | 9    |
        // | 29bit | 7bit | 4bit |
        auto dfs = [&](this auto && dfs, int i, bool limit_low, bool limit_high, int mul, int sum)->int{
            if(i == n){
                return sum && mul % sum == 0;
            }
            long long mask = (long long)mul << 11 | sum << 4 | i;
            if(!limit_low && !limit_high && mp.count(mask)) return mp[mask];
            // 注意：这里的 up 和 down 计算完之后就不要在改变
            int up = limit_high ? sr[i] - '0' : 9;
            int down = limit_low && i >= diff ? sl[i - diff] - '0' : 0;
            
            int res = 0, d = down;
            if(i < diff && limit_low){ // 表示前面还没有填数字
                res += dfs(i + 1, true, false, 1, 0);
                d = 1; // 此时如果要填数字，只能从 1 开始
            }
            for(; d <= up; d++){
                res += dfs(i + 1, limit_low && d == down, limit_high && d == up, mul * d, sum + d);
            }
            if(!limit_low && !limit_high){
                mp[mask] = res;
            }
            return res;
        };
        return dfs(0, true, true, 1, 0);
    }
};

# Python
class Solution:
    def beautifulNumbers(self, l: int, r: int) -> int:
        sr = list(map(int, str(r)))
        sl = list(map(int, str(l)))
        n = len(sr)
        diff = n - len(sl)
        @cache
        def dfs(i:int, limit_low:bool, limit_high:bool, mul:int, sum:int)->int:
            if i == n:
                return 1 if sum > 0 and mul % sum == 0 else 0
            up = sr[i] if limit_high else 9
            down = sl[i-diff] if limit_low and i >= diff else 0

            res = 0
            d = down
            if limit_low and i < diff:
                res += dfs(i + 1, True, False, 1, 0)
                d = 1
            for d in range(d, up + 1):
                res += dfs(i + 1, limit_low and d == down, limit_high and d == up, mul * d, sum + d)
            return res
        return dfs(0, True, True, 1, 0)

可能有人会觉得这样记忆化的状态个数太多了，会超时 / 爆内存，我们可以来计算一下看看

• $设i_{mx}表示i的所有可能值的个数，mu{l}_{mx}表示mul的所有可能值的个数，su{m}_{mx}表示sum的所有可能值的个数$
• $则i_{mx}=9，mu{l}_{mx}=9^9，su{m}_{mx}=81$
• $i_{mx}\times mu{l}_{mx}\times su{m}_{mx}\times 2\times 2=9^{12}\times 2^2>10^9，故超时并且爆内存$
• $但是实际上mu{l}_{mx}=3026，大家可以跑一个程序测试一下$
• $所以实际上i_{mx}\times mu{l}_{mx}\times su{m}_{mx}\times 2\times 2\approx 9\times 10^6$
• $有兴趣的可以思考一下为什么mul的可能结果只有这么少？欢迎在评论区留下你的看法$

// C++
int init = [](){
    set<int> st{1};
    for(int i = 0; i < 9; i++){
        auto tmp = st;
        for(auto& y : tmp){
            for(int x = 0; x < 10; x++){
                st.insert(x * y);
            }
        }
    }
    cout << st.size() << endl;
    return 0;
}();

# Python
st = set()
st.add(1)
for _ in range(9):
    st = set(x*i for x in st for i in range(10))
print(len(st))