# Week1 - Greedy Algorithm

###### tags: `Leetcode`

## 55. Jump Game
思路：指針 A 負責從左到右遍歷數組元素，指針 B 負責追蹤當前最遠可跑的位置。若 A 指針與 B 指針重疊，且指針所在位置之數值為 0，則表示失敗。若 B 指針所在位置大於等於數組長度，則表示成功。

class Solution(object):
    def canJump(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        max_reach = 0 
        l = len(nums)
        for i in range(l):
            max_reach = max(max_reach, i + nums[i])
            if max_reach >= l-1: 
                return True
            elif i == max_reach: 
                return False

+ **Links**
+ https://www.youtube.com/watch?v=i5L_onhWULc

## 45. Jump Game II
定義函數 $d(r) =$ 到位置 $r$ 所需的最少步數，$d(r)$ 滿足
+ 單調遞增。
+ $d(0) = 0$。
+ 走 $k$ 步可走的最大距離等於 $\max\{r + num[r] \, | d(r) = k \}$。
+ 失敗條件：$\max d^{-1}(k) <= \max d^{-1}(k-1)$。

思路：$k$ 負責紀錄步數，指針 A 負責從左到右遍歷數組元素，指針 B 負責紀錄走 $k$ 步最遠可到的位置，指針 C 負責紀錄走 $k+1$ 步最遠可到的位置。若 A 指針與 B 指針位置重疊，將 $k$ 值加 $1$，將 B 指針位置更新至 C 指針位置，C 指針位置保持不變；若 A 指針已位於數組最右邊，輸出 $k$。

class Solution(object):
    def jump(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        k, l = 0, len(nums) 
        curr_largest_step, next_largest_step = 0, nums[0]

        for i in range(l): 
            if i == l-1: 
                return k

            next_largest_step = max(next_largest_step, nums[i] + i)
            
            if i == curr_largest_step:
                k += 1
                curr_largest_step = next_largest_step

+ **Links**
+ https://www.youtube.com/watch?v=2A1CkbghE6Y)

## 134. Gas Station
我們知道若 $gas$ 之和小於 $cost$ 之和，則不存在路徑滿足條件，反之，$gas$ 之和若大於等於 $cost$ 之和，則存在路徑，證明見下圖。

思路：指針 A 負責從左到右遍歷數組元素，指針 B 負責紀錄本次路徑的起始位置，定義個變數 $total$, $remain$ 分別紀錄數組 $gas$ 之和減去數組 $cost$ 之和與當前路徑 $gas$ 之減去 $cost$ 之和，若 $remain$ 值小於 0，則結束這次的路徑，並以下一點為起始，重新開始路徑，直至遍歷完數組。若最後 $total$ 為負值，輸出 $-1$，反之，輸出 指針 B 所在位置。


class Solution(object):
    def canCompleteCircuit(self, gas, cost):
        """
        :type gas: List[int]
        :type cost: List[int]
        :rtype: int
        """
        k, l = 0, len(gas) 
        remain, total = 0, 0 
        
        for i in range(l):
            net = (gas[i] - cost[i])
            total += net
            remain += net
            if remain < 0:
                remain = 0 
                k = i + 1
        return -1 if total < 0 else k 

## 179. Largest Number

class Compare(str): 
    def __lt__(x, y): 
        return x + y < y + x

class Solution(object):
    def largestNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: str
        """
        a_list = sorted(map(str, nums), key=Compare, reverse=True)
        largest_num = "".join(a_list)
        return "0" if largest_num[0] == "0" else largest_num

+ **Links**
+ https://stackoverflow.com/questions/63164064/unable-to-understand-lt-method
+ https://hackmd.io/thsnM8y2Sx-AhF16ZFgZBg

## 122. Best Time to Buy and Sell Stock II

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        profit = 0 
        for i in range(len(prices)-1): 
            profit += max((prices[i+1] - prices[i]), 0)
        return profit

+ **Links**
+ https://hackmd.io/gAlljfGbS_intn3k1gQomA

## 11. Container With Most Water

class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        left, right = 0, len(height) -1 
        area = min(height[left], height[right]) * (right - left) 
        while left < right:
            if height[left] < height[right]: 
                left += 1
            else: 
                right -= 1 
            
            area = max(area, min(height[left], height[right]) * (right - left))
        return area

**數學證明**：假設 $i, j$ 為最佳組合
$$
area(i, j) = \max \{area(i, j)| 0< i < j < l\}
$$ 其中，$l$ 為數組的長度。我們要證明雙指針演算法會移動到 $i, j$ 這個組合。假設 A, B 分別為左右兩個指針，不失一般性，假設指針 A 先移動到位置 $i$ 且指針 B 還在 $j$ 點的右邊。因為 $i, j$ 為最佳組合，具有下列性質
$$
h(i) > h(n), \quad \forall n < i, \\
h(j) > h(m), \quad \forall m > j.
$$

考慮下列兩種情況
+ 若 $h(i) <= h(j)$：我們知道盛水的高度取決於短邊，因此，
$$
h(i) > h(m), \quad \forall m>j.
$$

+ 若 $h(i) > h(j)$: 根據下列不等式
$$
h(i) > h(j) > h(m), \quad \forall m>j.
$$
因此，指針 $m$ 需要往左移動。