字节跳动—雀魂启动wolfGuiDao的博客-

字节跳动—雀魂启动

一、题目描述

小包最近迷上了一款叫做雀魂的麻将游戏，但是这个游戏规则太复杂，小包玩了几个月了还是输多赢少。
于是生气的小包根据游戏简化了一下规则发明了一种新的麻将，只留下一种花色，并且去除了一些特殊和牌方式（例如七对子等），具体的规则如下：

• 总共有36张牌，每张牌是1~9。每个数字4张牌。
• 你手里有其中的14张牌，如果这14张牌满足如下条件，即算作和牌
• 14张牌中有2张相同数字的牌，称为雀头。
• 除去上述2张牌，剩下12张牌可以组成4个顺子或刻子。顺子的意思是递增的连续3个数字牌（例如234,567等），刻子的意思是相同数字的3个数字牌（例如111,777）

例如：

1 1 1 2 2 2 6 6 6 7 7 7 9 9 可以组成1,2,6,7的4个刻子和9的雀头，可以和牌 1 1 1 1 2 2 3 3 5 6 7 7 8 9 用1做雀头，组123,123,567,789的四个顺子，可以和牌 1 1 1 2 2 2 3 3 3 5 6 7 7 9 无论用1 2 3 7哪个做雀头，都无法组成和牌的条件。 

现在，小包从36张牌中抽取了13张牌，他想知道在剩下的23张牌中，再取一张牌，取到哪几种数字牌可以和牌。

输入描述:

输入只有一行，包含13个数字，用空格分隔，每个数字在1~9之间，数据保证同种数字最 多出现4次。 

输出描述:

输出同样是一行，包含1个或以上的数字。代表他再取到哪些牌可以和牌。若满足条件的有 多种牌，请按从小到大的顺序输出。若没有满足条件的牌，请输出一个数字0 

输入例子1:

1 1 1 2 2 2 5 5 5 6 6 6 9 

输出例子1:

9 

例子说明1:

可以组成1,2,6,7的4个刻子和9的雀头 

输入例子2:

1 1 1 1 2 2 3 3 5 6 7 8 9 

输出例子2:

4 7 

例子说明2:

用1做雀头，组123,123,567或456,789的四个顺子 

输入例子3:

1 1 1 2 2 2 3 3 3 5 7 7 9 

输出例子3:

0 

例子说明3:

来任何牌都无法和牌 

二、分析

