麻将胡牌判定的问题

问题描述:

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

相关文章

来自专栏于晓飞的专栏

读 Java TimSort算法 源码 笔记

本来准备看Java容器源码的。但是看到一开始发现Arrays这个类我不是很熟,就顺便把Arrays这个类给看了。Arrays类没有什么架构与难点,但Arrays...

702
来自专栏java学习

来测试一下你对数据结构中的栈和队列的了解有多少?

选择题 1.向一个栈顶指针为top的链栈中插入一个结点s,执行( )。 A.top.next=s; B.s.next=top.next ;top.next=s;...

5349
来自专栏微信公众号:Java团长

初学者应该了解的数据结构:Array、HashMap 与 List

当开发程序时,我们(通常)需要在内存中存储数据。根据操作数据方式的不同,可能会选择不同的数据结构。有很多常用的数据结构,如:Array、Map、Set、List...

632
来自专栏每日一篇技术文章

Swift3.0 - 枚举

602
来自专栏浪淘沙

Scala学习笔记

大数据框架(处理海量数据/处理实时流式数据) 一:以hadoop2.X为体系的海量数据处理框架         离线数据分析,往往分析的是N+1的数据  ...

1513
来自专栏我是攻城师

JDK8中HashMap的工作原理剖析

42511
来自专栏决胜机器学习

PHP数据结构(二十一) ——希尔排序

PHP数据结构(二十一)——希尔排序 (原创内容,转载请注明来源,谢谢) 一、概述 希尔排序,又称缩小增量排序,也属于插入排序类方法,时间上有较大改进。前面...

3257
来自专栏Java帮帮-微信公众号-技术文章全总结

Java基础-03(02).总结运算符、键盘录入、if语句

(3)案例: A:比较两个数是否相等 B:获取两个数中的最大值 C:获取三个数中的最大值(if语句的嵌套) D:根据成绩输出对应的等级 E:根据月份...

3767
来自专栏数据之美

基于堆实现的优先级队列:PriorityQueue 解决 Top K 问题

1、认识 PriorityQueue PriorityQueue是从JDK1.5开始提供的新的数据结构接口,它是一种基于优先级堆的极大优先级队列。优先级队...

2445
来自专栏Dawnzhang的开发者手册

ArrayMap和HashMap区别

Hash,也可以称为“散列”,就是把任意长度的输入,通过散列算法,变换成固定长度的输出,该输出就是散列值。这是一种压缩映射,也就是,散列值的空间通常远小于输入的...

533

扫码关注云+社区