leetcode 第 154 场双周赛 & 第 445 场周赛

2025-04-14

3512. 使数组和能被 K 整除的最少操作次数

class Solution {
public:
    int minOperations(vector<int>& nums, int k) {
        int sum  = 0;
        for(auto x : nums) sum += x;
        int t = sum % k;
        return t;
    }
};

3513. 不同 XOR 三元组的数目 I

class Solution {
public:
    int uniqueXorTriplets(vector<int>& nums) {
        int n = nums.size();
        if(n == 1) return 1;
        if(n == 2) return 2;
        int t = 0;
        while(n) {
            n >>= 1;
            t++;
        }
        return (1 << t);
    }
};

3514. 不同 XOR 三元组的数目 II

转化为两个两层for循环，暴力即可

class Solution {
public:
    int uniqueXorTriplets(vector<int>& nums) {
        int n = nums.size();
        unordered_set<int> mp;
        for(auto& x : nums) {
            for(auto& y : nums) {
                mp.insert(x ^ y);
            }
        }
        unordered_set<int> se;
        for(auto& x : nums) {
            for(auto& y : mp) {
                se.insert(x ^ y);
            }
        }
        return se.size();
    }
};

3515. 带权树中的最短路径

这场比赛最有价值的一道题了， dfs序，把一个树转化为一个数组使用数据结构来处理

dfs序代码

vector<int> in(n + 1), out(n + 1);
int clock = 0;
// dfs序, 通过clock 标记， 把树转化为数组， 数据结构处理修改查询
auto dfs = [&](this auto&& dfs, int x, int fa) -> void {
    in[x] = ++clock;
    for(int y : g[x]) {
        if(y != fa) dfs(y, x);
    }
    out[x] = clock;
};
dfs(1, 0);

处理查询时使用树状数组+差分即可

class BinaryIndexedTree
{
private:
    vector<int> tree;

public:
    BinaryIndexedTree(int n) : tree(n + 1) {}

    void add(int i, int v)
    {
        while (i < tree.size())
        {
            tree[i] += v;
            i += i & -i;
        }
    }

    int get(int i)
    {
        int res = 0;
        while (i > 0)
        {
            res += tree[i];
            i &= i - 1;
        }
        return res;
    }
};

class Solution {
public:
    vector<int> treeQueries(int n, vector<vector<int>>& edges, vector<vector<int>>& queries) {
        vector<vector<int>> g(n + 1);
        for(auto& e : edges) {
            int x = e[0], y = e[1];
            g[x].push_back(y);
            g[y].push_back(x);
        }
        vector<int> in(n + 1), out(n + 1);
        int clock = 0;
        // dfs序, 通过clock 标记， 把树转化为数组， 数据结构处理修改查询
        auto dfs = [&](this auto&& dfs, int x, int fa) -> void {
            in[x] = ++clock;
            for(int y : g[x]) {
                if(y != fa) dfs(y, x);
            }
            out[x] = clock;
        };
        dfs(1, 0);
        vector<int> weight(n + 1);
        BinaryIndexedTree bits(n + 1);
        auto update = [&](int x, int y, int w) {
            if(in[x] > in[y]) y = x;
            int d = w - weight[y];
            weight[y] = w;
            bits.add(in[y], d);
            bits.add(out[y] + 1, -d);
        };
        vector<int> ans;
        for(auto&e : edges) update(e[0], e[1], e[2]);
        for(auto& q : queries) {
            if(q[0] == 1) update(q[1], q[2], q[3]);
            else ans.push_back(bits.get(in[q[1]]));
        }
        return ans;
    }
};

3516. 找到最近的人

class Solution {
public:
    int findClosest(int x, int y, int z) {
        int a = abs(x - z), b = abs(y - z);
        if(a == b) return 0;
        else if(a < b) return 1;
        else return 2;
    }
};

3517. 最小回文排列

回文子序列，只考虑前半部分即可，把前半部分排序，再用前半部分 + reverse(前半部分)。如果n为奇数，把第（n / 2）+ 1 位加到中间即可

