首页 > 试题广场 > 雀魂启动!
[编程题]雀魂启动!
  • 热度指数:9333 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
小包最近迷上了一款叫做雀魂的麻将游戏,但是这个游戏规则太复杂,小包玩了几个月了还是输多赢少。
于是生气的小包根据游戏简化了一下规则发明了一种新的麻将,只留下一种花色,并且去除了一些特殊和牌方式(例如七对子等),具体的规则如下:

  1. 总共有36张牌,每张牌是1~9。每个数字4张牌。
  2. 你手里有其中的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

输出

9

说明

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

输入

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

输出

4 7

说明

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

输入

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

输出

0

说明

来任何牌都无法和牌

备注:
请不要根据自己的常识为题目增加未提及的条件

对于20%的数据,保证和牌时一定是4个刻子+雀头的形式
import java.util.*;

public class Main {

    private void sln() {
        Scanner sc = new Scanner(System.in);
        int[] state = new int[9], helpArr = new int[9];
        ArrayList<Integer> res = new ArrayList<>();
        for (int i = 0; i < 13; i++) {
            int num = sc.nextInt();
            state[num - 1]++;
        }
        for (int i = 0; i < 9; i++) {
            if (state[i] < 4) {
                int num = i + 1;
                System.arraycopy(state, 0, helpArr, 0, 9);
                helpArr[i]++;
                if (canHu(helpArr, 14, false)) res.add(num);
            }
        }
        if (res.isEmpty()) System.out.println(0);
        else {
            StringBuffer sbf = new StringBuffer();
            sbf.append(res.get(0));
            for (int i = 1; i < res.size(); i++) {
                sbf.append(" ");
                sbf.append(res.get(i));
            }
            System.out.println(sbf.toString());
        }
    }

    private boolean canHu(int[] arr, int total, boolean hasHead) {
        if (total == 0) return true;
        if (!hasHead) {
            for (int i = 0; i < 9; i++) {
                if (arr[i] >= 2) {
                    arr[i] -= 2;
                    if (canHu(arr, total - 2, true)) return true;
                    arr[i] += 2;
                }
            }
            return false;
        } else {
            for (int i = 0; i < 9; i++) {
                if (arr[i] > 0) {
                    if (arr[i] >= 3) {
                        arr[i] -= 3;
                        if (canHu(arr, total - 3, true)) return true;
                        arr[i] += 3;
                    }
                    if (i + 2 < 9 && arr[i + 1] > 0 && arr[i + 2] > 0) {
                        arr[i]--;
                        arr[i + 1]--;
                        arr[i + 2]--;
                        if (canHu(arr, total - 3, true)) return true;
                        arr[i]++;
                        arr[i + 1]++;
                        arr[i + 2]++;
                    }
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        new Main().sln();
    }
}

发表于 2019-08-08 14:37:24 回复(18)
本题考查的是回溯法,由于数据的规模非常小(n<=9),所以递归不会很深。
思路: 已有13张牌,我们从剩余的牌中依次从1到9选择一张牌作为第14张牌,然后判断是否已经构成胡牌。
判断胡牌思路:从1到9中选择一个数字作为雀头,然后判断剩余的数字是否包含4个三张牌
import java.util.Scanner;

/**
 * 回溯法
 */
public class Main {


    private static int[] arr = new int[13];
    private static int[] count;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);


        count = new int[9];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = scanner.nextInt();
            ++count[arr[i]-1];
        }


        int winCount = 0;
        // 选择1到9中的一个作为第14张牌,然后判断是否胡牌
        for (int i = 1 ; i <= 9; i++) {
            if(count[i-1]<4){
                ++count[i-1];
                if(win()){
                    ++winCount;
                    System.out.print(i);
                    System.out.print(" ");
                }
                --count[i-1];
            }
        }
        if(winCount==0){
            System.out.println(0);
        }
    }
    public static boolean win(){
        // 从1到9 中选择一个作为雀头, 然后判断剩余的牌是否构成4对
        for (int i = 1; i <= 9; i++) {
            if(count[i-1]<2){
                continue;
            }
            count[i-1]-=2;
            if(hasTriples(4)){
                count[i-1]+=2;
                return true;
            }
            count[i-1]+=2;
        }
        return false;
    }

    public static boolean hasTriples(int n){
        if(n==0){
            return true;
        }
        // 1到9,每一张牌尝试三张或顺子
        for (int i = 1; i <= 9; i++) {
            if(count[i-1]>=3){
                count[i-1]-=3;
                boolean subHashTriples = hasTriples(n-1);
                count[i-1]+=3;
                if(subHashTriples){
                    return true;
                }
            }
            if(i<=7  && count[i-1]>0 && count[i] > 0 && count[i+1]>0){
                --count[i-1];
                --count[i];
                --count[i+1];
                boolean subHasTriples = hasTriples(n-1);

                ++count[i-1];
                ++count[i];
                ++count[i+1];
                if(subHasTriples){
                    return true;
                }
            }
        }
        return false;
    }
}

