找规律

题目链接-来源：力扣（LeetCode）

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

示例 1:

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

思路：

此题的关键是理清楚「顺子」的充要条件。

  • 首先，不难得出顺子的必要条件，一条顺当中的最大值 max 与最小值 min 之差，一定满足 max - min <= 4。
  • 其次，牌中除了代表「大小王」的 ‘0’ 以外，不得出现重复的牌。
    其实这两个条件同时满足的话也恰恰构成「顺子」的充要条件。
    于是我们只要统计 5 个数字当中的最大值，最小值，比较差值是否小于 4，并检查是否有重复值即可。判重的方法有很多，哈希表是通用方法；此外，本例中由于值域仅限于 [1, 13]，非常小，还可直接用「桶」来判重，效率会略快于哈希表。
    时间复杂度：O(n)
    空间复杂度：O(1)

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public boolean isStraight(int[] nums) {
        int[] bucket = new int[14];
        int max = 0, min = 14;
        for (int card : nums) {
            bucket[card]++;
            if (card != 0) {
                max = Integer.max(max, card);
                min = Integer.min(min, card);
                if (bucket[card] > 1) {
                    return false;
                }
            }
        }
        if (max - min > 4) {
            return false;
        }
        return true;
    }
}