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

Leetcode題解 Python & C#：六月挑戰DAY11 Sort Colors

有三種顏色，編號為 0, 1, 2。給一個陣列包含三種顏色，要在 in-place 去由小至大排序過。
Note：不要使用內建的 sort() function。
題目給了兩種方向，先 Count 後排序，二是跑一遍就完成。方向一太簡單，數完各顏色再從頭依種類、數量做替換。
二被限制只能用常數空間，換句話說，只能記沒有長度的數值。
答案一定是 0 都在陣列的最左方， 2 都在陣列的最右方。如果 pass 一遍，遇 0 往左擺，遇 2 往右擺，這樣就能快速分類。
左方擺過 0 的位置就不再使用，同理右方擺過 2 的，如果重複用到，就會破壞已經排好的序列。
因此採用 「Two Pointer」 ，而 Two Pointer 也是一個 O(1) Space 的方法。
pass 過程遇到 0 或 2 都會使左界或右界縮窄，可以想成把答案夾出來。

Python 

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        l, m, r = 0, 0, len(nums)-1     
        while m <= r:
            if nums[m] == 0:
                nums[l], nums[m] = nums[m], nums[l]
                l += 1    
                m += 1
            elif nums[m] == 2:
                nums[r], nums[m] = nums[m], nums[r]
                r -= 1      
            else:
                m += 1

C# 

public class Solution {
    public void SortColors(int[] nums) {
        int l = 0;
        int m = 0;
        int r = nums.Length-1;
        int tem = -1;
        while(m <= r)
        {
            if(nums[m] == 0)
            {
                tem = nums[l];
                nums[l] = 0;
                nums[m] = tem;
                l += 1;    
                m += 1;
            }
            else if(nums[m] == 2)
            {
                tem = nums[r];
                nums[r] = 2;
                nums[m] = tem;
                r -= 1;      
            }else
            {
                m += 1;
            }
        }        
    }
}

Leetcode題解 Python & C#：六月挑戰DAY10 Search Insert Position

給一個排序過的數列 nums 和目標值 target，要找出 目標值 insert() 到 nums 後的不影響排序的位置。 
nums是遞增(升序)排列，因此要找到一個位置 index ，該位置使 nums[index – 1] = target。
可以從最前方開始找，快一點的做法是使用二分搜尋。

Python 

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums)
        while l < r:
            m = (r-l)//2+l
            if nums[m] == target:
                return m
            elif nums[m] >= target:
                r = m                
            else:
                l = m+1
        return r

C# 

public class Solution {
    public int SearchInsert(int[] nums, int target) {
        int l = 0;
        int r = nums.Length;
        while(l < r)
        {
            int m = (r-l)/2 + l;
            if(nums[m] == target)
                return m;
            else if(nums[m] > target)
                r = m;
            else
                l = m + 1;
        }
        return r;
    }
}

Leetcode題解 Python & C#：六月挑戰DAY9 Is Subsequence

給字串 s 和字串 t，找出 s 是否為 t 的子順序。子順序是相對位置不變，但中間可以刪減部分字元。

 這類的題目在LeetCode有不少，但變化性少，只會這個學會了，就能解部分類似的。
依 Follow up 的方式，我猜，要從 s 的組成字元逐一找該字元是否在 t 裡面，但我不是很懂它想表達的意思。
但沒關係，我的解法也是逐一去找的運作模式。
既然子順序的中間可以塞入非配對的字元，那可想成把那些字元拿掉後，剩下的字串跟 s 能全配對那就是 True。
從 t  的左至右搜查，如果匹對到 s[0] ，那就只能目前從 t 剩下的去匹配 s[1] ，中間沒匹配的都是可以拿掉的字元。
當 len(s) == 0 的時候，即為全匹配。如果還有 s 的字元但 t 已經到最後，那就沒有成功匹配。

Python
class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:        
        if not s: return True
        for i, c in enumerate(t):
            if c == s[0]:
                return self.isSubsequence(s[1:], t[i+1:])
        return False

C# 

public class Solution {
    public bool IsSubsequence(string s, string t) {
        int n = s.Length;
        if(n == 0){return true;}
        int si = 0;
        foreach(char c in t)
        {
            if(c == s[si])
            {
                si += 1;
                if(si == n){return true;}
            }
        }
        return false;
    }
}

Leetcode題解 Python & C#：六月挑戰DAY8 Power of Two

給一個整數，回傳該數是否為 2 的次方。
除了要注意整數 0 與負整數，其他整數都比較沒有問題。
2 的零次方是 1 ，而負次方都位於[0, 1]之間，也不是整數。所以只需要考量零以上次方要怎麼找。
如果是二的次方，除以二的餘數皆為 0，用此條件，只要餘數為 1 就不是 2 的次方。一直除到變成 1 (2**0)時，確定輸入是 2 的次方。
換一種進位，以「二進位」來看，二的次方，只會有一個bit為 1，最高位的bit為1，其餘為 0 ，所以只要判斷是否bit只存在一個1。