发表于 2020-02-08 17:07:40 回复(8)
def isHu(nums):
    """
    判断是否可以胡牌
    :param nums:
    :return:
    """
    if not nums:
        return True
    n = len(nums)
    count0 = nums.count(nums[0])
    # 没出现过雀头,且第一个数字出现的次数 >= 2,去掉雀头剩下的能不能和牌
    if n % 3 != 0 and count0 >= 2 and isHu(nums[2:]) == True:
        return True
    # 如果第一个数字出现次数 >= 3,去掉这个刻子后看剩下的能和牌
    if count0 >= 3 and isHu(nums[3:]) == True:
        return True
    # 如果存在顺子,移除顺子后剩下的能和牌
    if nums[0] + 1 in nums and nums[0] + 2 in nums:
        last_nums = nums.copy()
        last_nums.remove(nums[0])
        last_nums.remove(nums[0] + 1)
        last_nums.remove(nums[0] + 2)
        if isHu(last_nums) == True:
            return True
    # 以上条件都不满足,则不能和牌
    return False
 
def main(nums):
    """
    遍历所有可以抓到的牌看能不能胡牌
    :return:
    """
    d = {}
    for i in nums:
        d[i] = d.get(i,0) + 1
    card_list = set(range(1,10)) - {i for i,v in d.items() if v==4}
    res = []
    for i in card_list:
        if isHu(sorted(nums + [i])):  # 如果这种抽牌方式可以和牌
            res.append(i)  # 加入和牌类型列表
    res = ' '.join(str(x) for x in sorted(res)) if res else '0'
    print(res)
 
 
s = input()
nums = [int(x) for x in s.split()]
main(nums)

发表于 2019-05-14 13:37:42 回复(11)
C++ 借助map解决
#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;
}



