關(guān)注下方公眾號(hào)，分享硬核知識(shí)

? 作者 | 小夕? 出品 | 公眾號(hào)：小夕學(xué)算法

題目

從撲克牌中隨機(jī)抽5張牌，判斷是不是一個(gè)順子，即這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ù)組長(zhǎng)度為 5

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

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


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

思路

如果5張牌中無大小王

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

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

如果 5 張牌中有1個(gè)大小王

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

如果想要構(gòu)成順子，那么必須是1,2,3,4,5中的任意一個(gè)被0替換了，因?yàn)橄胍?可以變成任意的一個(gè)數(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種情況，都是可以構(gòu)成順子的情況。

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

如果 5 張牌中有2個(gè)大小王

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

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

思路總結(jié)

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

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

動(dòng)畫

代碼·

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?#?若有重復(fù)，提前返回?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;?//?若有重復(fù)，提前返回?false
????????????repeat.add(num);?//?添加此牌至?Set
????????}
????????return?max?-?min?????}
}


C

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