Leetcode題解 Python：Next Permutation

給一個組合，要回傳(按各組合由小到大)下一個組合，如果是最大的組合，則回傳最小的組合。

這一題是一種數學題，如果數學想通了就很好解，沒想通，那就只好琢磨到理解為止。

這裡要講如何理解。以 [4,2,3,1] 排組為例。

如果要找到下一個，就只要從右方移一個(從尾開始)，讓該組合的大小略增即可。

那要跟誰換呢？從右方開始，如果該位置的值比左方的大，那就是目標位置。
如果左方皆 >= 右方，那代表該組合是最大的。如 [4,3,2,1] [5,1,1]
([4,【2,3】,1])※選左右哪方當目標位置都可以。這裡用左右，必免混淆。

接著從目標位置右及右方開始選一個大於目標位置左的最小值，二者互相交換。可以想成進位。
([4,【2(左),3(右)】,1] -> [4,2,【3,1】] -> [4,2,【3】,1] -> [4,3,2,1])

換完之後，目標位置右方，應該要變成小到大的排序﹐才會是下一個組合。
([4,【3】,2,1] -> [4,3,1,2])

在換之前，目標位置右及右方已經是非升序排列(左>=右)，若把它看成一個排列組合，那此時的右方排列會是該排列組合中最大的。

最大的組合，只要反序，就會回到最小的組合。

若碰到 [4,3,2,1]，目標位置會在 4 的前方，沒辦法交換，所以直接把數列反序即可。

而交換之後，右方的非升序排列的性質依舊不變，因此只要把右方反序，就會變成右方最小的組合。

反序之後的組合就是題目所求。

流程

Python 

class Solution:
    def nextPermutation(self, nums) -> None:
        n = len(nums)
        si = n - 1
        while si > 0 and nums[si] <= nums[si-1]:
            si -= 1
        while si:
            for j in range(n-1, si-1, -1):
                if nums[j] > nums[si-1]:                    
                    nums[si-1], nums[j] = nums[j], nums[si-1] 
                    nums[si:] = nums[si:][::-1]
                    return
            si -= 1
        nums[si:] = nums[si:][::-1]

Leetcode題解 Python & C#：五月挑戰DAY10 Find the Town Judge

有 N 個人(編號 1,…,N)，若所有人信任第x個，而且第x個不信任任何人，若只有一個符合這樣條件的人，回傳其編號。
把條件一一拿來解讀：
他必須被所有人信任，所以那人得到的信任會是 N-1 個。
他不會信任任何人，所以在 trust[i][0] 的人都不是候選人。
於是在遍歷 trust 的同時，要去統計每個編號的被信任數(t[1])，並刪除候選人(t[0])。
剩下的候選人是不相信任何人的人，再剔除其被信任數不為 N-1 的。
最後符合條件1,2，若只剩一個即符合條件3，回傳其編號。若無則-1。

Python
class Solution:
    def findJudge(self, N: int, trust: List[List[int]]) -> int:
        from collections import defaultdict
        beTrust = defaultdict(int)
        candidates = set(range(1,N+1))
        for t in trust:
            beTrust[t[1]] += 1
            if t[0] in candidates: candidates.discard(t[0])
        for c in list(candidates):
            if beTrust[c] != N-1:
                candidates.discard(c)
        if len(candidates) == 1:
            return candidates.pop()
        return -1

C# 

public class Solution {
    public int FindJudge(int N, int[][] trust) {        
        var candidates = new HashSet();        
        var beTrusted = new Dictionary();        
        for(int i=1; i <= N; i++)
        {
            candidates.Add(i);
            beTrusted[i]=0;
        }
        foreach(var t in trust){
            beTrusted[t[1]] += 1;
            if(candidates.Contains(t[0]))
            {
                candidates.Remove(t[0]);
            }            
        }
        int result = -1;
        foreach(var c in candidates)
        {
            if(beTrusted[c] == N-1)
            {
                if(result==-1)
                {
                    result = c;
                }
                else
                {
                    return -1;
                }
            }
        }
        return result;
    }
}

Leetcode題解 Python：Number of Ways of Cutting a Pizza

