麻将胡牌判定的问题

问题描述:

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

python易错盲点排查之+=与+的区别分析以及一些赋值运算踩过的坑

问题1. int和list是不一样的 >>> a=1 >>> b=a >>> a+=1 >>> a,b (2, 1) >>> a=[1,2,3,4] >>> b...

2649
来自专栏Golang语言社区

第五节:Go语言常量

干货来了!!!为了让更多的小伙伴喜欢Golang、加入Golang之中来,Golang语言社区发起人彬哥联合业界大牛共同推出了Go语言基础、进阶、提高课程,目前...

702
来自专栏写代码的海盗

维多利亚的秘密 golang入坑系列

原文在gitbook,字字原创,版权没有,转载随意。 在写本文的前一天,2017维密在上海开始了。 为了纪念屌丝界的盛世,特为本节起名维多利亚的秘密。现在的社会...

3378
来自专栏iKcamp

翻译连载 |《你不知道的JS》姊妹篇 |《JavaScript 轻量级函数式编程》- 第 4 章:组合函数

原文地址:Functional-Light-JS 原文作者:Kyle Simpson-《You-Dont-Know-JS》作者 JavaScript轻量级函数式...

2006
来自专栏AzMark

Python函数

1407
来自专栏Android自学

Java中选择排序,冒泡排序等排序方法示例

1325
来自专栏web编程技术分享

js常用方法和一些封装(1)1.字符串相关2.数组相关

3379
来自专栏数据结构与算法

洛谷P2742 【模板】二维凸包

2、若$p_{i{(i > 3)}}$在直线$p_{i - 1}, p_{i - 2}$的右侧,则不断的弹出栈顶,直到该点在直线左侧

422
来自专栏Golang语言社区

Golang语言--slice 切片原理

golang 中的 slice 非常强大,让数组操作非常方便高效。在开发中不定长度表示的数组全部都是 slice 。但是很多同学对slice 的模糊认识,造成认...

3579
来自专栏用户2442861的专栏

C++智能指针简单剖析

http://blog.csdn.net/lanxuezaipiao/article/details/41603883

191

扫描关注云+社区