美团--字符串计数
美團–字符串計數
文章目錄
- 美團--字符串計數
- 一、題目描述
- 二、分析
- 三、代碼
一、題目描述
二、分析
- 做題之前我們需要明白什么是字典序,就以題目中的事例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以及之后的位置隨意取，以此類推，直到算到klen2-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],后面的位置隨意取，以此類推，直到算到klen2-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;elsesum += str2[k] - str1[k];}elsesum += ((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; }總結