給一塊矩陣 pizza，要用k-1刀切出 k 塊，每塊上面都要有至少一個 ‘A'(蘋果)，每刀只能切一直線，而且切完會拿走右方或是上方的那一塊。要回傳有幾種切法。
這算hard中偏簡單的問題，結果我在這題犯小錯卡很久，但正確的主體寫法一下子就寫好了。
因為這題給的拿取規則，使我們隨著每一刀而往右下移動，不用考慮前方的結果。(前不影響後)
因此，使用 dfs(深度優先)，以[y][x]做為dp的依據是沒問題的。(數字很大要取餘也是dp題的特色)
有刀數限制，再組合剛才的dp，組合成 dfs(y, x, pieces)的遞迴函數，而終止條件是 pieces == k。(可能有重複參數出現，可以使用 memo 紀錄)

首先拿到一大塊之後，可以直切，也可以橫切，選一個間隔作為下刀點。此時可分左右或上下。
如果被取走的那塊有蘋果，就可以往下一刀進行。dfs(y1, x1, pieces+1)
所以，總要判斷給定的區間內pizza是否有 1 個 “A”，寫成一個函數。(可能有重複參數出現，可以使用 memo 紀錄)
dfs 來到當 pieces == k ，就以目前的範圍找是否有蘋果，有則回傳 1 ，沒有則 0。

Python 

class Solution:
    def ways(self, pizza: List[str], k: int) -> int:
	from functools import lru_cache
        rows, cols = len(pizza), len(pizza[0])         
        @lru_cache(None)
        def hasApple(y0,y1,x0,x1):
            for y in range(y0,y1): 
                for x in range(x0,x1):        
                    if pizza[y][x] == "A": return True
            return False        
        @lru_cache(None)
        def dfs(y, x, pieces):
            if pieces == k:                
                if hasApple(y,rows, x,cols): 
                    return 1 
                else: return 0
                
            ans = 0
            # h cut
            for i in range(y, rows-1):                
                if hasApple(y, i+1, x, cols): 
                    ans += dfs(i+1, x, pieces+1)
            # v cut
            for i in range(x, cols-1):
                if hasApple(y, rows, x, i+1): 
                    ans += dfs(y, i+1, pieces+1)  
            return ans % (10**9+7)
        return dfs(0, 0, 1)

Leetcode題解 Python：Count Triplets That Can Form Two Arrays of Equal XOR

給一列整數數列，問兩相鄰的子數列XOR總值相等的個數。
今天就差這一個沒有解出來。QQ
這種在「一數列」中取「組合」做「比較」的題目，都有一個解題方向，就是用dp的觀念去保存比較值。
比較值，比較值，比較值，因為很重要，所以說三次。而且比較也要朝著在hash類內的做處理。

這一題的比較值，很明顯地就是XOR總值。
在計算XOR總值時，會選定一個區間，而這區間可能會重複計算，因此可用hashtable，dict() 保存。
因為題目所求，兩了數列一定要相鄰，如果前面是[i,j-1]，後面一定從 j 開始才有符合題目所求的可能性。
而結尾落在 j-1 位置的可能有好幾個，因此DP的會到二維，DP[pos][xor]，這樣才能充分保存比較值。
DP[pos][xor]是在以pos-1位置結尾的XOR之出現次數，若同值出現2次以上的話，計數也該加計相同次數。
流程
用雙迴圈去找出所有XOR總值，並順便找出在前方結尾即DP[pos]是否出現xor，若有則加DP[pos][xor]，
然後把目前的XOR總值加到DP去。

Python 

class Solution:
    def countTriplets(self, arr: List[int]) -> int:
	from functools import lru_cache
	from collections import defaultdict
        @lru_cache(None)
        def xor(si, ei):
            if si == ei: return 0
            ans = arr[si] ^ xor(si+1, ei)
            return ans        
        
        result = 0
        memo = defaultdict(dict)
        n = len(arr)
        for i in range(n):
            for j in range(i,n):
                val = xor(i, j+1)
                if val in memo[i]:
                    result += memo[i][val]
                memo[j+1][val] = memo[j+1].get(val,0) + 1

        return result

