Leetcode題解 Python：Number of Ways to Wear Different Hats to Each Other

給一組二維串列，一維代表第 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)

Leetcode題解 Python & C#：五月挑戰DAY3 Ransom Note

給兩個字串：ransomNote、magazine，問 ransomNote 是否能從 magazine 裡面的宇符組成。

嗯，這是一個電影會見到的情節吧…

方法很簡單，就是 ransomNote 的每個字符出現次數要比 magazine 的少或等於。

Python

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        for c in set(ransomNote):
            if ransomNote.count(c) > magazine.count(c):
                return False            
        return True

C# 

public class Solution {
    public bool CanConstruct(string ransomNote, string magazine) {
        var charSet = new HashSet(ransomNote);
        foreach(var c in charSet)
        {
            if(ransomNote.Count(p => p == c ) > magazine.Count(p => p == c ))
                return false;  
        }      
        return true;
    }
}

Leetcode題解 Pythonython：Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

給一串整數陣列 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

Leetcode題解 Python & C#：五月挑戰DAY2 Jewels and Stones

給兩個字串 J、S ，J裡面的字符是代表jewel，問 S 裡面有幾個 jewel。

這是一個相當簡單的問題，重點會放在用什麼作為搜尋的方式。

為了快速，這裡會使用 hash 家族的資料型態讓搜尋更快速。

如果是Python會用 set 或 dict 都可以，我用 collections.Counter， 只是換一點寫法。collection.Counter 是 dict 類的。

如果是C#，我直接用 string 的 Contains() ，其實做法都大同小異。 


Python 

class Solution:
    def numJewelsInStones(self, J: str, S: str) -> int:
        counter = Counter(S)
        return sum([counter[j] for j in set(J)])

C# 

public class Solution {
    public int NumJewelsInStones(string J, string S) {
        int result = 0;
        foreach(var s in S)
        {
            if(J.Contains(s))
                result += 1;
        }
        return result;        
    }
}

Leetcode題解 Python & C#：五月挑戰DAY1 First Bad Version

給一個 n 代表目前有 n 個版本，要透過 isBadVersion(version) 的函數去找到第一個 True(即BadVersion)的版本號。

這題如果是有使用git去控制版本，那應該是很生活化的搜尋思維。

首先決定搜尋法，這裡使用二分搜尋法去解。

左為 l 右為 r，每次都從 m = (r-l)//2+l 位置找，我之前不太能掌握 l, r 與 m 的替換，到底是 >=, <=, m+1, m 的關係要如何連結起來，當我試著想用 r 去貼齊 target 的位置 ，就比較了解該怎麼寫對。

不過這題也不會有這樣的困擾。

由於版本會從 1 開始， l (L)= 1 ，而 r 要等於 n + 1 ，不過最壞的陷阱來了。若 n = 2147483647 ，那麼就會發生溢位，所以要做一點小修改。(如果是Python就不用擔心了)

Python

class Solution:    
    def firstBadVersion(self, n):
        l, r = 1, n+1 
        while l < r:
            m = (r-l)//2 + l
            if isBadVersion(m):
                r = m
            else:
                l = m+1            
        return r

C# 

public class Solution : VersionControl {
    public int FirstBadVersion(int n) {
        int l=1; int r= n;   
        int m = (r-l+1)/2+l;
        while(l < r)
        {            
            if (IsBadVersion(m))
            {
                r = m;
            }
            else
            {
                l = m+1;
            }
            m = (r-l)/2+l;
        }
        return r;
    }
}

Leetcode題解 Python & C#：四月挑戰DAY30 Check If a String Is a Valid Sequence from Root to Leaves Path in a Binary Tree

給一串二進位二元樹跟一串二進位數列，是否能依數列的值到達葉(leaf)，也就是底層。

這算是「搜尋法」，只要有基本的暴力破解法觀念也可以順利解出。

如果要優化時空，使用遞迴函數就可以快速解出。

Python

class Solution:
    def isValidSequence(self, root: TreeNode, arr: List[int]) -> bool:
        if root and arr and root.val == arr[0]:
            if len(arr) == 1 and root.right is None and root.left is None: return True
            return self.isValidSequence(root.left, arr[1:]) or self.isValidSequence(root.right, arr[1:]) 
        else:
            return False

C# 

