麻将胡牌判定的问题

问题描述:

前面去面试,需要设计一个算法检测麻将是否可以胡牌。简单描述如下:胡牌的规则为,有一个同样的两张牌做将,然后剩下的组成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 }
MahjongGame


输出的结果如下:

麻将胡牌判定的问题麻将胡牌判定的问题
1 The mahjong could hu!Possible hu method show as below:
2 Jiang:1, ting:8|
3 Jiang:8, ting:4|
Result

 

黎明前最黑暗,成功前最绝望!
上一篇:photoshop 简单四步把风景照片转成淡油画效果


下一篇:Photoshop 地狱火文字特效