Leetcode題解 Python：Substring with Concatenation of All Words

給一字串 s 跟 words 字串串列，問哪些位置可以找到全部在words中的詞只出現一次。
思路很簡單，想辦法在一個 n 的時間讓全部都搜過。(用搜尋法倒很隨意)
有一個條件可以利用，那就是每個 word 都是一樣的長度，因此不必逐字元去判斷，可以拿詞去匹配。
於是產生原型的逐詞匹配，但這還不夠！速度還太慢。
每當遇到這種匹配題型，盡可能不要反覆同一位置重複匹配。之前有提到一個方式 KMP，若全照用，這裡可能會在 prefix table 產生太多組合 。
因為 words 的詞沒有指定先後順序，所以要是當前位置沒有匹配到，就可把最前面匹配的放回待匹配的隊伍，繼續匹配，若都沒有可匹配，那就往下移動。

Python(逐詞匹配) 

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        result = []
        if not s or not words: return result
        counter = Counter(words)        
        nowCounter = counter.copy()
        i = 0
        m = len(words[0])
        n = len(s)
        n2 = len(words)        
        while i <= n-m*n2:           
            nowCounter = counter.copy()
            for j in range(n2):
                word = s[i+j*m:i+m+j*m]
                if word in nowCounter:
                    if nowCounter[word] > 0:
                        nowCounter[word] -= 1
                        if nowCounter[word] == 0:
                            del nowCounter[word]
                else:
                    break
            if not nowCounter: result.append(i)
            i += 1
        return result

Python(逐詞匹配2) 

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        result = []
        if not s or not words: return result       
        wl = len(words[0])
        wn = len(words)
        counter = Counter(words)
        select = list()
        n = len(s)
        def search(pos, wi):
            if pos+wl > n:
                while select: counter[select.pop(0)] += 1
                return                
            word = s[pos: pos+wl]
            while select and (word not in counter or counter[word] == 0):
                counter[select.pop(0)] += 1
                wi -= 1
            if word in counter and counter[word] > 0:
                counter[word] -= 1
                select.append(word)
                if wi+1 == wn: result.append(pos - wi*wl)                    
                search(pos+wl, wi+1)
            else:
                search(pos+wl, wi)
        for i in range(wl):           
            search(i, 0)
        return result

Leetcode題解 Python & C#：五月挑戰DAY9 Valid Perfect Square

給一個正整數，問其是否為整數的平方。
若以不轉換資料型態來計算，即只用 int 去解決，只要判斷 num 是否在(枚舉)整數的平方。
(這是一種挑戰，不然用Python內建的計算，一句就能非常迅速的解決。)
不過枚舉這樣子太慢了，如果是完美，那 num 可以用兩個相同的因數相乘。
用上找因數，就能避免枚舉很多不必要的數字，也不會有怕溢位的問題。
如果使用二分搜尋法加速，又會面臨溢位的問題，但處理好後速度會快不少。

Python(基本) 

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        def isValid(x):
            ans = x*x
            if ans < num: return isValid(x+1)
            elif ans > num: return False
            else: return True
        return isValid(1)

C#(因數拆解) 

public class Solution {
    public bool IsPerfectSquare(int num) {
        int a = num; int b = 1;
        while(a>b)
        {
            a /= 2; 
            b *= 2;
        }            
        for(int i = a; i <= b; i++)
            if(i*i == num){return true;}
        return false;
    }
}

Leetcode題解 Python & C#：五月挑戰DAY8 Check If It Is a Straight Line