发表于 2019-09-05 16:25:00 回复(0)
看了大佬的思路,写个C++版的
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
bool ishu(vector<int>num)
{
    if (num.empty())
        return true;
    int count0 = 0;
    for(int i=0;i<num.size();++i)
    {
        if (num[0] == num[i])
            ++count0;
        else
            break;
    }
    if (num.size() % 3 != 0 && count0 >= 2)
    {
        vector<int> newnum(num.begin() + 2, num.end());
        if (ishu(newnum))
            return true;
    }
    if (count0 >= 3)
    {
        vector<int> newnum(num.begin() + 3, num.end());
        if (ishu(newnum))
            return true;
    }
    if(count(num.begin(),num.end(),num[0]+1)>0 && count(num.begin(), num.end(), num[0] + 2)>0)
    {
        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;
}
bool hupai(vector<int>num, int n)
{
    if (count(num.begin(), num.end(), n) == 4)
        return false;
    num.push_back(n);
    sort(num.begin(),num.end());
    return ishu(num);
}
int main()
{
    vector<int> num;
    vector<int> res;
    for (int i = 0; i < 13; ++i)
    {
        int tmp;
        cin >> tmp;
        if (tmp > 0 && tmp < 10)
            num.push_back(tmp);
        else
        {
            cout << "输入错误" << endl;
            return 0;
        }
    }
    for (int n = 1; n < 10; ++n)
    {
        if (hupai(num, n))
            res.push_back(n);
    }
    if (res.empty())
        cout << 0;
    else
        for (int i = 0; i < res.size(); ++i)
            cout << res[i]<<" ";
}

发表于 2019-06-28 20:32:11 回复(0)
参考大佬的思路,自己C++实现了一遍,对回溯又多了点理解,顺带加了点小注释
#include <iostream>
(720)#include <vector>
using namespace std;

vector<int> card(9);

//检查剩余的牌能否组成n个顺子或刻子
bool hasTrible(int n){
    if(n==0) return true;
    for(int i=0; i<card.size(); ++i){
        //因为仍是从1开始查验,因此若检查到其牌数>=3,则必定是刻子
        if(card[i]>2){   
            card[i] -= 3;
            if(hasTrible(n-1)){   //检查余下的牌能否组成n-1个顺子或刻子
                card[i] += 3;
                return true;
            }
            card[i] += 3;
        }
        //否则只能是顺子
        else if(i<card.size()-2 && card[i]>0 && card[i+1]>0 && card[i+2]>0){
                card[i]--;
                card[i+1]--;
                card[i+2]--;
                if(hasTrible(n-1)){
                    card[i]++;
                    card[i+1]++;
                    card[i+2]++;
                    return true;
                }
                card[i]++;
                card[i+1]++;
                card[i+2]++;
        }
    }
    return false;
}
//检查14张牌能否和牌
bool isWin(){
    for(int i=0; i<9; ++i){  //依次把1~9作为雀头拿出来,检查剩下的12张牌能否顺或刻子
        if(card[i]<2)
            continue;
        card[i] -= 2;
        if(hasTrible(4)){    
            card[i] += 2;
            return true;
        }
        card[i] += 2;
    }
    return false;
}

int main(){
    vector<int> res;
    int tmp;
    for(int i=0; i<13; ++i){
        cin >> tmp;
        card[tmp-1]++;
    }
    for(int i=0; i<9; ++i){  //1~9依次添加,检查是否可以和牌
        if(card[i]>3)
            continue;
        card[i]++;
        if(isWin())           //如果添加的这张牌可以和牌,则将其加入输出结果
            res.push_back(i+1);
        card[i]--;
    }
    if(res.empty()) res.push_back(0);
    for(int i=0; i<res.size(); ++i)
        cout << res[i] << ' ';
    return 0;
}


发表于 2020-03-18 13:45:47 回复(0)
给出一个算法思路吧,编程用C++或是Python可自己实现或参考其余评论的代码:
/*原理:如果该手牌胡牌,那么每个数字必然是,雀头、刻子、顺子的成员,
  
    编程实现:递归算法 : 从最小的数字开始尝试,如果把其当成雀头成员,该数字划掉两个,并看余下的数字能否划空 
                                     如果是刻子成员,该数字划掉三个,并查看余下数字能否划空 
                                     如果是顺子成员,划掉该值 a ,a+1,a+2,并查看余下数字能否划空 
            如果上述三种尝试都无法划空数组,说明存在数字无法是 雀头、刻子、顺子的成员, 即无法胡牌。 
            (上述任何一种情况能划空数组,都可以胡牌)  
*/ 

发表于 2019-07-09 17:15:48 回复(0)
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

/**
 *
 * https://www.nowcoder.com/question/next?pid=16516564&qid=362290&tid=28447145
 * 题设:总共有36张牌,每张牌是1~9。每个数字4张牌。
 * 你手里有其中的14张牌,如果这14张牌满足如下条件,即算作和牌,和牌条件如下:
 *  (1)14张牌中有2张相同数字的牌,称为雀头。
 *  (2)除去上述2张牌,剩下12张牌可以组成4个顺子或刻子。
 *      顺子的意思是:递增的连续3个数字牌(例如234,567等);
 *      刻子的意思是:相同数字的3个数字牌(例如111,777)
 * 输入:已有的13张牌
 * 输出:可以使14张牌成为和牌的最后一张(如果有多种可能,按从小到大的顺序输出)
 *
 * 分析:由小到大添加可能的牌(如果原来牌组已经有了4张该种牌那肯定就不可能了)。
 * 难点是判定14张牌是否是和牌:
 *      第一步选择两张数字相同的,作为雀头;
 *      剩下的牌作为顺子的部分还是刻子部分?(从小到打遍历)
 *          如果除去雀头,一个数字有1或2张:那么这两张肯定作为刻子;
 *          如果除去雀头,一个数字有3张:那么这三张都是刻子或者都是顺子;
 *              假设该数字是顺子,直接划掉
 *              假设该数字是刻子,就划掉a,a+1,a+2
 *          如果除去雀头,一个数字有4张:那么肯定有1张作为刻子,其余三张都是刻子或者都是顺子;
 *              先划掉刻子的那张,     a,a+1,a+2
 *              剩下三张依照上述内容继续处理!
 * 分析到这里,不难看出采用回溯法可以解决。
 *  回溯除了本身是一种暴力实用的算法,还能有效帮助我们理解值传递和引用传递的区别!
 * tips:Java数组如何转化为集合?https://www.cnblogs.com/kangkaii/p/8427739.html
 * 个人喜欢new一个list,然后调用Collections.addAll(list,arr);
 * Arrays.asList()里面不能传数组引用竟然!!!必须要传数组的具体内容!
 *
 */
public class Main {
    private static int[] count= new int[9];
    //由小到大存放可以使牌胡的最后一张(要有可能才行)
    private static ArrayList<Integer> getRes(Integer[] data){
        //存储可行解
        ArrayList<Integer> res=new ArrayList<>();
        //统计1~9出现的次数,count[i]统计的是i+1的次数。i从0~8
        for (Integer e : data) {
            count[e-1]++;
        }
        for (int i = 1; i <= 9; i++) {
            //1.visit
            if(count[i-1]<4){
                count[i-1]++;//说明该张牌可以被插入
            }else {
                continue;
            }
            //2.operate:after copying
            int[] countCp = Arrays.copyOf(count, count.length);
            if( canFindQueTou(countCp) ){
                res.add(i);
            }
            //3.backTrack
            count[i-1]--;
        }
        return res;
    }
    //找雀头
    private static boolean canFindQueTou(int[] count){
        int cnt=0;//记录删掉的牌
        for (int integer = 1; integer <= 9; integer++) {
            if(count[integer-1]>=2){//找到可以作为雀头的integer
                //1.visit
                count[integer-1]-=2;
                //2.operation
                cnt+=2;
                int[] countCp = Arrays.copyOf(count, count.length);
                if(canGoOn(countCp)){//&&后面也能正常进行
                    return true;
                }
                //3.backTrack
                count[integer-1]+=2;
            }
        }
        return false;
    }
    //给其它牌配顺子或者刻子!
    private static boolean canGoOn(int[] count) {
        for (int i = 1; i <= 7; i++) {
            if(count[i-1]==1||count[i-1]==2){//如果该牌只有1张或者两张,必然作为刻子
                if(count[i]>=count[i-1]&&count[i+1]>=count[i-1]){
                    count[i]-=count[i-1];
                    count[i+1]-=count[i-1];
                    count[i-1]-=count[i-1];
                    continue;
                }
                return false;
            }
            if(count[i-1]==3){//如果该牌有3张,作为顺子是当前可行step;3张都作为刻子看情况
                //能做刻子就做刻子,否则才做顺子?这种策略真的不会出错吗?
                //有没有做顺子可以做刻子不行的情况?
                //111 222 333 顺刻都行
                //111 2222 3333 顺子:2222 3333  刻子: 2 3
                if(count[i]>=count[i-1]&&count[i+1]>=count[i-1]){//3张都可以作为刻子的情形
                    count[i]-=count[i-1];
                    count[i+1]-=count[i-1];
                    count[i-1]-=count[i-1];
                    continue;
                }else {//作为顺子
                    count[i-1]-=count[i-1];
                    continue;
                }
//                return false;
            }
            if(count[i-1]==4){//如果该牌有4张,1张作为刻子
                if(count[i]>=1&&count[i+1]>=1){
                    count[i]-=1;
                    count[i+1]-=1;
                    count[i-1]-=1;
                    i--;//继续当前牌的判断,退役到上头该牌有3张的那种情况了
                    continue;
                }
                return false;
            }
        }
        return (count[7]==0||count[7]==3)&&(count[8]==0||count[8]==3);
    }


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) { //分隔符:换行||空格
            Integer[] data=new Integer[13];
            for (int i = 0; i < 13; i++) {
                data[i]=Integer.parseInt(sc.next());
            }
            ArrayList<Integer> res = getRes(data);
            if(res.size()==0){
                System.out.print(res.size());
            }else {
                for (int i = 0; i < res.size(); i++) {
                    System.out.print(res.get(i)+((i!=res.size()-1)?" ":""));
                }
            }
        }
    }
}

