惠济免费网站建设,58同城泰安,搜索网站排行,中国农村建设投资有限公司网站题目链接#xff1a;雀魂启动#xff01;_牛客题霸_牛客网
题解#xff1a; 回溯法 1、用哈希思想构建映射表#xff0c;标记已有的卡的种类和个数 2、遍历卡池#xff0c;先从卡池中抽一张卡#xff0c;因为只能抽一张卡#xff0c;所以一种卡只判断一次 3、抽到卡后找…题目链接雀魂启动_牛客题霸_牛客网
题解 回溯法 1、用哈希思想构建映射表标记已有的卡的种类和个数 2、遍历卡池先从卡池中抽一张卡因为只能抽一张卡所以一种卡只判断一次 3、抽到卡后找雀头 -- 遍历已有卡使用穷举法如果手中有一种卡的数量达到两张选其作为雀头 4、找到雀头后找顺子和刻子 -- 再次遍历已有卡如果手中有一种卡的数量达到三张选其作为刻子如果有三种卡是连号选其作为顺子 5、如果全部配对完后手里的卡没了那么恭喜你和牌如果手中还有牌剩余那就回溯重新找 有很多细节思路中没提到代码中都有注释求一个赞
#include algorithm
#include iostream
#include vector
using namespace std;vectorint res;bool is_valid(vectorint cards) {//继续穷举for (int i 1; i 9; i) {//先找顺子if (cards[i] 3) {cards[i] - 3;//递归如果剩余的牌能够和牌返回true//递归如果剩余的牌能够和牌返回trueif (is_valid(cards)) {//回溯cards[i] 3;return true;}//回溯cards[i] 3;}//再找刻子if (i 7 cards[i] 0 cards[i 1] 0 cards[i 2] 0) {cards[i]--;cards[i 1]--;cards[i 2]--;//递归如果剩余的牌能够和牌返回trueif (is_valid(cards)) { //回溯cards[i];cards[i 1];cards[i 2];return true; }//回溯cards[i];cards[i 1];cards[i 2];}}//走到这里有两种可能// 1、有剩下的牌 -- 无法和牌返回false// 2、没剩下牌 -- 和牌返回truefor (int i 1; i 9; i) {if (cards[i] 0) {return false;}}return true;
}bool head(vectorint cards) {//如果有两张一样的牌先尝试作为雀头for (int i 1; i 9; i) {if (cards[i] 2) {cards[i] - 2;//再用递归回溯从剩余牌中找顺子和刻子如果能和牌代表这次抽取成功打印记录if (is_valid(cards)) {//回溯 -- 这里return了就不走到70行回溯那么找下一种组合的时候就会少两张牌大漏洞cards[i] 2;return true;}//回溯cards[i] 2;}}//走到这代表没有雀头寄return false;
}void check(vectorint cards) {//抽一张穷举法for (int i 1; i 9; i) {//如果有一张牌的数量小于4代表可以抽这张牌进行穷举if (cards[i] 4) {//抽取cards[i];//继续穷举选择雀头if (head(cards)) {res.push_back(i);}//回溯cards[i]--;}}
}int main() {//哈希表存放已有的牌vectorint cards(10);//抽取13张牌for(int i0;i13;i){int n;cinn;cards[n];}//回溯法检查和牌check(cards);//防止顺序不一样排下序 -- res是全局变量懒得传参了sort(res.begin(),res.end());for(auto v : res){cout v ;}return 0;}
