首页 > 试题广场 >

雀魂启动！

[编程题]雀魂启动！

热度指数：16444 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

小包最近迷上了一款叫做雀魂的麻将游戏，但是这个游戏规则太复杂，小包玩了几个月了还是输多赢少。

于是生气的小包根据游戏简化了一下规则发明了一种新的麻将，只留下一种花色，并且去除了一些特殊和牌方式（例如七对子等），具体的规则如下：

总共有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,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

输出

说明

来任何牌都无法和牌

备注:

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

对于20%的数据，保证和牌时一定是4个刻子+雀头的形式

算法知识视频讲解

Java

青春猪头少年不会没有offer

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)

Java

烤串不吃串

愚蠢的枚举法。

枚举加入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)

Java

刷题的四郎

思路剖析：回溯法

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)

Java

neukfc

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)

Java

牛客196305255号

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            Map<Integer,Integer> map=new TreeMap<>();
            for(int i=0;i<13;i++){
                int n=sc.nextInt();
                map.put(n,map.getOrDefault(n,0)+1);
            }
            boolean flag=true;
            for(int n=1;n<=9;n++) {
                if(map.getOrDefault(n, 0)<4) {
                    map.put(n,map.getOrDefault(n, 0)+1);
                    if(solve1(map)){
                        flag=false;
                        System.out.print(n+" ");
                    }
                    map.put(n, map.get(n)-1);
                }
            }
            if(flag)
                 System.out.print(0);
            System.out.println();
        }
    }
    private static boolean solve1(Map<Integer,Integer> map) {
		for(int key:map.keySet()) {
			int tmp=map.get(key);
			if(tmp>=2) {
				map.put(key,tmp-2);
				if(solve2(map)) {
					map.put(key, tmp);
					return true;
				}
				map.put(key, tmp);
			}
		}
		return false;
	}
	private static boolean solve2(Map<Integer,Integer> map) {
		Map<Integer,Integer> tmp=new TreeMap<>(map);
		for(int key:tmp.keySet()) {
			int m=tmp.get(key);
			if(m>=3) {
				tmp.put(key,m-3);
			}	
			m=tmp.get(key);
			if(m>=1) {
				if(map.getOrDefault(key+1, 0)>=m&&map.getOrDefault(key+2, 0)>=m) {
					tmp.put(key,0);
					tmp.put(key+1,tmp.get(key+1)-m);
					tmp.put(key+2,tmp.get(key+2)-m);
				}else {
					return false;
				}
			}
		}
		return true;
	}
}

发表于 2021-03-17 17:25:42 回复(0)

Java

tatsuu

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;


public class Main {
	public static boolean checkRon(int d,int[]data) {
		if(data[d]<2)return false;
		data[d] -= 2;
		int num = 0;
		for (int i = 0; i < 9; i++) {
			if (data[i] == 0) {
				continue;
			}
			if (data[i] == 1) {
				if (i<7&&data[i + 1] >= 1 && data[i + 2] >= 1) {
					data[i]--;
					data[i + 1]--;
					data[i + 2]--;
					num++;
					if (num == 4)
						return true;
				} else
					return false;
			} else if (data[i] == 2) {
				if (i<7&&data[i + 1] >= 2 && data[i + 2] >= 2) {
					data[i] -= 2;
					data[i + 1] -= 2;
					data[i + 2] -= 2;
					num+=2;
					if (num == 4)
						return true;
				} else
					return false;
			} else if (data[i] == 3) {
				data[i] -= 3;
				num++;
				if (num == 4)
					return true;
			} else if (data[i] == 4) {
				if (i<7&&data[i + 1] == 4 && data[i + 2] == 4)
					return true;
				else if (i<7&&data[i + 1] >= 1 && data[i + 2] >= 1) {
					data[i]--;
					data[i + 1]--;
					data[i + 2]--;
					num+=2;
					if (num == 4)
						return true;
				} else
					return false;
			}
		}
		if (num != 4)
			return false;
		else
			return true;
	}
	public static void main(String[] args) {
		int[]data=new int[9];
		Scanner sc=new Scanner(System.in);
		Set<Integer> ronSet=new HashSet<Integer>();
		for(int i=0;i<13;i++) {
			int index=sc.nextInt()-1;
			data[index]++;
		}
		for(int i=0;i<9;i++) {
            if(data[i]==4)
                continue;
			int[] a=new int[9];
			for(int j=0;j<9;j++) {
				System.arraycopy(data, 0, a, 0, 9);
				a[i]++;
				if(checkRon(j, a)) {
					ronSet.add(i+1);
				}
			}
			
				
		}
		for(int i:ronSet) {
			System.out.print(i+" ");
		}
		
	}

}

发表于 2020-03-11 23:43:18 回复(0)

Java

Enowi

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int[] input = new int[13];
for (int i = 0; i < 13; i++) {
int num = sc.nextInt();
input[i] = num;
}

ArrayList<Integer> res = new ArrayList<>();
for (int i = 1; i < 10; i++) {
int[] list = new int[input.length + 1];
for (int j = 0; j < input.length; j++) {
list[j] = input[j];
}
if (timesOfI(list, i) == 4) {
continue;
}
list[input.length] = i;
if (isHe(list)) {
res.add(i);
}
}
for (Integer i:res) {
System.out.print(i+" ");
}
}

