LeetCode---121双周赛---数位dp

题目列表

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

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

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

2999. 统计强大整数的数目

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

简单的模拟题，只要按照题目的要求去写代码即可，代码如下

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

二、使数组异或和为K的最小操作次数

这题考异或的性质---相同为0，相异为1，我们只要关心nums的异或和与K的二进制位有几个不同即可，也就是将k和nums一起异或，最后看二进制位上还有几个1

(这里可能有人还是很懵，简单说一下思路的正确性，异或运算的性质决定了它不会干扰到其他位，我们可以把异或运算看作是每个二进制位的单独的运算且满足交换律，现在我们单独看某一个二进制位，如果共有3个1，2个0异或，那么异或结果为1，如果我们将其中的一个1换成0或者将一个0换成1，异或的结果就会改变，至于被修改的是哪个数字的二进制位无所谓都行，所以二进制位的单一位，只需进行一次操作就能发生改变，所以我们的答案如上诉所说)

代码如下

class Solution {
public:
    int minOperations(vector<int>& nums, int k) {
        for(auto&e:nums)
            k^=e;
        return __builtin_popcount(k);//求二进制位上的1的个数
    }
};

三、使X和Y相等的最小操作次数

这题有两种思路，都给大家讲一讲，在讲思路之前，我们都应该能观察得到，当x<=y时，我们只能用+1操作，即操作个数一定为y-x，也就是说我们只要考虑x>y的情况

思路一：图的bfs

我们将x->y过程中经过的每个数看作是图上的结点，然后我们用层序遍历的思路一层层往外遍历，直到我们找到y，返回结果，因为我们的操作次数是累加的，所以第一次找到y时我们一定能得到最小的操作次数(不代表层序遍历的次数就是最小操作次数，也可能出现操作后的数小于y，然后通过+1操作实现=y的情况，具体看代码)。这个思路的关键是你能想到它能用图来类比，从而想到层序遍历，当然实现细节还是很多的。

(启发：图的遍历不是只有图能用，像这种抽象的，从一个"点"到另一个"点"，且中间经过的"点"是确定的，然后要求最小操作次数，就可以往图的层序遍历去思考)

代码如下

class Solution {
public:
    int minimumOperationsToMakeEqual(int x, int y) {
        if(x<=y)
            return y-x;
        int ans=x-y;//代表操作上限（只用减法）
        //ans+x是在操作上限的范围内只做加法操作的最大数字，+1是因为下标
        vector<bool>vis(ans+x+1);//记录遍历到的结点，能减少重复数字的遍历次数
        int step=0;

        vector<int>q;
        auto add=[&](int v){
            if(v<y)
                ans=min(ans,step+1+y-v);
            else if(!vis[v]){
                vis[v]=true;
                q.push_back(v);
            }
        };

        add(x);
        while(1){
            auto tmp=q;
            q.clear();
            for(auto v:tmp){
                if(v==y)
                    return min(ans,step);
                if(v%5==0)
                    add(v/5);
                if(v%11==0)
                    add(v/11);
                add(v-1);
                add(v+1);
            }
            step++;
        }
    }
};

思路二：记忆化搜索

首先我们要对递归有一个大体的方向，由于我们只考虑x>y的情况，所以要求操作次数最少，我们肯定希望尽可能的用/5 、/11，让x能快速的接近y，即我们将加减1当作辅助操作，同时还要考虑到只用减法操作得到最小操作次数的情况。

我们根据题意，确定递归的参数和返回值，dfs(v)返回从v到y的最小操作次数

接下来我们来想想如何从v->y

1、v<=y，只能进行+1操作，操作次数为v-y，直接返回

2、v>y

1）只用减法操作，操作次数为v-y

2）用/5操作，两种可能，进行v%5次减法操作，或者进行5-v%5次加法操作，让v变成5的倍数后/5，操作次数为min(dfs(v/5)+v%5,dfs(v/5+1)+5-v%5)+1，+1是因为/5也要算操作次数

3）用/11操作，两种可能，进行v%11次减法操作，或者进行11-v%11次加法操作，让v变成11的倍数后/11，操作次数为min(dfs(v/11)+v%11,dfs(v/11+1)+11-v%11)+1

返回三者的最小值

对于v>y的后两种情况，我们是根据红字部分得来的，其实并不严谨，因为我们没有证明，v到它前后最近的5的倍数是最优解，即它再+5/-5得到的另一个5的倍数是否会更好？这个其实很好想，+5/-5的操作次数导致的结果就是/5之后的数字相差了一个1，那么我先/5后再+1/-1，不是能更快得到结果嘛(11同理)，所以我们只考虑v前后的5的倍数即可，代码如下

class Solution {
public:
    int minimumOperationsToMakeEqual(int x, int y) {
        if(x<=y)
            return y-x;
        int memo[x+1];
        memset(memo,-1,sizeof(memo));
        function<int(int)>dfs=[&](int v)->int{
            if(v<=y)
                return y-v;
            if(memo[v]!=-1) return memo[v];
            int res=v-y;
            res=min(res,min(dfs(v/5)+v%5,dfs(v/5+1)+5-v%5)+1);
            res=min(res,min(dfs(v/11)+v%11,dfs(v/11+1)+11-v%11)+1);
            return memo[v]=res;
        };
        return dfs(x);
    }
};

?四、统计强大整数的数目

这题很典型的数位dp题，要求我们返回在所给范围内的满足条件的数字个数。数位dp的思路就是考虑如何构造出这样一个符合要求的数字，我们一位一位的考虑即可。

代码如下

class Solution {
    typedef long long LL;
public:
    long long numberOfPowerfulInt(long long start, long long finish, int limit, string s) {
        //将数字区间端点变成字符串
        string left=to_string(start);
        string right=to_string(finish);
        int n=right.size();
        left=string(n-left.size(),'0')+left;//补上前导零，方便后面的计算
        int diff=n-s.size();

        //记忆化搜索
        vector<LL>memo(n,-1);
        function<LL(int,bool,bool)>dfs=[&](int i,bool limit_low,bool limit_high)->LL{
            if(i==n)//递归到这，说明构造的数字合法，返回1
                return 1;
            if(!limit_high&&!limit_low&&memo[i]!=-1) //这个是因为限制高/限低在递归中只会走一次，没有必要进行记忆化，所以记忆数组可以是一维的
                return memo[i];

            //求当前位置的数的取值范围
            int high=limit_high?right[i]-'0':9;
            int low=limit_low?left[i]-'0':0;
            LL res=0;
            
            //根据题目的其他限制条件，进行递归
            if(i<diff)
                for(int d=low;d<=min(high,limit);d++)
                    res+=dfs(i+1,d==low&&limit_low,d==high&&limit_high);
            else{
                int d=s[i-diff]-'0';
                if(d>=low&&d<=min(high,limit))
                    res=dfs(i+1,d==low&&limit_low,d==high&&limit_high);
            }
            if(!limit_high&&!limit_low)
                memo[i]=res;
            return res;
        };

        return dfs(0,true,true);
    }
};