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

发布时间:2024年01月16日

前言

?本场周赛,博主也只写出两道题(前两道, 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 的最大数字

  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 的个数

  1. 位运算 + 分类讨论
    在这里插入图片描述
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 / 2x-1 - 1) / 2 == k,解出上界,取一个大于 num 的即可。当然如果不想这样写,也可以直接枚举最大值作为上界。

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

  • 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;
    }
};
  1. 二分,也是固定 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算法 的线性复杂度值得探索。

尾序

我是舜华,期待与你的下一次相遇!

文章来源:https://blog.csdn.net/Shun_Hua/article/details/135597683
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。