[剑指offer]面试题第[61]题[JAVA][扑克牌中的点数][HashSet][数组]

ゝ一纸荒年。 2023-02-26 09:30 5阅读 0赞

#### 【问题描述】\[简单\] ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]

#### 【解答思路】 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]

###### 1. 集合 Set + 遍历 ######

![在这里插入图片描述][20200715100805271.png]  
**时间复杂度：O(N) 空间复杂度：O(N)**  
![在这里插入图片描述][2020071510082393.png]

class Solution { 
        public boolean isStraight(int[] nums) { 
            Set<Integer> repeat = new HashSet<>();
            int max = 0, min = 14;
            for(int num : nums) { 
                if(num == 0) continue; // 跳过大小王
                max = Math.max(max, num); // 最大牌
                min = Math.min(min, num); // 最小牌
                if(repeat.contains(num)) return false; // 若有重复，提前返回 false
                repeat.add(num); // 添加此牌至 Set
            }
            return max - min < 5; // 最大牌 - 最小牌 < 5 则可构成顺子
        }
    }

###### 2. 排序 + 遍历 ######

![在这里插入图片描述][20200715101333901.png]  
**时间复杂度：O(N) 空间复杂度：O(1)**  
![在这里插入图片描述][20200715101340545.png]

class Solution { 
        public boolean isStraight(int[] nums) { 
            int joker = 0;
            Arrays.sort(nums); // 数组排序
            for(int i = 0; i < 4; i++) { 
                if(nums[i] == 0) joker++; // 统计大小王数量
                else if(nums[i] == nums[i + 1]) return false; // 若有重复，提前返回 false
            }
            return nums[4] - nums[joker] < 5; // 最大牌 - 最小牌 < 5 则可构成顺子
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 2]

public class isStraight { 
        public boolean isStraight(int[] nums) { 
            Arrays.sort(nums);
            int countZero = 0, i = 0, gap = 0;
            for (; i < 5 && nums[i] == 0; i++)
                countZero++;
            for (i = i + 1; i < 5; i++) { 
                if (nums[i] == nums[i - 1])
                    return false;
                if (nums[i] - nums[i - 1] > 1)
                    gap += nums[i] - nums[i - 1] - 1;
            }
            return countZero >= gap;
        }
    }

#### 【总结】 ####

###### 1.连续数组问题 HashSet/找规律 遍历 ######

###### 2.头尾相减 相邻相减 找找规律 ######

转载链接：https://leetcode-cn.com/problems/bu-ke-pai-zhong-de-shun-zi-lcof/solution/61java-pai-xu-tong-ji-0he-kong-que-de-ge-shu-xiang/

转载链接：https://leetcode-cn.com/problems/bu-ke-pai-zhong-de-shun-zi-lcof/solution/mian-shi-ti-61-bu-ke-pai-zhong-de-shun-zi-ji-he-se/

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]: /images/20230209/b41874178cf14c75a2adef4ecb6e6df0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]: /images/20230209/9a6fcaa5dc4a4f39b47abd7d79a72a3e.png
[20200715100805271.png]: https://img-blog.csdnimg.cn/20200715100805271.png
[2020071510082393.png]: https://img-blog.csdnimg.cn/2020071510082393.png
[20200715101333901.png]: https://img-blog.csdnimg.cn/20200715101333901.png
[20200715101340545.png]: https://img-blog.csdnimg.cn/20200715101340545.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200715101402720.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70