# Leetcode 052721~

## 052721

### #454. 4Sum II

#### 論壇解1
combined double hashmap:
不必考慮數值重複問題。符合資格的case，兩個hashmap的值相乘即可

class Solution:
    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
        n1, n2, n3, n4 = len(nums1), len(nums2), len(nums3), len(nums4)
        tg_dict_a, tg_dict_b = {}, {}
        res = 0
        
        for i in nums1:
            for j in nums2:
                if i + j not in tg_dict_a: tg_dict_a[i+j] = 1
                else: tg_dict_a[i+j] += 1
                    
        for i in nums3:
            for j in nums4:
                if i + j not in tg_dict_b: tg_dict_b[i+j] = 1
                else: tg_dict_b[i+j] += 1
        
        for i in tg_dict_a:
            for j in tg_dict_b:
                if not i+j:
                    res += (tg_dict_a[i] * tg_dict_b[j])
        return res

### #13. Roman to Integer

#### first try:
By rule, naively.

class Solution:
    def romanToInt(self, s: str) -> int:
        res = 0
        if 'CM' in s:
            s = s.replace('CM', '')
            res += 900
        if 'CD' in s:
            s = s.replace('CD', '')
            res += 400
        if 'XC' in s:
            s = s.replace('XC', '')
            res += 90
        if 'XL' in s:
            s = s.replace('XL', '')
            res += 40
        if 'IX' in s:
            s = s.replace('IX', '')
            res += 9
        if 'IV' in s:
            s = s.replace('IV', 'we')
            res += 4
        if 'D' in s:
            s = s.replace('D', '')
            res += 500
        if 'L' in s:
            s = s.replace('L', '')
            res += 50
        if 'V' in s:
            s = s.replace('V', '')
            res += 5
        res += 10 * s.count('X')
        res += 100 * s.count('C')
        res += 1000 * s.count('M')
        res += s.count('I')
        return res     

#### 網友解

直指問題本質的解法。

沒辦法，我就不是西方人。

class Solution:
    def romanToInt(self, s: str) -> int:
        s = s.lower()
        roman = {'i':1,'v':5,'x':10,'l':50,'c':100,'d':500,'m':1000}
        res, index = 0, 'i'
        for i in s[::-1]:
            res, index = res-roman[i] if roman[index] > roman[i] else res + roman[i], i
        return res

## 053021
### #19. Remove Nth Node From End of List

#### first try:
題幹提示，希望one-pass。
naive solution的問題是，因為深度(長度)需要等traverse到尾端才知道，same for the location of removal. 需要先run一次確定深度，再run一次修改目標位置的指標。
所以我的方法就是建成一個list，list自然會包含長度資訊。接下來用list indexing就知道要抓的位置。

但這有一個問題是，list indexing本身是$O(1)$還是$O(N)$呢？如果是後者，那我的方法等同於naive solution的過程。

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        lnlist = []
        res = head
        while head.next:
            lnlist.append(head)
            head = head.next
        lnlist.append(head)
        if len(lnlist) - 1 >= n:
            lnlist[-n-1].next = lnlist[-n+1] if -n + 1 < 0 else None
            lnlist[-n] = None
            return res
        else:
            return res.next

#### 網友解
double pointer
等速雙指標，雖然他用fast, slow命名，但差距只有一開始的位置差(fast先前進n步)，fast, slow之後一起移動。
等等，但他這樣就不算2 pass?

恩對，官方解答看來定調這樣叫做1 pass。

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        fast = slow = head
        
        for _ in range(n):
            fast = fast.next
        if not fast:
            return head.next
        
        while fast.next:
            fast = fast.next
            slow = slow.next
        slow.next = slow.next.next
        return head

<br>
<br>

### #26. Remove Duplicates from Sorted Array

#### first try

明顯的浪費空間，不過Leetcode結果是看不出來的。
利用倒序刪除重複元素避免了index synchronization的問題。

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        loc = [0] * len(nums)
        for i in range(len(nums)):
            if i and nums[i] == nums[i-1]:
                loc[i] = 1
        for i in range(len(loc)-1, -1, -1):
            if loc[i]: del nums[i]
        return len(nums)

#### 網友解：

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        tail = 0
        for i in range(1, len(nums)):
            if nums[i] == nums[tail]:
                continue
            tail += 1
            nums[tail] = nums[i]
        return tail + 1

<br>
<br>

## 053121

### #27. Remove Element

#### first try:

跟昨天26題一樣的解法，但其實不需要，請見網友解1

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        for i in range(len(nums)-1, -1, -1):
            if nums[i] == val:
                del nums[i]
        return len(nums)

#### 網友解1：
用while就不會有iterable synchronization的問題

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        i = 0
        while i < len(nums):
            if nums[i] == val:
                del nums[i]
            else:
                i += 1
        return len(nums)