发表于 2019-10-11 11:15:33 回复(0)
# 小包最近迷上了一款叫做雀魂的麻将游戏,但是这个游戏规则太复杂,小包玩了几个月了还是输多赢少。
# 于是生气的小包根据游戏简化了一下规则发明了一种新的麻将,只留下一种花色,并且去除了一些特殊和牌方式(例如七对子等),具体的规则如下:
#     总共有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张牌中,再取一张牌,取到哪几种数字牌可以和牌。
# 原理:如果该手牌胡牌,那么每个数字必然是,雀头、刻子、顺子的成员,
# 递归算法 : 从最小的数字开始尝试,如果把其当成雀头成员,该数字划掉两个,并看余下的数字能否划空
# 如果是刻子成员,该数字划掉三个,并查看余下数字能否划空
# 如果是顺子成员,划掉该值
# a, a + 1, a + 2,并查看余下数字能否划空
# 如果上述三种尝试都无法划空数组,说明存在数字无法是
# 雀头、刻子、顺子的成员,
#将一个数字牌补入13个牌之中,判断是否和牌,是则输出,不是则下一个数字牌

def IShepai(str):
    lenth=str.__len__()
    if lenth == 0:
        return True
    count1=str.count(str[0])

    if lenth%3!=0 and count1>=2 and IShepai(str[2:])==True:
        return True
    if  count1 >= 3 and IShepai(str[3:])==True:
            return True
    if str[0] + 1 in str and str[0] + 2 in str:
        str1 = str[1:]
        str1.remove(str[0]+1)
        str1.remove(str[0]+2)
        if IShepai(str1) == True:
            return True
    return False
if __name__ == '__main__':
    a=input().split(" ")
    a=[int(x) for x in a]

    for i in range(1,10):
        al=sorted(a + [i])
        if al.count(i)>4:
            continue
        else:
            if IShepai(al) == True:
                print(i,end=" ")
    print()