• 首先清楚和牌的条件：1.两张相同的牌组成雀头。2.剩下的牌组成刻子或顺子
• 现在你有13张牌，在剩下的牌中选一张尽可能使手中的牌变成和牌
• 我们既然不知道怎么选择，那么就从1到9枚举所有的可能，记录结果即可

 for(int i = 1;i <= 9;++i) { if(hupai(num,i)) //判断是否可以和牌             ans.push_back(i);//加入结果集 } 

• 现在你拿到14张牌，关键是怎么判断和牌：
• 在判断和牌之前先进行一次过滤：因为在枚举1- – -9中的牌时，可能原本手中的13张牌出现了4张同样数字的牌，在进行枚举时，就会出现同样数字的牌有5张，所以需要过滤

//num是原本牌的集合，x是枚举的牌 inline bool hupai(vector<int> num,int x) { //过滤 if(count(num.begin(),num.end(),x) == 4) return false; //放到牌的集合当中     num.push_back(x); //进行一次排序 sort(num.begin(),num.end()); //进行判断 return ishu(num); } 

• 接下来主要实现ishu，来判断是否是和牌；

inline bool ishu(vector<int>num) { if(num.empty()) return true; int count0 = 0; //统计牌集合中第一张牌上数字在整个牌集合中出现的次数count0     count0 = count(num.begin(),num.end(),num[0]); //雀头  //num.size()%3 != 0是用来判断一旦选了雀头下次就不能选了 //因为牌共有14张，要么去掉雀头两张剩12张（12 % 3 == 0） //要么去掉顺子或刻子3张还剩11张（11 % 3 ！= 0） //count0 >= 2是用来判断第一张牌数量是否大于等于2（雀头是2张） if(num.size()%3 != 0 && count0 >= 2) { //去掉雀头的两张相同的牌继续递归判断         vector<int> newnum(num.begin() + 2,num.end()); if(ishu(newnum)) return true; } //刻子 //第一张牌的数量大于等于3张才有可能是刻子  if(count0 >= 3) { //去掉刻子的3张相同的牌继续判断         vector<int> newnum(num.begin()+3,num.end()); if(ishu(newnum)) return true; } //顺子  //注意走到这里并不代表count0 == 1,（牌面是1---9，所以可以直接进行+1来判断） //如果下一张牌和下下一张牌的数量出现的次数超过一，那么这种情况是有可能构成顺子的 if(count(num.begin(),num.end(),num[0] + 1) > 0 && count(num.begin(),num.end(),num[0] + 2) > 0) { //找到构成顺子的3张牌，删掉继续判断         vector<int> newnum(num.begin() + 1,num.end());         newnum.erase(find(newnum.begin(),newnum.end(),num[0] + 1));         newnum.erase(find(newnum.begin(),newnum.end(),num[0] + 2)); if(ishu(newnum)) return true; } return false; } 

三、完整代码

代码一：

#include<bits/stdc++.h> using namespace std; typedef long long ll; inline bool ishu(vector<int>num) { if(num.empty()) return true; int count0 = 0; //统计牌集合中第一张牌上数字在整个牌集合中出现的次数count0     count0 = count(num.begin(),num.end(),num[0]); //雀头  //num.size()%3 != 0是用来判断一旦选了雀头下次就不能选了 //因为牌共有14张，要么去掉雀头两张剩12张（12 % 3 == 0） //要么去掉顺子或刻子3张还剩11张（11 % 3 ！= 0） //count0 >= 2是用来判断第一张牌数量是否大于等于2（雀头是2张） if(num.size()%3 != 0 && count0 >= 2) { //去掉雀头的两张相同的牌继续递归判断         vector<int> newnum(num.begin() + 2,num.end()); if(ishu(newnum)) return true; } //刻子 //第一张牌的数量大于等于3张才有可能是刻子  if(count0 >= 3) { //去掉刻子的3张相同的牌继续判断         vector<int> newnum(num.begin()+3,num.end()); if(ishu(newnum)) return true; } //顺子  //注意走到这里并不代表count0 == 1,（牌面是1---9，所以可以直接进行+1来判断） //如果下一张牌和下下一张牌的数量出现的次数超过一，那么这种情况是有可能构成顺子的 if(count(num.begin(),num.end(),num[0] + 1) > 0 && count(num.begin(),num.end(),num[0] + 2) > 0) { //找到构成顺子的3张牌，删掉继续判断         vector<int> newnum(num.begin() + 1,num.end());         newnum.erase(find(newnum.begin(),newnum.end(),num[0] + 1));         newnum.erase(find(newnum.begin(),newnum.end(),num[0] + 2)); if(ishu(newnum)) return true; } return false; } //num是原本牌的集合，x是枚举的牌 inline bool hupai(vector<int> num,int x) { //过滤 if(count(num.begin(),num.end(),x) == 4) return false; //放到牌的集合当中     num.push_back(x); //进行一次排序 sort(num.begin(),num.end()); //进行判断 return ishu(num); } int main() {     vector<int> num(13),ans; for(int i = 0;i < 13;++i) {         cin>>num[i]; } for(int i = 1;i <= 9;++i) { if(hupai(num,i))              ans.push_back(i); } if(ans.size() == 0) puts("0"); else { for(int i = 0;i < ans.size();++i)             cout<<ans[i]<<" "; } return 0; } 

代码二：

#include<iostream> #include<map> #include<vector> using namespace std; bool isHu(map<int, int> mp, int num) { if(num <= 0) return true; while(mp[mp.begin()->first] == 0)      mp.erase(mp.begin());          map<int, int>::iterator it = mp.begin(); if(num % 3 != 0 && (it->second) >= 2) {         mp[it->first] -= 2; if(isHu(mp, num - 2)) return true;         mp[it->first] += 2; } if((it->second) >= 3) {         mp[it->first] -= 3; if(isHu(mp, num - 3)) return true;         mp[it->first] += 3; } if((it->second) > 0 && mp[(it->first) + 1] > 0 && mp[(it->first) + 2] > 0) {         mp[it->first]--;         mp[(it->first) + 1]--;         mp[(it->first) + 2]--; if(isHu(mp, num - 3)) return true;         mp[(it->first)]++;         mp[(it->first) + 1]++;         mp[(it->first) + 2]++; } return false; } int main() {     map<int, int> mp; int tmp; for(int i = 0;i < 13;i++) {         cin>>tmp;         mp[tmp]++; }          vector<int> ans; for(int i = 1;i < 10;i++) { if(mp[i] < 4) { ++mp[i]; if(isHu(mp, 14))                 ans.push_back(i); --mp[i]; } } if(ans.empty())      cout<<0<<endl; else { for(int i:ans)          cout<<i<<' '; } return 0; } 

两种代码 的思路一样，只不过第二个代码更好的体现回溯的思想