#### 網友解2:
最後是標準的double pointer，牛刀殺雞。

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        nums.sort()
        i, j = 0, 0
        while j < len(nums):
            if nums[j] != val:
                nums[i] = nums[j]
                i, j = i + 1, j + 1
            else:
                j += 1
        return i  

#### Analysis
- Time: $O(N)$ for all
- Space: $O(1)$ for all; all in-place

## 060121

### #88. Merge Sorted Array
題目原意是排兩個sorted array，也就是merge sort的最後一步(或每個subroutine的最後一步)。
如下面網友解，用2 pointer 的方式比較原汁原味，但實際上簡單粗暴的方法卻比較好用:
手動pop nums1多餘的元素，再把nums2接上去。然後call sort()，這會做一個in place sorting。

重點在避免改到nums1的id。
#### first try

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        for _ in range(n):
            nums1.pop()
        for i in range(n):
            nums1.append(nums2[i])
        nums1.sort()

#### 網友解:
體現題目要的精神，可惜表現不如人意(56ms(PR5) vs 32ms(PR88), by first try)

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        i, j = m-1, n-1
        while j+1 and i+1:
            if nums1[i] > nums2[j]:
                nums1[i+j+1] = nums1[i]
                i -= 1
            else:
                nums1[i+j+1] = nums2[j]
                j -= 1
        while j+1:
            nums1[i+j+1] = nums2[j]
            j -= 1
        

#### second try:
所以同first try的道理這樣也行。只是performance就真的比較差了。(60ms, PR5)

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        nums3, i, j = [], 0, 0
        while i < m and j < n:
            if nums1[i] < nums2[j]:
                nums3.append(nums1[i])
                i += 1
            else:
                nums3.append(nums2[j])
                j += 1
        
        if i < m:
            nums3 += nums1[i:m]
        elif j < n:
            nums3 += nums2[j:n]
        
        for i in range(len(nums3)):
            nums1[i] = nums3[i]

### #75. Sort Colors

### first try

好這完全是來亂的。
但是performance最好。

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        nums.sort()

### second try:
那就自己寫一個qsort。
performance在28ms(PR90)~56ms(PR 0)之間。leetcode的benchmark真的歹就補?

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        def qsort(data, left, right):
            if left > right: return
            i, j = left, right
            while i != j:
                while j > i and data[j] > data[left]:
                    j -= 1
                while j > i and data[i] <= data[left]:
                    i += 1
                if j > i:
                    data[i], data[j] = data[j], data[i]
            data[i], data[left] = data[left], data[i]
            qsort(data, left, i-1)
            qsort(data, i+1, right)
        qsort(nums, 0, len(nums)-1)

### third try
既然都知道所有的選項了，那就用字典紀錄次數再重組就好了。
對於沒有內建hashmap的語言來說關鍵就是如何實作hash table了。

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        ndict = {0:0, 1:0, 2:0}
        for n in nums:
            ndict[n] += 1
        for i in range(ndict[0]):
            nums[i] = 0
        for i in range(ndict[0], ndict[0] + ndict[1]):
            nums[i] = 1
        for i in range(ndict[0]+ndict[1], ndict[0]+ndict[1]+ndict[2]):
            nums[i] = 2

### 網友解:
原來這問題叫做Dutch national flag problem。簡單來說就是sorting的特例。
sorting的可能元素有限時，可以用$O(N)$解出而不是$O(NlogN)$。
只要拆成子問題即可。(如*)

但須考慮常數大小。常數太大，反而不如一般sorting。適用於總共數值不超過四五種的狀況。
(數值選項趨近len(data)時，其實就等同於$O(N^2)$了，超過的話甚至比bubble sorting還糟糕，所以真的是特例)

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

<br>
<br>

\* Mauritius，模里西斯的國旗:
四色旗，和荷蘭旗問題一樣的概念。

同樣的概念理論上可以延伸到N種值。

mau = [1,3,2,2,3,0,1,2,3,0,1,2,3,1,1,1,2,2,0,3,3,3,2,2,3,1,2,3,2,2,1,0,1,0,0]
print(mau)
def fourcolor(data):
  i, j, k= 0, 0, len(data)-1
  while i <= k:
    if data[i] < 2:
      data[i], data[j] = data[j], data[i]
      i, j = i + 1, j + 1
    elif data[i] == 2:
      i += 1
    elif data[i] == 3:    
      data[i], data[k] = data[k], data[i]
      k -= 1
  i, j = 0, j-1
  while i <= j:
    if data[i] == 0:
      i += 1
    else:
      data[i], data[j] = data[j], data[i]
      j -= 1
fourcolor(mau)
print(mau)

## 060221

### #35. Search Insert Position
只是看了一下網友的解，修正一下reassign pointer的方式。

#### first try:

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

