题目
麻将问题, 从1~9, 每个数字最多4个. 麻将已经按大小排序, 3个相同的为刻子, 连续三个数字为顺子, 两个相同的为对子, 在除去顺子和刻子后还剩一个对子即为胡牌, 输出yes, 否则输出no.
思路
递归. 先找出刻子, 然后递归. 找出顺子, 然后递归.
bool test(string str)
{
if (str.size() < 2 || str.size() > 15) return false;
if (str.size() == 2) return str[0] == str[1];
bool res = 0;
set<char> temp1;
set<char> temp2;
for (int i = 0;i < str.size()-2; i++) {
if (str[i] == str[i + 2]) {
// 刻子
temp1.insert(str[i]);
res |= test(str.substr(0,i)+str.substr(i+3));
if (res) return res;
}
if (str[i] == str[i+1]) {
continue;
}
if (str[i] +1 != str[i+1]) {
continue;
}
for (int j = 0;i < 4; j++) {
if (str[i] + 2 == str[i+2+j]) {
// 顺子
temp2.insert(str[i]);
string ss = "";
for (int k = 0; k< str.size();k++) {
if (k != i && k != i + 1 && k != i+2+j) {
ss += str[i];
}
}
res |= test(ss);
if (res) return res;
} else if (str[i] + 2 < str[i+2+j]) {
break;
}
}
}
return res;
}
总结
递归注意效率问题, 麻将有特殊性, 可以适当降低循环数.
