【上分日记】第380场周赛（数位dp+ KMP + 位运算 + 二分 + 双指针 ）

前言

?本场周赛，博主也只写出两道题(前两道, hhh菜鸡勿喷)，第三道涉及位运算 ，数位dp，第四道涉及KMP。 下面我们来总结一下这四道题。

正文

1.3005. 最大频率元素计数

?这道题不难，不过有一个比较妙的写法，因此还是来分析总结一下。

• 题目链接: 最大频率元素计数
• 题目思路：

1. 用一个unordered_map更新次数。
2. 更新出最大次数时，也更新ans的初始值。
3. 当等于最大次数时，对ans 加上 当前最大次数。

• 关键：最大次数的出现是呈现递增趋势的.
• 因此我们可以一边记录unordered_map, 一边更新最大次数和answer。并且一个循环就可以更新出结果。

class Solution {
public:
    int maxFrequencyElements(vector<int>& nums) 
    {
        int max_cnt = 0;
        int ans = 0;
        unordered_map<int,int> hash;
        for(auto e : nums)
        {
            if(++hash[e] > max_cnt)
                max_cnt = ans = hash[e];
            else if(hash[e] == max_cnt)
                ans += max_cnt;
        }
        return ans;   
    }
};

2.3007.价值和小于等于 K 的最大数字

• 题目链接：价值和小于等于 K 的最大数字

• 题目大思路：【数位dp】 / 【分类讨论 + 数学分析】 + 二分

1. 数位dp

1. 从高位开始枚举，一直枚举到最低位。
2. 下一位的枚举的数字范围收到上一位的约束。
3. 对不受到上一位约束的，采取记忆化的策略。受到上一位约束的，只有一种情况，无需记忆化。

• 实现代码:

class Solution {
public:
    long long findMaximumNumber(long long k, int x) 
    {
         //数位dp
        auto check = [&](long long num)
        {
            //找其中为1 - num 上 x 的整数倍上 为 1的个数。
            //1.先将num转换为二进制数,到最高位即可。
            string s;
            for(int i = 0; i < 64; i++)
            {
                if(num & (1ll << (63 - i)))
                    s += "1";
                else
                    s += "0";
            }
            long long dp[64][64];
            memset(dp,-1ll,sizeof(dp));
	       /*
		       其中dp表示为枚举第 i 位，之前之前已经有j个1时，数字出现1的总数
		       1.limit表示第i位是否收到约束,即只能枚举 0 ~ s[i] - '0'，
		        如果收到，下一位也要收到约束，否则可以枚举 0 ~ 9
		       2.如果枚举第i位没收到约束，且之前j个1已经求过，则无需再求，
		       即记忆化。反之，只会出现一次，没必要记忆化，当然记忆化也可以。
	       */
            function<long long(int,int,bool)> dfs = [&](int i ,\
            long long j,bool limit)
            {
                if(i == 64) return j;
                else if(!limit && dp[i][j] != -1) return dp[i][j];

                long long res = 0;
                int end = limit ? s[i] - '0' : 1;
                for(int m = 0;  m <= end; m++)
                {
                    res += dfs(i+1,j + (m == 1 && (64 - i) % x == 0),\
                    limit && (m == end));
                 /*
	                m == 1 且是x的倍数成立，结果位 j + 1，反之为 j
	                如果当前位受到限制，且枚举之后的n也达到了end，则下一位
	                受到限制。
                */
                }
                if(!limit) dp[i][j] = res;

                return res;
            };
            return dfs(0,0,true);
        };
        //二分
        long long left = 0,right = k << x;
        //找靠近右边最大的num,因此要固定右边枚举左边。
        while(left < right)
        {
            long long mid = (left + right + 1) / 2;
            if(check(mid) > k)
                right = mid - 1;
            else
                left = mid;
        }
        //必然会有答案。
        return left;
    }
};

说明：模版题——233. 数字 1 的个数

2. 位运算 + 分类讨论
   

class Solution {
public:
    long long findMaximumNumber(long long k, int x) 
    {
         //位运算 + 分类讨论
        auto check = [&](long long num)
        {
            long long ans = 0;
            int cnt = x - 1;
            for(long long i = num >> cnt; i; cnt += x,i >>= x)
            {
                ans += (i / 2) << cnt;
                if(i % 2)
                {
                    long long mask = (1ll << cnt) - 1;
                    ans += (num & mask) + 1;
                }
            }
            return ans;
        };
        //二分
        long long left = 0,right = k << x;
        //找靠近右边最大的num,因此要固定右边枚举左边。
        while(left < right)
        {
            long long mid = (left + right + 1) / 2;
            if(check(mid) > k)
                right = mid - 1;
            else
                left = mid;
        }
        //必然会有答案。
        return left;
    }
};