发表于 2019-09-07 16:05:55 回复(0)
 def is_win(cards):
    if len(cards) == 2 and cards[0] == cards[1]:
        return True
    for i in range(len(cards) - 2):
        if i < len(cards)-4 and  cards[i] == cards[i + 4]:
            return False
    for i in range(len(cards) - 2):
        tmp = cards[i]
        #shunzi
        if (tmp in cards) and (tmp + 1 in cards) and (tmp + 2 in cards):
            this_cards = cards.copy()
            this_cards.remove(tmp)
            this_cards.remove(tmp + 1)
            this_cards.remove(tmp + 2)
            if is_win(this_cards):
                return True
        #kezi
        elif tmp == cards[i + 2]:
            this_cards = cards.copy()
            this_cards.remove(tmp)
            this_cards.remove(tmp)
            this_cards.remove(tmp)
            if is_win(this_cards):
                return True
    return False

def main():
    nums = list(map(int, input().split()))
    # nums = list(map(int, "1 1 1 3 4 5 5 5 5 6 7 9 9".split()))
    res = []
    for i in range(1, 10):
        cards = nums.copy()
        cards.append(i)
        cards.sort()
        if is_win(cards):
            res.append(i)

    res = ' '.join(str(x) for x in sorted(res)) if res else '0'
    print(res)

if __name__ == "__main__":
    main()
编辑于 2019-07-16 20:44:14 回复(1)
思路:本题我采用的是二进制枚举状态(状态压缩)的方法,通过定义9位二进制表示数字1~9的状态,其中二进制位为1表明数字i应该凑一个刻子,当把当前的所有刻子减掉后,剩下的就是判断能否构成顺子即可。
#include<stdio.h>
#include<algorithm>
using namespace std;
int a[15],b[10],c[10],d[10];
bool shunzi(int arr[]){
    int e[10];
    for(int i=1;i<10;i++)
        e[i]=arr[i];
    for(int i=1;i<=7;i++){
        if(e[i]==0)
            continue;
        int mn=min(e[i], min(e[i+1], e[i+2]));
        e[i]-=mn;
        e[i+1]-=mn;
        e[i+2]-=mn;
        if(e[i]!=0)
            return false;
    }
    return e[8]==0 && e[9]==0;
}
bool check(int arr[]){
    for(int i=1;i<=9;i++){
        if(arr[i]<2) continue;
        for(int j=0;j<(1<<9);j++){
            for(int k=1;k<=9;k++)
                d[k]=arr[k];
            d[i]-=2;
            bool mark=false;
            for(int k=0;k<9;k++){
                if(j>>k&1){
                    if(d[k+1]<3){
                        mark=true;
                        break;
                    }
                    else
                        d[k+1]-=3;
                }
            }
            if(!mark && shunzi(d))
                return true;
        }
    }
    return false;
}
int main(void){
    for(int i=1;i<=9;i++)
        b[i]=4;
    for(int i=1;i<14;i++){
        scanf("%d",&a[i]);
        b[a[i]]--;
        c[a[i]]++;
    }
    for(int i=1;i<=9;i++){
        if(b[i]==0) 
            continue;
        c[i]++;
        if(check(c))
            printf("%d ",i);
        c[i]--;
    }
    printf("\n");
    return 0;
}


发表于 2021-01-15 20:28:16 回复(0)
本题要求找出所有可以和牌的数字,最多的情况为9种,因此,只需要从1->9依次验证即可,以下为验证方法:
首先,如果手牌中某张牌已经有4张了,是不可以再取到的,直接continue;
然后,开始判断14张牌能否和牌:
for(int i=1;i<10;i++){
        if(rec[i]==4)continue;
        rec[i]++;
        if(fun(rec,14)){
            cout<<i<<" ";
            flag=true;
        }
        rec[i]--;
    }
和牌的判断:
1.当总牌数为0时,返回true
 if(num<=0)return true;
2.每次减牌对map中第一个数都有三个选择:
  1. 当num不能被3整除,并且第一个数有2个以上,说明有雀头,num可以减2;
     if(num%3!=0 && (it->second)>=2){
            mp[it->first]-=2;
            if(fun(mp, num-2))return true;
            mp[it->first]+=2;//走到这步,说明上步失败了,还原mp
        }

  2. 当第一个数有3个以上时,说明有刻子可以选,num-3;
    if((it->second)>=3){
            mp[it->first]-=3;
            if(fun(mp, num-3))return true;
            mp[it->first]+=3;//也失败了,还原
        }

  3. 当上面两种都不行,就判断第一个数与后两个数是否都大于0,是就可以组成顺子,num-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(fun(mp, num-3))return true;
        mp[(it->first)]++;
        mp[(it->first)+1]++;
        mp[(it->first)+2]++;
    }
   4.如果三种情况都失败,就returun false;

