问题描述:
前面去面试,需要设计一个算法检测麻将是否可以胡牌。简单描述如下:胡牌的规则为,有一个同样的两张牌做将,然后剩下的组成ABC或者AAA的形式。假设有13张牌,都是万字。不存在碰或者杠等特殊情况,判断这13张牌是否可以听牌。如果可以,输出此时作为将的牌和可以听的牌。
实现的代码如下:
1 package com.rampage.algorithm.base;
2
3 import java.util.ArrayList;
4 import java.util.List;
5
6 /**
7 * 麻将游戏
8 * @author zyq
9 *
10 */
11 public class MahjongGame {
12 public static void main(String[] args) {
13 MahjongGame game = new MahjongGame();
14
15 // 可能有两组将的情况下
16 int[] arr = {1, 1, 1, 1, 3, 3, 2, 2, 5, 6, 7, 8, 8};
17 game.detectHu(arr);
18 }
19
20 /**
21 * 校验是否可以胡牌,并且输出所有胡牌情况下将和听的牌。13张牌的数组,假设都是万(如果包括其他的花色其实道理一样)。胡牌的规则为:有一个同样的两张牌做将,然后剩下的组成ABC或者AAA的形式。
22 * @param arr
23 */
24 private void detectHu(int[] arr) {
25 if (arr == null || arr.length != 13) {
26 System.out.println("Illegal array for mahjong game!");
27 return;
28 }
29
30 // 定义一个新的数组,存储每一个万出现的次数
31 int[] countArr = new int[10];
32 for (int i=0; i<arr.length; i++) {
33 countArr[arr[i]]++;
34 }
35
36 // 我们的算法思路是:先依次假设每一个牌作为将,剩下牌的再去判断是否满足ABC的形式。
37 List<Hu> possibleHu = new ArrayList<Hu>(); // 存储胡的结果列表
38 for (int i=1; i<=9; i++) {
39 // 如果对应的万字牌个数小于两个,则不可能做将。这里直接忽略。
40 if (countArr[i] < 2) {
41 continue;
42 }
43
44 // 用一个全新的数组,判断数组中的数是否都满足ABC的形式。
45 int[] newArr = new int[countArr.length];
46 List<Integer> tings = new ArrayList<Integer>();
47
48 // 我们可以假设每次听的不同的万字牌,将要胡的万字牌加进去之后,如果剩下的牌满足AAA或者ABC模式,则证明可以听该万字牌
49 for (int j=1; j<=9; j++) {
50 System.arraycopy(countArr, 0, newArr, 0, newArr.length);
51 newArr[i] -= 2; // 对应做将的万字个数减2
52 if (j == i && newArr[j] + 1 > 2) { // 不能超过4个牌
53 continue;
54 } else {
55 if (newArr[j] + 1 > 4) { // 不能超过4个牌
56 continue;
57 }
58 newArr[j] += 1; // 假设听该万字牌
59 }
60
61 if (isABCOrAAAPattern(newArr)) {
62 tings.add(j);
63 }
64 }
65
66 // 当以i为将的时候存在可以听得牌,则证明该将可以胡。将其存入结果列表
67 if (!tings.isEmpty()) {
68 Hu newOne = new Hu();
69 newOne.jiang = i;
70 newOne.tings = tings;
71 possibleHu.add(newOne);
72 }
73
74 }
75
76 if (possibleHu.isEmpty()) {
77 System.out.println("The mahjong could not hu!");
78 } else {
79 System.out.println("The mahjong could hu!Possible hu method show as below:");
80 for (Hu one : possibleHu) {
81 System.out.print("Jiang:" + one.jiang + ", ting:");
82 for (Integer ting : one.tings) {
83 System.out.print(ting + "|");
84 }
85 System.out.println();
86 }
87 }
88 }
89
90 /**
91 * 校验数组是否满足ABC形式
92 * @param newArr
93 */
94 private boolean isABCOrAAAPattern(int[] newArr) {
95 for (int i=0; i<newArr.length - 2; i++) {
96 // 一旦有3张的情况,必然只能是AAA类型的,其他情况都是ABC类型的
97 while (newArr[i] > 0 && newArr[i] != 3) {
98 newArr[i] -= 1;
99 if (newArr[i + 1] == 0) {
100 return false;
101 } else {
102 newArr[i + 1] -= 1;
103 }
104
105 if (newArr[i + 2] == 0) {
106 return false;
107 } else {
108 newArr[i + 2] -= 1;
109 }
110 }
111 }
112
113 // 剩下的如果每个万字牌的个数为0或者3。才表示可以听此牌。
114 for (int i=0; i<newArr.length; i++) {
115 if (newArr[i] != 0 && newArr[i] != 3) {
116 return false;
117 }
118 }
119
120 return true;
121 }
122
123 /**
124 * 定义胡牌的情况,将和听的牌
125 * @author zyq
126 *
127 */
128 private class Hu {
129 private int jiang;
130 private List<Integer> tings; // 可能听的牌不止一张
131 }
132 }
输出的结果如下:
1 The mahjong could hu!Possible hu method show as below:
2 Jiang:1, ting:8|
3 Jiang:8, ting:4|