标签搜索

目 录CONTENT

文章目录

字节跳动---雀魂启动.md

小小城
2022-05-02 / 0 评论 / 0 点赞 / 16 阅读 / 4,964 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-05-02,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

雀魂启动.md
date: 2021-08-22 12:11:39.912
updated: 2021-08-22 12:11:39.912
url: /2021/08/22/字节跳动---雀魂启动md
categories:
tags:

字节跳动---雀魂启动

@[toc]

一、题目描述

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

  •  总共有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;
}

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

0

评论区