Python(除二餘數) 

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        if n <= 1: return n == 1
        return self.isPowerOfTwo(n//2) if n % 2 == 0 else False

Python(bit存在只有1個1) 

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        if n < 1: return False
        while n & 1 == 0:
            n >>= 1
        return n >> 1 == 0

Python(最高位為1) 

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        return n > 0 and n == (1 << (n.bit_length()-1))

C# 

public class Solution {
    public bool IsPowerOfTwo(int n) {
        if(n <= 1){return n == 1;}
        return n % 2 == 0 ? IsPowerOfTwo(n/2): false;
    }
}

Leetcode題解 Python & C#：六月挑戰DAY7 Coin Change 2

給各硬幣的幣值 coins，與目標金額 amount ，要找出有幾種硬幣組合的總金額會等於 amount。
在這題琢磨了好幾小時，因為對於 DP 速度感到好奇，這題用 DFS 就是慢。
對於這種求特定組合數的題目，最重要的就是去看限制條件，再決定 DP 要取什麼要比較快。
「0 <= amount <= 5000」這意味著每道題目的答案並不是大數目，從「the answer is guaranteed to fit into signed 32-bit integer」也可得知。
如果是天文數字，就會有 % (10**9+7) ，這樣的題型不可能遍歷所有位置去解。但這題最快的方法是去跑遍所有位置。

這題用 DFS 無法達到「收斂」的效果，收斂要把幾種可能答案做取捨並向上傳遞，用 DFS 只能開支散葉，也就不需要用遞迴函數。
用各硬幣累加，在總金額 0 的地方預設為 1 ，各幣從幣值處開始，dp[i] += dp[i-coin]，直到 i 超出 amount。
如 5, [1,2,5]，在 dp[2] == 2，到達此處的方法有 1*2, 2*1，或寫 1 + 1, 0 + 2。固定增加的方式，輪到幣值永遠加在已計路逕的最後方，也使得不會有重複出現。 
1: [1,1,1,1,1,1]
2: [1,1,2,2,3,3]
5: [1,1,2,2,3,4]
「1」：1+1+1+1+1 => dp[4] 
「2」：1+1+1+2 => dp[3]
「2」：1+2+2 => dp[3] => 1+2(dp[1]) + 2
「5」：5 => dp[0]

Python 

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp  = [0] * (amount+1)
        dp[0] = 1
        for coin in coins: 
            for i in range(coin, amount+1):                
                dp[i] += dp[i - coin]
        return dp[-1]

C# 

public class Solution {
    public int Change(int amount, int[] coins) {
        var dp = new int[amount+1];
        dp[0] = 1;
        foreach(int coin in coins)
        {
            for(int i = coin; i <= amount; i++)
            {
                dp[i] += dp[i - coin];
            }
        }
        return dp[amount];
    }
}

Leetcode題解 Python：Next Greater Element I & II & III

在 contest 前，來抽一題暖手感，剛好就中這一題，有系列就依序解完吧。
(這次的contest有解完)

【Next Greater Element I】

給二個陣列 nums1 和 nums2，nums1 是 nums2 的子集合。
依 nums1 的元素找出(對應nums2位置)下一個比自身大的值。如果沒有則 -1 ，回傳所有的結果 List。
由於 nums1 並非照著原來在 nums2 的相對關係排序，最快的方法是依照 nums1 的元素，在 O(N) Time 解決。
但如果從 nums2 對應的位置開始照規則找，最糟會到 O(N^2) Time。
先找出所有的答案再依 nums1 重組，時間複雜度恰好 O(MN) ，也不用在找答案過程做是否在 nums1 的判斷。

每個元素只要找後方第一個大於它的元素，用一個暫時的「遞增數列」，因為要從後方找，所以從後方開始，就能確保沒有比它大的而馬上填 -1。
(位置不能動，找之於每個元素大或小，或一區段內最大或或最小面積，就可能用上遞增遞減數列)

Python(後往前) 

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        if not nums1 or not nums2: return []
        memo = dict()        
        result = []
        while nums2:
            num = nums2.pop()          
            while result and result[0] <= num:
                del result[0]
            memo[num] = result[0] if result else -1
            result.insert(0, num)

        return [memo[num] for num in nums1]

Python(Stack) 

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        if not nums1 or not nums2: return []
        memo = dict()
        result = []
        for i in range(len(nums1)):
            memo[nums1[i]] = i
            result.append(-1)

        stack = []
        for num in nums2:
            while stack and stack[-1] < num:
                if stack[-1] in memo:
                    result[memo[stack[-1]]] = num
                    del memo[stack[-1]] 
                del stack[-1]
            stack.append(num)
        return result

【Next Greater Element II】

一樣的規則，但是變成 circle array，也就是頭接尾。
circle 也可以用系列I的方法，只要把輸入變二倍去解，最後再取原本的長度(題目所求)回傳。
但是擺成二倍等於要跑二偣 N ，也不好。同樣在 O(N) Time ime 也是有高下之分的。
有什麼數字後方一定找不到更大的？最大值，也只有最大值找不到，其餘找到的必 <= 最大值。
把最大值移到最後，就可以用「 Next Greater Element I 」的方法找，再把順序換回所給的順序就能解了。
如 ：[1,2,1] => [1,1,2] 。只有最大值的解會是 -1 ，因此把最大值放到最後，可確保每個位置答案都正確。
 [2,2,-1]，需要換回成 [2,-1,2]，依當初往後挪動多少，就把答案往前挪，舉例是 1 ，故往前挪 1。 [2,2,-1] => [2,-1,2]

Python 

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:  
        mi = nums.index(max(nums))
        array = []
        n = len(nums)
        result = [-1 for _ in range(n)]            
        for i in range(n,0,-1):
            ix = (i+mi)%n
            num = nums[ix]   
            while array and array[0] <= num:
                del array[0]
            if array: result[ix] = array[0]
            array.insert(0, num)

        return result

Python(Stack) 

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]: 
        if not nums: return nums
        n = len(nums)        
        mi = nums.index(max(nums))       
        result = [-1 for _ in range(n)]          
        stack = []
        for i in range(n):
            ix = (i+mi+1)%n
            num = nums[ix]   
            while stack and nums[stack[-1]] < num:
                result[stack.pop()] = num
            stack.append(ix)           
        return result