private static int timesOfI(int[] list, int i) {
int count = 0;
for (int j = 0; j < list.length; j++) {
if (list[j] == i) {
count++;
}
}
return count;
}

public static boolean isHe(int[] number) {
int length = number.length;
if (length == 0)
return true;
Arrays.sort(number);
//如果没出现雀头，且第一个数字出现的次数超过一次，且去掉雀头剩下的数能组成和牌
if (length % 3 != 0 && Count(number) > 1 && isHe(Arrays.copyOfRange(number, 2, length))) {
return true;
}
//如果第一个数字出现大于等于3次，且去掉此刻子后剩下的数能组成和牌
if (Count(number) >= 3 && isHe(Arrays.copyOfRange(number, 3, length))) {
return true;
}
//如果出现顺子，且去掉此顺子后剩下的数字能组成和牌
int num0 = number[0];
int num1 = number[0] + 1;
int num2 = number[0] + 2;
if (Contains(number, num1) && Contains(number, num2)
&& isHe(Remove(number, num0, num1, num2))) {
return true;
}
return false;
}

//移除数组中的三个数
private static int[] Remove(int[] number, int num0, int num1, int num2) {
int[] res = new int[number.length - 3];
int c0 = 0;
int c1 = 0;
int c2 = 0;
int j = 0;
for (int i = 0; i < number.length; i++) {
if (number[i] == num0 && c0 == 0) {
c0++;
continue;
}
if (number[i] == num1 && c1 == 0) {
c1++;
continue;
}
if (number[i] == num2 && c2 == 0) {
c2++;
continue;
}
res[j++] = number[i];
}
return res;
}

private static boolean Contains(int[] number, int num1) {
for (int i = 0; i < number.length; i++) {
if (num1 == number[i]) {
return true;
}
}
return false;
}

private static int Count(int[] number) {
int num = 1;
for (int i = 1; i < number.length; i++) {
if (number[i] == number[0]) {
num++;
}
}
return num;
}
}

发表于 2019-09-14 21:16:20 回复(0)

Java

1+½+¼+⅛+...

import java.util.ArrayList;
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int[] card = new int[13];
        for(int i = 0; i < 13; i++) {
        	card[i] = input.nextInt();
        }
        input.close();
        Solution(card);       
    }
    public static void Solution(int[] card){
    	int[] num = new int[9];
    	ArrayList<Integer> al = new ArrayList<Integer>();
    	for(int i = 0; i <13; i++) {
    		num[card[i]-1]++;
    	}
    	for(int i = 0; i < 9; i++) {
    		if(num[i] != 4) {
    			num[i] ++;
    			if(hupai(num, 0)) {
    				al.add(i+1);
    			}
    			num[i] --;
    		}
    	}
    	if(al.isEmpty())
    		System.out.println(0);
    	else{
    		System.out.print(al.get(0));
        	for(int i = 1; i < al.size(); i++) 
        		System.out.print(" "+al.get(i));
    	}
    }
    
    public static boolean hupai(int[] num1, int head) {
		int[] num = num1.clone();
    	for(int i = 0; i < 9; i++) {
			if(num[i] != 0) {
				if(num[i] == 1) {
					if(i + 2 < 9 && num[i+1] > 0 && num[i+2] > 0) {
						num[i] --;
						num[i+1] --;
						num[i+2] --;
						return hupai(num, head);
					}else
						return false;
					
				}else if(num[i] == 2) {
					if(head == 0) {
						num[i] -= 2;
						if(hupai(num, 1))
							return true;
						else if(i + 2 < 9 && num[i+1] > 1 && num[i+2] > 1){
							num[i+1] -= 2;
							num[i+2] -= 2;
							return hupai(num, 0);
							}else
								return false;
						}else {
							if(i + 2 < 9 && num[i+1] > 1 && num[i+2] > 1) {
								num[i] -= 2;
								num[i+1] -= 2;
								num[i+2] -= 2;
								return hupai(num, 1);
							}else
								return false;
						}
				}else {
					if(head == 0) {
						num[i] -= 2;
						if(hupai(num, 1)) {
							return true;
						}else {
							num[i] --;
							return hupai(num, 0);
						}
					}else {
						num[i] -= 3;
						return hupai(num, 1);
					}
				}
			}
		}
		return true;    	
    }    
}

编辑于 2019-09-05 15:23:01 回复(0)

Java

kakifuu

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)

提交观点

问题信息

C++工程师 iOS工程师安卓工程师运维工程师算法工程师测试工程师 PHP工程师动态规划模拟穷举字节跳动 2019 Java工程师

上传者：小小

难度：

13条回答 603收藏 29387浏览

通过挑战的用户

查看代码

Easonfan

2023-03-09 11:10:36
小师弟想要offer

2023-02-20 16:42:13
牛客36908...

2023-02-13 14:51:05
spmomo

2023-02-10 20:36:40
Elizabe...

2022-12-05 11:56:41

雀魂启动！

输入描述:

输出描述:

输入

输出

说明

输入

输出

说明

输入

输出

说明

备注:

问题信息

热门推荐

通过挑战的用户

相关试题