数据结构与算法--判断扑克牌是否顺子

灰太狼 2022-10-13 05:19 5阅读 0赞

#### 扑克牌的顺子 ####

*  题目：从扑克牌中随机抽取N张牌，判断是否顺子，即这N张牌是不是连续的。扑克牌中2 ~ 10 为数字，11代表j，12代表k，13代表K，并且大小王可以代表任意数字。

#### 抽象概念 ####

*  将扑克牌抽象成计算机语言，数字自然好处理，n张牌用 n 个元素的数组标识，大小王特殊数字，我们用0 标识。
 *  分析：
    
     *  用数组标识，那么问题变为判断数组是否连续，最直观就是排序了
     *  此处有特殊因素0，也就是即使不连续，但是差值 小于 0 的个数还是看成连续
     *  有对子必然不是顺子，除了0 以外
     *  案例\{2,3，4,0，6,8，0\}，两个0 分别代表
     *  那么需做三件事，排序，统计0 个数，检查是否连续，判断对子
        
         *  排序：因为是固定的范围，此处最合适的排序算法是桶排序，[在之前的排序总结中有所有排序动图][Link 1]，此处不再详细讲解，时间复杂度O(n)，空间复杂度O(1)
         *  统计0 个数，因为在检查是否连续时候，已经是排序的状态，那么先遇到的必然是0（如果0 存在）可以顺带统计，时间复杂度O(n)
         *  遍历检查，时间复杂度O(n)
 *  经如上分析有如下代码

/** * 扑克牌中随机抽 5 张牌， 判断是否是顺子，注意大小王可以替任何数字 * @author liaojiamin * @Date:Created in 15:07 2021/7/6 */
    public class ValidateContinuous { 
        public static void main(String[] args) { 
            int[] array = new int[60];
            int position = 0;
            for (int i = 0; i <= 13; i++) { 
                if(i==0){ 
                    for (int i1 = 53; i1 < 60; i1++) { 
                        array[i1] = 0;
                        position+=1;
                    }
                }else { 
                    for (int i1 = 0; i1 < 4; i1++) { 
                        array[position]=i;
                        position++;
                    }
                }
            }
            System.out.println(isContinuous(array, 5));
    
        }
    
        /** * 用数组标识抽取出来的扑克，0-标识大小王，11-j，12-Q，13K * 先排序，在判断各个数据直接的间隔差距，差距大于0的数量则不连续 * 有0以外的对子，不连续 * */
        public static boolean isContinuous(int[] pukeArray, int number){ 
            int[] array = new int[number];
            Random random = new Random();
            for (int i = 0; i < array.length; i++) { 
                int card = pukeArray[random.nextInt(pukeArray.length -1)];
                System.out.println(card);
                array[i] = card;
            }
            int[] bucketArray = bucketSort(array);
            int position = 0;
            for (int i = 0; i < bucketArray.length; i++) { 
                if(i != 0 && bucketArray[i] >= 2){ 
                    return false;
                }
                for (int i1 = 0; i1 < bucketArray[i]; i1++) { 
                    array[position] = i;
                    position++;
                }
            }
            Integer countZero = 0;
            for (int i = 0; i < array.length; i++) { 
                if(array[i] == 0){ 
                    countZero ++;
                }
                if(i > 0 && array[i-1] != 0){ 
                    if(array[i] - array[i-1] > countZero){ 
                        return false;
                    }
                }
            }
            return true;
        }
    
        /** * 桶排序:此处返回通，不返回排序后的数组，用来判断是否有除了0 以外的对子 * */
        public static int[] bucketSort(int[] array){ 
            if(array == null || array.length<=0){ 
                return array;
            }
            int[] bucketArray = new int[14];
            for (int i : array) { 
                bucketArray[i]+=1;
            }
            return bucketArray;
        }
    }

*  如上我们在桶排序时候做了一点小优化，直接返回的桶而不是排序后的数据，在归纳桶中数据时候顺便判断是否存在对子
 *  以上随机选取n 张牌时候并不规范，因为没将已经选取的牌踢出 扑克牌总数组，此处我们只为说明之后的算法流程，不考虑这个
 *  算法时间复杂度O(n)，空间复杂度O(1)

[上一篇：数据结构与算法–翻转单词顺序][Link 2]  
[下一篇：数据结构与算法–我们来玩丢手绢（约瑟夫环问题）][Link 3]

[Link 1]: https://blog.csdn.net/liaojiamin0102/article/details/109512635
[Link 2]: https://blog.csdn.net/liaojiamin0102/article/details/118406709
[Link 3]: https://blog.csdn.net/liaojiamin0102/article/details/118552557