#### Analysis:
基本上就是sorted binary search
直接call bisect的bisect_left是一樣的意思。
- Time: $O(logN)$
- Space:$O(1)$

## 060521
### #4. Median of Two Sorted Arrays

#### first try:
redundant solution：比naive solution還差。做了多餘的排序，反而變成需要$O(NlogN)$。
naive solution是從兩邊的頭取較小的，取到median 為止，需要花費$O(N)$。

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        index = len(nums1) + len(nums2)
        if not index % 2:
            index //= 2
            return (sorted(nums1 + nums2)[index - 1] + sorted(nums1 + nums2)[index]) / 2
        else:
            index //= 2
            return sorted(nums1 + nums2)[index]

#### 網友解
最佳解，使用binary search。
因為限定是median number，位置固定的情況下，nums1取數後就知道nums2該取何者。所以就在兩者之中較短者上用binary search。
如何知道找到了？
只要檢視nums1[i-1], nums1[i], nums2[j-1], nums2[j]的關係就可以知道。因為median number必然是：

max(nums1[i-1], nums2[j-1])

若len相加是偶數，則為：

(min(nums1[i], nums2[j]) + max(nums1[i-1 + nums2[j-1]]) ) / 2

這樣就可以在$O(logN)$內得到解。

比較要注意的是邊界條件：例如i==0, j==0。這是令這題變得複雜的原因之一。

## 060621

### #1486. XOR Operation in an Array

乍看之下很簡單，照著題意做一次就得到$O(N)$的解，也會過。
但觀察後發現規則，只要照規則就可以$O(1)$判斷出來。

class Solution:
    def xorOperation(self, n: int, start: int) -> int:
        if n == 1: return start
        last = start + (n - 1) * 2
        
        if start % 4 < 2:
            # 如果start % 4 < 2, 可以知道第2位一定是0(以下皆以LSB為第一位)
            # 所以如果n是4的倍數，XOR後一定為0
            # 如果n % 4 == 2，因為只有第2位會變，所以一定是bx0010
            # 那餘1和於3的情況就可以推導出來了
            if n % 4 == 0: return 0
            elif n % 4 == 1: return last
            elif n % 4 == 2: return 2
            elif n % 4 == 3: return 2 ^ last
        else:
            # 如果start % 4 > 1: 其實就是上例往前推一步，也就是說start+2就會回到上面的例子。
            # n % 4 == 3的情況，首項保留，中間4的倍數消去後，倒數第1、2位又如同上面start % 4 < 2的前兩位，所以XOR結果為2。
            if n % 4 == 1: return start
            elif n % 4 == 2: return start ^ last
            elif n % 4 == 3: return start ^ 2
            elif n % 4 == 0: return start ^ 2 ^ last
            

## 060721
### #53. Maximum Subarray

看起來是DP但其實不是，只不過有那個味道在。

#### 論壇解1
subarray最大和預設為首項值。一項項往後看，如果和小於當前最大值就直接丟棄，重設起點。

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        self.max_sum = nums[0]
        def _max_sub(nums, f):
            if f == 0: 
                self.max_sum = nums[0]
                return nums[0]
            local_max = max(nums[f], _max_sub(nums, f-1) + nums[f])
            self.max_sum = max(local_max, self.max_sum)
            return local_max
        _max_sub(nums, len(nums) - 1)
        return self.max_sum if len(nums) > 1 else nums[0]
    

#### 論壇解2
概念一樣，只是不用遞迴，用iteration

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        res, sums = nums[0], nums[0]
        for i in range(1, len(nums)):
            sums = max(nums[i] + sums, nums[i])
            if sums > res: res = sums
        return res

#### 論壇解3
用divide and conquer。
每個sub-procedure由中間往左右找該fragment最大值。
sub-procedure求最大值的過程看起來跟前面有點像，不同之處在於必須要跟最內側(nums[mid-1] for left part, nums[mid+1] for right part)連在一起，所以加過去一路取max就可以了。不過這作法不聰明，只是為DC而DC。

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        def dvcqr(nums, l, r):
            if l > r: return -2**32
            mid = (l + r) // 2
            
            cur, rtbest, ltbest = 0, 0, 0
            for i in range(mid + 1, r + 1):
                cur += nums[i]
                rtbest = max(rtbest, cur)
            cur = 0
            for i in range(mid - 1, l - 1, -1):
                cur += nums[i]
                ltbest = max(ltbest, cur)
            
            ctbest = rtbest + ltbest + nums[mid]
            ltonlybest = dvcqr(nums, l, mid - 1)
            rtonlybest = dvcqr(nums, mid + 1, r)
            return max(ctbest, ltonlybest, rtonlybest)
        
        return dvcqr(nums, 0, len(nums) - 1)

#### 論壇解4
更聰明的DC。
我沒寫過，要找時間寫一遍。
###### tags: TO DO

