Leetcode題解 Python & C#：六月挑戰DAY16 Validate IP Address

給一個字串 IP ，回傳其屬於 IPv4 或 IPv6 或都不是 Neighter。 
如果要找「合格」的字串，會想到用 re 去解決，這是在一般的情況下。如果是LeetCode，也許就不會用它。
不過官方的解法是有用到 re 的，直接傻眼，但那確實是最正當的解法。
通過「正則表達式(Regex)」是最嚴謹的做法，但也要有支持這項功能，在未知跟沒有的情況下，只能土炮出來。
這裡要從根本講，不論IPv6或是IPv4對電腦來說都是連續的二進位，IPv4長度為32bit，IPv6為128bit。
給人看的十進位跟十六進位是經由轉換而來的，如果換回原來的二進位形式，就只要留意是否長度是否合格就好。
所以把 string IP 轉換成連續二進位，就能輕而易舉去找出是否為合格的IP位置。(但是寫轉換的過程不容易) 

在 IPv4 中用「.」做分隔，是用十進位的數字，分四段，每一段要有8bit。
在 IPv6 中用「:」做分隔，是用十六進位的數字，分八段，每一段要有32bit。
寫成IP轉換版，轉 IPv6 或 IPv4 的流程是大同小異的，甚至可以只用一個函數修改一些傳入參數就能變成IPv4或IPv6皆可的式子。

Python 

class Solution:
    def validIPAddress(self, IP: str) -> str:
        
        deci = {*"0123456789"}
        hexdeci = {*"0123456789abcdef"}
        
        def checkIPv4(IP):
            group = IP.split(".")
            if len(group) != 4: return False
            for seg in group:
                if not(3 >= len(seg) >= 1): return False 
                if any([c not in deci for c in seg]): return False
                if not(255 >= int(seg) >= 0): return False
                if str(int(seg)) != seg: return False
            return True

        def checkIPv6(IP):            
            group = IP.lower().split(":")   
            if len(group) != 8: return False
            for seg in group:
                if not(4 >= len(seg) >= 1): return False                    
                if any([c not in hexdeci for c in seg]): return False                    
            return True
        
        if checkIPv4(IP): return "IPv4"
        if checkIPv6(IP): return "IPv6"
        return "Neither"

Python(IP轉換版) 

class Solution:
    def validIPAddress(self, IP: str) -> str:   
        
        decimal = {*"0123456789"}
        
        def covertIPv4(IP):
            IPv4 = ""
            seg = ""
            segCount = 0
            for c in IP:
                if c == ".":
                    segCount += 1
                    if segCount >= 4 or not seg: return False
                    if len(seg) > 1 and seg[0] == '0': return False
                    seg = "{:0>8}".format(bin(int(seg))[2:])
                    if len(seg) > 8: return False
                    IPv4 += seg
                    seg = ""
                elif c in decimal:
                    seg += c
                else:
                    return False
            if seg:                
                if len(seg) > 1 and seg[0] == '0': return False                
                seg = "{:0>8}".format(bin(int(seg))[2:])
                if len(seg) > 8: return False
                IPv4 += seg  
            return len(IPv4) == 32
        
        hexadecimal = {*"0123456789abcdefABCDEF"}
        
        def covertIPv6(IP):
            IPv6 = ""
            seg = ""
            segCount = 0   
            for c in IP:
                if c == ":":   
                    segCount += 1
                    if segCount >= 8 or not seg: return False
                    seg = "{:0>16}".format(seg)
                    if len(seg) > 16: return False
                    IPv6 += seg
                    seg = ""    
                elif c in hexadecimal:
                    seg += "{:0>4}".format(bin(int(c, 16))[2:])
                else:
                    return False
            if seg:                
                seg = "{:0>16}".format(seg)
                if len(seg) > 16: return False
                IPv6 += seg  
            return len(IPv6) == 128                    
            
        if covertIPv4(IP): return "IPv4"
        if covertIPv6(IP): return "IPv6"
        return "Neither"

Python(IP轉換合一版) 

class Solution:
    def validIPAddress(self, IP: str) -> str:   
        
        decimal = {*"0123456789"}
        hexadecimal = {*"0123456789abcdef"}
        
        def covertIP(strIP, Segs, PerSegBit, Carry, Delimiter):            
            def addSeg(IP, seg):
                if segCount >= Segs or not seg: return False 
                if Delimiter == "." and len(seg) > 1 and seg[0] == '0': return False   
                if Delimiter == ":" and len(seg) > 4: return False  
                try:
                    seg = ("{:0>"+str(PerSegBit)+"}").format(bin(int(seg, len(Carry)))[2:])
                except:
                    return False
                if len(seg) > PerSegBit: return False
                return IP + seg                
            
            IP = seg = ""
            segCount = 0
            for c in strIP.lower():
                if c == Delimiter:
                    segCount += 1
                    IP = addSeg(IP, seg)
                    if not IP: return False
                    seg = ""
                elif c in Carry:
                    seg += c       
                else:
                    return False    
            if not seg: return False 
            IP = addSeg(IP, seg)
            if not IP: return False           
            return len(IP) == Segs * PerSegBit            
            
        if covertIP(IP, 4, 8, decimal, "."): return "IPv4"
        if covertIP(IP, 8, 16, hexadecimal, ":"): return "IPv6"
        return "Neither"

