首页 > 试题广场 >

雀魂启动!

[编程题]雀魂启动!
  • 热度指数:16110 时间限制: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个刻子+雀头的形式
 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)
#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 {

    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 回复(21)
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 回复(12)
本题考查的是回溯法,由于数据的规模非常小(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 回复(11)
参考大佬的思路,自己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 回复(1)
给出一个算法思路吧,编程用C++或是Python可自己实现或参考其余评论的代码:
/*原理:如果该手牌胡牌,那么每个数字必然是,雀头、刻子、顺子的成员,
  
    编程实现:递归算法 : 从最小的数字开始尝试,如果把其当成雀头成员,该数字划掉两个,并看余下的数字能否划空 
                                     如果是刻子成员,该数字划掉三个,并查看余下数字能否划空 
                                     如果是顺子成员,划掉该值 a ,a+1,a+2,并查看余下数字能否划空 
            如果上述三种尝试都无法划空数组,说明存在数字无法是 雀头、刻子、顺子的成员, 即无法胡牌。 
            (上述任何一种情况能划空数组,都可以胡牌)  
*/ 

发表于 2019-07-09 17:15:48 回复(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++ 借助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 回复(1)
本题要求找出所有可以和牌的数字,最多的情况为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)
# 小包最近迷上了一款叫做雀魂的麻将游戏,但是这个游戏规则太复杂,小包玩了几个月了还是输多赢少。
# 于是生气的小包根据游戏简化了一下规则发明了一种新的麻将,只留下一种花色,并且去除了一些特殊和牌方式(例如七对子等),具体的规则如下:
#     总共有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)
map记录牌的张数,size记录有几张牌,k记录是否已经使用刻头
#include<bits/stdc++.h>
using namespace std;
bool dfs(vector<int>map,int size,bool k){
    if(size==0){
        return true;
    }
    bool a = false,b = false,c = false;
    for(int i = 1;i<10;i++){
        if(!k&&map[i]>=2){
            map[i]-=2;
            a = dfs(map,size-2,true);
            map[i]+=2;
        }
        if(map[i]>=3){
            map[i]-=3;
            b = dfs(map,size-3,k);
            map[i]+=3; 
        }
        if(i<=7&&map[i]>0&&map[i+1]>0&&map[i+2]>0){
            --map[i];--map[i+1];--map[i+2];
            c = dfs(map,size-3,k);
            ++map[i];++map[i+1];++map[i+2];
        }
    }
    return a||b||c;
}
int main(){
    vector<int>map(10);
    int k;
    while(cin>>k){
        map[k]++;
    }
    for(int i = 0;i<10;i++){
        if(map[i]+1<=4){
            ++map[i];
            if(dfs(map,14,false)){
                cout<<i<<' ';
            }
            --map[i];
        }
    }
    return 0;
}

编辑于 2022-04-10 20:29:29 回复(0)
一直以为要四个顺子或四个刻子,竟然是四个刻子或顺子,晕。
发表于 2021-04-22 14:43:32 回复(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)
#include <bits/stdc++.h>
using namespace std;

vector<int> find_kezi(vector<int> a) {
    vector<int> b;
    for (int i = 0; i < 9; i++) {
        if (a[i] == 3) {
            int k = i;
            b.push_back(k);
        }
        if (a[i] == 4) {
            int k = i;
            b.push_back(k);
        }
    }
    return b;
}

int find_shunzi(vector<int> a) {
    int count = 0;
    int begin = 1;
    while (begin <= 7) {
        if (a[begin] != 0) {
            if (a[begin + 1] != 0 && a[begin + 2] != 0) {
                a[begin] -= 1;
                a[begin + 1] -= 1;
                a[begin + 2] -= 1;
                count++;
            } else begin++;
        } else begin++;
    }
    return count;
}

void without_quezi(vector<int> a, int n, bool& win_flag) {
    vector<int> kezi = find_kezi(a);
    int kezi_num = kezi.size();
    for (int i = 1; i <= 9; i++) {
        int b = find_shunzi(a);
        if (b == n) {
            win_flag = true;
            break;
        } else {
            if (a[i] >= 3) {
                vector<int> copy = a;
                copy[i] -= 3;
                int b = find_shunzi(copy);
                if (b == n - 1) {
                    win_flag = true;
                    return;
                } else {
                    bool sub_win_flag = false;
                    without_quezi(copy, n - 1, sub_win_flag);
                    if (sub_win_flag) {
                        win_flag = true;
                        return;
                    }
                }
            } else continue;
        }
    }
}

bool ifWin(vector<int> count, int b) {
    count[b]++;
    bool flag = false;
    for (int i = 1; i <= 9; i++) {
        if (count[i] >= 2) {
            vector<int> copy = count;
            copy[i] -= 2;
            bool win_flag = false;
            without_quezi(copy, 4, win_flag);
            if (win_flag == true) {
                flag = true;
                break;
            }
        } else continue;
    }
    return flag;
}
int main() {
    vector<int> input(13);
    for (int i = 0; i < 13; i++) {
        cin >> input[i];
    }
    int flag = 0;
    vector<int> count(10);
    for (int i = 0; i < 13; i++) {
        count[input[i]]++;
    }
    for (int i = 1; i <= 9; i++) {
        if (count[i] != 4) {
            if (ifWin(count, i)) {
                cout << i << " ";
                flag++;
            }
        } else continue;
    }
    if (flag == 0) {
        cout << 0;
    }
    count.clear();
    vector<int> ().swap(count);
    return 0;
}
发表于 2023-08-17 11:21:18 回复(0)
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int[] c = new int[10];
        while (in.hasNextInt()) c[in.nextInt()]++;
        boolean f = false;  
        for (int i = 1; i <= 9; ++i) {
            if (c[i] == 4) continue;
            c[i]++;
            if (check(c)) {
                System.out.print(i + " ");
                f = true;
            }
            c[i]--;
        }
        if (!f) System.out.println(0);
    }

    public static boolean check(int[] c) {
        for (int i = 1; i <= 9; ++i) {
            if (c[i] >= 2) {
                int[] cc = new int[10];
                System.arraycopy(c, 0, cc, 0, 10);
                cc[i] -= 2;
                if (op(cc)) return true;
            }
        }
        return false;
    }

    public static boolean op(int[] c) {
        int cnt = 0;
        for (int i = 1; i <= 9; ++i) {
            if (c[i] < 0) return false;
            if (c[i] >= 3) {
                cnt++;
                c[i] -= 3;
            }
            while (c[i] > 0) {
                if (i >= 8) return false;
                c[i]--;
                c[i + 1]--;
                c[i + 2]--;
                cnt++;
            }
        }
        return cnt == 4;
    }
}
枚举加入每种牌的可能,之后枚举每种对子的可能,最后判断剩下的牌是否可行。