class Solution:
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        def divide_and_conquer(nums, i, j):
            if i == j-1:
                return nums[i],nums[i],nums[i],nums[i]
            
            # we will compute :
            # a which is max contiguous sum in nums[i:j] including the first value
            # m which is max contiguous sum in nums[i:j] anywhere 
            # b which is max contiguous sum in nums[i:j] including the last value
            # s which is the sum of all values in nums[i:j]
                
            # compute middle index to divide array in two halves
            i_mid = i+(j-i)//2
            
            # compute a, m, b, s for left half
            a1, m1, b1, s1 = divide_and_conquer(nums, i, i_mid)
            
            # compute a, m, b, s for right half
            a2, m2, b2, s2 = divide_and_conquer(nums, i_mid, j)
            
            # combine a, m, b, s values from left and right halves to form a, m, b, s for whole array (bottom up)
            a = max(a1, s1+a2)
            b = max(b2, s2+b1)
            m = max(m1,m2,b1+a2)
            s = s1+s2
            return a,m,b,s
                  
        _,m,_,_ = divide_and_conquer(nums, 0, len(nums))
        return m

#### Analysis:
- Time: $O(N)$, $O(N)$, $O(NlogN)$, $O(N)$

### #7. Reverse Integer

first javascript try

/**
 * @param {number} x
 * @return {number}
 */
var reverse = function(x) {
    if (x > 0) {
        x = x.toString()
        let y = x.split('')
        y = y.reverse()
        y = y.join('')
        if (y <= 2 ** 31 - 1) return y
        else return 0
    }
    else if (x < 0) {
        x = (-x).toString()
        let y = x.split('')
        y = y.reverse()
        y = y.join('')
        if (y <= 2 ** 31) return -y
        else return 0
    }
    else return 0
};

## 060821

### #121. Best Time to Buy and Sell Stock
上一題的變體。
解法觀念類似。這邊用上一題第一個解法的概念。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) < 2: return 0
        profit = - prices[0]
        lowest = highest = prices[0]
        for i in range(1, len(prices)):
            if prices[i] < lowest: 
                lowest = prices[i]
                continue
            if prices[i] - lowest > profit: 
                profit = prices[i] - lowest
        return profit if profit > 0 else 0

## 061621
### #122. Best Time to Buy and Sell Stock II
題意想清楚就知道，這樣就可以了。比前一題還簡單。
最難的地方應該是了解題意的意涵。
#### first try

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) == 1: return 0
        res = 0
        for i in range(1, len(prices)):
            if prices[i] > prices[i-1]:
                res += (prices[i] - prices[i-1])
        return res

#### Analysis
- Time:$O(N)$

### #309. Best Time to Buy and Sell Stock with Cooldown

#### HuaHua_1
DP, naive ver.:

import sys
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) == 1: return 0
        prices = prices[0]
        lp = len(prices)
        hold, sold, rest = [0] * lp, [0] * lp, [0] * lp
        hold[0] = -sys.maxsize
        for i in range(1, lp):
            rest[i] = max(rest[i-1], sold[i-1])
            sold[i] = hold[i-1] + prices[i]
            hold[i] = max(rest[i-1] - prices[i], hold[i-1])
        
        return max(rest[-1], sold[-1])

#### HuaHua_2
DP, dimension-reduction ver.:

import sys
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) == 1: return 0
        sold, rest, hold = 0, 0, -sys.maxsize
        
        for p in prices:
            prev_sold = sold
            sold = hold + p
            hold = max(rest - p, hold)
            rest = max(rest, prev_sold)
        return max(sold, rest)

pic1.

pic2.

了解pic1的邏輯後，畫出來就可以簡單計算出答案。
因為每個狀態都只需要前一項，所以只要maintain每個狀態的前一項，不需要整個list，這就是第二個implementation做的簡化。

#### Analysis

- Time: $O(N)$
- Space: $O(N)$ / $O(1)$

## 061721

### #123. Best Time to Buy and Sell Stock III

網友解：
[小明](https://maxming0.github.io/2020/08/16/Best-Time-to-Buy-and-Sell-Stock-III/)

一樣用動態規劃。限制只能做兩次交易，那就是分成buy1, sell1; buy2, sell2兩對、四個數組來做DP。實務上，一樣，由於今日狀態只跟前一天有關，所以縮減成maintain四個variables就可以了。
需要給定限制，在第一次交易完成前不能進行第二次交易嗎？不需要。在我們的模型裡，第一次交易完成後(包含完成當下)，第二次交易的結果會等同"當天立即買進賣出"。即假設現在為day 3，本日完成buy1賺2元；同日buy2和sell2的取值動作可以解讀為"這天立即買進並賣出"，這跟沒做是一樣的，所以不違反題意。
所以最後也不用return max(s1, s2)，return s2即可。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) < 2: return 0
        
        b1 = b2 = -float('inf')
        s1 = s2 = 0
        for p in prices:
            b1 = max(b1, -p)
            s1 = max(b1 + p, s1)
            b2 = max(s1 - p, b2)
            s2 = max(b2 + p, s2)
        return s2

