Leetcode題解 Python & C#：五月挑戰DAY26 Uncrossed Lines

給兩個數列 A B 分別寫成上下平行，如果 A[i] == B[j] ，那可以用一直線相連，要找出最大沒有交叉的連線數。
做完上一個 contest ，再看這個問題，很自然就會以相似的解法去進行。
這裡有一個特色「兩數列，各取一個兩兩配對，配對後不能重複再用到。」這樣想到可能會有一個表格狀的DP，再應題目做處理。
這題也是這樣。
DP[i][j] 定為該位置上的最大的沒交叉的相連數。
如果位置 A[i] == B[j] ，那 DP[i][j] = 1 再加右下方 DP[i+1][j+1] ，即加上後方的最大沒交叉相連數。
然後 DP[i][j]  = 從自身、右、下三者取最大值，這樣 DP[i][j] 會是最大的沒交叉的相連數。
最後回傳 DP[0][0] 即可。

Python 

class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        from functools import lru_cache
        ia, ib = 0, 0
        na, nb = len(A), len(B)
        
        @lru_cache(None)
        def dfs(ia, ib):
            if ia > na - 1 or ib > nb - 1:
                return 0
            ans = 1 if A[ia] == B[ib] else 0
            ans = max(ans + dfs(ia+1, ib+1), dfs(ia+1, ib), dfs(ia, ib+1))
            return ans
        
        return dfs(0, 0)

C# 

public class Solution {
    public int MaxUncrossedLines(int[] A, int[] B) {
        int[,] dp = new int[A.Length, B.Length];
        dp[A.Length-1, B.Length-1] = A[A.Length - 1] == B[B.Length - 1] ? 1 : 0;
        int lastNum = B[B.Length - 1];
        for(int i = A.Length - 2; i >= 0; i--)
        {
            if(A[i] == lastNum)
                dp[i, B.Length-1] = 1;
            else
                dp[i, B.Length-1] = dp[i+1, B.Length-1];
        }
        lastNum = A[A.Length - 1];
        for(int j = B.Length - 2; j >= 0; j--)
        {
            if(B[j] == lastNum)
                dp[A.Length-1, j] = 1;
            else
                dp[A.Length-1, j] = dp[A.Length-1, j+1];
        }
        
        for(int i = A.Length - 2; i >= 0; i--)            
        {
            for(int j = B.Length - 2; j >= 0; j--)            
            {
                dp[i, j] = dp[i+1, j+1] + (A[i] == B[j] ? 1 : 0);
                dp[i, j] = Math.Max(dp[i, j], dp[i+1, j]);
                dp[i, j] = Math.Max(dp[i, j], dp[i, j+1]);
            }
        }
        return dp[0, 0];
    }
}

Leetcode題解 Python：Max Dot Product of Two Subsequences

給兩個陣列 nums1 和 nums2。回傳兩陣列中非空子序列(皆相同長度)的最大的點積(Dot Product)。
子序列可以是以原陣列刪除部分(也可以不刪)，但元素的相對順序不變。
dot product的運算：
假設從 nums1 跟 nums2 取出 A 序列 跟 B序列。
A1、A2、A3
B1、B2、B3
=> A1*B1 + A2*B2 + A3*B3 => value
我又沒在時限內做完contest，QQ。
這題使用 DP 的觀念，用 p1 p2 代表兩陣列的點乘位置並加上後續的最大值，同時也是規劃 DFS 的遞迴函數。
由於不能有空值，一定要有個兩位置相乘作為開頭。即 nums1[p1] * nums2[p2] 。
面對 DFS 的設計，要從底開始想，也就是到底的情形。即 nums1[len(nums1)-1] * nums2[len(nums2)-1]。因為不能為空串列，該位置只有 nums1[p1] * nums2[p2] 的可能。
DP[len(nums1)-1][len(nums2)-1] ==  nums1[len(nums1)-1] * nums2[len(nums2)-1]
往上回傳，上面會是 p1-1 或是 p2-1 的，這樣不是 p2 會被重複乘到，不然就是 p1 。有共用的情況下，應該要取最大的可能，自身點乘跟下一個(下方、右方)取最大值，然後決定當前位置的 DP 值。
重點來了，那要如何再取更多，也就是要變成多組的情況。
每一對 p1, p2 都是一個點乘，其左上一個 p1-1,  p2-1 。
對 p1-1,  p2-1 來說，除了乘積外，還要加上 DP[p1][p2]的值，也就是後面的最大可能，如果後方最大值小於零，則不加。
這樣就能用到多組，從多組中找出最大的數值。
 