檢查是否所有座標都在一條直線上。
這是很簡單的數學題，只要細節不漏掉就好。
寫出方程式： ax + b = y。但這不適用於垂直直線，因為同 x 會出現兩個以上的 y。 
這兩種情況要分開判斷，只要不是垂直直線的，靠解方程式就可以判斷。
若是，則看所有的座標的x是否為相同值。
(打完題解後，發現我本來寫好的是錯的但卻可以接受，只好幫提供testcase，默默改正code。

Python
class Solution:
    def checkStraightLine(self, coordinates: List[List[int]]) -> bool:
        dx = coordinates[1][0] - coordinates[0][0]
        if dx == 0:
            x = coordinates[0][0]
            return all(map(lambda c: c[0] == x, coordinates))              
        else:
            a = (coordinates[1][1] - coordinates[0][1]) / dx      
            b = coordinates[0][1] - a*coordinates[0][0]
            return all(map(lambda c: a*c[0] == c[1]-b, coordinates))

C# 

public class Solution {
    public bool CheckStraightLine(int[][] coordinates) {
        int dx = coordinates[1][0] - coordinates[0][0];        
        if(dx == 0)
        {            
            int x = coordinates[0][0];
            foreach(var c in coordinates)
            {
                if(c[0] != x)
                {
                    return false;
                }
            }
        }
        else
        {
            double a = (coordinates[1][1] - coordinates[0][1]) / dx;
            double b = coordinates[0][1] - a * coordinates[0][0];
            foreach(var c in coordinates)
            {
                if(c[0]*a != c[1]-b)
                {
                    return false;
                }
            }            
        }
        return true;
    }
}

Leetcode題解 Python：Reverse Nodes in k-Group

給一個 Linked List，從左至右以 k 個節為一組作反轉，若不滿 k 個，則該維持原有排序。
像是在 List 中作位移的題目，多半跟 TwoPointer 的技巧是相關的。
這題也不例外，用 TwoPointer 控制兩個點互換，按題目要求解出所求。
如果由左至右，考量到後方未必有 k 個節，使用「深度優先」的遞迴函數，對於求解會比較好進行。(個人覺得比較好理解。
先檢查目前是否還有 k 個節，沒有則不逆序，有則逆序。

Python 

class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:         
        nextKNode = FP = head
        for _ in range(k): 
            if not nextKNode: return head
            nextKNode = nextKNode.next    
        lastNode = self.reverseKGroup(nextKNode, k)
        for _ in range(k): 
            SP, FP = FP, FP.next 
            SP.next, lastNode = lastNode, SP  
        return SP

Leetcode題解 Python：Merge k Sorted Lists

合併 k 個 linked list 成一個 linked list，並且值由小到大排序。
說到要保持由小而大，不外乎就想到 min heap，關於 heap 的介紹，這裡就不多說了。
因為每次新的加入就得重新找出最小的，選擇 heap 是快多了。
不過不論是 heap 還是 sort() 都無法對於 ListNode 做比較，所以不是重新生成ListNode，
不然就是得找另外一種的保存方式。
我選擇用 dict() 以Node的值為鍵去存放 ListNode。但可能會出現同值有二個以上的ListNode，所以得用list存放，
同值的順序並不重要，抓哪個都可以。為了方便，使用 collections.defaultdict(list)。
用 heap 的 list 只有放 ListNode.val，只要拿值去對就可以取出下一個要接的 ListNode。

Python 

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        # 使用 min heap
        import heapq      
        import collections
        nodeMap = collections.defaultdict(list)
        stack = []
        for node in lists:
            if node:
                nodeMap[node.val].append(node)
                heapq.heappush(stack, node.val)   
        if not stack: return None
        root = nowNode = ListNode()
        while stack:
            nowNode.next = nodeMap[heapq.heappop(stack)].pop()
            nowNode, nextNode = nowNode.next, nowNode.next.next
            if nextNode:
                nodeMap[nextNode.val].append(nextNode)
                heapq.heappush(stack, nextNode.val)            
        return root.next

Leetcode題解 Python & C#：4Sum

如果有做出 3Sum 的人，這類題有一套公式，即使用 TwoPointer 的技巧，靠迴圈、加速搜遍數列。
3Sun是選定一個 i(由前往後)，4Sum就多選一個 j(由後往前)，剩下用 l、r，即 TwoPointer，用總和值來決定移動 l 還是 r。
先把數列排序，若 nums[i] + nums[l] + nums[r] + nums[j] > target，則我們要縮小總和，因此讓 r – 1，反則 l + 1，
這使得每次移動都讓總和與目標值靠近。如果跟總和跟目標值相同，記錄組合，然後移動 l 與 r 。  
由於不能重複，存放組合的資料型態可以選hash家族，這樣就能有效率的避免有同樣組合被計到二次以上。
又或者將重複的狀況跳過，不僅可加速迴圈，也可以直接用 list 放結果，不用轉換資料型態。 

Python(基本) 

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        n = len(nums)
        result = set()
        nums.sort()
        for i in range(n-3):
            for j in range(n-1,i+2,-1):
                l, r = i+1, j-1
                while l < r:
                    v = nums[i] + nums[l] + nums[r] + nums[j]
                    if v > target: 
                        r -= 1
                    elif v < target:
                        l += 1
                    else:                     
                        result.add((nums[i],nums[l],nums[r],nums[j]))
                        l += 1
                        r -= 1
        return result

C# 

public class Solution {
    public IList> FourSum(int[] nums, int target) {
        Array.Sort(nums);
        int n = nums.Length;
        IList> result = new List>();
        for(int i = 0; i < n - 3; i++)
        {
            for(int j = n - 1; j > i + 2; j--)
            {
                var l = i + 1; var r = j - 1;
                while(l < r)
                {
                    var nsum = nums[i] + nums[l] + nums[r] + nums[j];
                    if(nsum == target)
                    {
                        result.Add(new List(){nums[i], nums[l], nums[r], nums[j]});
                        while(l < r && nums[l] == nums[l+1] && nums[r] == nums[r-1])
                        {
                            l++;
                            r--;
                        }
                        l += 1;
                        r -= 1;   
                    }
                    else if(nsum > target)
                    {
                        r -= 1;
                    } 
                    else
                    {
                        l += 1;
                    }
                }
                while(j > i + 2 && nums[j] == nums[j-1]){j--;}
            }
            while(i < n - 3  && nums[i] == nums[i+1]){i++;}
        }
        return result;
    }
}
不過會發現，Python這樣子的寫法不夠快，有沒有什麼可以加速的條件可用。
例如重複跳過，若接下來找不到目標值，則進入下一個迴圈。這些條件都很好理解，就不多敘述了。
在添加了一些提前中止的條件後，速度可以壓在100ms以內。

Python 

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        n = len(nums)
        result = []
        nums.sort()
        for i in range(n-3):
            if( i > 0 and nums[i] == nums[i-1]): continue
            if nums[i] * 4 > target: break
            for j in range(n-1,i+2,-1):
                if(j target: 
                        if curSum + 2 * nums[l] > target: break
                        r -= 1
                    elif v < target:
                        if curSum + 2 * nums[r] < target: break
                        l += 1
                    else:                     
                        result.append([nums[i],nums[l],nums[r],nums[j]])
                        while(l < r and nums[l] == nums[l+1] and nums[r] == nums[r-1]):
                            l += 1
                            r -= 1      
                        l += 1
                        r -= 1
        return result

Leetcode題解 Python & C#：五月挑戰DAY7 Cousins in Binary Tree

給一個二元樹的根節，找出 x、y是否為cousin（同深度，不同父）。
遍歷所有的節，再把找到的x、y資料（深度，父節）做對比，就可以辨別是否為cousin 。
要找遍二元樹上的每一個元素，除了可以用遞迴函數，也可以用一層一層的stack（queue皆可)來找。由於每節的值不會重複，不用擔心多個可能。
就效率來看，這題的情況單純，儘可能減少判斷，才是通往高效之路。

Python
class Solution:
    def isCousins(self, root: TreeNode, x: int, y: int) -> bool:
        
        def search(node, parent, depth, val):
            if not node: return None, None
            if node.val == val:
                return parent, depth
            else:
                res = search(node.left, node, depth+1, val)
                if res[0]: return res
                return search(node.right, node, depth+1, val)
            
        nodeX = search(root, None, 0, x)
        nodeY = search(root, None, 0, y)
        return (nodeX[0] != nodeY[0] and nodeX[1] == nodeY[1])

C# 

public class Solution {
    public bool IsCousins(TreeNode root, int x, int y) {
        var queue = new Queue();
        var memo = new Dictionary();
        queue.Enqueue(root);
        memo[root.val] = root;
        while(queue.Count > 0)
        {
            int len = queue.Count;
            for(int i = 0; i < len; i++)
            {
                var node = queue.Dequeue();
                if(!(node.left is null))
                {
                    memo[node.left.val] = node;
                    queue.Enqueue(node.left);
                }   
                if(!(node.right is null))
                {
                    memo[node.right.val] = node;
                    queue.Enqueue(node.right);
                }                   
            }
            var hasX = memo.ContainsKey(x);
            var hasY = memo.ContainsKey(y);
            if(hasX | hasY)
            {
                if(hasX & hasY)
                {
                    if(memo[x] != memo[y])
                        return true;
                    else
                        break;
                }
                else
                {
                    break;
                }
            }
        }
        return false;
    }
}

專案開發紀錄1：規劃使用環境

雖然我已經自己寫過好幾版的應用程式，不過卻很鬆散，沒有一個明確的SOP，想到什麼就做什麼。

每次都有一點突破，這次也要求自己要用上更多的進階技巧。
我在想打造一個方便跨平台，同時又能減少關卡的資訊傳送方式。不是那種要用IP位置的通訊協定、這太費工夫。
同時最好可以主機用API去修改內容，但不改變網址，如果每次更新都要開權限再重新分享，實在太麻煩。
對於跨平台是第一次嘗試，考量我之後沒辦法總是在我主機上使用，就算出門在外，也要能時時刻刻掌握動態。
線上DB + google sheet 本來是我第一個的組合。之前搭載虛擬機，可以用MSSQL，目前DB類的都不成問題。
不過，google sheet 暫時卡住我，因為我開新帳號，原因是覺得目前我用的帳號太過氣，取一個比較合身分的帳號。
我知道google新帳號，會被限縮很多功能，但主帳有很多私人的資料，我不想因為這次開發開一堆權限出去。
於是我的新帳號沒辦法使用 外掛功能 ，第一個嘗試就被迫停止在這裡。
接著我打算試試看 WordPress ，如果資料可上雲端，那麼我需要的是「隱私性」，只有我能看，不給一般尋常方式(google搜查)可找到。
WordPress有外掛功能，可以連接DB，也有權限設定。但，那需要商業版，一年300$，也就是9000台幣。
行不行？讓我不爽，因為我不知道WordPress，到底值不值，也許用起來跟我想像的不同，因為沒有試用，我的疑慮無法消。
「GIVE UP」換一種吧。
我希望主機要能即時影響所要呈現的資訊，不需要到每秒，但希望也能有每分鐘的更新頻率。

後來嘗試了用google API 上傳檔案到 drive，google 的管制很嚴，如果用得太爽，它總是能偵測出來，冷不防地鎖一個，我不知道會不會被標記為濫用？
但我只是嘗試要如何使用，如果只有google API，那達不到我想要的方便性。
接下來，發現了一個說可以把 google drive 或 one drive 當成網站的教學文章，還可以控制網域，那不就解決只用 google drive 的問題嗎？
固定的網域就不會老是更新位置，而且一行網址就能取得資料，也不會直接公開到網路上，即時更新的功能也可以靠Google API完成，還可以順利切換不同網頁。
其實網頁的功能，是瀏覽器下載原始碼後建構的，所以理論上，用google drive可以做到一般網頁的基本功能沒問題，
而動態加載的部分，如果主機可以直接影響，那也不必有查詢的功能，或者都放到json檔再篩選，就不需送互動的指令，我仍掌握要呈現什麼資訊的權力。
至於流量，我只打算是我一人使用，所以也不會流量暴表的異常被鎖吧？
決定架構是很初期的工作，先定好了框架，後續才能繼續開發。這次要用上我之前沒有搭配的工具，大致的code寫法我心裡有底，只有這一塊是不明不白的。

(這一版將使用 python scarpy + db(非access) + git + 網頁)
既然跨平台瀏覽 + 即時更新可行，那後續的進階規劃就可以再展開，下一步就是把細項與流程寫得更齊全。

目前趨勢

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