C# 

public class Solution {
    public string ValidIPAddress(string IP) {
        if(IsIPv4(IP)){return "IPv4";}
        if(IsIPv6(IP)){return "IPv6";}
        return "Neither";
    }    
 
    private bool IsIPv4(string IP) {
        var parts = IP.Split('.');
        if(parts.Length != 4){return false;}           
        int dec = 0;
        foreach(var part in parts)
        {
            if(!(Int32.TryParse(part, out dec))){return false;}
            if(dec  255 || (dec.ToString().Length != part.Length)){return false;}
        }
        return true;
    }

    private bool IsIPv6(string IP) {
        var parts = IP.Split(':');
        if(parts.Length != 8){return false;}        
        int hex;
        foreach(var part in parts)
        {
            if(part.Length > 4){return false;}
            if(!Int32.TryParse(part, 
                               System.Globalization.NumberStyles.HexNumber, 
                               null,
                               out hex)){return false;}
            if(hex < 0){return false;}
        }
        return true;
    }       
}

TestCase 

"1.1.1.01"
"01.01.01.01"
"001.001.001.001"
"301.301.301.301"
"12..33.4"
"1.0.1."
"1.-1.1.1"
"0.0.0.0"
"172.16.254.1"
"256.256.256.256"
"2001:0db8:85a3:0:0:8A2E:0370:7334"
"2001:0db8:85a3::8A2E:0370:7334"
"2001:db8:85a3:0:0:8A2E:0370:7334"
"20EE:FGb8:85a3:0:0:8A2E:0370:7334"
"2001:0db8:85a3:00000:0:8A2E:0370:7334"
"1081:db8:85a3:01:-0:8A2E:0370:7334"
"2001:0db8:85a3:0:0:8A2E:0370:7334:"

Leetcode題解 Python：Maximum Frequency Stack

實作一個 FreqStack，類似 stack，但 pop() 會先從出現次數最高的最後一個開始，也就是 出現次數 > 位置 的順序。
這題導入了 Freq 的計數，因此要有一個計數的設計，用一個 HashTable 去記錄 val 對應的出現次數。
接下來要把 stack 套上以計數為優先的方式，出現最多次的一定先被 pop() 掉，對相同次數的來說，pop() 是正常的。
但對不同次數的來說，一定要先 pop() 光更多次的，才會輪到自己這一層。
如果連 push 五次同一個 val，那麼會是第五次的 val 先被 pop() ，才會換到第四次的 val，中間會有個換層的移動，如果已經pop()光就往下一層。
fruq = {1:[val], 2:[val], 3:[val], 4:[val], 5:[val]}
在計數的時候，各 val 計數的最高值也就是最優先要被 pop() 的那一層，用一個 MaxFreq 去記錄。
fruq[MaxFreq].pop() 過後，fruq[MaxFreq] == [] 時， MaxFreq -= 1 ，同時也要把 count[val] -= 1。
雖然標 hard，但非常快就解出了，感覺要定為 medium。不過結果我寫的跟官方的只有變數命名有差。

Python 

class FreqStack:

    def __init__(self):
        self.count = defaultdict(int)
        self.freq = defaultdict(list)
        self.MaxFreq = 0

    def push(self, x: int) -> None:
        self.count[x] += 1
        self.freq[self.count[x]].append(x)
        self.MaxFreq = max(self.MaxFreq, self.count[x])

    def pop(self) -> int:
        num = self.freq[self.MaxFreq].pop()        
        self.count[num] -= 1
        if not self.freq[self.MaxFreq]: self.MaxFreq -= 1
        return num

Leetcode題解 Python & C#：Maximum Binary Tree

給一列沒有重複的整數陣列，要建立一個 maximum tree，規則如下，並回傳其 root 。

1.The root is the maximum number in the array.
2.The left subtree is the maximum tree constructed from left part subarray divided by the maximum number.

3.The right subtree is the maximum tree constructed from right part subarray divided by the maximum number.
root一定是陣列中最大的，最大值位置左方是左子樹的所有值，右方是右子樹的。
因此把 nums[:maxVal] 傳入到 constructMaximumBinaryTree 就可以得到左方子樹，右方也同理。
如此運作下去，最後會傳入一個空陣列，這就是「中止條件」，所以一遇到就馬上回傳 None 使其停止遞迴。

Python 

class Solution:
    def constructMaximumBinaryTree(self, nums: List[int]) -> TreeNode:
        if not nums: return None
        maxIdx = nums.index(max(nums))
        return TreeNode(nums[maxIdx], self.constructMaximumBinaryTree(nums[:maxIdx]), self.constructMaximumBinaryTree(nums[maxIdx+1:]))

C# 