public class Solution {        
    public bool IsValidSequence(TreeNode root, int[] arr) {
        int l = 0; 
        int r = arr.Length;
        var stack = new List(){root};
        while(l 0)
        {
            int n = stack.Count;
            for(int i = 0; i < n; i++)
            {
                var node = stack[0];
                if(node.val==arr[l])
                {
                    if(l == r-1 && node.left is null && node.right is null)
                        return true;
                    if(!(node.left is null)){stack.Add(node.left);}
                    if(!(node.right is null)){stack.Add(node.right);}                        
                }                
                stack.RemoveAt(0);
            }
            l++;
        }
        return false;
    }
}

Leetcode題解 Python & C#：四月挑戰DAY29 Binary Tree Maximum Path Sum

給一串非空的二元樹，找出最大的路徑總和。

如果要使用遞迴的想法：以尋找當前的節與左右兩邊子樹最大的路徑，可以找到通過該節的最大路徑。

如果要住上傳，那會是左右或零取大者加自身再上傳。

因此遞迴函數要有兩種：
1.回傳值是到該點的最大路徑。
2.由1.得到左右最大的路徑，去計算通過該點的最大路徑。

Python 

class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        self.result = root.val
        def dfs(node):
            if not node: return 0
            rsum = dfs(node.right)
            lsum = dfs(node.left)
            maxPath = node.val+max(0, rsum, lsum)
            self.result = max(maxPath, node.val+lsum+rsum, self.result)
            return maxPath              
        dfs(root)
        return self.result

C# 

public class Solution {    
    public int result;
    
    public int MaxPathSum(TreeNode root) {
        result = root.val;
        dfs(root);
        return result;
    }
    
    public int dfs(TreeNode node)
    {
        if(node is null){return 0;}    
        var values = new int[2];
        int rsum = dfs(node.right);
        int lsum = dfs(node.left);
        values[0] = Math.Max(node.val + rsum, node.val + lsum);
        values[0] = Math.Max(node.val, values[0]);
        values[1] = node.val + lsum + rsum;
        result = Math.Max(Math.Max(values[0],values[1]),result);
        return values[0];
    }
}

Leetcode題解 Python：四月挑戰DAY28 First Unique Number

有一個 queue 類別 FirstUnique 特點是要回傳第一個沒有重複的整數。要完成有這項功能的 FirstUnique 。

這個題目倒是沒有 remove 的功能要實現，所以相當容易解決。

要如何知道重複出現？最快的找法就是使用hash 類的資料型態去記錄。

單獨出現過的放在一個 hashtable 不用set是因為我們要保留序列；重複出現的移到第二個 hashtable，並刪除第一個 hashtable 的鍵。

如此 showFirstUnique() 只需要看第一個 hashtable 的第一個鍵，沒有鍵則是 return -1


Python

class FirstUnique:

    def __init__(self, nums: List[int]):
        self.memo = Counter(nums)   
        self.memo2 = defaultdict(int)        
        for key in list(self.memo.keys()):
            if self.memo[key] > 1:
                del self.memo[key]
                self.memo2[key] += 1 

    def showFirstUnique(self) -> int:
        if self.memo:
            for key in self.memo:
                return key
        else:
            return -1


    def add(self, value: int) -> None:
        if value in self.memo2:
            pass
        elif value in self.memo:
            del self.memo[value]
            self.memo2[value] += 1
        else:
            self.memo[value] = 1

Leetcode題解 Python & C#：四月挑戰DAY27 Maximal Square

給一個2D矩陣，其中只有 1 或 0 ，找出最大的連續 1 組成的最大正方形面積。

首先來想要怎樣去找任意一個正方形的面積。

如果選定某一位置，那正方形會在往右下延伸、或左上，簡單來說就是四周。

不過這樣相當不容易寫，而且也會效率不佳。

再觀察一下，正方形出現時會有怎樣的情形？

假設有個面積為 4 的正方形：

基礎假設

可以發現組成邊長2的正方形，其相鄰加身自身會有2個連續出現1超過二次。

同理邊長為3的正方形。

計算流程

於是各欄只要計數1的連續出現次數，接下來問題變成要如何從數列中找出最大的正方形面積。

接著要去從數列中求出最大的正方形面積。

我這裡使用暴力破解法，以自身為左右索引的起始點，往左右找有大於自身數值的個數。
如 2 ，只要往左右再找一個，因為自身本身可以當作一個計數。

過程中，數值小於當前的最大面積的邊長也可以跳過不往左右找。


