給一個 m*n 的矩陣，跟整數 k，而且每行已經排列。從每行取一個出來作總和，求第 k 小的總和是多少。

這題跟 373. 是很類似的，不過這題多了很多行數列，但並不是什麼難點。

若採用全部枚舉的話，最多40**40個，這樣子會超時。

若分批進行，一樣從全部的索引 0 開始，每輪後索引總和+1，繼續枚舉，因為目標大小 k 最高200個，所以這方法是可行的？

只要每輪枚舉結束，枚舉的總數超過 k 就可以找到目標值？但並不是這麼一回事。

的確一開是從最小值開始枚舉，會得到各索引+1的組合。

若只是單純以索引+1為枚舉的方式，這不能保證一定能包含完整的最小總和順序。

例如：mat = [[1,2,3,4,5,6],[1,1,1,1,1,1]], k = 3

然而下一輪要枚舉的，是以什麼當基準呢？

如果一開始是最小值，那麼，第二小的值會在枚舉中被找到。

若換種角度，都以最小值的索引組合為基準，而第三小的值會在第二小的枚舉中被找到，第四小的也是同理。

因此我們需要參考最小值的索引組合做枚舉。使用 heap 的話，就能保持最小值總在第一個，也方便進行後面的枚舉。

如此連鎖，第二找第三，第三找第四，……，就能找到第 k 的值。

Python

class SolutionPass:
    def kthSmallest(self, mat, k: int) -> int:
        import heapq
        result = []
        n, m = len(mat), len(mat[0])
        heap = [(sum(each[0] for each in mat) , *[0 for _ in range(n)])]
        memo = set()             
        while k > 0 and heap:
            sm, *idxs = heapq.heappop(heap)
            result.append(sm)
            k -= 1
            for i in range(n):
                idxs[i] += 1
                if idxs[i] < m and tuple(idxs) not in memo:       
                    memo.add(tuple(idxs))
                    heapq.heappush(heap, [sum([mat[j][idxs[j]] for j in range(n)]), *idxs])
                idxs[i] -= 1
        return result[-1] 

給兩個數列 nums1 nums2 ，要回傳 k 個總和由小排列的組合。參考

關於會作這一題， 是因為有一題更進階的在後頭，所以先把這個處理掉再進階。

之前我碰到 heap 都不是了解，但是又很多人會用，所以這次我得學著用 heap 去解問題。

關於 heap ， 是一種「堆積法」，有 maxheap 和 minheap ，可想成是一個二元樹，把根節設為最大或最小。

好處是可以快速找到 max 或是 min ，在要用到這類的計算排列時，heap 就很好用了。

python的 heapq 是以 minheap 為主的，跟一般排序的 maxheap 是不同的。

而 minheap，也是這題會用到的 heap ，要找最小值。

如果用 heapq.heappush() 相當於 append()、sort()，這樣在枚舉時也能加速。

這題要找組合，所以要保存總和由小到大的組合的 result 。

由於 nums1 跟 nums2 都已經排序過，所以我們可以得知每個的第[0]位相加會是最小總和。

接下來第二小的，不是 nums1 的索引+1，就是 nums2 的索引+1。

這樣子會陷入一個難題，到底重複出現搜尋過索引組合的要如何避免？最簡單的方法是拿索引組合用hash類型做檢查。

由於 heap 的排序若有二維是用第[0]位做判斷(跟list一樣)，因此 heap 中元素的第[0]位是總和，這樣也能符合由小到大的要求。

而後面幾位擺上索引組合，因為元素可能是相同數值，若只計算加總值可能會漏掉該出現的重複。

(這題的解法，已針對後面進階題做改良。)

Python

class Solution:
    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:
        result = []
        if not nums1 or not nums2: return result
        nums = [nums1, nums2]        
        heap = [(sum(each[0] for each in nums) , 0, 0)]
        memo = {(0,0)}        
        n = len(nums)
        
        while k > 0 and heap:
            _, *idxs = heapq.heappop(heap)
            result.append([nums[j][idxs[j]] for j in range(n)])
            k -= 1
            for i in range(len(idxs)):
                idxs[i] += 1
                if idxs[i] < len(nums[i]) and tuple(idxs) not in memo:       
                    memo.add(tuple(idxs))
                    heapq.heappush(heap, [sum([nums[j][idxs[j]] for j in range(n)]), *idxs])
                idxs[i] -= 1
            
        return result  

給一組二維串列，一維代表第 i 位的人，二維代表該位置上的人可選的帽子種類編號。回傳全部人都戴上帽子且都是不同種類的方法數。