• 补充一点：这里的right 是 最多 num 能取到的数，设为上界，具体分析跟位运算的分析雷同，看奇数位且只看最低位，即 (num / 2^x-1 - 1) / 2 == k，解出上界，取一个大于 num 的即可。当然如果不想这样写，也可以直接枚举最大值作为上界。

3.3008. 找出数组中的美丽下标 II

• 题目链接:找出数组中的美丽下标 II

• 题目大思路：KMP + 【二分】/ 【双指针】

• 前置知识 ——【数据结构与算法】KMP算法

• KMP模版

vector<int> kmp(string& text,string& pattern)
{
    //求next数组
    int tsz = text.size(),psz = pattern.size();
    vector<int> next(psz);
    int index = 0;
    for(int i = 1; i < psz; i++)
    {
        char ch = pattern[i];
        while(index && ch != pattern[index])
        {
            //进行回退找最长匹配串与之匹配
            index = next[index-1];
        }
        if(ch == pattern[index])
            index++;
        next[i] = index;
    }
    vector<int> ans;
    //求子串的起始位置。
    index = 0;
    for(int i = 0; i < tsz; i++)
    {
        char ch = text[i];
        while(index && ch != pattern[index])
        {
            index = next[index-1];
        }
        if(ch == pattern[index])
            index++;
        
        if(index == psz)
        {
            //说明找到子串了,记录下标并进行回退
            ans.push_back(i + 1 - psz);
            index = next[index - 1];
        }
    }
    return ans;
};

1. 双指针，因为要找 |j - i| <= k 的，所以我们固定 i，找符合满足的 j 即可, 可以让j追i，当 j < i - k, 就让k++, 追上 i 或者 超过i 就停下。

• 实现代码：

class Solution {
public:
    vector<int> beautifulIndices(string s, string a, string b, int k) 
    {
       
        vector<int> res;
        vector<int> pos_a = kmp(s,a);
        vector<int> pos_b = kmp(s,b);
        int asz = pos_a.size(),bsz = pos_b.size();
        int j = 0;
        for(int i = 0; i < asz; i++)
        {
            //让 j 追 i 且满足pos_b[j] < pos_a[i] - k, 就去追
            while(j < bsz && pos_b[j] + k < pos_a[i])
                j++;

            // 追上了，且满足情况
            if(j < bsz && abs(pos_a[i] - pos_b[j]) <= k)
                res.push_back(pos_a[i]);
        }
        return res;
    }
};

2. 二分，也是固定 i , 二分找 j，因为pos_b存的是下标是递增的，因此可以二分找，我们可以找 大于等于 pos_a[ i ] 的第一个pos_b[ j ]，pos_b[j - 1]可能是靠近pos_a[i]的其左边最近的那一个，对这两种情况进行讨论即可。

• 实现代码：

   vector<int> beautifulIndices(string s, string a, string b, int k) 
   {
      
       vector<int> res;
       vector<int> pos_a = kmp(s,a);
       vector<int> pos_b = kmp(s,b);
       int asz = pos_a.size(),bsz = pos_b.size();
       for(int i = 0; i < asz; i++)
       {
           //二分找左边那个j  >= i 的最靠近的元素
           int left = 0,right = bsz - 1;
           while(left <  right)
           {
               int mid = (left + right - 1) / 2;
               if(pos_b[mid] < pos_a[i])
                   left = mid + 1;
               else
                   right = mid;
           }
           if(right >= 0 && pos_b[right] >= pos_a[i])
           {
               left = right - 1;
           }
           else
           {
               left = bsz == 0 ? -1 : right;
               right = bsz;
           }
           if( right < bsz && pos_b[right] - pos_a[i] <= k 
           || left >= 0 && pos_a[i] - pos_b[left] <= k)
           {
               res.push_back(pos_a[i]);
           } 
       }
       return res;
   }
};

• 这里的二分，要对结果判断一下是否有效，且这里 left是 pos_b 左边最靠近 pos_a[i ] 的，right 是 pos_b右边最靠近 pos_a[i]的。
• 推荐双指针的写法。

总结

1. 第一道题的一种遍历写法值得品味一番。
2. 第二道题的数位dp + 位运算 需要认真思考。
3. 第三道题的KMP算法 的线性复杂度值得探索。

尾序

我是舜华，期待与你的下一次相遇！