Python

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        if not matrix or not matrix[0]: return 0       
        rows,cols= len(matrix), len(matrix[0])
        cur = [0]*cols
        maxSideLength = 0
        for y in range(rows):
            # 逐行掃瞄
            for x in range(cols):
                if matrix[y][x] == "1":
                    cur[x] += 1
                else:
                    cur[x] = 0
            # 檢查連續最大值
            for x in range(cols):                 
                v = cur[x]
                if v <= maxSideLength: continue                    
                v -= 1
                l, r = x, x
                while v:
                    if l > 0 and cur[l-1] >= cur[x]:
                        l-=1
                        v-=1
                        continue
                    if r = cur[x]:
                        r+=1
                        v-=1
                        continue
                    break
                if v==0: 
                    maxSideLength = max(maxSideLength, cur[x])
        return maxSideLength**2

C# 

public class Solution {
    public int MaximalSquare(char[][] matrix) {
        if(matrix.Length == 0 || matrix[0].Length == 0){return 0;}
        var cur = new int[matrix[0].Length];
        Array.Fill(cur, 0);
        int maxSideLength = 0;
        
        for(int y = 0; y < matrix.Length; y++)
        {
            for(int x = 0; x < matrix[0].Length; x++)
            {
                if(matrix[y][x]=='1')
                {
                    cur[x] += 1; 
                }
                else
                {
                    cur[x] = 0;
                }               
            }

            for(int x = 0; x < matrix[0].Length; x++)
            {
                if(cur[x] <= maxSideLength)
                {
                    continue;
                }
                int num = cur[x]-1;
                int l = x; int r = x;
                while(num > 0)
                {
                    if(l > 0 && cur[l-1] >= cur[x])
                    {
                        l -= 1;
                        num -= 1;
                        continue;
                    }
                    if(r = cur[x])
                    {
                        r += 1;
                        num -= 1;
                        continue;
                    }
                    break;
                }
                if(num==0)
                {                    
                    maxSideLength = cur[x];
                }
            }
        }
        
        return maxSideLength*maxSideLength;
    }
}

Leetcode題解 Python & C#：四月挑戰DAY26 Longest Common Subsequence

給兩個字串，請回傳兩字串有幾個相同的部分？匹配的位置可以不用相鄰，但相對位置要一致。

這不是一般的字串匹配問題，因為匹配的部分可以不相鄰。

換個思維，要如何做到不相鄰的配對？

首先看兩者的[0]位，如果相同，則兩者往右尋找。
若不，則 text2 往下一位 [j+1] 匹配,，因此，對應 text2 的索引 j 的意思是 j 之前的匹配數目。
如果沒有匹配對，那 [j] 就等於上一位 [j-1] 的數目。
此外，因為可以不相鄰，所以 text1[i] text2[j] 沒有匹配到的話，[i][j]也可以從[i-1][j] 得到匹配數目。
於是沒有匹配的話 =>  [i][j] = max([i-1][j], [i][j-1])

這是正序的方法，若看 Hint ，我第一個寫成反序的遞迴函數，其實道理都相同。


如果有匹配到，數目一定是 +1 ，那是什麼位置的數目 +1 ？
[i-1][j-1]，這邏輯就像一般的字符匹配那般。

流程

Python 

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        l1, l2 = len(text1), len(text2)
        cur = [0] * (l2+1)
        for i in range(l1):
            cur, pre = [0]*(l2+1), cur
            for j in range(l2):
                if text1[i] == text2[j]:
                    cur[j] = pre[j-1] + 1
                else:
                    cur[j] = max(cur[j-1], pre[j])
        return cur[-1]

C# 

public class Solution {
    public int LongestCommonSubsequence(string text1, string text2) {
        var cur = new int[text2.Length+1];
        Array.Fill(cur, 0);
        for(int i = 0; i < text1.Length; i++)
        {
            var pre = cur;
            cur = new int[text2.Length+1];
            Array.Fill(cur, 0);
            for(int j = 0; j < text2.Length; j++)
            {
                if(text1[i] == text2[j])
                {
                    cur[j+1] = pre[j] + 1;
                }
                else
                {
                    cur[j+1] = (cur[j] > pre[j+1])? cur[j]: pre[j+1];
                }
            }
        }
        return cur[text2.Length];
    }
}

Leetcode題解 Python & C#：Constrained Subset Sum

給一串整數陣列，回傳最大非空子集合的最大總和，子集合為連續的 nums[i] nums[j] 組成，j<i 且 j-i <= k。

本來今天高高興興的，結果這一題沒有在時限內完成。光是看懂題目就已經用上三十分鐘。

等到明暸的時候，也無啥時間可寫了。檢討失敗的原因，我想是對這樣的題型陌生吧。