public class Solution {
    public TreeNode ConstructMaximumBinaryTree(int[] nums) {
        if(nums.Length == 0){return null;}
        int maxIdx = Array.IndexOf(nums, nums.Max());
        return new TreeNode(nums[maxIdx], 
                            ConstructMaximumBinaryTree(nums.Take(maxIdx).ToArray()),
                            ConstructMaximumBinaryTree(nums.Skip(maxIdx+1).Take(nums.Length-maxIdx+1).ToArray()));
    }
}

Leetcode題解 Python & C#：六月挑戰DAY15 Search in a Binary Search Tree

給一個二元樹的根，要找到值為 val 的 node 並回傳，沒有則回傳 None。
這裡的二元樹是嚴格的，即 node 的左子樹皆小於自身，右子樹皆大於自身，即二元搜尋樹。
用一個標準的二元樹遞迴函數也能順利地解找到答案。
不過那樣會找到太多不必要的部分，也沒有用上二元搜尋樹的特色。
由於左邊皆比自身小，如果 val 小於 node.val，那就往左方而去，反之則右方。相等就直接回傳。

Python 

class Solution:
    def searchBST(self, root: TreeNode, val: int) -> TreeNode:
        while root:         
            if root.val == val: 
                return root
            elif root.val > val: 
                root = root.left
            elif root.val < val: 
                root = root.right
        return root

C# 

public class Solution {
    public TreeNode SearchBST(TreeNode root, int val) {
        if(root is null || root.val == val)
            return root;
        if(root.val > val)
            return SearchBST(root.left, val);
        else
            return SearchBST(root.right, val);
    }
}

Leetcode題解 Python：Allocate Mailboxes

給一個陣列 houses ，houses[i]為第 i 個房子的位置，k 為郵筒數，要找出最佳分配下，每房子到最近郵筒的總距離。 
如果郵筒數夠，在每房子前面設一個是最好的，但如果不夠，就會折衷，在房子間找個中間點去設立。
這其實是一個分群的問題。
要設一個郵筒，如果只有二間房子，那最佳位置會在中間。如果三間，那郵筒會在中間的房子前。
換句話說，如果房子有偶數個，在中間那二間之內都可以。如果有奇數個，那只能在中間的房子前。
找到如何決定最佳設置點，接下來就要分 k 組，找到最短的距離總和。

要能決定出一個區間需要有兩個 index， 分別為 l, i。有了 l, i 就能去算距離總和。
用 DFS ，一旦只剩一個郵筒可設，就從只能去算 [l, len(houses)]的距離總和。
如果有二個以上郵筒的可設，就從在 [l,i] 設 或 當前不設 dfs[l, i+1, remain] 的總距離取小者。
或者，以 i 去找 [i,n] 間的選一個位置 j ，將 [i, j]之間的房子配設一個郵筒，然後從中取最小值。
同樣地，若只剩一個郵筒可設，就直接算到 [i, len(houses)] 的距離總和。
這方法好處是少用一個 index，若迴圈定好，也不用做超出邊界的判斷。

Python 

