題目
麻將問題, 從1~9, 每個(gè)數(shù)字最多4個(gè). 麻將已經(jīng)按大小排序, 3個(gè)相同的為刻子, 連續(xù)三個(gè)數(shù)字為順子, 兩個(gè)相同的為對(duì)子, 在除去順子和刻子后還剩一個(gè)對(duì)子即為胡牌, 輸出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;
}
總結(jié)
遞歸注意效率問題, 麻將有特殊性, 可以適當(dāng)降低循環(huán)數(shù).
