C语言判断5张牌是不是顺子,leetcode剑指 Offer 61(扑克牌中的顺子)–Java语言实现

  • Post author:
  • Post category:java


求:

从扑克牌中随机抽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] .

解:

有2种常规做法,不管是哪种做法,注意如果数组中出现了相同的元素,说明有对子,那么肯定无法组成顺子,这种情况在程序里应该有判断。

1、排序后比较

先排序,然后先获取0的数量。(也可以放到一个for循环里统一拿,因为已经排序,最后一位数是不是0不影响结果)

遍历数组,如果相邻元素的差大于1,则考虑使用0进行填补,如果遍历后发现0的个数不足以填补,返回false,否则返回true。

public booleanisStraight(int[] nums) {

intN = nums.length;Arrays.sort(nums);intzeroCount = 0;for(inti = 0;i < N – 1;i++) {

if(nums[i] == 0) ++zeroCount;else if(nums[i] == nums[i + 1]) return false;else if(nums[i + 1] – nums[i] > 1)

zeroCount -= (nums[i + 1] – nums[i] – 1);}

returnzeroCount >= 0;}

时间复杂度 O(Nlog N),N个元素排序复杂度为NlogN

空间复杂度 :O(1)

2、使用HashSet比较

这里没有记录0的个数,而是直接跳过了0。之所以可以这么操作的逻辑是我们发现,不考虑0来遍历数组,如果最大最小值之差小于5(题目要求的张数),则可以形成顺子,否则不能。这里同样需要去重,我们考虑使用Hashset去重,一个元素在遍历时,如果发现hashSet已经有了,说明在之前出现过,返回false。

这个方法的好处是不需要进行排序。

public booleanisStraight(int[] nums) {

intN = nums.length;intmin = 14,max = 0;Set iSet = newHashSet<>();for(inti = 0;i < N;i++) {

if(nums[i] == 0) continue;min = Math.min(min,nums[i]);max = Math.max(max,nums[i]);if(iSet.contains(nums[i])) return false;iSet.add(nums[i]);}

returnmax – min < 5;}