【上分日记】第378场周赛(分类讨论 + 分组循环 + 前缀和)

2024-01-03 14:02:18

前言

?这场周赛博主勉强算是写出了3道题,“勉强” 就在于 第3道题没在规定时间内写出来,但还是自己单独想
出来了,还算是有一点进步 ( hhh, 菜鸡勿喷 )。下面博主把这两道题再总结一下。

正文

1. 2982. 找出出现至少三次的最长特殊子字符串 II

  • 再多bb两句,这道题在做的时候因为数据量太大,暴力是做不出来的,博主先想到了分组循环,然后又想到了滑动窗口,接着又想到了堆,又开始观察分类讨论分析规律,最后时间不够了,做题的心路历程真是曲折的一批。

  • 题目思路:
  1. 我们先得对每一个连续的特殊子字符串,求长度,然后进行分组。
  1. 在实现过程中,当前一个字符与前一个字符不匹配时,当前的特殊字符串的长度就求完了,就可以扔到对应的组里面,这里我们以直接用unoredered_map进行求解,也可以用一个26个元素的vector进行求解, 然后接着循环。
  2. 分组时,我们还可以用一个小根堆进行优化,因为至少出现3次,且要取最长的长度,也就是在前3个最大的长度中求可以取3个特殊字符串的最长的长度,因此我们可以用一个3个元素的小根堆维护前3大个数即可。
  • 此处可能会出现堆中元素小于3个的情况,我们可以放两个0,来让其达到3个,进而方便求解。
  1. 每一组取出最长的前3个元素,进行分类讨论可以取得3个特殊字符串的最大长度。
  • 因为至少取得这3个特殊字符串的最大长度,只可能在这3个元素中出现,那么我们对这3个元素分别进行讨论即可。
  1. 设这3个元素分别为 n1(最长), n2(次长),n3(较长)
  2. 假设最长的是n3, 则一定能取到 3 个长度为 n3的 特殊子字符串。
  3. 假设最长的是n2, 则 n1 - n2 <= 1
  1. 如 果 n2 == n1, 则取 n2 - 1。
  2. 如果 n1 == n2 + 1, 则取 n2
  1. 假设最长的是n1,则 n1 - n2 >= 2, 则取 n1 - 2。
  • 取这些情况的最大值即可。
  • 理解方式:可以取长度为len的子串,进行滑动看能在n1,n2,n3中取几个。
  • 实现代码:
class Solution {
public:
    int maximumLength(string s) 
    {
          //将所有的相同的特殊子字符串都分组并进行划分,并求出其长度。
          unordered_map<char,priority_queue<int,vector<int>,greater<int>>> hash;
          int sz = s.size(),begin = 0;
          for(int i = 0; i <  sz; i++)
          {
              if(i + 1 == sz || s[i] != s[i + 1])
              {
                  int len = i + 1 - begin;
                  //维护一个堆为3的小根堆
                  if(hash[s[i]].size() < 3)
                  {
                    hash[s[i]].push(len);
                  }
                  else
                  {
                      //等于3时我们只需与堆顶元素进行比较如果大就入堆即可
                      int top = hash[s[i]].top(); hash[s[i]].pop();
                      //将最大值再入堆即可
                      hash[s[i]].push(max(top,len));
                  }
                  begin = i + 1;
              }
          }
          int ans = 0;
          for(int i = 'a'; i <= 'z'; i++)
          {
              //需要判断一下队列不为空
              if(!hash[i].empty())
              {
                //防止只有一个的情况
                if(hash[i].size() < 3)
                    hash[i].push(0);
                if(hash[i].size() < 3)
                    hash[i].push(0);
                int n3 = hash[i].top(); hash[i].pop();
                int n2 = hash[i].top(); hash[i].pop();
                int n1 = hash[i].top(); hash[i].pop();
                //对第三长的和第二长的以及第一长的取最长的字符串进行分类讨论。
                int len3 = n3;//一定能取到

                int len2 = 0;
                if(n1 == n2) // 相等取n2-1
                    len2 = n2 - 1;
                else if(n1 - n2 == 1) //差1取n2
                    len2 = n2;

                int len1 = 0;
                if(n1 - n2 >= 2)// 差2取 n1 - 2
                    len1 = n1 - 2;
                    
                int len = max(len3,max(len1,len2));
                ans = max(ans,len);
              }
          }         
          return ans == 0 ? -1 : ans;
    }
};

