算法作业1-2 字典序问题

题目 字典序问题

分析

分析题意，其实就是求排在 s (输入的字符串)之前的字符串个数+1，
将排在 s 之前的字符串分成两类：（假设字符串 s 长度为k）

1. 第一类：长度为1 ~ k-1的所有字符串。
   （eg: a ~ z 、 ab ~ yz 、 abc ~xyz 、 abcd ~ wxyz…)
2. 第二类：长度为 k 且排在 s 之前的字符串。

实现思路

第一类字符串：

由以下代码的函数f1() f2()实现:

1. f1(int x,int k)
   功能：计算以 x （序号）为首字母，字符串长度为k的情况数目。
   实现思路：for 循环和递归
   （1）赋给位置1 为字母 x+1 ~ 26之间挑选
   （2）赋给位置2 为字母 位置1字母+1~26中挑选
   （3）…
2. f2(int k)
   功能：计算长度为 k 的字符串的所有情况
   实现思路：for 循环+ f1()
   计算以字母1~26为首字母的长度为 k 的所有字符串的情况

第二类字符串：

由f3()和solve()中的部分代码实现：
功能：计算长度为 k 且排在 s 之前的字符串。
实现思路：暴力举例所有的情况：
如果某字符串在 s 之前，说明从左到右开始扫描的时候，某位置的字符比 s 在该对应位置的字符 小， 这个“某位置”可以是第一位也可以是最后一位，因此需要在下面的代码外面套一个 for 循环，
那么暴力举例的时候的思路就是：该位置的字符∈（s 前一个位置的字符， s 该位置的字符 ），而该位置的字符确定后，后面位置的字符的选择等价于求以该位置为首字符的字符串长度一定的情况，即可以直接使用函数f1()。

AC代码

#include
#include
using namespace std;

string s;
int f1(int x,int k) { //计算以x为首字母（序号），字符串长度为k的情况数目
	int sum=0;
	if(k==1)
		return 1;
	for(int i=x+1; i<=26; i++) {
		sum+=f1(i,k-1);
	}
	return sum;
}

int f2(int k) { //计算长度为k的字符串的所有情况
	int sum=0;
	for(int i=1; i<=26; i++) {
		sum+=f1(i,k);
	}
	return sum;
}

int f3(int m,int n,int k) { //计算长度为k 且在m-n之前
	int sum=0;
	for(int i=m; i<n; i++) {
		sum+=f1(i,k);//计算以i为首字母（序号），字符串长度为k的情况数目
	}
	return sum;
}
void solve() {
	int sum=0;
	int len=s.length();

	for(int i=1; i<len; i++) { //计算长度为第一种思路的字符串个数,长度为len,abcdefg之前的所有情况 
		sum+=f2(i);
	} 
	int m=1;
	int len2=len;
	for(int i=0; i<len; i++) {
		if(i==0)
		sum+=f3(1,s[i]-'a'+1,len2);//首字符 属于[a,a[i])
		else{
			m=s[i-1]-'a'+1;
		sum+=f3(m+1,s[i]-'a'+1,len2);}//在位置i的字符的可能范围为[a[i-1]+1,a[i])
		len2--;
	}
	cout<<sum+1<<"\n";
}
int main() {
	int k;
	cin>>k;
	while(k--) {
		cin>>s;
		solve() ;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57