535,剑指 Offer-扑克牌中的顺子

The real voyage of discovery consists not in seeking new landscapes, but in having new eyes. 

真正的发现之旅不在于找寻新的天地,而在于拥有新的眼光。

问题描述

从扑克牌中随机抽5张牌,判断是不是一个顺子,即这5张牌是不是连续的。2~10为数字本身,A为1,J为11,Q为12,K为13,而大、小王为 0 ,可以看成任意数字。A 不能视为 14。

 

示例 1:

输入: [1,2,3,4,5]

输出: True

示例 2:

输入: [0,0,1,2,5]

输出: True

 

限制:

  • 数组长度为 5 

  • 数组的数取值为 [0, 13] .

 

先排序

这题要求很简单

  • 假如没有大小王的情况下,只需要这5个数字不能有重复的,并且这5个数字中的最大值减去最小值等于4就行了。类似于[a,a+1,a+2,a+3,a+4]。

  • 假如有大小王的情况下,无论有一个还是有两个,我们只需要让大小王替换上面数组[a,a+1,a+2,a+3,a+4]中的任意元素,也能构成顺子。比如替换a,类似于[0,a+1,a+2,a+3,a+4],那么这个数组中的最大值减去最小值就是3了。

 

所以我们可以得出结论

  • 只要数组中的最大值减去最小值小于等于4

  • 数组中的元素不能有重复的

只要满足上面两个条件就是顺子

我们先对数组进行排序,然后再来求解,来看下代码

 1public boolean isStraight(int[] nums) {
2    //先对数组进行排序
3    Arrays.sort(nums);
4    //记录大小王的数量
5    int zero = 0;
6    for (int i = 0; i < 5; i++) {
7        //统计大小王的数量
8        if (nums[i] == 0) {
9            zero++;
10            continue;
11        }
12        //如果不是大小王,不能有重复的
13        if (i != 0 && nums[i] == nums[i - 1])
14            return false;
15    }
16    //最大牌和最小牌的差值小于等于4(这里zero是大小王是数量,
17    // nums[zero]表示排序后第一个非大小王的牌)
18    return nums[nums.length - 1] - nums[zero] <= 4;
19}

 

位运算解决

因为题中的最大数字是14,小于int的32位,所以我们可以用位运算来标记是否有重复的。原理和上面一样,只需要满足上面的两个条件即可。

来看下代码

 1public boolean isStraight(int[] nums) {
2    int bit = 0;//记录每个数字是否出现过
3    //记录数组中的最小数字
4    int min = Integer.MAX_VALUE;
5    //记录数组中的最大数字
6    int max = Integer.MIN_VALUE;
7    for (int num : nums) {
8        //如果是大小王则跳过
9        if (num == 0)
10            continue;
11        //判断相应的位置是否有数字,如果有数字
12        //说明之前出现过,也就是有重复的,
13        //直接返回false
14        if ((bit & (1 << num)) != 0)
15            return false;
16        //把相应的位置标记为有数字
17        bit |= 1 << num;
18        //记录遍历过的最大值和最小值
19        min = min > num ? num : min;
20        max = max < num ? num : max;
21    }
22    //最大牌和最小牌的差值小于等于4
23    return max - min <= 4;
24}

 

535,剑指 Offer-扑克牌中的顺子

533,剑指 Offer-最小的k个数

442,剑指 Offer-回溯算法解二叉树中和为某一值的路径

441,剑指 Offer-二叉搜索树的后序遍历序列

434,剑指 Offer-二叉树的镜像

 

 

截止到目前我已经写了500多道算法题了,为了方便大家阅读,我把部分算法题整理成了pdf文档,目前有900多页,大家可以在公众号中回复关键字“pdf”即可获取下载链接。

 

535,剑指 Offer-扑克牌中的顺子你点的每个赞,我都认真当成了喜欢
上一篇:1292 - Incorrect datetime value: '0000-00-00 00:00:00' for column


下一篇:LeetCode 11 Container With Most Water(分支​判断问题)