时间复杂度是0(9*9*9)
发表于 2023-12-21 09:33:33 回复(0)
愚蠢的枚举法。
枚举加入1,2,3,4,5,6,7,8,9后是否胡牌。 对于每种情况枚举所有可能的雀头,对剩余的牌型进行回溯判断是否能组成四句话。
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int[] majhong = new int[9];
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int a = in.nextInt();
            majhong[a-1]++;
        }
        int res = cal(majhong);
        if (res == 0) System.out.println(0);
        else System.out.println("\n");
    }
    static int cal(int[] majhong) {
        int res = 0;
        for (int i = 0; i < 9; i++) {
            majhong[i]++;
            // 不能多于4张诈胡
            if (majhong[i] <= 4 && success(majhong.clone())) {
                res ++;
                System.out.print(i+1);
                System.out.print(" ");
            }
            majhong[i]--;
        }
        return res;
    }
    // 传入的是已经拷贝过的
    static boolean success(int[] mm) {
        for (int i = 0; i < 9; i++) {
            if (mm[i] >= 2) {
                // 考虑 作为雀头
                mm[i] -= 2;
                if (successThreeThree(mm)) {
                    return true;
                }
                mm[i] += 2;
            }
        }
        return false;
    }
    static boolean successThreeThree (int[] mm) {
        int sum = 0;
        for (int i = 0; i < 9; i ++) {
            if (mm[i] < 0) return false;
            sum += mm[i];
        }
        if (sum == 0) return true;
        for (int i = 0; i < 9; i++) {
            if (mm[i] != 0) {
                // 开始处理
                if (mm[i] >= 3) { // 刻字
                    mm[i] -= 3;
                    if (successThreeThree(mm)) return true;
                    mm[i] += 3;
                }
                if (i <= 6) { // 顺子
                    mm[i]--; mm[i+1]--; mm[i+2]--;
                    if (successThreeThree(mm)) return true;
                    mm[i]++; mm[i+1]++; mm[i+2]++;
                }
                break;
            }
        }
        return false;
    }
}