class Solution {
public:
    string smallestPalindrome(string s) {
        int n = s.size();
        string t;
        for(int i = 0; i < n / 2; i++) t += s[i];
        sort(t.begin(), t.end());
        string rt = t;
        reverse(rt.begin(), rt.end());
        if(n & 1) {
            t += s[n / 2];
        }
        t += rt;
        return t;
    }
};

3518. 最小回文排列 II

整体思路是试填法，组合数学comb见代码

class Solution {
public:
    string smallestPalindrome(string s, int k) {
        int n = s.size();
        int m = n / 2;
        int cnt[26]{};
        for(int i = 0; i < m; i++) {
            cnt[s[i] - 'a']++;
        }
		// 计算组合数学
        auto comb = [&](int n, int m) -> int {
            m = min(m, n - m);
            long long res = 1;
            for(int i = 1; i <= m; i++) {
                res = res * (n + 1 - i) / i; // 可以证明 这里 (n + 1 - i) / i 一定是整数
                if(res >= k) return k; // res > k 就没必要计算了
            }
            return res;
        };
        
        auto prem = [&](int sz) -> int {
            long long res = 1;
            for(int c : cnt) {
                if(c == 0) continue;
                // 组合数学计算总方案数
                res *= comb(sz, c);
                if(res >= k) {
                    return k;
                }
                sz -= c;
            }
            return res;
        };
        // 判断排列情况是否大于等于k
        if(prem(m) < k) {
            return "";
        }
        string t(m, 0);
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < 26; j++) {
                if(!cnt[j]) continue;
                cnt[j]--;
                int p = prem(m - i - 1);
                // 试填法， 如果把这个字符填入当前位置， 排列数是否满足条件
                if(p >= k) {
                    t[i] = 'a' + j;
                    break;
                }
                //这个位置不能填 ‘a’ + j， 排列 - p， 表示当前减去了第k之前的p个排列 
                k -= p;
          
                cnt[j]++;
            }
        }
        string ans = t;
        ranges::reverse(t);
        if(n & 1) {
            ans += s[n / 2];
        }
        return ans + t;
    }
};

3519. 统计逐位非递减的整数

先把10进制转化为b进制，这样直接计算b 进制下满足条件的数量即可

数位dp 板子题，最大挑战就是进制转换了

class Solution {
public:
    const int MOD = 1e9 + 7;
    int calc(string s, int b) {
        int n = s.size();
        vector<vector<int>> memo(n + 1, vector<int>(10, -1));
        auto dfs = [&](auto&& dfs, int i, bool is_limit, bool is_num, int pre) -> int {
            if(i == n)  {
                return is_num;
            }
            int res = 0;
            if(!is_num) {
                res = (res + dfs(dfs, i + 1, false, false, 0)) % MOD;
            }
            if(!is_limit && is_num && memo[i][pre] != -1) return memo[i][pre];
            int up = is_limit ? s[i] - '0' : b - 1;
            for(int d = 1 - is_num; d <= up; d++) {
                if(!is_num) {
                    res = (res + dfs(dfs, i + 1, is_limit && d == up, true, d)) % MOD;
                }else{
                    if(d >= pre) {
                        res = (res + dfs(dfs, i + 1, is_limit && d == up, true, d)) % MOD;
                    }
                }
            }
            if(!is_limit && is_num) memo[i][pre] = res;
            return res;
        };
        return dfs(dfs, 0, true, false, 0);
    }
    string func(string s, int b) {
        string result;
        while (!s.empty()) {
            int remainder = 0;
            string quotient;
            for (char c : s) {
                int current = remainder * 10 + (c - '0');
                if (current < b && quotient.empty()) {
                    remainder = current;
                } else {
                    quotient.push_back(current / b + '0');
                    remainder = current % b;
                }
            }
            result.push_back(remainder + '0');
            s = quotient;
        }
        reverse(result.begin(), result.end());
        return result;
    }
    int countNumbers(string low, string high, int b) {       
        for(int i = low.size(); i--; i >= 0) {
            if(low[i] > '0') {
                low[i]--;
                break;
            }else{
                low[i] = '9';
            }
        }
        high = func(high, b);
        low = func(low, b);

        return (calc(high, b) - calc(low, b) + MOD) % MOD;
    }
};

以上两场是2025 4.12 和 4.13 的leetcode 周赛，

。。。端正态度