class Solution:
    def minDistance(self, houses: List[int], k: int) -> int:
        houses.sort()
        n = len(houses)
        
        @lru_cache(None)
        def calu_dst(si, ei): 
            avg = houses[(si+ei)//2]
            return sum([abs(num - avg) for num in houses[si:ei]])

        @lru_cache(None)
        def dfs(i, remain):            
            if remain == 1: return calu_dst(i, n) 
            distance = 10000 # 1 <= houses[i] <= 10^4
            for j in range(i+1, n+1-remain+1):  
                distance = min(distance, calu_dst(i, j) + dfs(j, remain-1))             
            return distance
        
        return dfs(0, k)

Leetcode題解 Python：Find Two Non-overlapping Sub-arrays Each With Target Sum

給一個正整數陣列 arr ，跟一整數 target ，最找出二子陣列各自總和皆為target且二子陣列不重壘的最小長度總和。若沒有回傳 -1。
關於找子陣列(注意要為連續的或是稱序列)總和為target，通常用計算其累進值，accu[0] = arr[0], accu[1] = accu[0] + arr[0], accu[-1] = sum(arr)。
如果 accu[i] – target 在 accu 內，就代表有對應另外一個的連續子陣列存在。透過 accu[j] – accu[i] 可以找到 arr 任位置的連續子陣列總和。
在計算累進值的同時，就可以開始找目標值，也是這種算法的優勢，如果搭配 hash類 的查詢，只要累進值算完，就能找完所有可能，相當於 O(N) Time。 
首先要決定 ans 的預設值，因為如果拿 -1 當預設去比小，最後會是 -1 ，需要找一個比 -1 大且不會有可能出現的值，最大可能為 len(arr)，所以 ans 預設為 len(arr) + 1。
一旦有 accu[i] – target 出現，表示現在到找一段總和為 target，這一段的頭位置為 accu[i] – target 在 accu 中的位置，尾位置為 i 。
如果前面已經有一段，只要前一段的尾位置 >= 這一段的頭位置，代表兩者沒有重壘到，就能拿二段長度相交去更新 ans 。
每個找到的子陣列其尾位置(i)是最先被知道的，之後的找到的子陣列只要其頭位置在此或之後，都可以與之形成合格的可能總長度。
如在 i 位置上找到總長度最短的 shortest，在 i 位置之後的找到每段其頭位置在 i 或 i 之後，都能與 shortest 組合起來。
因此可這麼看，在i與之後的位置最小長都是 shortest。
每個位置都有一個 shortest，整體用 shortests 紀錄。
shortests [i] 為頭位置在 i 時能組合最小的長度。
每位置不論有沒有找到，都要把 shortest 保存在 shortests [i]。
(※shortest: [default,s1,s1,s1,s2,s2,s2,s2,s3,…,shortest] )
找到一段，就用該段的頭位置 headPos 去對 shortest[headPos] 得到前方可組合的最小長度，二者長度相加去更新ans。
shortest 預設也為 len(arr)+1 ，如果前方沒有找到或沒能組合的，也不會改動 ans。

Python 

class Solution:
    def minSumOfLengths(self, arr: List[int], target: int) -> int:
        accuPos = {0:-1}
        accu = 0
        ans = shortest = len(arr)+1 
        shortests = [len(arr)+1] * len(arr)    
        for i, num in enumerate(arr):
            accu += num
            accuPos[accu] = i
            if accu - target in accuPos:                   
                length = i - accuPos[accu - target] 
                if accuPos[accu - target] > -1:
                    ans = min(ans, length + shortests[accuPos[accu - target]])                              
                shortest = min(shortest, length)
            shortests[i] = shortest
        return -1 if ans == len(arr)+1 else ans

Leetcode題解 Python：Kth Ancestor of a Tree Node

有 n 個 node，編號為[0, n-1]，給一個 parent ，parent[i] 代表第 i 個 node 的 parent 為第 parent[i] 節。
然後給一 node 編號與 k ，要找出其第 k 個祖先。若沒有則回傳 -1 。
難的不是在於能不能順利找到，找到是難度 easy 的問題。難在於能不能「快速」地找到。
我在過程中有試過保存 2 跳的祖先，最糟也能在 25000 跳內解決，不過會超時。
關聯是一對一的，如果為每個node做map，即root到node的每node，就可以 1 跳解決，但是記憶體會爆，O(N**2) Space，因為每node的map都是不一樣的。
這題的關鍵在於要再哪一塊做取捨，如果純照parent跳，會用 O(N) Time。而且本題「大量」執行查詢，最多50000次，那會使沒做查詢優化的超時。
雖然我做了 2 跳祖先，但不夠，仍是 O(N) Time。如果換成保存「指數」跳的祖，就能把查詢變成 O(logN) Time，才有辦法應付大量的查詢。
依 parnet 可以找到 1(2**0) 跳的祖先，那 2(2**1) 跳的是1跳的再1跳，那 4(2**2) 跳呢？是2跳的再2跳。依此類推。

如果有 5 個 node ，那保存到 4(2**2)跳 的袓先就夠了；如果有 8 個 node，那保存到 8(2**3)跳。
因此要保存多少，看總數取log2決定，長度為 log2(n) + 1，而 + 1 是給 1(2**0)跳 空間。 
長度為16的話，代表最多也只會用到16次跳去找到第k個祖先。只有65535會用到16跳，因為其二進位有16個1。
這樣的保存轉換使 __init__() 會用上 O(NlogN) Time，而查詢會變成 O(logN) Time，但大量的查詢使其整體近 O(logN) Time，在效能與記憶體做最好的平衡。

Python

class TreeAncestor:
    def __init__(self, n: int, parent):
        m = int(math.log2(n)) + 1
        self.table = [[-1 for _ in range(m)] for _ in range(n)]      
        for p in range(1,n):       
            self.table[p][0] = parent[p]
            for k in range(1, m):
                self.table[p][k] = self.table[self.table[p][k-1]][k-1]
                if self.table[p][k] == -1: break

    def getKthAncestor(self, node: int, k: int) -> int:
        while k and node != -1:
            pos = int(math.log2(k))
            node = self.table[node][pos]
            k -= 1 << pos
        return node

Leetcode題解 Python & C#：六月挑戰DAY13 Largest Divisible Subset

給一組不同的正整數 nums，要找出滿足條件 s[i]%s[j]==0 or s[j]%s[i]==0 之最大的集合
這題要回傳的是「最大的集合」，所以需要先知道最大的，然後再回頭生成。
要滿足條件，大的一定要是次大的乘以某整數，這樣才能歸納於同一組，同時也符合餘數的條件。
我卡了很久，因為我一直想突破 O(N^2) 的障礙，要是想到 O(N^2) 的方法就不會去嘗試，而且對於這樣的題目被太多種DP衍生的可能給卡住。
大概花了二天，才完成我的理想型，也是最初設想的數學理論版。要把想法變成方法就是難度所在，也是樂趣所在。
一個排列過的最大集合，最大的一定是其左一個乘上某數，即「因數」。而一個數的左方會接子集合有最大數目的因數。

將 nums 先 sort() 過，接下來用 for 就會是而小至大的 num 。
比較的是「數目」，因此要保存每個數的最大可能數目，用 count 保存，每個數至少會有 1 即自身。
然而這題要的是最大數目的集合，所以不只要找出數目有多少，也要有能得到最大數目集合有哪些元素的手段。
一種是把所有可能取出來，再從中找到數目最大即可。二是弄成關聯的形式，再從最大數目的某一資訊去回溯出最大的集合。
走方案一比較直觀，但是會用上大量的記憶體，也比方案二慢。
選擇方案二，弄個關聯 path ，如果自身的因數在 nums 裡，那麼會從中選有最大數目集合的因數跟自身組合。
那個因數也是如此進行，直到找不到除了自身之外任何有在 nums 的因數。
如︰[1,2,4,8]，對 8 而言是 4 ，對 4 而言是 2 ，對 2 而言是 1 ，對 1 而言沒有，所以就停止，過程回溯了最大數目集合的所有元素。 
因此，在初始化的時候，每個數字的預設即為自身，如果有找到其它的因數在 nums 中，再去選擇有最大數目的因數 。
於是變成，對 1 而言是 1，所以就停止。(預期path = {1:1, 2:1, 4:2, 8:4})
確立了關聯，但要能回溯出來最大集合，一定要有最大數目集合的最大數值。 所以一旦當前 num 的最大數目是比紀錄更高，就把數字保存下來。
可能最大數目相同的集合會有二種以上，但哪一種都沒有關係，取一就好。
這題與其他題不一樣的是，合法的規則都建立在「因數」上，所以用因數的算法是最合理的，而不是從 nums 去一對對試 s[i]%s[j]==0 or s[j]%s[i]==0 。
因數的找法是從左右界找尋，左界預設為 1，右界預設為 nums[i]，下一輪，左界 + 1 為 2，右界為 nums[i]/2(左界) ，如果右界沒有整除，左界就繼續 + 1，右界為 nums[i]/左界。
這個找法會用上 O(N**(1/2)) Time ，然後所有元素都這樣用，整體會是 O(N**(3/2)) Time， 比起一對對試的 O(N**2) 是更快速的。

Python 

class Solution:
    def largestDivisibleSubset(self, nums):
        if not nums: return nums
        nums.sort()
        count = dict([(num, 0) for num in nums])
        path = dict([(num, num) for num in nums])
        max_num, max_count = nums[0], 0          
        for num in nums:
            l = 1
            r = num 
            while l <= r:
                if r in path and count[r]+1 > count[num]:
                    count[num] = count[r]+1 
                    path[num] = r
                if l in path and count[l]+1 > count[num]:
                    count[num] = count[l]+1 
                    path[num] = l
                l += 1
                while l <= r and num / l % 1 != 0:
                    r = num / l
                    l += 1                
                r = num // l
            if max_count < count[num]:
                max_num, max_count = num, count[num]
                
        result = [max_num]
        while path[max_num] != max_num:
            max_num = path[max_num]
            result.append(max_num)
        return result

C# 

public class Solution {
    public IList LargestDivisibleSubset(int[] nums) {
        var result = new List();
        if(nums.Length == 0){return result;}
        Array.Sort(nums);
        var path = new Dictionary();
        var count = new Dictionary();
        for(int i = 0; i < nums.Length; i++)
        {
            int num = nums[i];
            path[num] = num;
            count[num] = 0;
            //
            int l = 1;
            int r = num;
            while(l <= r)
            {
                if(path.ContainsKey(l) && count[l] + 1 > count[num])
                {
                    count[num] = count[l] + 1;
                    path[num] = l;
                }    
                if(path.ContainsKey(r) && count[r] + 1 > count[num] && r != num && r != l)
                {
                    count[num] = count[r] + 1;
                    path[num] = r;
                }                
                l += 1;
                r = num/l;
                while(l  0)
                {
                    l += 1;   
                    r = num/l;
                }                
            }
        }        
        int maxNum = count.Aggregate((x, y) => x.Value > y.Value ? x : y).Key;
        result.Add(maxNum);
        while(path[maxNum] != maxNum)
        {
            maxNum = path[maxNum];
            result.Add(maxNum);
        }
        return result;
    }
}

Leetcode題解 Python & C#：六月挑戰DAY14 Cheapest Flights Within K Stops

有 n 個城市，出發地 src 目的地 dst ，以及航次表 edges : [[cityA(src), cityB(dis), price]…]，最多可轉 K 站到 dis。
要在轉K站之內，找出從 src 到 dst 的最少的總花費，如果沒有則 -1 ，有則回傳花費。
QQ，最近兩天不順，沒有順利解Leetcode，昨日的挑戰也不小心中斷了。
這是一題「Path」題，找路線不外乎就是先把 edge 串連起來，然後再開始找。
 
最常用的是 Dictionary 做映照，如 DP[0] 要映出從 city0 可到的目的地，然後看題目決定要不要雙向，這題是不用雙向。
除了位置的連結，這題還要把花費累積，因此需要不斷從各可能花費取最小的保留。

Python 

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, K: int) -> int:
        flightMap = defaultdict(list)
        for f in flights:
            flightMap[f[0]].append((f[1], f[2]))
            
        path = dict()
        stack = [(src, 0)] 
        for i in range(K+2):            
            for _ in range(len(stack)):
                start, price = stack.pop(0)    
                if start not in path: path[start] = price
                elif price < path[start]: path[start] = price 
                else: continue
                for f in flightMap[start]:   
                    if dst not in path or price + f[1] < path[dst]:
                        stack.append((f[0], price +  f[1]))
                    
        return path[dst] if dst in path else -1

