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;
    }
}

Leetcode題解 Python & C#：五月挑戰DAY15 Maximum Sum Circular Subarray

給一個環形陣列 A，要找出總和最大的子陣列。
這題蠻有意思的，讓我沒有順利解出來，有想到好幾種可能，看了別人的解法，發現是用最大最小的方式。
但我想到這方法的當下，沒有去進一步思考。
官方有 Solution ，內有四種解法，但我還是照步調去走從未知去導出解法的思維分析。
如果會做陣列中子陣列最大總和，那環形的也只是稍做變化。
要如何後面接回前面？這是第一個要解決的問題。

對於一個陣列來說，用Python是可以再添加一個一樣的，達到 2n 的長度，在 n – 1 位置之後，又會回到開頭的值。
但由於限制每個元素只能被取一次，這作法可能會讓一元素被選中二次(如全部為正的)，並不是一種簡單可行的方法。
又或者弄 linked list ，然後作 DP 以各元素的選取保存每一位置的最大值總和。這能避免重複，但寫來會有點麻煩。
照著 Hint ，要用「 Kadane’s algorithm 」， 然而這不是算環形的陣列，需要改良才能用上。如果只跑一遍陣列，那也不會碰到同元素被選二次的狀況。
如果最大值落於陣列間，最後的位置不是 n – 1，那 Kadane’s algorithm 就可以找出正解。
但最後位置有碰到 n – 1，那麼就會接回開頭去找的需求。
再思考，如果目前正計算最大的子陣列，沒到計算結束前是不知道目前的是否處在最大子陣列中。而且 Kadane’s algorithm 的方式也沒有保存位置，判斷最後位置並不是好的方法。
但以結果回推，最大子陣列以外的元素加總就是最小子陣列。
因此取得最小子陣列的總和，用整個數列的總和去減它，也可以得到最大子陣列的總和。
如果最小子陣列在陣列之間，那最大子陣列會是環形接起的。
因此所求在「陣列(沒有環)子陣列最大總和」或「總合減陣列子陣列最小總和」中，兩者取大。
但這樣子有一個狀況，如果是遞減數列，最小總和會是全體元素集合，而總和減去它會是 0 ，也比最大總和還大。
因此，如果 總和 == 子陣列最小總和 ，那只能回傳前者。

Python 

class Solution:
    def maxSubarraySumCircular(self, A: List[int]) -> int:
        min_now = max_now = A[0]        
        nmin = nmax = nsum = A[0]
        for num in A[1:]:
            min_now = min(num, min_now + num)
            nmin = min(nmin, min_now)
            max_now = max(num, max_now + num)
            nmax = max(nmax, max_now)
            nsum += num
        if nsum == nmin: return nmax
        return max(nsum - nmin, nmax)

C# 

public class Solution {
    public int MaxSubarraySumCircular(int[] A) {
        int min_now = A[0]; int max_now = A[0];
        int nmin = A[0]; int nmax = A[0]; int nsum = A[0];
        for(int i = 1; i < A.Length; i++)
        {
            int num = A[i];
            min_now = (min_now + num < num) ? min_now + num : num;
            nmin = nmin < min_now ? nmin : min_now;
            max_now = (max_now + num > num) ? max_now + num : num;
            nmax = nmax > max_now ? nmax : max_now;
            nsum += num;
        }
        if(nsum == nmin){return nmax;}
        return (nmax > nsum - nmin) ? nmax : nsum - nmin;
    }
}

Leetcode題解 Python & C#：五月挑戰DAY14 Implement Trie (Prefix Tree)

要實作 trie ，有 insert, search 和 startsWith 的功能。

trie 很實用，但在 algorithm 中，不太好用上這樣的方法解題。昨日在學 cisco ，就使用 trie 來加速指今輸入。

由於 Leetcode 有教學，這裡就不多說如何解題。(如果懂 trie 是怎樣的型態就會知道要怎麼寫)

Python

class Trie:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.trie = {}
        

    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        now = self.trie
        for char in word:
            if char not in now: now[char] = {}                
            now = now[char]
        now['exist'] = True
        

    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        now = self.trie
        for char in word:
            if char not in now: return False
            now = now[char]
        return 'exist' in now 
        

    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        now = self.trie
        for char in prefix:
            if char not in now: return False
            now = now[char]
        return True

C# 

class TrieNode
{
    public bool End;
    public Dictionary Next;
    public TrieNode() {   
        Next = new Dictionary();
        End = false;
    }
}

public class Trie {
    private TrieNode root;
    /** Initialize your data structure here. */
    public Trie() {
        root = new TrieNode();
    }
    
    /** Inserts a word into the trie. */
    public void Insert(string word) {
        TrieNode now = root;
        foreach(char c in word)
        {
            if(!(now.Next.ContainsKey(c)))
            {
                now.Next[c] = new TrieNode();
            }
            now = now.Next[c];
        }
        now.End = true;
    }
    
    /** Returns if the word is in the trie. */
    public bool Search(string word) {
        TrieNode now = root;
        foreach(char c in word)
        {            
            if(now.Next.ContainsKey(c))
            {
                now = now.Next[c];
            }
            else
            {
                return false;
            }
        }
        return now.End;        
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public bool StartsWith(string prefix) {
        TrieNode now = root;
        foreach(char c in prefix)
        {            
            if(now.Next.ContainsKey(c))
            {
                now = now.Next[c];
            }
            else
            {
                return false;
            }
        }
        return true;
    }
}

目前趨勢

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