這題是DP，最大的特徵就是數目很大，需要取餘。(以前提過)

但DP的精華就是如何設計DP在放些什麼，而我這次學到了「bit」的方法。(然而我沒有在contest解出來QQ)

由於帽子種類跟人數都是有限制範圍的，若要取DP，可以由帽子做分配，或是由人開始。

要選哪一個？這我當時沒有想清楚，結果用人為主體。然後backtrace都超時。

以人為主體的話：1人可能有40種﹐最多有10人，是 40**10 是嗎？不，最糟是40*39*38*…*30。

以帽子為主體的話：則是 40*10! ，40是帽子的種類，10的階乘是代表沒有戴上帽子的人。只要能提前戴上帽子，就可以提前結束遞迴函數。

而且我之前沒有想到bit法，用 set 是不能當 hashtable 的 key ， 於是我用 tuple，太花時間。

bit法是相互獨立且非 1即 0 的狀態才適用，剛好這題適用，不論是用來表示帽子被選擇，或是誰戴上帽子，都可以。

我以為會有很多種的方法，結果沒有，而目前沒有看到更好的解法，大概都這一套。

Python

from functools import lru_cache
from collections import defaultdict

class Solution:    
    def numberWays(self, hats) -> int:      
        n = 40 # 題目限制的帽子種類
        m = (1 << len(hats)) - 1 # 全部人都戴上帽子的狀態
        
        hatToP = defaultdict(list)
        for i, each in enumerate(hats):
            for hat in each:
                hatToP[hat].append(i)   
 
        @lru_cache(None) 
        def search(i, state):  
            if state == m: return 1 
            if i > n: return 0              
            ways = 0            
            for p in hatToP[i]:
                if state < (state | 1 << p): # 選
                    ways += search(i+1, (state | 1 << p))  
            ways += search(i+1, state) # 不選   
            return ways % (10**9+7)
        
        return search(0, 0)

給一串整數陣列 nums 跟整數 limit，求連續子陣列的最大小值相減 <= limit 的最大子陣列個數。

我以前有碰到過這種問題，但我沒有在當下把 deque 的觀念內化，都選擇用dp，終於在今天吃苦頭。
(又或者可以用 two pointers 做解決。)

這種類型的問題有一個特色，就是有「連續子陣列(或串列)」，若條件不合，去掉頭再繼續。

用 時間複雜度 O(N) 解決掉，只給跑一次 nums 的機會。

基本架構是用一個串列，先把遇到的數加進串列後方，(while)若 max() – mix() > limit 則 del[0]，在每輪最後檢查len()。

基本型(Python) ※會超時

class Solution:
    def longestSubarray(self, nums, limit) -> int:
        queue = []
        result = 0
        for i in range(len(nums)):            
            queue.append(nums[i])
            while queue and max(queue) - min(queue) > limit:
                del queue[0]
            result = max(result, len(queue))
        return result

其中最耗費時間的函數是 max() 跟 min() ，如果queue的所含的個數很多，就會在這裡因為一直找而超時。

所以改善這一塊，用兩個變數 maxValue 跟 minValue 去保存最大小值就能順利通過。

改善型(Python)

class Solution:
    def longestSubarray(self, nums, limit) -> int:
        queue = []
        result = 0
        maxValue = minValue = nums[0]
        for i in range(len(nums)):            
            queue.append(nums[i])
            maxValue = max(maxValue, nums[i])
            minValue = min(minValue, nums[i])
            while queue and maxValue - minValue > limit:
                v = queue.pop(0)
                if queue:
                    if v == maxValue: maxValue = max(queue)
                    if v == minValue: minValue = min(queue)
                else:
                    maxValue = nums[i+1]
                    minValue = nums[i+1]
            result = max(result, len(queue))
        return result

class Solution:
    def longestSubarray(self, nums, limit) -> int:
        sp = 0
        result = 0
        maxValues = [] 
        minValues = []
        for i in range(len(nums)):    
            num = nums[i]            
            if not maxValues or num >= maxValues[-1]: maxValues.append(num)
            if not minValues or num <= minValues[-1]: minValues.append(num)
            print(i, sp, maxValues, minValues)

            while maxValues and minValues and i>sp and maxValues[-1] - minValues[-1] > limit:
                v = nums[sp]
                sp += 1
                if v == maxValues[0]: 
                    del maxValues[0]
                    if not maxValues: maxValues.append(max(nums[sp:i+1]))
                if v == minValues[0]: 
                    del minValues[0]
                    if not minValues: minValues.append(min(nums[sp:i+1]))

            result = max(result, i-sp+1)
        return result