C# 

public class Solution {
    public int FindCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
        var flightMap = new Dictionary>();
        var priceMap = new Dictionary();
        foreach(var f in flights)
        {
            if (!(flightMap.ContainsKey(f[0]))){flightMap[f[0]] = new Dictionary();}
            flightMap[f[0]].Add(f[1], f[2]);
        }
        
        var queue = new Queue();
        queue.Enqueue(new int[2]{src,0});
        for(int i = 0; i < K + 2; i++)
        {
            int range = queue.Count;
            for(int j = 0; j < range; j++)
            {
                var f = queue.Dequeue();
                if(!(priceMap.ContainsKey(f[0])) || priceMap[f[0]] > f[1])
                {
                    priceMap[f[0]] =  f[1];
                    if (flightMap.ContainsKey(f[0]))
                    {
                        foreach(var nextCity in flightMap[f[0]])
                        {
                            queue.Enqueue(new int[2]{nextCity.Key, f[1] + nextCity.Value});
                        }
                    }
                }
            }
        }
        if (priceMap.ContainsKey(dst)){return priceMap[dst];}
        return -1;

Leetcode題解 Python & C#：Insert Delete GetRandom O(1) – Duplicates allowed

這題是「Insert Delete GetRandom O(1)」的進階，連運作原理都相同。

這次允許了重複出現，也就是說，一個數值的位置保存是要能容納多個的。

這時會有 list() 或是 set() 的取捨，但是由於要在 O(1) Time 的限制，就選擇 set() 來存放同val的多個位置。

其它都跟前一題差不多，前一題能解，這題就不是大問題。

Python 

class RandomizedCollection:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.posMap = defaultdict(set)
        self.data = list()        

