Re: [閒聊] 每日leetcode

[sustainer123 (caster )]

※ 引述《oin1104 (是oin的說)》之銘言：
: ※ 引述 《SecondRun (南爹摳打)》 之銘言：
: : 　
: : 846. Hand of Straights
: : 　
: : 給定一整數陣列和分組大小
: : 回傳可否把數字分組，每一組的數字要連續
: : 　
: : Example 1:
: : Input: hand = [1,2,3,6,2,3,4,7,8], groupSize = 3
: : Output: true
: : Explanation: Alice's hand can be rearranged as [1,2,3],[2,3,4],[6,7,8]
: : 　
: : Example 2:
: : Input: hand = [1,2,3,4,5], groupSize = 4
: : Output: false
: : Explanation: Alice's hand can not be rearranged into groups of 4.
: :
: 思路 :
: 反正一定是要每一個數字都用來排他的卡組
: 先看能不能整除
: 然後就把每個數字都塞進map
: 因為要有序
: 所以就每一次都拿最小的數字組成卡組
: 然後刪除他們
: 如果可以組成的話就 可以
: 不行就return false
: class Solution {
: public:
:     bool isNStraightHand(vector<int>& hand, int groupSize)
:     {
:         int len = hand.size();
:         if(len%groupSize != 0)return false;
:         map<int,int> paper;
:         for(int k : hand)
:         {
:             paper[k]++;
:         }
:         while(!paper.empty())
:         {
:             vector<int> now;
:             for(auto it = paper.begin() ; it != paper.end() ; it ++)
:             {
:                 now.push_back(it->first);
:                 it->second--;
:                 if(it->second == 0)paper.erase(it);
:                 if(now.size() == groupSize)break;
:             }
:             if(now.size() != groupSize) return false;
:             for(int i = 0 ; i < groupSize-1 ; i ++)
:             {
:                 if(now[i] != now[i+1]-1)return false;
:             }
:         }
:         return true;
:     }
: };

思路:
首先確認長度能不能被整除

再來哈希表記數 然後排序 之後從最小的開始扣 能全部扣完就成功


Python Code:
class Solution:
    def isNStraightHand(self, hand: List[int], groupSize: int) -> bool:
        record = defaultdict(int)
        l = len(hand)

        if l % groupSize != 0:
            return False

        for n in hand:
            record[n] += 1

        keys = [k for k in record.keys()]
        keys.sort()

        while l > 0:
            if record[keys[0]] <= 0:
                keys = keys[1:]
                continue
            else:
                record[keys[0]] -= 1

            for i in range(1,groupSize):
                if record[keys[0]+i] <= 0:
                    return False
                else:
                    record[keys[0]+i] -= 1
            l -= groupSize
        return True


我本來想說能省排序 哭了

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.119.120.6 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1717652558.A.BB0.html
推 oin1104: c++ 的map會幫你在插入的時候排序 原理不知道 反正很方
→ oin1104: 便
→ sustainer123: 我感覺能想辦法省下來 因為我才16%
→ sustainer123: 省下這個就變O(N) 多排序就nlogn
推 oin1104: 可是要讓他有序的話 就一定要排 所以這個方法大概就這樣
→ oin1104: 惹 nlogn
→ oin1104: 我跟你都是nlogn 八
→ sustainer123: 你n吧 那兩個迴圈都實質N
→ sustainer123: 假如我沒理解錯誤的話 我C++很糞
推 oin1104: 沒八 我插入map的時候會是logn 插入n個所以是nlogn
→ sustainer123: 啊 對欸 忘了插入本身就要成本
→ sustainer123: 不對 哈希表插入元素的時間複雜度不是1?
推 oin1104: 好想插入靈夢 我插入靈夢都不需要成本 隨便插的
→ oin1104: 不是 map是紅黑樹做的 unordered map 比較像是哈希 因為
→ oin1104: 它無序
→ oin1104: map有序 插入的時候排的 然後原理是紅黑書
→ sustainer123: 喔喔 原來
→ yam276: 你效率要用unordered_map