整理一下順序。
先算出 nums1[p1] * nums2[p2] ，視狀況加上 DP[p1+1][p2+1] 的值，成為該位置的基礎值。
跟下方(共用一個)的取最大值，即 DP[p1][p2] = max(DP[p1][p2], DP[p1+1][p2], DP[p1][p2+1])。

Python 

class Solution:
    def maxDotProduct(self, nums1, nums2) -> int:
        
        from functools import lru_cache
        n1, n2 = len(nums1), len(nums2)
        @lru_cache(None)
        def dfs(p1, p2):
            if p1 > n1-1 or p2 > n2-1:
                return 0
            ans = nums1[p1] * nums2[p2]
            if p1 < n1 - 1 and p2 < n2 - 1:
                ans += max(dfs(p1+1, p2+1), 0)
            if p1 < n1 - 1:
                ans = max(ans, dfs(p1+1, p2))
            if p2 < n2 - 1:
                ans = max(ans, dfs(p1, p2+1))
            return ans

        return dfs(0,0)

Leetcode題解 Python & C#：五月挑戰DAY24 Construct Binary Search Tree from Preorder Traversal

給一個以「Preorder」得到的值陣列，重構出二元樹，並回傳 root 。
這是一個嚴謹的二元樹，所以左邊子樹皆小於自身，右邊皆大於自身。
preorder 是以 自身 → 左 → 右 ，因此陣列的第一個元素會是root。
接著下一個會是左邊第一個，直到比root大。
第一個比root大的是右方第一個，直到最後。
因此可用從陣列中篩選(比第一個)大小，並把 solution 當遞迴函式用，完成二元樹的重構。
(因為本題重複過，所以更多說明請點這裡。)

Python 

class Solution:
    def bstFromPreorder(self, preorder: List[int]) -> TreeNode:
        if not preorder: return None
        node = TreeNode(preorder[0])
        node.left = self.bstFromPreorder([v for v in preorder if v < node.val])
        node.right = self.bstFromPreorder([v for v in preorder if v > node.val])
        return node

C# 

public class Solution {
    public TreeNode BstFromPreorder(int[] preorder) {
        if(preorder.Length == 0){return null;}
        TreeNode node = new TreeNode(preorder[0]);  
        node.left = BstFromPreorder((from num in preorder where num < preorder[0] select num).ToArray());
        node.right = BstFromPreorder((from num in preorder where num > preorder[0] select num).ToArray());
        return node;
    }
}

Leetcode題解 Python & C#：五月挑戰DAY23 Interval List Intersections

要找出 A 與 B 的區間，因為不一定會按順序交疊，所以用 indexA , indexB 來記錄目前 Traverse 的位置。
如果有交疊，範圍會是從二者的左側取大，右側取小的範圍。
那要怎麼移動 index ? 
如果有一個的右側很大，對方的下一個右側可能還沒超過它。因此，此時應該是要繼續移動右側較小的。

