baby-gin 算法

一、算法问题描述 随机取6张牌，牌上的数字为 0 ~ 9，可以重复，组成 baby-gin算法的条件：1个run + 1 个trip或者2个run或者2个trip 类型 一种组合为 run(1,2,3)，三张牌为顺子，另一种为trip(1,1,1),三张牌相同。 二、算法分析 1.暴力查询法（慢） （1）.先从6张牌中任意选取3张自由组合，也就是C6(3),共有20种不同的组合。

public class BabyGin { public static void main(String[] args){ int[] baby = {1,3,5,6,2,2}; BabyGin.select3(baby); } // 从 6 张牌中任意选取3张 public static int[] select3(int[] baby6){ int[] baby3 = new int[3]; // 创建一个存放组合的数组 int count = 0; for(int i = 0;i < baby6.length - 2;i++){ for(int j = i+1;j < baby6.length - 1;j++){ for(int k = j+1;k < baby6.length;k++){ baby3[0] = baby6[i]; baby3[1] = baby6[j]; baby3[2] = baby6[k]; // 20种排好序 System.out.println("第" + (count+1) + "种，[" + baby3[0] + "," + baby3[1] + "," + baby3[2] + "]"); count++; } } } return baby3; } }

（2）.将组合起来的20种组合分别排序，建议从小到大排序。

// 冒泡排序，将选取的3张牌从小到大排序 public static int[] bubble(int[] select3){ for(int i = 0;i < select3.length - 1;i++){ for(int j = i + 1;j < select3.length;j++){ if(select3[i] > select3[j]){ int temp = select3[j]; select3[j] = select3[i]; select3[i] = temp; } } } return select3; }

（3）.判断是否符合baby-gin算法需求，有一种run/trip组合，就计一次数，计满2次就符合baby-gin算法。

// 判断是否为 run / trip,前提条件是传入的数组已经从小到大排好序 public static boolean countRunOrTrip(int[] bubble) { boolean flag = false; if (bubble[0] == (bubble[1] - 1)) { if (bubble[1] == (bubble[2] - 1)) { flag = true; } } else if (bubble[0] == bubble[1]) { if (bubble[1] == bubble[2]) { flag = true; } } return flag; }

(4) 最终代码

package com.daxiong.encode; public class BabyGin { public static void main(String[] args) { int[] baby = { 1, 1, 2, 2, 3, 3 }; BabyGin.select3(baby); } // 从 6 张牌中任意选取3张 public static int[] select3(int[] baby6) { int[] baby3 = new int[3]; // 创建一个存放组合的数组 int count = 0; int yesCount = 0; for (int i = 0; i < baby6.length - 2; i++) { for (int j = i + 1; j < baby6.length - 1; j++) { for (int k = j + 1; k < baby6.length; k++) { baby3[0] = baby6[i]; baby3[1] = baby6[j]; baby3[2] = baby6[k]; // 20种排好序 System.out.println("第" + (count + 1) + "种，[" + baby3[0] + "," + baby3[1] + "," + baby3[2] + "]组合"); int[] bubble = BabyGin.bubble(baby3); System.out.print("排序后，[" + bubble[0] + "," + bubble[1] + "," + bubble[2] + "]"); boolean flag = BabyGin.countRunOrTrip(bubble); System.out.print(" ," + flag); System.out.println(); if (flag) { yesCount++; } count++; } } } if (yesCount >= 2) { System.out.println("YES 该数组为 baby-gin"); } else { System.out.println("NO 该数组不是 baby-gin"); } return baby3; } // 冒泡排序，将选取的3张牌从小到大排序 public static int[] bubble(int[] select3) { for (int i = 0; i < select3.length - 1; i++) { for (int j = i + 1; j < select3.length; j++) { if (select3[i] > select3[j]) { int temp = select3[j]; select3[j] = select3[i]; select3[i] = temp; } } } return select3; } // 判断是否为 run / trip,前提条件是传入的数组已经从小到大排好序 public static boolean countRunOrTrip(int[] bubble) { boolean flag = false; if (bubble[0] == (bubble[1] - 1)) { if (bubble[1] == (bubble[2] - 1)) { flag = true; } } else if (bubble[0] == bubble[1]) { if (bubble[1] == bubble[2]) { flag = true; } } return flag; } }

2.计数法（高效，快速） (1).先统计给定6张牌出现0~9的次数，并记录

// 统计0~9出现的频率 public static int[] countHZ(int[] baby){ int[] baby09 = {0,0,0,0,0,0,0,0,0,0}; // 0 ~ 9 出现的次数 for(int i = 0;i < baby.length;i++){ for(int j = 0; j < 9;j++){ if(baby[i] == j){ baby09[j] = baby09[j] + 1; } } } return baby09; }

（2）判断是否为 baby-gin 算法 需要注意：112233，这种情况，当判断0~9中123的个人分别都大于0时，同时减去1，还回剩下123，此时需要再次调用该方法，才会执行，所以这里采用递归调用的方式，如果调用完第一次后0~9中频率还大于0，此时再次调用

// 判断是否为 baby-gin 算法 public static int countBabyGin(int[] baby09) { int count = 0; int flag = 0; for (int i = 0; i < baby09.length - 2; i++) { if (baby09[i] >= 3) { // 说明至少有一个 trip baby09[i] = baby09[i] - 3; count++; } else if (baby09[i] > 0 && baby09[i + 1] > 0 && baby09[i + 2] > 0) { baby09[i] = baby09[i] - 1; baby09[i + 1] = baby09[i + 1] - 1; baby09[i + 2] = baby09[i + 2] - 1; count++; } if (baby09[i] != 0) { flag++; } } System.out.println("flag =" + flag); for (int i = 0; i < 9; i++) { System.out.println("baby09 =" + baby09[i]); } if(flag > 0){ // 递归调用，需要注意递归调用结束的条件 count = count + BabyGin2.countBabyGin(baby09); } return count; }

（3）整体代码

package com.daxiong.encode; public class BabyGin2 { public static void main(String[] args) { int[] baby = { 1, 1, 2, 2, 3, 3 }; System.out.println(BabyGin2.countBabyGin(BabyGin2.countHZ(baby))); int[] baby09 = BabyGin2.countHZ(baby); int countFlag = BabyGin2.countBabyGin(baby09); if(countFlag >= 2){ System.out.println("YES 该数组为 baby-gin"); } else{ System.out.println("NO 该数组不是 baby-gin"); } } // 统计0~9出现的频率 public static int[] countHZ(int[] baby) { int[] baby09 = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; // 0 ~ 9 出现的次数 for (int i = 0; i < baby.length; i++) { for (int j = 0; j < 9; j++) { if (baby[i] == j) { baby09[j] = baby09[j] + 1; } } } return baby09; } // 判断是否为 baby-gin 算法 public static int countBabyGin(int[] baby09) { int count = 0; int flag = 0; for (int i = 0; i < baby09.length - 2; i++) { if (baby09[i] >= 3) { // 说明至少有一个 trip baby09[i] = baby09[i] - 3; count++; } else if (baby09[i] > 0 && baby09[i + 1] > 0 && baby09[i + 2] > 0) { baby09[i] = baby09[i] - 1; baby09[i + 1] = baby09[i + 1] - 1; baby09[i + 2] = baby09[i + 2] - 1; count++; } if (baby09[i] != 0) { flag++; } } System.out.println("flag =" + flag); for (int i = 0; i < 9; i++) { System.out.println("baby09 =" + baby09[i]); } if(flag > 0){ // 递归调用，需要注意递归调用结束的条件 count = count + BabyGin2.countBabyGin(baby09); } return count; } }