2.2983. 回文串重新排列查询


  • 题目大致思路:
  1. 因为要查询,且要将字符串分为两部分进行,然后再各取一部分排列组合,看是否能组成回文串。

  2. 因此我们直接将字符串分成两部分,然后再对第二部分逆转,这样就转换为了分别取字符串的一部分,取的一部分可以随意排列组合,看字符串之间能否互相转换。

  3. 我们可以将区间大致分为两部分,能进行排列的部分,和不能进行排列的部分。

  4. 能进行排列的部分看是否能转换为对应的字符串,不能转换的部分看是否相等即可。

  5. 我们可以使用前缀和,即对26种字符分别求前缀和,这样就可得到指定区间的字符个数,只要指定区间的字符个数都相等,则对应部分可以进行互相转换,反之则不能。 两个字符串都要求,因此有52个前缀和。

  6. 我们还可以使用前缀和,即判断两个原始字符串的每个字符串是否相等,如果相等就为0,不等就为1,并对此求前缀和,这样我们就可以快速判断某一段区间的字符串是否相等,即如果为0则相等,如果为1则不相等。 这里有1个前缀和,总共53个前缀和。

  7. 我们再进行分类讨论,对应的具体情况有6种,有3种可以互相转换,因此我们可以优化一下。具体情况请看实现代码,并建议画图分析。

  • 实现代码:
class Solution {
public:

    vector<bool> canMakePalindromeQueries(string s, vector<vector<int>>& queries) 
    {
        //1.预处理,方便对数据进行处理
        int len = s.size();
        string s1 =  s.substr(0,len / 2);
        string s2 =  s.substr(len / 2, len / 2);
        reverse(s2.begin(),s2.end()); 
        int len1 = s1.size(); 
        auto get_range = [&](int i)->pair<int,int>
        {
            int len2 = s2.size();
            int ci = queries[i][2],di = queries[i][3];
            int begin = len2 - 1 - (ci - len / 2);
            int end = len2 - 1 - (di - len / 2);
            return {min(begin,end), max(begin,end)};
        };
        /*
            1.细节:题目中给出长度一定为偶数,因此s1和s2的长度必然相等
            2.逆转是为了方便进行正向对比。
                注意:此时对于s[ci : di]在s2的下标会有所变化。
                未反转的s2:   ci-> ci - len / 2 , di->di - len / 2;
                翻转之后的s2: [ min{s2.size()-1 - ci , s2.size() - di},
                max{s2.size()-1 - ci, s2.size() - di} ];
                //对称的性质: x1 + x2 = s2.size() - 1;
        */
        //2.求出26 + 26 + 1个前缀和方便进行查询
        vector<vector<int>> ch1_que(26,vector<int>(len1 + 1,0)),ch2_que(ch1_que);
        for(int i = 0; i < 26; i++)
        {
            for(int j = 1; j <= len1; j++)
            {
                ch1_que[i][j] = s1[j-1] - 'a' == i ? ch1_que[i][j-1] + 1 : ch1_que[i][j-1];
                ch2_que[i][j] = s2[j-1] - 'a' == i ? ch2_que[i][j-1] + 1 : ch2_que[i][j-1];
            }
        }
        /*
           求出每一段对应的每种字母出现的次数,且只有26个小写字母,方便后面的大量查询。 
        */
        vector<int> dif(len1 + 1,0);
        for(int i = 1; i <= len1; i++)
        {
            dif[i] = s1[i-1] == s2[i-1] ? dif[i-1] : dif[i-1] + 1;                
        }
        /*
            异或前缀和:快速判断某段区间是否相等,如果相等就是可能构成回文串,因为我们已经对s2做了逆转。
            此处用于对不进行排列的区间的快速判断。
        */

        //3.分类进行讨论
        function<bool(int,int)> count = [&](int begin,int end)->bool
        {
            //[begin,end]
            for(int i = 0; i < 26; i++)
            {
                if(ch1_que[i][end + 1] - ch1_que[i][begin] !=
                 ch2_que[i][end + 1] - ch2_que[i][begin])
                {
                    return false;
                }
            }
            return true;
        };
        auto check = [&](int l1,int r1,int l2,int r2,string& s1,string& s2,\
        vector<vector<int>>& ch1_que,vector<vector<int>>&ch2_que)->bool
        {
            //保证l1 <= l2 会有3种情况。
            //先处理两边必然不相交的,因此先判断 [0,l1), [r2+1,len1)的字符串是否匹配。
            //细节:求的前缀和是不包含当前顶点的。
            int right = max(r1 + 1,r2 + 1);
            if(dif[l1] || (dif[len1] - dif[right]))
            {
                return false;
            }
            //先处理不相交的情况
            if(l2 > r1)
            {
                //先判断中间[r1 + 1,l2)的字符串是否匹配.
                if(dif[l2] - dif[r1 + 1])
                {
                    return false;
                }
                //计算s1[l1,r1]的种类个数能否与s2[l1,r1]的种类个数匹配
                if(count(l1,r1) && count(l2,r2))
                {
                    return true;
                }
                return false;
            }
            //再处理包含的情况
            if(r1 >= r2)
            {
                if(count(l1,r1))
                {
                    return true;
                }
                return false;
            }
            //最后处理相交但不包含的情况
            if(r1 >= l2)
            {
                //1. 先让[l1,r1]去匹配[l1,l2]
                int tmp1[26] = {0};
                for(int i = 0; i < 26; i++)
                {
                    int sub = ch1_que[i][r1 + 1] - ch1_que[i][l1] - 
                    (ch2_que[i][l2] - ch2_que[i][l1]);
                    if(sub < 0) return false;
                    else 
                    {
                        tmp1[i] = sub;
                    }
                }
                //2. 再让[l2,r2] 去匹配[r1 + 1,r2]
                int tmp2[26] = {0};
                for(int i = 0; i < 26; i++)
                {
                    int sub = ch2_que[i][r2 + 1] - ch2_que[i][l2] - 
                    (ch1_que[i][r2 + 1] - ch1_que[i][r1 + 1]);
                    if(sub < 0) return false;
                    else
                    {
                        tmp2[i] = sub;
                    }
                }
                //最后看[l2,r1] 即tmp1 和 tmp2 是否匹配
                for(int i = 0; i < 26; i++)
                {
                    if(tmp1[i] != tmp2[i])
                        return false;
                }
            }
            return true;
        };
        int qsz = queries.size();
        vector<bool> ans(qsz);
        for(int i = 0; i < qsz; i++)
        {
            int l1 = queries[i][0];
            int r1 = queries[i][1];
            pair<int,int> ret = get_range(i);
            int l2 = ret.first;
            int r2 = ret.second;
            //这一步很关键,可以将6种情况转换为3种情况。
            ans[i] = l1 <= l2 ? check(l1,r1,l2,r2,s1,s2,ch1_que,ch2_que) 
            : check(l2,r2,l1,r1,s2,s1,ch2_que,ch1_que);
        }
        return ans;
    }
};
  • 说明:本题的思路参考灵神的思路实现,详细内容可见灵神在b站的周赛回放视频。

总结

  1. 第一题,用unordered_map 或者 vector 可以将特殊字符串的所有长度进行分组,然后对其进行分类讨论,对3种情况进行讨论即可。(哈希分组循环 + 分类讨论 + priority_queue小优化——感觉优化了个寂寞)
  2. 第二题,可以说是将前缀和用的淋漓尽致,从而可以快速的判断是否可以组成回文串,且如果有重复的对称的情况,这里将6种情况转换为3种情况,从而减少代码量。(53个前缀和 + 问题转换 + 分类讨论)

尾序

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

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