Python
class Solution:
    def intervalIntersection(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
        ia = ib = 0
        na = len(A)
        nb = len(B)
        result = []
        while ia < na and ib < nb:
            if A[ia][1]  B[ib][1]:
                pass
                #continue
            else:
                l = max(A[ia][0], B[ib][0])
                r = min(A[ia][1], B[ib][1])
                result.append([l, r])
            if A[ia][1] < B[ib][1]:
                ia += 1
            else:
                ib += 1
        return result

C# 

public class Solution {
    public int[][] IntervalIntersection(int[][] A, int[][] B) {
        int idxA = 0;
        int idxB = 0;
        var result = new List();
        while(idxA < A.Length && idxB < B.Length)
        {
            int l = Math.Max(A[idxA][0], B[idxB][0]);
            int r = Math.Min(A[idxA][1], B[idxB][1]);
            if(l <= r)
            {
                result.Add(new int[2]{l, r});
            }
            if(A[idxA][1] <= B[idxB][1])
            {
                idxA += 1;
            }
            else
            {
                idxB += 1;
            }
        }
        return result.ToArray();
    }
}

Leetcode題解 Python & C#：五月挑戰DAY22 Sort Characters By Frequency

給一個字串，要以字母的出現次數重新排列。
首先要有可以統計字母的方式，用 hash table 可以很容易記錄哪些字的有出現與其次數。
python 有 collections.Counter 可以快速轉換。

Python
class Solution:
    def frequencySort(self, s: str) -> str:
        counter = Counter(s)
        result = ""
        for each in sorted(counter.items(), key = lambda x: x[1], reverse = True):
            result += each[0] * each[1]
        return result

C# 

public class Solution {
    public string FrequencySort(string s) {
        var counter = new Dictionary();
        foreach(char c in s)
        {
            if(counter.ContainsKey(c))
            {
                counter[c] += 1;
            }
            else
            {
                counter[c] = 1;
            }
        }
        var result = new StringBuilder();
        foreach(var item in counter.OrderByDescending(x=>x.Value))
        {
            result.Append(item.Key, item.Value);
        }
        return result.ToString();
    }
}

Leetcode題解 Python & C#：五月挑戰DAY21 Count Square Submatrices with All Ones

給一個由 0 1 組成的矩陣，回傳有多少個正方形全部都是 1 。
這題蠻容易的，就算用暴力法 + dp ，也不會被判超時。
如果本身是 1 ，自己能形成一個正方形，然後往四角延伸去看是否能構成更大的正方形。
用 y x 由上至下，由左至右，所以選右下作基準點。那麼能構成更大的正方形，是其左上、左、上都是同一個數字。
如構成 2 * 2：
[[1,1],
[1,2]] 
位置[1][1]的點，其左上、左、上都是 1 ，所以可以構成 2(1+1)。
3 * 3：
[[1,1,1],
[1,2,2],
[1,2,3]]
位置[2][2]的點，其左上、左、上都是 2 ，所以可以構成 3(2+1)。3 表示該位置有(1*1、2*2、3*3)的正方形。
位置[2][1]的點，其左上2、左1、上1，所以可以構成 2(1+1)。
也就是說，是左上、左、上中取最小值+1。前提也要該位置本來是 1 才可以這樣處理。

Python
class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:             
        result = 0
        cols = len(matrix[0])
        for y in range(len(matrix)):
            for x in range(cols):
                if matrix[y][x] == 1:
                    if y - 1 >= 0 and x - 1 >= 0:
                        matrix[y][x] = min(matrix[y-1][x-1], matrix[y][x-1], matrix[y-1][x]) + 1
                    result += matrix[y][x]                        
        return result

C# 

public class Solution {
    public int CountSquares(int[][] matrix) {
        int result = 0;
        for(int y = 0; y < matrix.Length; y++)
        {
            for(int x = 0; x < matrix[0].Length; x++)
            {
                if(matrix[y][x] == 1)
                {
                    if(y >= 1 && x >= 1)
                    {                        
                        matrix[y][x] = 1 + Math.Min(matrix[y-1][x], Math.Min(matrix[y-1][x-1], matrix[y][x-1]));
                    }
                    result += matrix[y][x];
                }                
            }
        }
        return result;
    }
}

Leetcode題解 Python & C#：五月挑戰DAY20 Smallest Element in a BST

給一串二元樹，在找出第 k 個小的元素。
這題目給的二元樹是比較嚴謹的，子樹左邊皆小於自身，右邊皆大於自身。
因此，左邊最底層的是最小的，接著其父，其父之右子樹，這與「in-order」的 traversal 方式是一樣的。
所以用上這樣的方法，並且加入「第幾小的序數」就能得到題目所求。
對於二元樹的題目，各種traversal模式都要熟練，才會很快地想到寫法。

Python(遞迴函數)
class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        
        self.result = 0
        def dfs(node, rank):
            if not node: return rank
            rank = dfs(node.left, rank) + 1
            if rank == k: self.result = node.val               
            rank = dfs(node.right, rank)
            return rank
        
        dfs(root, 0)
        return self.result

Python(官方) 

class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        
        stack = []        
        while True:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            k -= 1
            if k == 0: return root.val                
            root = root.right

C# 

public class Solution {
    public int KthSmallest(TreeNode root, int k) {
        var stack = new Stack();
        while(true)
        {
            while(!(root is null))
            {
                stack.Push(root);
                root = root.left;
            }
            root = stack.Pop();
            k--;
            if(k==0){return root.val;}
            root = root.right;                
        }
    }
}

Leetcode題解 Python & C#：五月挑戰DAY19 Online Stock Span

做一個 StockSpanner 收集每日價格資訊 price (int)，並有設方法 next() 輸入 price ，回傳當前 price 是幾日新高。
對於這樣的問題，要想會不會用上 遞增數列 的觀念，這是這類題的一種數學思維，想通就會做。
(遞增數列的典型倒是沒有想到有什麼特徵可以快速抓出該用這個概念)
如果前面不超過price(<= price)，那麼就把前方的紀錄丟掉。如果沒資料可丟，代表目前是紀錄中最大的。
用一個計數 count，把用 next() 次數保留下來，就可以其減出當前price是幾日新高。(若沒紀錄，則 count – 0)
並且把 price 跟 count 添加到紀錄中，price跟count的紀錄代表前方沒有比price更高的。
官方寫法用 weight ，省下了 1 空間，但功能跟 count 都是記錄次數的。

Python
class StockSpanner:

    def __init__(self):
        self.prices = []
        self.count = 0


    def next(self, price: int) -> int:
        self.count += 1
        result = self.count
            
        while self.prices and self.prices[-1][0] <= price:
            del self.prices[-1]
            
        if self.prices:
            result -= self.prices[-1][1]
            
        self.prices.append([price, self.count])

        return result

C# 

public class StockSpanner {
    List prices;

    public StockSpanner() {
        prices = new List();
    }
    
    public int Next(int price) {
        int result = 1;
        int i = prices.Count - 1;        
        while(i >= 0 && prices[i].price <= price)
            {
            result += prices[i].days;
            i -= 1;
            }
        prices.RemoveRange(i+1, prices.Count-i-1);
        prices.Add((price, result));
        return result;

} }

Leetcode題解 Python & C#：五月挑戰DAY18 Permutation in String

給二字串 s1 s2，問 s2 是否有含 s1 的排列。

這題跟昨天的原理一樣，就不多說了。 DAY17

Python 

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        count = Counter(s1)
        match_len = 0
        p_len = len(s1)
        for i, c in enumerate(s2):
            while match_len and (c not in count or count[c] == 0):
                count[s2[i - match_len]] += 1
                match_len -= 1
            if c in count and count[c] > 0:
                match_len += 1
                count[c] -= 1
                if match_len == p_len:
                    return True
        return False

C#
public class Solution {
    public bool CheckInclusion(string s1, string s2) {
        var count = new int[26];
        foreach(char c in s1)
        {
            count[c - 'a'] += 1;
        }        
        int match_len = 0;        
        for(int i = 0; i < s2.Length; i++)
        {
            char c = s2[i];
            while(match_len > 0 && count[c - 'a'] == 0)
            {
                count[s2[i - match_len] - 'a'] += 1;
                match_len -= 1;
            }
            if(count[c - 'a'] > 0) 
            {
                match_len += 1;
                count[c - 'a'] -= 1;
                if(match_len == s1.Length)
                {
                    return true;
                }
            }
        }            
        return false;
    }
}

Leetcode題解 Python & C#：五月挑戰DAY17 Find All Anagrams in a String

給一個字串 s 跟 非空字串 p 。要從 s 中找出所有 p 字謎的的起始位置。
(字謎是所有字母都出現一次，連續出現但順序可以變動)

如果順序不重要，那麼用 hashtable 記下哪些字母出現與次數及可。

從 s 開頭，依序匹配，是否在hashtable中及目前有可匹配的次數嗎？如果有，該字母的可匹配的次數 – 1，匹配長度 +1。
如果沒有，用匹配長度把最前方的已匹配字母放回hashtable所對應的次數，直到匹配或是匹配長度歸零為止。

如果匹配長度與 p 長度相同，則回推開始位置放入 result 中。

Python 

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        count = Counter(p)
        match_len = 0
        p_len = len(p)
        result = []
        for i in range(len(s)):
            c = s[i]
            while match_len and (c not in count or count[c] == 0):
                count[s[i-match_len]] += 1
                match_len -= 1
            
            if c in count and count[c] > 0:
                count[c] -= 1
                match_len += 1
                if match_len == p_len:
                    result.append(i-p_len+1)
                        
        return result

C# 

public class Solution {
    public IList FindAnagrams(string s, string p) {
        var count = new Dictionary();
        foreach(char c in p)
        {
            if(count.ContainsKey(c))
                count[c] += 1;
            else
                count[c] = 1;
        }
        var result = new List();
        int match_len = 0;
        for(int i = 0; i < s.Length; i ++)
        {
            char c = s[i];
            bool hasKey = count.ContainsKey(c);
            while(match_len > 0 && (!(hasKey) || count[c] == 0))
            {
                count[s[i - match_len]] += 1;
                match_len -= 1;
            }   
            if(hasKey && count[c] > 0)
            {
                match_len += 1;
                count[c] -= 1;
                if(match_len == p.Length)
                    result.Add(i - match_len + 1);
            }
        }
        return result;
    }
}

Leetcode題解 Python：Form Largest Integer With Digits That Add up to Target

給一串數字[1-9]的花費 cost，跟 總花費 target，回傳總花費相等的最大可能數字。
這題是DP，我本來感覺沒很難，結果敗在這裡 QQ 。考驗對DP與遞迴函數的熟練度。(我用了一些時間才精簡到可行)
對於規劃，函數要使用 t 也就是剩餘的花費，在同一個 t 之下，結果只會有一個最大值。
(我一開始用三個、二個都會超時，睡起再改成一個)
於是要朝著 dfs(t) 的方向前進。
在[1-9]花費有可能一樣的，為了加速，二者花費相等，只要保留較大的數字，結果也只會用到最大的數字。
如果 t == 0 做中止條件，那麼就無法知道是哪個數字讓其歸零。
得用 t – each_cost == 0，這樣就可以知道哪個數字了。
回傳值是最大的數字，若 t – each_cost > 0，那麼應該用 dfs(t – each_cost)去找出後面的最大數字，
並與 each_cost 代表的數字結合。
而 each_cost 有數種，同個 t 之下也有不同的組合，所以用 max() 去選出最大的數字，才能符合設計。

Python 

class Solution:
    def largestNumber(self, cost, target) -> str:   
	from functools import lru_cache     
        cost_dict = dict()        
        for i, c in enumerate(cost):
            cost_dict[c] = str(i+1)
        sorted_dk = sorted(cost_dict.keys())

        @lru_cache(None)
        def dfs(t):           
            ans = 0
            for c in sorted_dk:              
                if t - c == 0:                     
                    ans = max(ans, int(cost_dict[c]))
                elif t - c < 0: 
                    break
                else: 
                    result = dfs(t - c)
                    if result != "0": 
                        ans = max(ans, int(cost_dict[c] + result))
            return str(ans) 

        return dfs(target)

Leetcode題解 Python & C#：五月挑戰DAY16 Odd Even Linked List

給一個 linked list，要以 偶數位 奇數位 重新排列。
要求在 O(1) Space、 O(n) Time 解決。
分別拆成偶數奇數頭出來，再把剩下的 linked list 分給兩者，最後合併，回傳偶數頭。這符合題目要求。
或者直接在頭尾開始接，但這預期不如上者，因為上者到 n-1 位置時，就幾乎要完成了；而這方法才剛開始。

Python 

class Solution:
    def oddEvenList(self, head: ListNode) -> ListNode:
        if not head or not head.next: return head
        oddHead = OP = head
        evenHead = EP = head.next
        #
        head = head.next.next
        i = 0
        while head:
            i += 1            
            if i % 2 == 1:
                OP.next = head
                OP = OP.next
            else:
                EP.next = head
                EP = EP.next 
            head = head.next
        EP.next = None 
        OP.next = evenHead
        return oddHead

C# 

public class Solution {
    public ListNode OddEvenList(ListNode head) {
        if(head is null){return head;}
        if(head.next is null){return head;}
        ListNode OddHead = head; ListNode OddLN = OddHead;
        ListNode EvenHead = OddHead.next; ListNode EvenLN = EvenHead;
        head = head.next.next;
        int i = 0;
        while(!(head is null))
        {
            if(i % 2 == 0)
            {
                OddLN.next = head;
                OddLN = OddLN.next;
            }
            else
            {
                EvenLN.next = head;
                EvenLN = EvenLN.next;
            }
            i += 1;
            head = head.next;
        }
        EvenLN.next = null;
        OddLN.next = EvenHead;
        return OddHead;
    }
}

目前趨勢

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