完整代码:
#include <iostream>
#include <map>
using namespace std;
bool fun(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(fun(mp, num-2))return true;
        mp[it->first]+=2;
    }
    if((it->second)>=3){
        mp[it->first]-=3;
        if(fun(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(fun(mp, num-3))return true;
        mp[(it->first)]++;
        mp[(it->first)+1]++;
        mp[(it->first)+2]++;
    }
    return false;
     
}
int main(){
    map<int,int> rec;
    int tmp;
    bool flag=false;
    for(int i=0;i<13;i++){
        cin>>tmp;
        rec[tmp]++;
    }
    for(int i=1;i<10;i++){
        if(rec[i]==4)continue;
        rec[i]++;
        if(fun(rec,14)){
            cout<<i<<" ";
            flag=true;
        }
        rec[i]--;
    }
    if(!flag)
        cout<<0;
    return 0;
     
}





编辑于 2020-07-01 10:19:00 回复(0)
#include <bits/stdc++.h>
using namespace std;

bool F(map<int,int> M, int t){
    if(t<=0)
        return true;
    while(M[M.begin()->first]==0)
        M.erase(M.begin());
    map<int,int>::iterator it = M.begin();
    int i=it->first, cnt=it->second;
    if(t%3!=0 && cnt>=2){
        M[i] -= 2;
        if(F(M, t-2))
            return true;
        M[i] += 2;
    }
    if(cnt>=3){
        M[i] -= 3;
        if(F(M, t-3))
            return true;
        M[i] += 3;
    }
    if(cnt>0 && M[i+1]>0 && M[i+2]>0){
        M[i]--;
        M[i+1]--;
        M[i+2]--;
        if(F(M, t-3))
            return true;
        M[i]++;
        M[i+1]++;
        M[i+2]++;
    }
    return false;
}

int main(){
    map<int, int> M;
    int x;
    for(int i=0;i<13;i++){
        cin>>x;
        M[x]++;
    }
    vector<int> v;
    for(int i=1;i<10;i++){
        if(M[i]<4){
            M[i]++;
            if(F(M, 14))
                v.push_back(i);
            M[i]--;
        }
    }
    if(v.empty())
        cout<<0<<endl;
    else{
        for(int i=0;i<v.size();i++){
            if(i==v.size()-1)
                cout<<v[i]<<endl;
            else
                cout<<v[i]<<" ";
        }
    }

    return 0;
}

发表于 2019-12-29 09:12:15 回复(0)
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sin=new Scanner(System.in);
        while(sin.hasNext()){
            int[] cards=new int[13];
            for(int i=0;i<13;i++){
                cards[i]=sin.nextInt();
            }
            List<Integer> res=solve(cards);
            for(int num:res){
                System.out.print(num+" ");
            }
            System.out.println();
        }
    }
    public static List<Integer> solve(int[] cards){
        List<Integer> list=new ArrayList<>();
        int[] has=new int[10];
        for(int card:cards){
            has[card]+=1;
        }
        for(int i=1;i<=9;i++){
            if(has[i]<4){
                has[i]+=1;
                //选一个当雀头
                for(int j=1;j<=9;j++){
                    if(has[j]>=2){
                        has[j]-=2;
                        if(backTrack(12,has)){
                            list.add(i);
                            has[j]+=2;
                            break;
                        }
                        has[j]+=2;
                    }
                }
                has[i]-=1;
            }
        }
        if(list.size()==0)  list.add(0);
        return list;
    }
    public static boolean backTrack(int remain,int[] has){
        if(remain==0)  return true;
        //凑刻子
        for(int i=1;i<=9;i++){
            if(has[i]>=3){
                has[i]-=3;
                if(backTrack(remain-3,has)){
                    has[i]+=3;
                    return true;
                }
                has[i]+=3;
            }
        }
        //凑顺子
        for(int i=1;i<=7;i++){
            if(has[i]>0 && has[i+1]>0 && has[i+2]>0){
                has[i]-=1; has[i+1]-=1; has[i+2]-=1;
                if(backTrack(remain-3,has)){
                    has[i]+=1; has[i+1]+=1; has[i+2]+=1;
                    return true;
                }
                has[i]+=1; has[i+1]+=1; has[i+2]+=1;
            }
        }
        //一次机会都没
        return false;
    }
}
思路就补牌,采用回溯凑顺子或者刻子
s
发表于 2021-02-26 20:00:27 回复(0)
纯____题目
1. 刻和顺子可以混合着来,111+123+333+456 是可以的,不讲清楚。
2. 每种牌最多4张。