#### Analysis
- Time: $O(N)$

### #188. Best Time to Buy and Sell Stock IV
呼呼，系列題最終回，也是最難的。
一樣使用DP with dimension diminishing
解析待補，以及greedy解法。待我沈澱一晚。

#### 網友解：

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        n = len(prices)
        if n < 2: return 0
        elif n <= k // 2: 
            res = 0
            for i, j in zip(prices[1:], prices[:-1]):
                if i > j: res += i - j
            return res
        
        res = [[0, 0] for _ in range(k + 1)]
        for i in range(k + 1):
            res[i][1] = -prices[0]
        for i in range(n):
            for j in range(1, k + 1):
                res[j - 1][1] = max(res[j - 1][1], res[j - 1][0] - prices[i])
                res[j][0] = max(res[j][0], res[j - 1][1] + prices[i])
        return res[k][0]

### #67. Add Binary
#### first try:
邊界條件注意一下。

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        if len(a) < len(b):
            a, b = b, a
        b = b.zfill(len(a)) # 10011 -> 00010011
        
        a, b = a[::-1] + '0', b[::-1] + '0'
        a, b = list(a), list(b)
        # 00010011, 10011100 => 110010000, 001110010 
        # one more 0 at tail for possible carrying number
        
        
        res = ['0'] * (len(a))
        c, n1, n2 = 0, 0, 0
        for i in range(len(a)):
            if not c:
                n1, n2 = int(a[i]), int(b[i])
                if n1 + n2 == 2:
                    c = 1
                elif n1 + n2 < 2:
                    res[i] = str(n1 + n2)
            elif c == 1:
                n1, n2 = int(a[i]), int(b[i])
                if n1 + n2 == 2:
                    res[i] = '1'
                elif n1 + n2 == 1:
                    res[i] = '0'
                elif not (n1 + n2):
                    res[i] = '1'
                    c = 0
        if not int(res[-1]): res = res[:-1]
        return "".join(res[::-1])

#### 網友解
概念是一樣的。
不過更優良地利用了基本庫的函式，程式碼較簡潔。

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        c, res = 0, ''
        a, b = list(a), list(b)
        
        while a or b or c:
            if a:
                c += int(a.pop())
            if b: 
                c += int(b.pop())
            res += str(c%2)
            c //= 2
        return res[::-1]

## 070621

### #1338. Reduce Array Size to The Half

#### first try
題意就是要了解arr內一樣的數字分組，需要多少會過半。只要知道每個數字有多少個就好，所以就先用字典分組。然後排序，看加到多少會過半。

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        s = len(arr)
        number_times = {}
        for i in arr:
            if i not in number_times: number_times[i] = 1
            else: number_times[i] += 1
        number_times_rank = sorted(list(number_times.values()), reverse = True)
        if len(number_times_rank) == 1: return 1
        res, aggre = 0, number_times_rank[0]
        while aggre < (len(arr) + 1) // 2:
            res += 1
            aggre += number_times_rank[res]
        return res + 1

#### 官方解1:
bucket sort:
對一陣列arr:

arr = [1,2,2,4,1,2,1,5,4,5,3,2,2,1]
counts = collections.Counter(arr).values() # == [4,5,2,2,1]
max_val = max(counts) # == 5

buckets = [0] * (max_val + 1)

for c in counts:
    buckets[c] += 1
# buckets這個array非常重要。它的index等於'arr裡有index個的數字的個數'
# buckets == [0,1,2,0,1,1]

所以在這個情況下我們不需要跑任何n(logn)排序，因為只要由buckets的尾端往回取值，就可以知道我們已掌握了arr之中的多少個數字。取到超過一半時就是答案。當然最後一步需要一點處理：

min(buckets[bucket], math.ceil(number_to_count / bucket))

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        counts = collections.Counter(arr).values() # e.g. Counter({1: 4, 2: 5, 3: 1, 4: 2, 5: 2})
        number_to_count = len(arr) // 2
         # e.g. [4,5,1,2,2]
        max_val = max(counts)
        buckets = [0] * (max_val + 1)
        for c in counts:
            buckets[c] += 1
        # buckets: [0,1,2,0,1,1]
        bucket = max_val
        num_set = 0
        
        while number_to_count > 0:
            if number_to_count - buckets[bucket] * bucket >= 0:
                num_set += buckets[bucket]
                number_to_count -= buckets[bucket] * bucket
                bucket -= 1
                continue
            num_set += min(buckets[bucket], math.ceil(number_to_count / bucket))
            return num_set
        return num_set

#### Analysis:
- Time: $O(NlogN)$ (mine) / $O(N)$ (official better solution)