    def insert(self, val: int) -> bool:
        """
        Inserts a value to the collection. Returns true if the collection did not already contain the specified element.
        """
        exist = val in self.posMap
        self.posMap[val].add(len(self.data))
        self.data.append(val)
        return not exist

    def remove(self, val: int) -> bool:
        """
        Removes a value from the collection. Returns true if the collection contained the specified element.
        """
        exist = val in self.posMap
        if exist:
            i = self.posMap[val].pop()    
            lastVal = self.data[-1]
            self.data[i] = lastVal
            self.posMap[lastVal].add(i)             
            del self.data[-1] 
            self.posMap[lastVal].discard(len(self.data))
            if not self.posMap[val]: del self.posMap[val]
        return exist        

    def getRandom(self) -> int:
        """
        Get a random element from the collection.
        """
        return self.data[int(random.random()*len(self.data))]

C# 

public class RandomizedCollection {
    private Dictionary> posMap;
    private List data;
    public Random rand;

    /** Initialize your data structure here. */
    public RandomizedCollection() {
        posMap = new Dictionary>(); 
        data = new List();
        rand = new Random();
    }
    
    /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
    public bool Insert(int val) {
        bool exist = posMap.ContainsKey(val);
        if(!(exist)){posMap[val] = new HashSet();}
        posMap[val].Add(data.Count);
        data.Add(val);
        return !(exist);
    }
    
    /** Removes a value from the collection. Returns true if the collection contained the specified element. */
    public bool Remove(int val) {
        bool exist = posMap.ContainsKey(val);
        if(exist)
        {
            int lastNum = data[data.Count - 1];
            int i = posMap[val].First();
            data[i] = lastNum;
            posMap[val].Remove(i);            
            posMap[lastNum].Add(i);
            data.RemoveAt(data.Count - 1);
            posMap[lastNum].Remove(data.Count);  
            if(posMap[val].Count == 0){posMap.Remove(val);}
        }
        return exist;        
    }
    