搞清题目,直接枚举就完事了。
1. 枚举加哪张牌
2. 枚举哪张牌是头
3. 剩下的牌依次枚举其作为刻子和顺子的情况,因为只有12张必然要选完的。
#include<bits/stdc++.h>
using namespace std;
map<int,int> mp, backup;
bool check(int dep)
{
    if(dep > 4) return 1;
    int x = 1;
    for(int i = 1; i <= 9; i++) if(mp[i]) {
        x = i; break;
    }
    int flag = 0;
    int y = x + 1, z = y + 1;
    if(mp[x] && mp[y] && mp[z]) {
        mp[x]--; mp[y]--; mp[z]--;
        flag |= check(dep + 1);
        mp[x]++; mp[y]++; mp[z]++;
    }
    if(flag) return 1;
    if(mp[x] >= 3) {
        mp[x] -= 3;
        flag |= check(dep + 1);
        mp[x] += 3;
    }
    return flag;
}
int main()
{
    for(int i = 1; i <= 13; i++) {
        int x; cin >> x; mp[x] += 1; backup[x] += 1;
    }
    vector<int> ans;
    for(int i = 1; i <= 9; i++) {
        for(int t = 1; t <= 9; t++) mp[t] = backup[t];
        mp[i] += 1;
        if(mp[i] > 4) continue;
        for(int j = 1; j <= 9; j++) {
            if(mp[j] >= 2) {
                mp[j] -= 2;
                if(check(1)) {
                    ans.push_back(i);
                    break;
                }
                for(int t = 1; t <= 9; t++) mp[t] = backup[t]; mp[i] += 1;
            }
        }
    }
    if(ans.size() == 0) cout << "0";
    else for(auto &i: ans) cout << i << ' ';
}


发表于 2021-01-24 19:46:55 回复(0)
backtracking solution

import collections def maJiang(nums):
    counter = collections.Counter(nums)
    ret = set() def helper(cur_counter): if sum(cur_counter.values()) <= 2:
            has_value = [] for k in cur_counter.keys(): if cur_counter[k] > 0:
                    has_value.append(k) if len(has_value) == 1:
                ret.add(has_value[0]) elif len(has_value) == 2: if abs(has_value[0] - has_value[1]) == 1: if min(has_value) - 1 > 0:
                        ret.add(min(has_value) - 1) if max(has_value) + 1 < 10:
                        ret.add(max(has_value) + 1) elif abs(has_value[0] - has_value[1]) == 2:
                    ret.add(min(has_value) + 1) return  keys = cur_counter.keys() for k in keys: if cur_counter[k] >= 3:
                cur_counter[k] -= 3  helper(cur_counter)
                cur_counter[k] += 3  if cur_counter[k] > 0 and cur_counter[k+1] > 0 and cur_counter[k+2] > 0:
                cur_counter[k] -= 1  cur_counter[k + 1] -= 1  cur_counter[k + 2] -= 1  helper(cur_counter)
                cur_counter[k] += 1  cur_counter[k + 1] += 1  cur_counter[k + 2] += 1   helper(counter) for key in counter.keys(): if counter[key] >= 2:
            counter[key] -= 2  helper(counter)
            counter[key] += 2  ans = [] for k in ret: if counter[k] < 4:
            ans.append(k) return " ".join(map(str, sorted(list(ans))))

编辑于 2020-12-27 12:06:42 回复(0)
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
	"strings"
)

func have(nums []int, s int) int {
	for i, v := range nums {
		if v == s {
			return i
		}
	}
	return -1
}

func ishu(nums []int) bool {
	if len(nums) == 0 {
		return true
	}
	n := len(nums)
	count0 := 0
	for i := 0; i < n; i++ {
		if nums[i] == nums[0] {
			count0++
		}
	}
	if n%3 != 0 && count0 >= 2 && ishu(nums[2:]) {
		return true
	}
	if count0 >= 3 && ishu(nums[3:]) {
		return true
	}
	if have(nums, nums[0]+1) != -1 && have(nums, nums[0]+2) != -1 {
		var mid []int
		mid = append(mid, nums...)
		mid = append(mid[:have(mid, nums[0])], mid[have(mid, nums[0])+1:]...)
		mid = append(mid[:have(mid, nums[0]+1)], mid[have(mid, nums[0]+1)+1:]...)
		mid = append(mid[:have(mid, nums[0]+2)], mid[have(mid, nums[0]+2)+1:]...)
		if ishu(mid) {
			return true
		}
	}
	return false
}

func main() () {
	in := bufio.NewReader(os.Stdin)
	str, _, _ := in.ReadLine()
	numss := strings.Split(strings.Trim(string(str), " "), " ")
	var nums []int
	nums = make([]int, len(numss))
	for i := 0; i < len(numss); i++ {
		nums[i], _ = strconv.Atoi(numss[i])
	}

	d := make(map[int]int)
	rst := make([]int, 0)
	for i := 0; i < len(nums); i++ {
		d[nums[i]] ++
	}
	var card_list []int
	for i := 1; i < 10; i++ {
		if v, err := d[i]; err && v == 4 {
		} else {
			card_list = append(card_list, i)
		}

	}
	for i := 0; i < len(card_list); i++ {
		mid := append(nums, card_list[i])
		sort.Ints(mid)
		if ishu(mid) {
			rst = append(rst, card_list[i])
		}
	}
	sort.Ints(rst)
	var srst []string
	srst = make([]string, len(rst))
	for i := 0; i < len(rst); i++ {
		srst[i] = strconv.Itoa(rst[i])
	}
	if len(srst) == 0 {
		fmt.Println("0")
	} else {
		fmt.Println(strings.Join(srst, " "))
	}
}

