關注下方公眾號，分享硬核知識

? 作者 | 小夕? 出品 | 公眾號：小夕學算法

題目

從撲克牌中隨機抽5張牌，判斷是不是一個順子，即這5張牌是不是連續(xù)的。2～10為數(shù)字本身，A為1，J為11，Q為12，K為13，而大、小王為 0 ，可以看成任意數(shù)字。A 不能視為 14。

示例?1:

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

示例?2:

輸入: [0,0,1,2,5] 輸出: True

限制：

數(shù)組長度為 5

數(shù)組的數(shù)取值為 [0, 13] .

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/bu-ke-pai-zhong-de-shun-zi-lcof
著作權歸領扣網(wǎng)絡所有。商業(yè)轉載請聯(lián)系官方授權，非商業(yè)轉載請注明出處。


本題目中的順子，只是代表從1開始的到13, 和現(xiàn)實玩牌的順子有一點差別的就是，10 J Q K A 不構成本題目中的順子：

思路

如果5張牌中無大小王

如果要構成是順子的情況，那么必然需要連起來,比如像下圖中的 1,2,3,4,5.

由于必須構成順子，所以最大值5減去最小值1等于4，如果差值大于4，那么必然不是順子了。

如果 5 張牌中有1個大小王

有一個大小王，也就是有一個數(shù)字 0，對于我們舉的例子1,2,3,4,5,中有一個數(shù)字被 0進行替換了。

如果想要構成順子，那么必須是1,2,3,4,5中的任意一個被0替換了，因為想要0可以變成任意的一個數(shù)字

1 被替換

除了0以為，最大差值5-2是3.

2 被替換

除了0以為，最大差值5-1是4.

3 被替換

除了0以為，最大差值5-1是4. ####4 被替換

除了0以為，最大差值5-1是4.

5 被替換

除了0以為，最大差值4-1是3.

上述5種情況，都是可以構成順子的情況。

從上述 5 種情況可以看出來，只要是能構成順子的情況，除了0以為，那么最大值和最小值差值必然小于等于4

如果 5 張牌中有2個大小王

總共有上述10種情況，觀察這10種情況知道：

除了0以為，如果可以構成順子，最大值，最小值的差必然小于等于 4.

思路總結

從上面的流程中可以知道本題的算法思路：

• 遍歷5張牌，遇到是0的話直接跳過
• 遍歷的時候有集合set把數(shù)存在里面，如果有重復，那么必然有對子，有對子必然無法變成順子
• 用一個max 存最大值，有一個 min 存最小值，如果最后max和mix的差值小于等于4，那么說明是順子。

動畫

代碼·

Python

class?Solution:
????def?isStraight(self,?nums:?List[int])?->?bool:
????????repeat?=?set()
????????ma,?mi?=?0,?14
????????for?num?in?nums:
????????????if?num?==?0:?continue?#?跳過大小王
????????????ma?=?max(ma,?num)?#?最大牌
????????????mi?=?min(mi,?num)?#?最小牌
????????????if?num?in?repeat:?return?False?#?若有重復，提前返回?false
????????????repeat.add(num)?#?添加牌至?Set
????????return?ma?-?mi?#?最大牌?-?最小牌?


Java

class?Solution?{
????public?boolean?isStraight(int[]?nums)?{
????????Set?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?????}
}


C

class?Solution?{
public:
????bool?isStraight(vector