【Next Greater Element III】

這題就不在 I、II 的後續，而是一個獨立的題型。
給一個正整數 n ，要找出數字集合相同，下一個更大的數字。更大的可能有很多，要回傳其中最小的。
前面的解法都基於「遞增數列」，這題也是得用這概念去解。
 
有一個數字集合，其最大值的排法為「非遞增數列」的時候，即 nums[i] >= nums[i+1]。
若反過來從後方看，就是非遞減數列。要使 n 變大一些，從後方開始找是最好的方式。
一旦找到一個數字破壞了非遞減數列，那就代表需要交換此數字、從後方選一個最小的大於此數字交換，然後反轉後方順序。
要交換的數字後方是非遞增數列(排序組合中的最大值)，然而在交換數字後也能保持排序規則。
因此再將順序反轉後，非遞增數列就會變成非遞減數列(排序組合中的最小值)，也就是最小增加。

Python 

class Solution:
    def nextGreaterElement(self, n: int) -> int:
        stack = [n % 10]
        n //= 10
        while n and n % 10 >= stack[-1]:
            stack.append(n % 10)
            n //= 10
        if not n: return -1
        
        num_change = n % 10
        stack.sort()
        l, r = 0, len(stack)        
        while l < r:
            m = (r-l)//2 + l
            if stack[m] <= num_change:
                l = m+1
            else:
                r = m
        if r < len(stack):
            n, stack[r] = (n-n%10+stack[r]),  num_change

        for num in stack:
            n = n*10 + num

        return n if n <= 2**31-1 else -1

Leetcode題解 Python & C#：六月挑戰DAY6 Queue Reconstruction by Height

給一個串列 people ， 其中每一個元素為 (h, k)，h 代表自身的高度， k 代表自身前方有 k 個人的 h >= 自身。
people目前是亂的，要回傳照規則(即每個位置與其 h, k 值皆是對的)排列的串列。 
我沒有第一時想通，看了一下別人的題解。
卡在我只有想到 brute force，但沒有想到要如何簡化。
按照逆向的想法，預想本來會有一個原形只有身高的排列，然後從身高小到大從後方取出，並標上其位置(前方有位置號個比自己 h >=)
所以逆向回去，即身高由高到矮，從前方排，依序一個個放入。
由於是按身高高到矮放入，因此直接把整理好的 people 按其 people[i][1] 去 insert(people[i][1], people[i]) ，即可確保前方有 people[i][1] 比自身高或同。
而輪到較矮的 insert() 也不會影響其排列的正確性，就能順利逆向回所求。

Python 

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        people.sort(key = lambda x: (-x[0], x[1]))
        result = []
        for p in people:
            result.insert(p[1], p)
        return result

C# 

public class Solution {
    public int[][] ReconstructQueue(int[][] people) {
        var sorted = people.OrderBy(x => (-x[0], x[1])).ToArray();
        var result = new List();
        foreach(var pair in sorted)
        {
            result.Insert(pair[1], pair);
        }
        return result.ToArray();
    }
}

目前趨勢

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