发表于 2020-12-01 22:17:19 回复(0)
解题思路是每次提取三个数  对剩下的迭代看是否仍然满足“一对+n组3个”这个条件。
特殊情况是某一种牌已经用完,在函数开头判断添加该牌是否有5张连续一样即可。
最后别忘了自己先排序,自己打麻将也知道先把牌理好的吧(笑)
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool calc(int a,int b,int c){
    if(a==b&&a==c)return true;
    if(b-a==1&&c-b==1)return true;
    return false;
}

bool win(vector<int> data){
    if(data.size()==2){
        if(data[0]==data[1])return true;
    }
    if(data.size()==14){
        for(int i=0;i<10;i++)
            if(data[i]==data[i+1]&&data[i]==data[i+2]&&data[i]==data[i+3]&&data[i]==data[i+4]) return false;
    }
    int i,j,k;
    vector<int> temp;
    for(i=0;i<data.size()-2;i++){
        for(j=i+1;j<data.size()-1;j++){
            for(k=j+1;k<data.size();k++){
                if(calc(data[i],data[j],data[k])){
                    temp=data;
                    temp.erase(temp.begin()+k);
                    temp.erase(temp.begin()+j);
                    temp.erase(temp.begin()+i);
                if(win(temp))return true;
                }
            }
        }
    }
    return false;
}

int main(){
    vector<int> data(14);
    for(int i=0;i<13;i++)cin>>data[i];
    bool flag=false;
    vector<int> origin=data;
    for(int i=1;i<=9;i++){
        data=origin;
        data[13]=i;
        sort(data.begin(),data.end());
        if(win(data)){
            cout<<i<<" ";
            flag=true;
        }
    }
    if(!flag)cout<<int(0);
}

发表于 2020-10-26 17:39:23 回复(0)
虽然理解了后不算太难...但为什么这题是简单,明明“实现二叉树先序,中序和后序遍历”这种题都有中等
发表于 2020-10-18 13:48:04 回复(0)
import java.util.HashMap;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < 13; i++) {
            map.merge(scanner.nextInt(), 1, (a, b) -> (a + b));
        }
        String re = deal(map);
        System.out.println(re);
        scanner.close();

    }

    private static String deal(HashMap<Integer, Integer> param) {
        StringBuilder stringBuilder = new StringBuilder();
        HashMap<Integer, Integer> map = new HashMap<>();

        for (int i = 1; i <= 9; i++) {
            map.clear();
            map.putAll(param);
            map.merge(i, 1, (a, b) -> (a + b));
            if (map.get(i) < 5) {
                if (canDo(14, map, false)) {
                    stringBuilder.append(i).append(" ");
                }
            }
            map.merge(i, -1, (a, b) -> (a + b));
        }
        return stringBuilder.toString();
    }

    private static boolean canDo(int num, HashMap<Integer, Integer> map, boolean hasHead) {
        if (num == 0) {
            return true;
        }
        if (!hasHead) {
            for (int i = 1; i < 10; i++) {
                if (map.containsKey(i) && map.get(i) >= 2) {
                    map.merge(i, -2, (a, b) -> (a + b));
                    if (canDo(num - 2, map, true)) return true;
                    map.merge(i, 2, (a, b) -> (a + b));
                }
            }
        } else {
            for (int i = 1; i < 10; i++) {
                if (map.containsKey(i) && map.get(i) >= 3) {
                    map.merge(i, -3, (a, b) -> (a + b));
                    if (canDo(num - 3, map, true)) return true;
                    map.merge(i, 3, (a, b) -> (a + b));
                } else if (i - 1 > 0 && i + 1 < 10 && map.containsKey(i) && map.containsKey(i + 1) && map.containsKey(i - 1) && map.get(i) > 0 && map.get(i - 1) > 0 && map.get(i + 1) > 0) {
                    map.merge(i, -1, (a, b) -> (a + b));
                    map.merge(i - 1, -1, (a, b) -> (a + b));
                    map.merge(i + 1, -1, (a, b) -> (a + b));
                    if (canDo(num - 3, map, true)) return true;
                    map.merge(i, 1, (a, b) -> (a + b));
                    map.merge(i - 1, 1, (a, b) -> (a + b));
                    map.merge(i + 1, 1, (a, b) -> (a + b));
                }
            }
        }
        return false;
    }

}

发表于 2020-09-13 17:50:05 回复(0)