编辑于 2023-12-20 19:51:55 回复(0)

思路剖析:回溯法

1、手头有13张牌,向其中添加1张牌,看能否和牌;

2、遍历1-9大小的牌,每种数字的牌依次尝试用作雀头、顺子、刻子。

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    static boolean flag;

    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int[] nums = new int[10];
        for (int i = 0; i < 13; i++) {
            nums[cin.nextInt()]++;
        }

        for (int i = 1; i <= 9; i++) {
            if (nums[i] <= 3) {
                int[] card = Arrays.copyOf(nums, nums.length); // 深拷贝一份card
                card[i]++;
                if (isHu(card, 1, 0, 0)) {
                    flag = true;
                    System.out.print(i + " ");
                }
            }
        }
        if(flag == false) // 不能和牌
            System.out.print(0);
    }

    public static boolean isHu(int[] card, int start, int quetou, int lian){
        if(start>=10){
            // 胡牌条件:1个雀头,4个顺子或刻子(这里我一起称之为lian)
            if(quetou==1 && lian==4) return true;
            else  //全部搜索完都没和牌 
                return false;
        }
        // 从start开始,用作雀头
        if(card[start]>=2 && quetou==0){
            card[start] -=2;
            if(isHu(card, start, 1, lian)) return true;
            card[start] +=2;
        }
        // 从start开始,用作刻子
        if(card[start]>=3){
            card[start] -=3;
            if(isHu(card, start, quetou, lian+1)) return true; 
            card[start] +=3;
        }
        // 从start开始,用作顺子
        if (start + 2 <= 9 && card[start] > 0 && card[start + 1] > 0 && card[start + 2] > 0){
            card[start]--;
            card[start + 1]--;
            card[start + 2]--;
            if(isHu(card, start, quetou, lian+1)) return true;
            card[start]++;
            card[start + 1]++;
            card[start + 2]++;
        }
        // 当前牌无法组成雀头、顺子或刻子,直接跳到下一个数额的牌
        if(isHu(card, 1+start, quetou, lian)) return true;
        return false;
    }
}



发表于 2023-08-29 17:55:14 回复(0)
import java.util.*;

//从1-9尝试把第14张牌加入,然后按规律删除,删光了就递归返回true 
//先尝试删除雀头,再尝试删除刻子,最后尝试删除顺子
//要点:
//    1.每张牌最多4张
//    2.顺子和刻子可以混着出现,不一定要求4张顺子或4张刻子
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int[] arr = new int[10];
        int num = 0;
        boolean flag = false;
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            arr[in.nextInt()]++;
            num++;
        }
        num++;
        for (int i = 1; i < 10; i++) {
            if (arr[i] < 4) { //每张牌最多四个
                int[] tempArr = new int[10];
                for (int j = 0; j < arr.length; j++) {
                    tempArr[j] = arr[j];
                }
                tempArr[i]++;
                if (handle(tempArr, num)) {
                    System.out.print(i + " ");
                    flag = true;
                }
            }
        }
        if (!flag) {
            System.out.println(0);
        }
    }
    private static boolean handle(int[] array, int num) {
        if (num < 0 || num > 14) {
            return false;
        }
        if (num == 0) {
            return true;
        }
        if (num == 14) { //雀头
            for (int i = 1; i < 10; i++) {
                if (array[i] > 1) {
                    array[i] = array[i] - 2;
                    if (handle(array, num - 2)) { //递归返回
                        return true;
                    }
                    array[i] = array[i] + 2; //回溯
                }
            }
        } else {
            for (int i = 1; i < 10; i++) { //刻子
                if (array[i] > 2) {
                    array[i] = array[i] - 3;
                    if (handle(array, num - 3)) {
                        return true;
                    }
                    array[i] = array[i] + 3; //回溯
                }
            }
            for (int i = 1; i < 8; i++) { //顺子
                if (array[i] > 0 && array[i + 1] > 0 && array[i + 2] > 0) {
                    array[i]--;
                    array[i + 1]--;
                    array[i + 2]--;
                    if (handle(array, num - 3)) {
                        return true;
                    }
                    array[i]++; //回溯
                    array[i + 1]++;
                    array[i + 2]++;
                }
            }
        }
        return false;
    }
}


发表于 2023-08-08 20:34:15 回复(0)