劍指offer | 面試題48：撲克牌中的順子

死磕算法系列文章

1. 幹貨 | 手撕十大經典排序算法
2. 劍指offer | 認識面試
3. 劍指offer | 面試題2：實作Singleton模式
4. 劍指offer | 面試題3：二維數組的查找
5. 劍指offer | 面試題4：替換空格
6. 劍指offer | 面試題5：從尾到頭列印連結清單
7. 劍指offer | 面試題6：重建二叉樹
8. 劍指offer | 面試題7：用兩個棧實作隊列
9. 劍指offer | 面試題8：旋轉數組的最小數字
10. 劍指offer | 面試題9：斐波那契數列
11. 劍指offer | 面試題10：青蛙跳台階問題
12. 劍指offer | 面試題11：矩陣覆寫
13. 劍指offer | 面試題12：二進制中1的個數
14. 劍指offer | 面試題13：數值的整數次方
15. 劍指offer | 面試題14：列印從1到最大的n位數
16. 劍指offer | 面試題15：删除連結清單的節點
17. 劍指offer | 面試題16：将數組中的奇數放在偶數前
18. 劍指offer | 面試題17：連結清單中倒數第k個節點
19. 劍指offer | 面試題18：反轉連結清單
20. 劍指offer | 面試題19：合并兩個有序連結清單
21. 劍指offer | 面試題20：判斷二叉樹A中是否包含子樹B
22. 劍指offer | 面試題21：二叉樹的鏡像
23. 劍指offer | 面試題22：順時針列印矩陣
24. 劍指offer | 面試題23：包含min函數的棧
25. 劍指offer | 面試題24：棧的壓入、彈出序列
26. 劍指offer | 面試題25：從上到下列印二叉樹
27. 劍指offer | 面試題26：二叉搜尋樹的後序周遊序列
28. 劍指offer | 面試題27：二叉樹中和為某一值的路徑
29. 劍指offer | 面試題28：複雜連結清單的複制
30. 劍指offer | 面試題29：二叉搜尋樹轉換為雙向連結清單
31. 劍指offer | 面試題30：字元串的排列
32. 劍指offer | 面試題31：數組中出現次數超過一半的數字
33. 劍指offer | 面試題32：最小的k個數
34. 劍指offer | 面試題33：連續子數組的最大和
35. 劍指offer | 面試題34：1～n 整數中 1 出現的次數
36. 劍指offer | 面試題35：把數組排成最小的數
37. 劍指offer | 面試題36：醜數
38. 劍指offer | 面試題37：第一個隻出現一次的字元
39. 劍指offer | 面試題38：數組中的逆序對
40. 劍指offer | 面試題39：兩個連結清單的第一個公共節點
41. 劍指offer | 面試題40：數組中數字出現的次數
42. 劍指offer | 面試題41：二叉樹的深度
43. 劍指offer | 面試題42：平衡二叉樹
44. 劍指offer | 面試題43：和為s的兩個數字
45. 劍指offer | 面試題44：和為s的連續整數序列
46. 劍指offer | 面試題45：翻轉單詞順序
47. 劍指offer | 面試題46：左旋轉字元串
48. 劍指offer | 面試題47：n個骰子的點數

歡迎關注千羽的公衆号

“Leetcode : https://leetcode-cn.com/problems/bu-ke-pai-zhong-de-shun-zi-lcof/

“GitHub : https://github.com/nateshao/leetcode/blob/main/algo-notes/src/main/java/com/nateshao/sword_offer/topic_48_isStraight/Solution.java

劍指 Offer 61. 撲克牌中的順子

“題目描述 ：從若幹副撲克牌中随機抽 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
           

複制

方法一：排序 + 周遊

1. 先對數組執行排序。
2. 判别重複： 排序數組中的相同元素位置相鄰，是以可通過周遊數組，判斷 nums[i] = nums[i + 1]是否成立來判重。
3. 擷取最大 / 最小的牌： 排序後，數組末位元素 nums[4] 為最大牌；元素 nums[joker]為最小牌，其中 joker 為大小王的數量。

複雜度分析：

• 時間複雜度O(NlogN)= O(5log5)=O(1) ：中N為nums長度,本題中N=5 ；數組排序使用 O(N log N)時間。
• 空間複雜度0(1) ：變量joker使用O(1)大小的額外空間。

package com.nateshao.sword_offer.topic_48_isStraight;

import java.util.Arrays;

/**
 * @date Created by 邵桐傑 on 2022/2/21 22:45
 * @微信公衆号 千羽的程式設計時光
 * @個人網站 www.nateshao.cn
 * @部落格 https://nateshao.gitee.io
 * @GitHub https://github.com/nateshao
 * @Gitee https://gitee.com/nateshao
 * Description:
 */
public class Solution {
    public static void main(String[] args) {
        int[] nums = {1,2,3,4,5};
        System.out.println("isStraight(nums) = " + isStraight(nums));
    }
    public static boolean isStraight(int[] nums) {
        Arrays.sort(nums);
        int joker = 0;
        for (int i = 0; i < 4; i++) {
            if (nums[i]==0)joker++;//統計大小王的數量
            else if(nums[i]==nums[i+1])return false;//重複就傳回false
        }
        return nums[4]-nums[joker]<5;//最大牌 - 最小牌 < 5 則可構成順子
    }
}

           

複制

方法二：集合 Set + 周遊

思路：

1. 周遊五張牌，遇到大小王(即0)直接跳過。
2. 判别重複：利用Set實作周遊判重， Set的查找方法的時間複雜度為O(1) ;
3. 擷取最大1最小的牌：借助輔助變量max和min，周遊統計即可。

複雜度分析:

• 時間複雜度O(N)= O(5)=O(1) ：中N為nums長度，本題中N =5 ;周遊數組使用O(N)時間。
• 空間複雜度O(N)= O(5)=O(1) ：用于判重的輔助Set使傭O(N)額外空間。

public static boolean isStraight2(int[] nums) {
        Set<Integer> 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 < 5; // 最大牌 - 最小牌 < 5 則可構成順子
    }
           

複制

參考連結：https://leetcode-cn.com/problems/bu-ke-pai-zhong-de-shun-zi-lcof/solution/mian-shi-ti-61-bu-ke-pai-zhong-de-shun-zi-ji-he-se

END