第 121 场 LeetCode 双周赛题解

发布时间:2024年01月07日

A 大于等于顺序前缀和的最小缺失整数

在这里插入图片描述

模拟:先求最长顺序前缀的和 s s s ,然后从 s s s 开始找没有出现在 n u m s nums nums 中的最小整数

class Solution {
public:
    int missingInteger(vector<int> &nums) {
        unordered_set<int> vis(nums.begin(), nums.end());
        int s = nums[0];
        int i = 0;
        while (i + 1 < nums.size() && nums[i + 1] == nums[i] + 1)
            s += nums[++i];
        while (vis.count(s))
            s++;
        return s;
    }
};


B 使数组异或和等于 K 的最少操作次数

在这里插入图片描述

枚举:求出 n u m s nums nums 各元素异或和 t o t tot tot ,对 t o t tot tot k k k 的二进制表示按位枚举,若两数某一位不同,则需要增加一次操作数

class Solution {
public:
    int minOperations(vector<int> &nums, int k) {
        int tot = 0;
        for (auto x: nums)
            tot ^= x;
        int res = 0;
        for (int i = 0; i < 32; i++)
            if ((tot >> i & 1) != (k >> i & 1))
                res++;
        return res;
    }
};

C 使 X 和 Y 相等的最少操作次数

在这里插入图片描述
在这里插入图片描述

bfs:相当于求从 x x x 出发到 y y y 的最短路,搜素过程中用集合记录已经到达过的数

class Solution {
public:
    int minimumOperationsToMakeEqual(int x, int y) {
        unordered_set<int> vis;
        queue<pair<int, int>> q;
        vis.insert(x);
        q.emplace(x, 0);
        int res;
        while (!q.empty()) {
            auto [v, cnt] = q.front();
            q.pop();
            if (v == y) {
                res = cnt;
                break;
            }
            if (v > y && v % 11 == 0 && !vis.count(v / 11)) {
                vis.insert(v / 11);
                q.emplace(v / 11, cnt + 1);
            }
            if (v > y && v % 5 == 0 && !vis.count(v / 5)) {
                vis.insert(v / 5);
                q.emplace(v / 5, cnt + 1);
            }
            if (!vis.count(v + 1)) {
                vis.insert(v + 1);
                q.emplace(v + 1, cnt + 1);
            }
            if (v > y && !vis.count(v - 1)) {
                vis.insert(v - 1);
                q.emplace(v - 1, cnt + 1);
            }
        }
        return res;
    }
};


D 统计强大整数的数目

在这里插入图片描述

数位dp + 记忆化搜素:定义 c m p ( x , m x , s u f ) cmp(x,mx,suf) cmp(x,mx,suf) 为不超过 x x x 且数中各数位不超过 m x mx mx 且数的末尾部分是 s u f suf suf 的数的数目,则题目答案为 c m p ( f i n i s h , l i m i t , s ) ? c m p ( s t a r t ? 1 , l i m i t , s ) cmp(finish, limit, s) - cmp(start - 1, limit, s) cmp(finish,limit,s)?cmp(start?1,limit,s) 。在 c m p cmp cmp 中定义 p [ l o c ] [ v a l ] [ e q ] p[loc][val][eq] p[loc][val][eq] 为:当前枚举下标为 l o c loc loc 且 之前位置对应的数位是否有数字(0:无,1:有)且 之前位置对应的数位的数字形成的前缀是否和 x x x 对应的前缀相等(0:不等,1:相等),这种情况下末尾部分是 s u f suf suf 的数的数目,通过记忆化搜素枚举状态转移的过程,最终 c m p ( x , m x , s u f ) cmp(x,mx,suf) cmp(x,mx,suf) 即为 p [ 0 ] [ 0 ] [ 1 ] p[0][0][1] p[0][0][1]

class Solution {
public:
    using ll = long long;

    long long numberOfPowerfulInt(long long start, long long finish, int limit, string s) {
        return cmp(finish, limit, s) - cmp(start - 1, limit, s);
    }

    ll cmp(ll x, int mx, string &suf) {
        if (x < stol(suf))
            return 0;
        string s0 = to_string(x);
        int n = s0.size();
        int m = suf.size();
        ll suf0 = stol(s0.substr(n - m, m));//x与suf相同长度的末尾部分
        ll vsuf = stol(suf);
        ll p[n][2][2];
        memset(p, -1, sizeof(p));
        function<ll(int, int, int)> get = [&](int loc, int val, int eq) {//记忆化搜素
            if (p[loc][val][eq] != -1)
                return p[loc][val][eq];
            if (n - loc == m) {//loc已经为suf的第一位
                if (suf0 >= vsuf || eq == 0)
                    p[loc][val][eq] = 1;
                else //末尾若是suf则会大于x,所以不存在这样的数
                    p[loc][val][eq] = 0;
                return p[loc][val][eq];
            }
            p[loc][val][eq] = 0;
            if (val) {//之前位置对应的数位有数字
                if (eq) {//之前位置对应的数位的数字形成的前缀和x对应的前缀相等
                    for (int i = 0; i <= s0[loc] - '0' && i <= mx; i++)
                        p[loc][val][eq] += get(loc + 1, 1, i == s0[loc] - '0' ? 1 : 0);
                } else {//之前位置对应的数位的数字形成的前缀和x对应的前缀不等
                    for (int i = 0; i <= mx; i++)
                        p[loc][val][eq] += get(loc + 1, 1, 0);
                }
            } else {//之前位置对应的数位无数字
                if (eq) {//之前位置对应的数位的数字形成的前缀和x对应的前缀相等
                    p[loc][val][eq] += get(loc + 1, 0, 0);//当前数位没有数字
                    for (int i = 1; i <= s0[loc] - '0' && i <= mx; i++)
                        p[loc][val][eq] += get(loc + 1, 1, i == s0[loc] - '0' ? 1 : 0);
                } else {//之前位置对应的数位的数字形成的前缀和x对应的前缀不等
                    p[loc][val][eq] += get(loc + 1, 0, 0);//当前数位没有数字
                    for (int i = 1; i <= mx; i++)
                        p[loc][val][eq] += get(loc + 1, 1, 0);
                }
            }
            return p[loc][val][eq];
        };
        return get(0, 0, 1);
    }
};
文章来源:https://blog.csdn.net/weixin_40519680/article/details/135433862
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。