由於是集合，所以可選相同位置上的(如前一組的j，後一組的i)，但每一個位置只會被計算到一次。

因此如果使用深度優先的遞迴函數，我倒是沒寫好在取相同位置的判斷。(我就在這裡卡住)

這顕是DP的題型，因此選擇會紀錄什麼是接下來首先思考的。

如果遞迴函數不適合，那可以攤開變成迴圈，並且由後往前找。

由於一次選擇一定要成對nums[i] nums[j]，因此從 len(nums) – 2 之處開始。(-1位置是無法選一對的)

接者，在 [i+1,i+k] 的範圍中選擇最大的總和，所以DP是紀錄該位置上的總和，然後nums[i] + max([i+1:i+k+1])為dp[i]新的總和。


例題與流程：
[1,-1,1,2,3], 2
[1,-1,1,5,3]
[1,-1,6,5,3]
[1,5,6,5,3]
[7,5,6,5,3]
=> max() => 7

[-1,-2,-3],1
[-1,-2,-3]
[-1,-2,-3]
=> max() => -1

由於 k 可能會很大，如果都跑完一定會超時。但其實在選擇最大值的時候，就已經決定了題目中的子集合的最後一個元素。

如果迴圈[i+1,i+k]超越上次最大值所選的位置，後面也不會有更大的總和，所以當前位置就可以不用再往下選最大總和與自身相加。

去掉不必要的部分，這樣就能加快速度，順利完成此題。

Python 

class Solution:
    def constrainedSubsetSum(self, nums, k):
        maxIndex = len(nums)
        for i in range(maxIndex-2, -1, -1):           
            value = nums[i]          
            for j in range(1,min(k+1,maxIndex-i)):
                if value + max(0, nums[i+j]) > nums[i]:
                    nums[i] = value + max(0, nums[i+j])
                    maxIndex = i+j+1
        return max(nums)

C# 

public class Solution {
    public int ConstrainedSubsetSum(int[] nums, int k) {
        int maxIndex = nums.Length;
        for(int i = nums.Length-2; i >= 0; i--)
        {
            int v = nums[i];
            int ik = (k+1 < maxIndex-i)? k+1: maxIndex-i;
            for(int j = 1; j < ik; j++)
            {
                int num = v + (nums[i+j] <= 0? 0: nums[i+j]);
                if( num > nums[i])
                {
                    nums[i] = num;
                    maxIndex = i+j+1;  
                }
                
            }
        }
        return nums.Max();
    }
}

Leetcode題解 Python：Restore The Array

給一由數字組成的字串，可以在任意位置上切割，但每個切割出來的數字要在[1,k] 之間，而且分割出來的數字不能有前導零的出現，要回傳有幾種可能。

(可能組合數很多，回傳結果對 10^9+7 的取餘)

這題明顯是dp的題目，因為要找出所有組合數，而且答案可能超級大。

如果使用遞迴函數，因為這題的 s.Length 可達 10^5，因此可能會超出最大遞迴深度而報錯。

先繼續講如何設計。

從位置[0]開始，如果左方的數字在[1,k] 之間，可以選擇在這裡切，或是住下一位切。因為要記錄上次的切割位置，所以得設一參數接收。
memo[pos][slicePos]

如果切，往深 dfs(pos+1, pos+1)；不切，dfs(pos+1, slicePos)。

要是下一位是 “0” 或是左方數字 < 1 ，那就只能不切，因為在這遞迴函數只取符合規則的方法數。

接著來思考中止條件。

如果 pos == s.length，檢查左方數字是否在範圍內，決定回傳 1 或 0 。

如果 int(s[slicePos:pos+1]) > k ，超出範圍，即回傳 0 。


python 

class Solution:
    def numberOfArrays(self, s: str, k: int) -> int:
        n = len(s)
        
        @lru_cache(None)
        def nextPos(i, j):            
            if i == n:
                if j != n and int(s[j:n]) >= 1 and int(s[j:n]) <= k: return 1
                return 0   
            while i < n-1 and s[i+1] == "0": 
                i += 1                                
            lnum = int(s[j:i+1])
            if lnum > k: return 0   
            return (nextPos(i+1, j)+nextPos(i+1, i+1)) % (10**9+7)
        
        # 由於可能超出最大深度，所以先執行一半
        nextPos(len(s)//2, len(s)//2)
        
        return nextPos(0, 0)

目前趨勢

忘記行李後的心情低落
2017.9.23 學習了一個月的python歷程
臺鐵大誤點以及捲簾式快門
嘗試用Python爬蟲技巧抓混音音樂