17年商汤笔试题

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <set>
using namespace std;
           

/*
* 编码规则是a-z 对应1-26
* 输入一个字符串
* 输出可能的解码方案
* sample input 12
* sample output 2
* note : a(1)b(2) or l(12)
* explantion: 采用递归方法，对当前串的解码方案，由第一个字母的解码方式 和后面串
* 总的解码方案个数决定
* 若第一个字母只有一种解码方式，则总的解码方案书等于除去第一个字符的子串解码方案
* 若第一个字母有多种解码方式，则总的解码方案数等于每种解码方式后除去第一个字符的子串解码方案 之和
* 在这个例子中第一个字母最多有两种解码方式（由第一个字符代表的数字解码，或者由前两个字符代表的数字解码）
**/

int num_decode_recursive(string str){
	set<int> alpha ={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};
	if(str.length() <= 1){
		return 1;
	}
	else{
			int code = 10*(str[0]-'0') + (str[1]-'0');
			if (code == 0) return 0;
			if( alpha.find(code) != alpha.end()){
					if( (str[1] - '0') != 0){
						int num1 = num_decode_recursive(str.substr(1));
						int num2 = num_decode_recursive(str.substr(2));
						if(num1 == 0 || num2 == 0)
							return 0;
						else
							return num1+num2;
					}
					else
						return num_decode_recursive(str.substr(2));
			}
			else{
				return num_decode_recursive(str.substr(1));
			}

	}
}

/* 非递归实现方式*/

int num_decode(string str){
	//num[i] 表示str[0]--str[i] 可能的解码方案数
	int num[str.length()] = {1};
	//第一个数字不为0，否则无法解码，方案数为0 
	if( str.length() < 1 || str[0] == '0')
		return 0;
	for(unsigned int i = 1 ; i < str.length(); ++i){ 
		//多一个数字的情况下编码方案的变化取决于多的数字与前一位数字组合是否是一个字符编码
		int code = 10*(str[i-1]-'0') + (str[i]-'0');

		if(str[i] != '0' && str[i-1] != '0' && code < 27)
			num[i] = num[i-1]+num[i-2];
		// 前一位是0或者该位是0 或者两位组成的数大于26
		// 都不能组成新的编码，则方案数等于str[0]--str[i-1]
		// 的解码方案数
		else if(str[i] == '0' && str[i-1] == '0')// 连续两位为0 ，出错，无法解码
			return 0;
		else
			num[i] = num[i-1];
	}
	return num[str.length()-1];
}
int main(){
	//cout<<num_decode("31717126241541717")<<endl;
	//cout<<num_decode_recursive("31717126241541717")<<endl;
	//cout<<num_decode("1003");
	//cout<<num_decode_recursive("1003");
           

}