# info2021-homework1
暱稱：滿天星/Stars

## 針對 interviewer 的檢討
+ 專注在討論時間複雜度，忽略空間複雜度的討論
+ 沒有引導 interviewee 針對特殊 case 做更詳細的討論
+ 在說明題意時太冗、沒有用更直白的方法描述題目需求
+ 直接接受 interviewee 的答案，沒有多做提問
+ 要求 interviewer 提出更好的作法，但沒有說清楚「好」的意思是什麼
+ 英語能力不夠好

## 針對 interviewee 的檢討
+ 沒有提及空間複雜度
+ 沒有針對特殊 case 做更多提問，導致寫出來的程式碼可能會在極端案例中出錯
+ 一開始錄的時候忘記補上遞迴的終止條件
+ [94. Binary Tree Inorder Traversal](https://leetcode.com/problems/binary-tree-inorder-traversal/) 邊說明想法就邊開始寫程式碼了，但應該先跟 interviewer 討論，確定要採用這個方案再開始寫程式碼
<br/>

# Homework 1

### 第一題 Two sum (Leetcode 1)

題目要求：

> Given an array of integers `nums` and an integer `target`, return indices
of the two numbers such that they add up to `target`.
> <br/>You may assume that each input would have exactly one solution, and
you may not use the same element twice.
> <br/>You can return the answer in any order.

一開始的做法

def twoSum(self, nums, target) :
    global x,y
    n = len(nums)
    for i in range(n):
        for j in range(i+1,n):#n-i-1
            if nums[i]+nums[j] == target:
                x = i
                y = j
                break
    return x, y

使用 two for loop 實作，兩兩確認是否相加為 target，時間複雜度O(n^2^)
<br/>

O(n) 的做法

def twoSum(self, nums: List[int], target: int) -> List[int]:
    hashmap = {}
    for i in range(len(nums)):
        complement = target - nums[i]
        if nums[i] in hashmap:
            return [hashmap[nums[i]], i]
        hashmap[complement] = i

利用 hashmap 查詢只要 O(1) 的特性，將 complement 存至 hashmap，並一一確認是否為先前的 complement，時間複雜度 O(n)
<br/>

### 第二題 Binary Tree Inorder Traversal (Leetcode 94)

題目要求：

> Given the `root` of a binary tree, return the inorder traversal of its nodes' values.

一開始的做法

def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
    if root == None: return []
    l = self.inorderTraversal(root.left)
    r = self.inorderTraversal(root.right)
    l.append(root.val)
    if r:
        l.extend(r)
    return l

使用 recursive 的方式，把左子、現在的 node、右子串再一起回傳即可
<br/>
更改為 iterative 的做法

def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
    stack = []
    ans = []
    while stack or root:
        while root:
            stack.append(root)
            root = root.left
        root = stack.pop()
        ans.append(root.val)
        root = root.right
    return ans

使用 stack 的方式，依照先前 recursive 的順序將 node 推進 stack 裡面，直到不能推（沒有右子）的時候，再將 node 從 stack 裡面 pop 出來
<br/>

### 第三題 Jump Game (Leetcode 55)

題目要求：

> You are given an integer array `nums`. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.<br/>
> Return `true` if you can reach the last index, or `false` otherwise.

一開始的做法

def canJump(self, nums: List[int]) -> bool:
    n = len(nums)
    aux = [0 for i in range(n)]
    aux[0] = 1
    for i in range(n):
        if aux[i] == 0:
            return False
        for j in range(1, nums[i]+1):
            if i + j < n:
                aux[i+j] = 1
    return True

相當直覺的做法，依照每個元素的大小向後做標記，如果走到未經標記的位置(0)則 return False，反之如果一路走到最後，則 return True，這樣做的時間複雜度是O(m*n)，m 為元素的平均大小，n 為元素個數
<br/>
只需要O(n)的做法

def canJump(self, nums: List[int]) -> bool:
    n = len(nums)
    farthest = 0
    for i in range(n):
        if i + nums[i] > farthest:
            farthest = i + nums[i]
        elif i == farthest and i != n - 1: return False
    return farthest >= n - 1

每次記錄可以走的最遠距離，一但超過最遠距離則 return False，否則確認當下元素的大小，到能不能走得更遠，若走到最後則 return True，因為只要每個元素都走過一遍，時間複雜度只需要O(n)，且不需要額外的陣列做輔助

<br/>

# Homework 2

### 第一題 [94. Binary Tree Inorder Traversal](https://leetcode.com/problems/binary-tree-inorder-traversal/)

題目要求：

> Given the `root` of a binary tree, return the inorder traversal of its nodes' values.

一開始的做法

def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
    if root == None: return []
    l = self.inorderTraversal(root.left)
    r = self.inorderTraversal(root.right)
    l.append(root.val)
    if r:
        l.extend(r)
    return l

使用 recursive 的方式，把左子、現在的 node、右子串再一起回傳即可，與 interviewer 討論後，發現這樣的作法需要 O(n^2^) 的時間複雜度，故更改為 iterative 的做法
<br/>
更改為 iterative 的做法

def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
    stack = []
    ans = []
    while stack or root:
        while root:
            stack.append(root)
            root = root.left
        root = stack.pop()
        ans.append(root.val)
        root = root.right
    return ans

使用 stack 的方式，依照先前 recursive 的順序將 node 推進 stack 裡面，直到不能推（沒有右子）的時候，再將 node 從 stack 裡面 pop 出來
### 變形題 [98. Validate Binary Search Tree](https://leetcode.com/problems/validate-binary-search-tree/)
> Given the root of a binary tree, determine if it is a valid binary search tree (BST).

由於我們在上面的程式碼就是 inorder traversal，要拿來檢查一顆 BST 是否 valid，我們只需要確認每次造訪（被pop出來）的 node 的值是否愈來愈大

def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
    stack = []
    tmp = float("-inf")
    while stack or root:
        while root:
            stack.append(root)
            root = root.left
        root = stack.pop()
        if tmp > root.val: return False
		tmp = root.val
        root = root.right
    return True

所以多花一個 tmp 來儲存上一次造訪節點的值，並在每一次確認新的值是否更大（影片中的程式碼忘記加上 tmp 的初始化了，這邊有再補上），由於只多用到一個變數，時間與空間複雜度皆與前面程式碼相同
<br/>

### 第二題 [55. Jump Game](https://leetcode.com/problems/jump-game/)

題目要求：

> You are given an integer array `nums`. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.<br/>
> Return `true` if you can reach the last index, or `false` otherwise.

一開始的做法

def canJump(self, nums: List[int]) -> bool:
    n = len(nums)
    aux = [0 for i in range(n)]
    aux[0] = 1
    for i in range(n):
        if aux[i] == 0:
            return False
        for j in range(1, nums[i]+1):
            if i + j < n:
                aux[i+j] = 1
    return True

相當直覺的做法，依照每個元素的大小向後做標記，如果走到未經標記的位置(0)則 return False，反之如果一路走到最後，則 return True，這樣做的時間複雜度是O(m*n)，m 為元素的平均大小，n 為元素個數
<br/>
只需要O(n)的做法

def canJump(self, nums: List[int]) -> bool:
    n = len(nums)
    farthest = 0
    for i in range(n):
        if i + nums[i] > farthest:
            farthest = i + nums[i]
        elif i == farthest and i != n - 1: return False
    return farthest >= n - 1

每次記錄可以走的最遠距離，一但超過最遠距離則 return False，否則確認當下元素的大小，到能不能走得更遠，若走到最後則 return True，因為只要每個元素都走過一遍，時間複雜度只需要O(n)，且不需要額外的陣列做輔助

### 變形題 [45. Jump Game II](https://leetcode.com/problems/jump-game-ii/)
> Your goal is to reach the last index in the minimum number of jumps.
> You can assume that you can always reach the last index.

利用原來的程式碼，不同的地方在於，我們要用類似 checkpoint 的方式，checkpoint 是上次可以到達的最遠距離，每次到達 checkpoint 的時候會再把 checkpoint 更新成可以到達的最遠距離，同時 count + 1，如此一來，我們就能確保每次都跨出最遠的步伐，最後 return count 即可

def canJump(self, nums: List[int]) -> bool:
    n = len(nums)
    farthest = 0
    curr = 0
    count = 0
    for i in range(n):
        if i + nums[i] > farthest:
            farthest = i + nums[i]
        if curr == i:
            count += 1
            curr = farthest
    return count

<br/>