    /** Get a random element from the collection. */
    public int GetRandom() {
        return data[rand.Next(0, data.Count)];
    }
}

Leetcode題解 Python & C#：六月挑戰DAY12 Insert Delete GetRandom O(1)

設計一個資料結構，要在 O(1) Time 內完成 insert() remove() getRandom() 三個功能。

如果只有 insert 與 remove 那麼用 hash 系列是比較快的，不過多了 getRandom()，這使 hash 類的不能單獨使用，因為hash類的沒有 sequence 之分。
沒有序列之分，又要隨機，那就得把 hash 轉換成有 squence 的，用隨機抽一個位置。

但與其每次這樣轉換，倒不如多用一個有 squence 的做 val 的存放。更別提轉換會用到 O(N) Time。

要查 val 是否存在？去查 hash 系列的最快。要回隨機值？用有 squence 的再隨機回一個位置最快。

整合起來，val 不僅在有squence的資料類型存在，也要同時存在於hash系列。

以上已經把 insert 跟 getRandom 的注意細節講完，remove會是一個問題。

從hash系列移除 val 那只需要 O(1) Time，但在有squence的呢？要先找到 val 所在的位置才能移除，如果使用內置方法去找，會用O(N) Time，
因為它是從頭依序一個個找。所以，要有一個能保存 該val的位置 ，一查 val 就能得到 位置 的。

順水推舟，hash系列會用 hahsTable，對Python而言是「Dictionary」。

如果在 remove() 中，一查到 val 的位置就刪除，那麼在被刪除的val之後的位置應該也要往前推進，才能保持 Dictionary[val] 總是能正確反映出位置。
但是 Dictionary[val] 並不會隨著 val 在有squence的資料類型被刪除而自動改值，如果由後一個個往前推(即-1)，這過程也會用到 O(N) Time，因為不知道到底影響幾個。

被刪的後面有其它值，會影響甚大。但如果後方沒有任何值，那麼刪除也不會改動到別的位置，也就不必煩惱修改 Dictionary[val] 。

因此先把要被刪除的val與最後一個val作交換，再刪除最後一個，就能在 O(1) Time 完成 remove()。

Python 

class RandomizedSet:
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.data = list()
        self.key = dict()

    def insert(self, val: int) -> bool:
        """
        Inserts a value to the set. Returns true if the set did not already contain the specified element.
        """
        if val in self.key:
            return False
        else:
            self.key[val] = len(self.data)
            self.data.append(val)
            return True
        

    def remove(self, val: int) -> bool:
        """
        Removes a value from the set. Returns true if the set contained the specified element.
        """
        if val in self.key:
            i = self.key[val]
            self.key[self.data[-1]] = i
            self.data[i] = self.data[-1]
            del self.key[val], self.data[-1]
            return True
        else:
            return False

    def getRandom(self) -> int:
        """
        Get a random element from the set.
        """
        return self.data[int(random.random()*len(self.key))]

C# 

public class RandomizedSet {
    private Dictionary posMap; 
    private List data;
    private Random rand;
    
    /** Initialize your data structure here. */
    public RandomizedSet() {
        posMap = new Dictionary(); 
        data = new List();   
        rand = new Random();
    }
    
    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    public bool Insert(int val) {
        if (posMap.ContainsKey(val))
        {
            return false;
        }
        else
        {
            posMap[val] = data.Count;
            data.Add(val);
        }
        return true;
    }
    
    /** Removes a value from the set. Returns true if the set contained the specified element. */
    public bool Remove(int val) {
        if (posMap.ContainsKey(val))
        {
            int i = posMap[val];
            data[i] = data[data.Count-1]; 
            posMap[data[data.Count-1]] = i;           
            data.RemoveAt(data.Count-1);      
            posMap.Remove(val);
            return true;
        }
        else
        {
            return false;
        }
        
    }
    
