标签搜索

目 录CONTENT

文章目录

美团--字符串计数.md

小小城
2021-08-22 / 0 评论 / 0 点赞 / 2 阅读 / 2,238 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-05-02,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

美团--字符串计数

@[toc]

一、题目描述

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

二、分析

  •  做题之前我们需要明白什么是字典序,就以题目中的事例1来说,字典序在ab和ce之间并且满足长度在1到2之间的所有字符串的个数

首先,ab的下一个字典序是什么?是aba,abb,abc.....但是发现长度不满足;
所以ab真正的下一个字典序是ac,同样对于aca,acb,....也是不满足情况的,所以ac的下一个字典序是ad,ae,....az(24);
同理az的下一个字典序是b,ba,bb,bc,...bz(27);
bz的下一个字典序是c,ca,cb,cc,cd(5)
所以ab和ce之间的
题意:ab ce : 1 - 2
ac ad ... az : 24
b ba bb ... bz : 27
c ca cb cc cd : 5

  •  现在明确了字典序,根据上面对用例对分析,说明题意中只有小写字母,现在假设其中一个为 str1 = cpqejrrgp, str2 = cpqejtrdg,len1 = 9, len2 = 9,设所求满足情况的字符串代号为 str
  •  第一步:首先找到两个字符串相对应位置的第一个不相等的位置,即若ab 和 ce,第一个相对位置不相等的为值就是下标为0的地方 a 和 c 不一样,str1和str2中第一个相对不相等的位置是下标为5的地方,即 r 和 t,设下标为k
  •  第二步先求在此下标处,字符处于下标位置字符之间的情况,即str[k]>str1[k] && str[k]<str2[k]的情况,这个最好算,只要k位置大于str1小于str2对应的k位置,后面的任一位置可以随意取,每个位置有26种
  •  例如str1[5]和str2[5]之间共有num1种(‘t’-'r'-1=1种即为's'这一种情况),str[5]为s的时候,后面三位可以随意取;共有(str2[k] - str1[k] - 1)*pow(26, i - k)种,
    其中i为len1到len2之间的取值,这里用一个for循环累加;
  •  第三步:其次再求str[k]==str1[k]时有多少种,此时,str[k+1]需大于str1[k+1],k+2位,k+3位...可以随意取,接着str[k]==str1[k]&&str[k+1]==str1[k+1]的情况,需str[k+2]大于str1[k+2],k+3以及之后的位置随意取,以此类推,直到算到k==len2-1的位置为止;
  •  第四步:最后求str[k]==str2[k]的情况,此时,str[k+1]需要小于str2[k+1],k+2,k+3等之后的位置随意取,接着再求str[k]==str2[k]&&str[k+1]==str2[k+1]的情况,需要str[k+2]小于str2[k+2],后面的位置随意取,以此类推,直到算到k==len2-1的位置为止;
  •  第五步:把所有情况相加,注意还有几处边界位置需要处理,具体参考以下代码

三、代码

#include<iostream>
#include<string>
#include<math.h>
using namespace std;

const int mod = 1000007;

int main()
{
    string str1,str2;
    int len1,len2;
    while(cin>>str1>>str2>>len1>>len2)
    {
    	 //补全str1为满足题意的开始字典序
         if(str1.length() < len2)
             str1.append(len2 - str1.length(),'a');
          
          //补全str2为满足题意的结束字典序
          if(str2.length() < len2)
              str2.append(len2 - str2.length(),'z');

		  //保存结果
          int sum = 0;

		  //标记第一个不想等的位置
          int k = 0;
          
          //第一步,找第一个相对位置不相等的位置下标
          while(str1[k] == str2[k])
          {
                k++;
          }

		  //第一种情况,字符介于str1和str2之间
          if(str1[k] < str2[k] && len1 <= len2)
          {
                //第二步,计算str[k]>str1[k] && str[k]<str2[k]的情况
                for(int i = len1 - 1;i < len2;i++)
                {
                     if(i == k)
                     {
                         if(k == len1 - 1 && k == len2 - 1)
                              sum += str2[k] - str1[k] - 1;
                         else
                              sum += str2[k] - str1[k];
                     }
                     else
                            sum += ((str2[k] - str1[k] - 1)*(int)pow(26,i - k)) % mod;
                }
                k++;
                
                //第三步,计算str[k]==str1[k]时的情况和str[k]==str2[k]的情况
                for(int i = len1;i <= len2;i++)
                {  
                	for(int j = k;j < i;j++)
                        sum += (('z' - str1[j]) * (int)pow(26,i - j - 1)) % mod;
                    
                    for(int j = k;j < i;j++)
                        sum += ((str2[j] - 'a') * (int)pow(26,i - j - 1)) % mod;
                }
          }
          cout << sum % mod << endl;
    }
    return 0;
}
0

评论区