牛客网–字节跳动面试题–雀魂启动
博客说明
文章所涉及的资料来自互联网整理和个人总结，意在于个人学习和经验汇总，如有什么地方侵权，请联系本人删除，谢谢！
来源
链接：雀魂启动
来源：牛客网
题目
小包最近迷上了一款叫做雀魂的麻将游戏，但是这个游戏规则太复杂，小包玩了几个月了还是输多赢少。 于是生气的小包根据游戏简化了一下规则发明了一种新的麻将，只留下一种花色，并且去除了一些特殊和牌方式（例如七对子等），具体的规则如下：
- 总共有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张牌中，再取一张牌，取到哪几种数字牌可以和牌。
输入描述:
1
| 输入只有一行，包含13个数字，用空格分隔，每个数字在1~9之间，数据保证同种数字最多出现4次。
|
输出描述:
1
| 输出同样是一行，包含1个或以上的数字。代表他再取到哪些牌可以和牌。若满足条件的有多种牌，请按从小到大的顺序输出。若没有满足条件的牌，请输出一个数字0
|
示例1
输入
1
| 1 1 1 2 2 2 5 5 5 6 6 6 9
|
输出
说明
示例2
输入
1
| 1 1 1 1 2 2 3 3 5 6 7 8 9
|
输出
说明
1
| 用1做雀头，组123,123,567或456,789的四个顺子
|
示例3
输入
1
| 1 1 1 2 2 2 3 3 3 5 7 7 9
|
输出
说明
思路
1、统计所有数字出现的次数
2、循环补充一个数字，凑成14个数字
3、循环选取次数2以及以上的数字为雀头
4、排除雀头，递归判断剩下12个数字是否可以组成刻子或者顺子，如果能够符合规则，记录次数字
5、返回数据
代码
代码整理自牛客大佬kakifuu
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
| import java.util.ArrayList;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int[] state = new int[9], temp = new int[9];
ArrayList<Integer> res = new ArrayList<>();
for (int i = 0; i < 13; i++) {
int num = scanner.nextInt();
state[num - 1]++;
}
for (int i = 0; i < 9; i++) {
if (state[i] < 4) {
int num = i + 1;
System.arraycopy(state, 0, temp, 0, 9);
temp[i]++;
if (run(temp, 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());
}
}
public static boolean run(int[] temp, int count, boolean hasRun) {
if (count == 0) {
return true;
}
if (!hasRun) {
for (int i = 0; i < 9; i++) {
if (temp[i] >= 2) {
temp[i] -= 2;
if (run(temp, count - 2, true)) {
return true;
}
temp[i] += 2;
}
}
return false;
} else {
for (int i = 0; i < 9; i++) {
if (temp[i] > 0) {
if (temp[i] >= 3) {
temp[i] -= 3;
if (run(temp, count - 3, true)) {
return true;
}
temp[i] += 3;
}
if (i + 2 < 9 && temp[i + 1] > 0 && temp[i + 2] > 0) {
temp[i]--;
temp[i+1]--;
temp[i+2]--;
if(run(temp,count-3,true)){
return true;
}
temp[i]++;
temp[i+1]++;
temp[i+2]++;
}
}
}
}
return false;
}
}
|
感谢
牛客网
字节跳动
以及勤劳的自己