    /** Get a random element from the set. */
    public int GetRandom() {
        return data[rand.Next(0, data.Count)];
    }
}

Leetcode題解 Python：Minimum Moves to Reach Target with Rotations

有一個 n * n 大小的網格，有一條蛇佔據二格，要從 (0,0) 和 (0,1) 移動到 (n-1,n-2) 和 (n-1, n-1)。
網格上的點為 0 代表是空的， 1 代表障礙。
蛇可以往右移或往下移，或是旋轉，旋轉以左上方的那格為基準，轉朝下或右。旋轉時鄰近右下那一格必需是 0 。
這題光寫基本流程就蠻花時間的，其實並不難。
首先如果有二個點且中間有障礙，要找最短路徑。可以想像用一個越來越大的圓，圓心是出發點，最後圓納入終點的時候，其半徑即為最短路徑。
向外擴張的時候，可以把每輪向外的一步都當成新的圓半徑。為了要實現這樣的方式，不能使用 DFS ，要用像是二元樹的階層式往深探索。
起點(0,0) steps: 0，下一輪往四周 (-1,0), (0,1), (0,-1), (1,0) steps: 1，為了避免重複尋找，要把找過的位置加入 memo ，
若從 memo 找到要找的位置，就直接換下一個找。
這題蛇加入了「旋轉」，朝右或朝下會影響下一步能怎麼走，所以除了位置之外，保存狀態也是必要的。
每一步以 (row, col, state) 保存，並且在每次尋找最前方做判斷，為中止條件。
如果以一個起點出發，要是可以通，在找到路徑之前，就會先探索許多背離終點的路徑。更好的作法是再加上從終點尋找，只要二者路徑重疊到，就代表找到最短路徑。

Python(One Start Point) 

class Solution:
    def minimumMoves(self, grid: List[List[int]]) -> int:
        # (row, col, state) = steps。 state: right = 0, down = 1.  
        n = len(grid)
        path = set()                           
        steps = [(0,0,0)]
        ans = 0
        while steps:
            for _ in range(len(steps)):
                row, col, state = steps.pop(0)                
                if (row, col, state) in path: continue
                if row == n-1 and col == n-2 : return ans
                path.add((row, col, state))
                shortPath = []                
                if state == 0:           
                    if col+2 < n and grid[row][col+2] == 0:
                        steps.append((row, col+1, state))
                    if row+1 < n and grid[row+1][col] == 0 and grid[row+1][col+1] == 0:
                        steps.append((row+1, col, state))               
                        steps.append((row, col, 1))  
                else:         
                    if col+1 < n and grid[row][col+1] == 0 and grid[row+1][col+1] == 0:
                        steps.append((row, col+1, state))
                        steps.append((row, col, 0))                       
                    if row+2 < n and grid[row+2][col] == 0 :
                        steps.append((row+1, col, state))      
            ans += 1
        return -1

Python(Two Start Point) 

class Solution:
    def minimumMoves(self, grid: List[List[int]]) -> int:
        # (row, col, state) = steps。 state: right = 0, down = 1.  
        n = len(grid)
        path = set()  
        path2 = set()
        steps = [(0,0,0)]
        steps2 = [(n-1,n-2,0)]
        ans = -1
        while steps and steps2:
            for _ in range(len(steps)):
                row, col, state = steps.pop(0)                
                if (row, col, state) in path: continue
                if (row, col, state) in path2: return ans
                path.add((row, col, state))              
                if state == 0:           
                    if col+2 < n and grid[row][col+2] == 0:
                        steps.append((row, col+1, state))
                    if row+1 < n and grid[row+1][col] == 0 and grid[row+1][col+1] == 0:
                        steps.append((row+1, col, state))               
                        steps.append((row, col, 1))  
                else:         
                    if col+1 < n and grid[row][col+1] == 0 and grid[row+1][col+1] == 0:
                        steps.append((row, col+1, state))
                        steps.append((row, col, 0))                       
                    if row+2 < n and grid[row+2][col] == 0 :
                        steps.append((row+1, col, state))      
            ans += 1
            for _ in range(len(steps2)):
                row, col, state = steps2.pop(0)                
                if (row, col, state) in path2: continue
                if (row, col, state) in path: return ans
                path2.add((row, col, state))               
                if state == 0:           
                    if col-1 >= 0 and grid[row][col-1] == 0:
                        steps2.append((row, col-1, state))
                    if row-1 >= 0 and grid[row-1][col] == 0 and grid[row-1][col+1] == 0:
                        steps2.append((row-1, col, state)) 
                    if row+1 < n and grid[row+1][col] == 0 and grid[row+1][col+1] == 0:
                        steps2.append((row, col, 1))  
                else:     
                    if row-1 >= 0 and grid[row-1][col] == 0 :
                        steps2.append((row-1, col, state))                      
                    if col-1 >= 0 and grid[row][col-1] == 0 and grid[row+1][col-1] == 0:
                        steps2.append((row, col-1, state))                                               
                    if col+1 < n and grid[row][col+1] == 0 and grid[row+1][col+1] == 0:
                        steps2.append((row, col, 0))
            ans += 1
        return -1

## 非正解，不小心寫錯的版本

Python(可上下左右的版本) 

class Solution:
    def minimumMoves(self, grid: List[List[int]]) -> int:
        # dp[row][col][state] = steps 
        # state: right = 0, down = 1.
        # return dp[row-1][col-2][0]
        n = len(grid)
        path = set()                           
        steps = [(0,0,0)]
        ans = 0
        while steps:
            for _ in range(len(steps)):
                row, col, state = steps.pop(0)                
                if (row, col, state) in path: continue
                if row == n-1 and col == n-2 : return ans
                path.add((row, col, state))             
                if state == 0:
                    if 0 and col-1 >= 0 and grid[row][col-1] == 0:
                        steps.append((row, col-1, state))             
                    if col+2 < n and grid[row][col+2] == 0:
                        steps.append((row, col+1, state))
                    if 0 and row-1 >= 0 and grid[row-1][col] == 0 and grid[row-1][col+1] == 0:
                        steps.append((row-1, col, state))  
                    if row+1 < n and grid[row+1][col] == 0 and grid[row+1][col+1] == 0:
                        steps.append((row+1, col, state))               
                        steps.append((row, col, 1))  
                else:
                    if 0 and col-1 >= 0 and grid[row][col-1] == 0 and grid[row+1][col-1] == 0:
                        steps.append((row, col-1, state))             
                    if col+1 < n and grid[row][col+1] == 0 and grid[row+1][col+1] == 0:
                        steps.append((row, col+1, state))
                        steps.append((row, col, 0))                       
                    if 0 and row-1 >= 0 and grid[row-1][col] == 0 :
                        steps.append((row-1, col, state))  
                    if row+2 < n and grid[row+2][col] == 0 :
                        steps.append((row+1, col, state))      
            ans += 1
        return -1

目前趨勢

Aruba CX Switch Network Analytics Engine (NAE) 入門
忘記行李後的心情低落
2017.9.23 學習了一個月的python歷程
臺鐵大誤點以及捲簾式快門