### #94. Binary Tree Inorder Traversal

### first try:
recursive method; is said to be trivial

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        if not root: return []
        return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right)

### 網友解： iterative method: stack method

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        res, stack = [], []
        
        while True:
            while root:
                stack.append(root)
                root = root.left
            if not stack:
                return res
            node = stack.pop()
            res.append(node.val)
            root = node.right

### 網友解2: Morris traversal
這是一種threaded binary tree。
其主要優點是可以在同樣$O(N)$時間複雜度的前提下，實現$O(1)$的空間複雜度，不需要使用stack等額外記錄路徑的data structure。

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        
        while root:
            if not root.left:
                res.append(root.val)
                root = root.right
            else:
                pred = self.find_pred(root)
                
                if pred.right != root:
                    pred.right = root
                    root = root.left
                else:
                    root.left = None
        return res
        
    def find_pred(self, root):
        cur = root.left
        while cur.right and cur.right != root:
            cur = cur.right
        return cur

[Morris Traversal](https://www.youtube.com/watch?v=wGXB9OWhPTg&ab_channel=TusharRoy-CodingMadeSimple)

#### Analysis:
- Time: $O(N)$
- Space: $O(N)$ $O(N)$ $O(1)$

### #100. Same Tree

## 070821

### #101. Symmetric Tree
和前面比較兩棵樹是否相等的作法一樣，稍微變化而已。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        return self.is_symmetric_tree(root.left, root.right)
        
    def is_symmetric_tree(self, p, q):
        if not p and not q: return True
        if not p or not q: return False
        if p.val != q.val: return False
        return self.is_symmetric_tree(p.left, q.right) and self.is_symmetric_tree(p.right, q.left)
        

#### 網友解
補上iterative method

from collections import deque

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        p, q = root.left, root.right
        deq = deque([(p, q)])
        
        while deq:
            p, q = deq.popleft()
            if not self.check(p, q):
                return False
            if p:
                deq.append((p.left, q.right))
                deq.append((p.right, q.left))
        return True
    
    def check(self, p, q):
        if p == None and q == None: return True
        if p == None or q == None: return False
        if p.val != q.val: return False
        return True

#### Analysis:
- Time: $O(N)$
- Space: $O(N)$

### #718. Maximum Length of Repeated Subarray
DP

#### 網友解

class Solution:
    def findLength(self, nums1: List[int], nums2: List[int]) -> int:
        if len(nums1) < len(nums2): 
            nums1, nums2 = nums2, nums1
        
        m, n = len(nums1), len(nums2)
        ans = 0
        for a in range(-n + 1, m + n - 1):
            cnt = 0
            for bptr in range(n):
                aptr = a + bptr
                if aptr < 0: continue
                if aptr >= m: break
                if nums1[aptr] == nums2[bptr]:
                    cnt += 1
                    if cnt > ans: ans = cnt
                else:
                    cnt = 0
        return ans

### #104. Maximum Depth of Binary Tree

#### first try

class Solution:
    max_depth, cur_depth = 0, 0
    def maxDepth(self, root: TreeNode) -> int:
        if not root: return 0
        self.cur_depth += 1
        self.max_depth = max(self.max_depth, self.cur_depth)
        self.maxDepth(root.left)
        self.maxDepth(root.right)
        self.cur_depth -= 1
        if self.cur_depth == 0: return self.max_depth

#### 網友解1
一行文

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        return 1 + max(self.maxDepth(root.right), self.maxDepth(root.left)) if root else 0

### #12. Integer to Roman
只是路過看到寫一下而已

class Solution:
    def intToRoman(self, num: int) -> str:
        digits = {
            1000:'M', 900:'CM', 500:'D', 400:'CD', 100:'C', \
            90:'XC', 50:'L', 40:'XL', 10:'X', 9:'IX', 5:'V', 4:'IV', 1:'I' \
        }
        digits_li = list(digits.keys())
        res, ptr = '', 0
        while num and ptr < len(digits_li):
            if num / digits_li[ptr] >= 1:
                num -= digits_li[ptr]
                res += digits[digits_li[ptr]]
            else: ptr += 1
        return res

### #110. Balanced Binary Tree

#### first try
第12次提交。再不對，我可要哭了。

其實這樣就是DFS。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        self.balance = True
        if not root: return self.balance
        self.br_depth(root, 1)
        return self.balance
        
    def br_depth(self, root, cur_dep):
        lt_depth = rt_depth = cur_dep
        if root.left:
            lt_depth = self.br_depth(root.left, cur_dep + 1)
        if root.right:
            rt_depth = self.br_depth(root.right, cur_dep + 1)
        if abs(rt_depth - lt_depth) > 1: self.balance = False
        return max(lt_depth, rt_depth)

#### 網友解
DFS, 簡潔版

class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        self.balance = 1
        
        def dfs(node):
            if not node: return 0
            ld, rd = dfs(node.left), dfs(node.right)
            if abs(ld - rd) > 1: self.balance = 0
            return max(ld, rd) + 1
        
        dfs(root)
        return self.balance

#### Analysis:
- Time:$O(N)$
- Space: $O(N)$

## 081321

### #94. Binary Tree Inorder Traversal (revisited)

#### Morrison's traversal
question:
is space complexity of this really constant?
since we make thread to root(or current) at every step and there should be $O(logN)$ number of this thread links, the space complexity should bt $O(logN)$

but if you allocate space for all node with their member variables no matter if they exist(i.e. if they are None or not), this traversal shall be $O(1)$ in space complexity. Since all we did is just use the already allocated space efficiently.

第一個判斷是現在的節點有沒有left subtree
如果沒有就直接印出現在的節點並移到右子樹，這邊很簡單。
第二個判斷是要找出thread，方法可以另外寫，但因為不複雜，直接寫在一起也可以。
thread是一個暫時的連結(産霊, musubi)，其起點是cur的left subtree的最後一個節點(至於怎樣是最後一個節點要看traversal方法)，終點是cur本身。

建立thread的方法是先移動到cur的left(因為我們才剛經歷過上一個條件判斷，這裡必定不會是None)，然後一直往右移動(pred = pred.right)直到以下兩個情形之一發生為止：
1. pred.right == None
2. pred.right = cur

1的情況表示我們找到thread的正確起點了，這時就設定thread並且將cur = cur.left

2的情況表示這個的確是thread的起點，但這條路我們已經是第二次走了，並且對cur來說，他的left subtree應該已經都被瀏覽過了，所以直接切斷：cur.left = None，然後繼續。下一個while loop就會執行第一個判斷(cur.left==None)。

這樣應該夠清楚吧......

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res, cur = [], root
        
        while cur:
            if not cur.left:
                res.append(cur.val)
                cur = cur.right
            
            else:
                pred = cur.left
                while pred.right and pred.right != cur:
                    pred = pred.right
                if not pred.right: 
                    pred.right = cur
                    cur = cur.left
                else: # equal to "if pred.right == cur:"
                    cur.left = None
        return res

### #73. Set Matrix Zeroes

#### first try
naive method:

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        i_set, j_set = set(), set()
        for i in range(len(matrix)):
            for j in range(len(matrix[i])):
                if matrix[i][j] == 0:
                    i_set.add(i)
                    j_set.add(j)
        for i in range(len(matrix)):
            if i in i_set:
                matrix[i] = [0] * len(matrix[i])
        
            else:
                for j in range(len(matrix[i])):
                    if j in j_set:
                        matrix[i][j] = 0

slightly changed:

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        i_set, j_set = set(), set()
        for i in range(len(matrix)):
            for j in range(len(matrix[i])):
                if matrix[i][j] == 0:
                    i_set.add(i)
                    j_set.add(j)
        for i in i_set:
            matrix[i] = [0] * len(matrix[i]) 
        for j in j_set:
            for i in range(len(matrix)):
                matrix[i][j] = 0

## 090221

###

### #102. Binary Tree Level Order Traversal

#### first try:
用字典存，key是level number。只要照著左->右的順序recursion，intralevel順序不會有問題，再來就是排序key，按照key順序填入答案。

不過這其實有點麻煩，因為照我目前的技術，還必須把levels分開寫，不然會有referenced before assignment的問題。

class Solution:
    def __init__(self):
        self.levels = {}
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        output = []
        
        def _traverse(node, lv):
            if node.left:
                if lv not in self.levels:
                    self.levels[lv] = [node.left.val]
                else:
                    self.levels[lv].append(node.left.val)
                _traverse(node.left, lv + 1)
            if node.right:
                if lv not in self.levels:
                    self.levels[lv] = [node.right.val]
                else:
                    self.levels[lv].append(node.right.val)
                _traverse(node.right, lv + 1)
        
        self.levels[0] = [root.val]
        _traverse(root, 1)
        
        all_level = sorted(self.levels.keys())
        for i in all_level:
            output.append(self.levels[i])
        return output

####

#### second try:
採用BFS，好處是不需要遞迴呼叫。

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        res = [[root.val]]
        queue = [root]
        
        while queue:
            size = len(queue)
            layer = []
            while size:
                size -= 1
                s = queue[0]
                if s.left:
                    queue.append(s.left)
                    layer.append(s.left.val)
                if s.right:
                    queue.append(s.right)
                    layer.append(s.right.val)
                queue.pop(0)
            if layer:
                res.append(layer)
        return res
                
                

#### Analysis:
- Time:$O(N)$
- Space:$O(N)$

N:node number

## 090621

### #1629. Slowest Key
给你一个长度为 n 的字符串 keysPressed ，其中 keysPressed[i] 表示测试序列中第 i 个被按下的键。releaseTimes 是一个升序排列的列表，其中 releaseTimes[i] 表示松开第 i 个键的时间。字符串和数组的 下标都从 0 开始 。第 0 个键在时间为 0 时被按下，接下来每个键都 恰好 在前一个键松开时被按下。

测试人员想要找出按键 持续时间最长 的键。第 i 次按键的持续时间为 releaseTimes[i] - releaseTimes[i - 1] ，第 0 次按键的持续时间为 releaseTimes[0] 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/slowest-key
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
#### first try:

class Solution:
    def slowestKey(self, releaseTimes: List[int], keysPressed: str) -> str:
        releaseTimes = [0] + releaseTimes
        longest, max_duration = ' ', 0
        
        for k in range(len(keysPressed)):
            duration = releaseTimes[k + 1] - releaseTimes[k]
            if duration > max_duration:
                longest = keysPressed[k]
                max_duration = duration
            elif duration == max_duration and ord(keysPressed[k]) > ord(longest):
                longest = keysPressed[k]
        return longest

### #562. Longest Line of Consecutive One in Matrix

33
#### 網友解1

善用python內建的data structure。

class Solution:
    def longestLine(self, mat: List[List[int]]) -> int:
        if not mat: return 0
        
        def consecutive(line):
            return max(len(list(v)) if k else 0 
                       for k, v in itertools.groupby(line))
        
        group = collections.defaultdict(list)
        
        for n, row in enumerate(mat):
            for m, col in enumerate(row):
                group[0, n] += [col]
                group[1, m] += [col]
                group[2, n - m] += [col]
                group[3, n + m] += [col]
        
        return max( map(consecutive, group.values()) )
                

# 網友解2

DFS

class Solution:
    def longestLine(self, mat: List[List[int]]) -> int:
        if not mat or not mat[0]:
            return 0
        seen = [set(), set(), set(), set()]
        cur_dir = ((1, 0), (0, 1), (1, 1), (1, -1))
        
        row_len, col_len = len(mat), len(mat[0])
        res = 0
        
        for r in range(row_len):
            for c in range(col_len):
                if mat[r][c]:
                    for i in range(4):
                        if (r, c) not in seen[i]:
                            _dir = cur_dir[i]
                            res = max(res, 
                                      self.dfs(r, c, _dir, i, seen, mat, row_len, col_len))
        return res
    
    def dfs(self, r, c, _dir, i, seen, mat, row_len, col_len):
        cur_res = 1
        seen[i].add((r, c))
        new_r, new_c = r + _dir[0], c + _dir[1]
        if row_len > new_r >= 0 and col_len > new_c >= 0 and mat[new_r][new_c]:
            cur_res += self.dfs(new_r, new_c, _dir, i, seen, mat, row_len, col_len)
        return cur_res

#### Analysis:
- Time: $O(M * N)$
- Space: $O(M * N)$

## 090721

### #206. Reverse Linked List
很好啊，這種題目一個小時寫不出來嘛~

#### 公式解1: iteration method

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev, cur = None, head
        while cur:
            next_temp = cur.next
            cur.next = prev
            prev = cur
            cur = next_temp
        return prev
            

#### 公式解2: recursive method

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
    # recursive method
        if not head or not head.next: return head
        p = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return p

#### Analysis:
- Time: $O(N)$ both
- Space: $O(1)$ / $O(N)$

## 091021
### #83. Remove Duplicates from Sorted List

first try:

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head: return
        cur = head
        while cur.next:
            if cur.val == cur.next.val:
                while cur.val == cur.next.val:
                    cur.next = cur.next.next
                    if not cur.next: break
                
            if cur.next:
                cur = cur.next
        return head

#### Analysis:
- Time: $O(N)$
- Space: $O(1)$

#### 網友解：recursion

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next: return head
        head.next = self.deleteDuplicates(head.next)
        return head if head.val != head.next.val else head.next

#### Analysis:
- Time: $O(N)$
- Space: $O(N)$

### #82. Remove Duplicates from Sorted List II

#### first try
解是解出來了，但是...

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        pre, cur, _init = ListNode(float('-inf'), head), head, True
        if not head: return head
        while cur.next:
            if cur.val != cur.next.val:
                pre = cur
                cur = pre.next
                _init = False
            else:
                while cur.val == cur.next.val:
                    cur.next = cur.next.next
                    if not cur.next: break
                pre.next = cur.next
                cur = pre.next
                if _init: 
                    head = cur
                if not cur: break
        return head

#### 公式解

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        sentinel = ListNode(-100, head)
        pred = sentinel
        
        while head:
            if head.next and head.val == head.next.val:
                while head.next and head.val == head.next.val:
                    head = head.next
                pred.next = head.next
            else:
                pred = pred.next
            head = head.next
        return sentinel.next