2018网易校招运营开发工程师编程第一题

由于之前准备不充分，没有做大量的编程练习，在实际编程过程中算法设计出现疏漏，最终导致结果没有AC。

题目很简单，字符串编码问题。 一个长度不超过6的字符串，内部不会重复且所有字母已经按照字典序排好。接下来按照字典序从短到长对这些字符串进行编码，接下来让你输入一个字符串，输出对应的编码即可。 eg: a为1，z为26，ab为27，az为51，bc为52。。。

思路和之前在牛客网做过的编码题类似，跳过某些的字符串，直到定位到该字符串为止。

举个例子：

字符串为forx。它跳过了所有的长度为1，长度为2，长度为3的字符串，以及所有长度为4的字符串中ae开头的，fgfn开头的，fop~foq开头的字符串。最后检查从fors到forx的序号就行了。

刚开始思路出了点问题，跳过的过程中，我跳过了fa~fn这类包括了fa但是不可能出现的情况，结果导致最后的算法出来的结果并不如意，并且一直很异常。直到笔试结束，我也没及时跳出这个坑。

笔试结束后我重新审查我的算法才发现了这个bug，并最终解决。最终的代码如下：

#include <iostream>
using namespace std;
int C_a_b(int a, int b){
	if(b == 0) return 0;
	int result = 1, num = a;
	while(num>(a-b))
		result *= num--;

	num = b;

	while(num>0) result /= num--;
	return result;
}
int main()
{
	int N, len, number = 0;
	string input_str;
	cin >> N;
	while(N--){
		number = 0;
		cin >> input_str;
		len = input_str.length();

		if(len == 1){
			cout << input_str[0] -'a' + 1 << endl;
			continue;
		}
		
		// 跳过所有长度小于该字符串的数目
		for(int i = 1; i<len; ++i){
			number += C_a_b(26, i);
		}

		// 逐次跳过，eg：forx，首先跳过a开头的到e开头的所有长度为4的字符串（C_25_3累加到C_21_3）
		// 然后跳过fg开头到fn的所有长度为3的字符串（C_19_2累加到C_12_2）
		// 然后跳过fop到foq（C_10_1累加到C_9）
		for(int i = len-1, j = 25; i>0; --i){
			for(; j != 'z' - input_str[len-i-1]; j--){
				number += C_a_b(j, i);
			}
			j--;
		}
		// 将最后一位的值算出来。eg：forx，则先算出从fors开始计数到forx时，对应的值
		number += (input_str[len-1] - input_str[len-2]);

		cout << number << endl;
	}
}

目测应该没够ac。特殊测试样例为a，z，ab，az，bc（和前面样例差一），bz，yz，abc（和前面样例差一），abz，acd（和前面样例差一）

Donate