---
# System prepended metadata

title: Leetcode 六月挑戰

---

Leetcode 六月挑戰
===
[TOC]

## Week 1
### Invert Binary Tree
![](https://i.imgur.com/QSXdUXK.png)

```python=
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution(object):
    def invertTree(self, root):
        if root == None:
            return
        root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
        return root
```

```c=
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


struct TreeNode* invertTree(struct TreeNode* root){
    if (root == NULL) return NULL;
    struct TreeNode* temp = root->left;
    root->left = root->right;
    root->right = temp;
    invertTree(root->left);
    invertTree(root->right);
    return root;
}
```

#### 解題思路
這題比較直觀一些，直接將樹根的左右交換，然後往下遞迴即可


### Delete Node in a Linked List
![](https://i.imgur.com/vtYXLEq.png)

Input: head = [4,5,1,9], node = 5
Output: [4,1,9]
Explanation: You are given the second node with value 5, the linked list should become 4 -> 1 -> 9 after calling your function.

```python=
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def deleteNode(self, node):
        node.val, node.next = node.next.val, node.next.next
        
```

```c=
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
void deleteNode(struct ListNode* node) {
    struct ListNode* temp = node->next;
    node->val = node->next->val;
    node->next = node->next->next;
    free(temp);
}
```

#### 解題思路
用C的觀點來解釋，我們先用temp存取要刪除的節點的next，接著把下next的value指定給現在的node的val，並且把現在node的next指向下下個節點，最後free掉temp
```
Step 1.
(4) (5) (1) (9)
temp-----^

Step 2.
(4) (1) (1) (9)
　　　|-------^
   
Step 3.
(4) (1)     (9)
```

###  Two City Scheduling
![](https://i.imgur.com/oMMIaGb.png)

```python=
def diff(l):
    return l[0] - l[1]

def twoCitySchedCost(costs):
    costs.sort(key=diff)
    countA = 0
    ans = 0
    for costA, costB in costs:
        if countA < (len(costs) // 2):
            ans += costA
            countA += 1
        else:
            ans += costB
    return ans
    
class Solution(object):
    def twoCitySchedCost(self, costs):
        return twoCitySchedCost(costs)
```

```c=
int diff(int* l){
    return l[0] - l[1];
}

int cmp(void* a, void* b){
    int* l1 = *(int**)a;
    int* l2 = *(int**)b;
    return diff(l1) - diff(l2);
}

int twoCitySchedCost(int** costs, int costsSize, int* costsColSize){
    qsort(costs, costsSize, sizeof(int*), cmp);
    int ans = 0;
    int countA = 0;
    for(int i = 0; i < costsSize; i++){
        int costA = costs[i][0];
        int costB = costs[i][1];
        if (countA < costsSize / 2){
            ans+= costA;
            countA++;
        }
        else
            ans+= costB;
    }
    
    return ans;
}
```
#### 解題思路
這題就是把陣列裡面的元素相減，若負越多，代表選A賺越多，所以我們就可以做個排序，賺越多得先選，選到不能再選才給B

###  Reverse String

![](https://i.imgur.com/3DGq2nt.png)

#### 法一 :
```python=
class Solution:
    def reverseString(self, s: List[str]) -> None:
        # 1) s是區域變數, s='olleh'是不會改變s的
        # 2) s是個字串(str), Python中字串的物件都是唯讀的
        # 3) 所以s傳進來的會是列表(list) ['h', 'e', 'l', 'l', 'o']
        s[:] = s[::-1]
        
        # 長度為5的list
        # 可用的索引範圍是-5~-1, 0~4 (-len(s)~-1, 0~len(s)-1)
        # -5 -4 -3 -2 -1
        #  0  1  2  3  4

        #  另解
        # for i in range(len(s)//2):
        #     # i + j == len(s) - 1
        #     j = len(s)-1-i
        #     t = s[i]
        #     s[i] = s[j]
        #     s[j] = t
```

```c=
void reverseString(char* s, int sSize){
    for (int i = 0; i < sSize/2; i++){
        int j = sSize - 1 - i;
        char t = s[i];
        s[i] = s[j];
        s[j] = t;
    }
}
```

#### 法二 :
```python=
class Solution:
    def reverseString(self, s: List[str]) -> None:
        i, j = 0, len(s)-1
        while i < j:
            s[i], s[j] = s[j], s[i]
            i += 1
            j -= 1
```

```c=
void reverseString(char* s, int sSize){
    int i = 0, j = sSize - 1;
    while (i < j){
        char t = s[i];
        s[i] = s[j];
        s[j] = t;
        
        i++;
        j--;
    }
}

void reverseString(char* s, int sSize){
    char* si = s;
    char* sj = s + sSize - 1;
    
    while(si < sj){
        char t = *si;
        *si = *sj;
        *sj = t;
        si++;
        sj--;
    }
}
```

#### 法三 :

在python中，能不自己寫就不要，直接開大決即可
```python=
class Solution(object):
    def reverseString(self, s):
        s.reverse()
```

### Random Pick with Weight
![](https://i.imgur.com/8N6L4WN.png)

```python=
class Solution(object):

    def __init__(self, w):
        #      0   1   2
        # w : [1,  3,  3]
        
        #        1        4       7 
        #        v        v       v
        #     0  1  2  3  4  5  6
        # l: [0, 1, 1, 1, 2, 2, 2]  -> we don't want produce this
        
        # 累積和圖
        # <=   0   1   2
        # a : [1,  4,  7]
        # a[0] = w[0]
        # a[1] = w[0] + w[1] = a[0] + w[1]
        # a[2] = w[0] + w[1] + w[2] = a[1] + w[2]
        a = [None] * len(w)
        a[0] = w[0]
        for i in range(1, len(w)):
            a[i] = a[i-1] + w[i]
        self._a = a
        
        
    def pickIndex(self):
        # len(self._l) : 7
        # random.randrange(len(self._l)) : 0 ~ 6
        d= random.randrange(self._a[-1])
        #      0   1   2    -> i
        # a : [1,  4,  7]   -> c
        # d :  3
        for i, c in enumerate(self._a):
            if d < c:
                return i
        
# Your Solution object will be instantiated and called as such:
# obj = Solution(w)
# param_1 = obj.pickIndex()
```

==We can use binary search to reduce time complexity.==

```python=
class Solution:

    def __init__(self, w: List[int]):
        #      0   1   2
        # w : [1,  3,  3]
        
        #        1        4       7 
        #        v        v       v
        #     0  1  2  3  4  5  6
        # l: [0, 1, 1, 1, 2, 2, 2]  -> we don't want produce this
        
        # 累積和圖
        # <=   0   1   2
        # a : [1,  4,  7]
        # a[0] = w[0]
        # a[1] = w[0] + w[1] = a[0] + w[1]
        # a[2] = w[0] + w[1] + w[2] = a[1] + w[2]
        a = [None] * len(w)
        a[0] = w[0]
        for i in range(1, len(w)):
            a[i] = a[i-1] + w[i]
        self._a = a
        
    def pickIndex(self) -> int:
        # len(self._l) : 7
        # random.randrange(len(self._l)) : 0 ~ 6
        d= random.randrange(self._a[-1])
        #      0   1   2    -> i
        # a : [1,  4,  7]   -> c
        # d :  3
        # for i, c in enumerate(self._a):
        #     if d < c:
        #         return i
        l, r = 0, len(self._a) # l : 0, r : 3
        # d < self._a[i] and d >= self._a[i-1] -> find i
        while l < r:
            mid = (l+r) // 2 # mid = 1
            if d < self._a[mid]:
                if mid == 0 or d >= self._a[mid-1]:
                    return mid
                r = mid
            else:
                l = mid+1

# Your Solution object will be instantiated and called as such:
# obj = Solution(w)
# param_1 = obj.pickIndex()

```

```c=
typedef struct {
    int* a;
    int aSize;
} Solution;


Solution* solutionCreate(int* w, int wSize) {
    /*
    a = [None] * len(w)
    a[0] = w[0]
    for i in range(1, len(w)):
        a[i] = a[i-1] + w[i]
    */
    Solution* self = malloc(sizeof(Solution));
    self->a = malloc(sizeof(int) * wSize);
    self->aSize = wSize;
    self->a[0] = w[0];
    for (int i = 1; i < wSize; i++){
        self->a[i] = self->a[i-1] + w[i];
    }
    return self;
}

int solutionPickIndex(Solution* self) {
    /*
     d= random.randrange(self._a[-1])
     l, r = 0, len(self._a)
     while l < r:
        mid = (l+r) // 2 
        if d < self._a[mid]:
            if mid == 0 or d >= self._a[mid-1]:
                return mid
            r = mid
        else:
            l = mid+1
    */
    int d = rand() % self->a[self->aSize-1];
    int l = 0, r = self->aSize;
    while (l < r){
        int mid = (l+r) / 2;
        if (d < self->a[mid]){
            if (mid == 0 || d >= self->a[mid-1]){
                return mid;
            }
            r = mid;
        }
        else{
            l = mid+1;
        }
    }
    return -1;
}

void solutionFree(Solution* obj) {
    free(obj->a);
    free(obj);
}

/**
 * Your Solution struct will be instantiated and called as such:
 * Solution* obj = solutionCreate(w, wSize);
 * int param_1 = solutionPickIndex(obj);
 
 * solutionFree(obj);
*/
```

Python有現成的API可以call就call，速度差很多

```python=
class Solution:

    def __init__(self, w: List[int]):
        self._a = tuple(accumulate(w))
        
    def pickIndex(self) -> int:
        d= random.randrange(self._a[-1])
        return bisect_right(self._a, d)


# Your Solution object will be instantiated and called as such:
# obj = Solution(w)
# param_1 = obj.pickIndex()
```

### Queue Reconstruction by Height
![](https://i.imgur.com/ZwwoJVR.png)

```python=
class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        # people : [[7, 0], [4, 4], [7, 1], [5, 0], [6, 1], [5, 2]]
        #          (-7, 0) (-4, 4), (-7, 1), (-5, 0), (-6, 1), (-5, 2)
        people.sort(key=lambda l : (-l[0], l[1]))
        # people : [[7, 0], [7, 1], [6, 1], [5, 0], [5, 2], [4, 4]]
        answer = []
        for l in people:
            answer.insert(l[1], l) # 把l插在l[1]的位置
        return answer
```

```c=
int cmp(const void *pa, const void *pb){
    // 如果*pa要放在*pb後面，回傳正數
    // 如果*pa要放在*pb前面，回傳負數
    const int* a = *(const int**)pa;
    const int* b = *(const int**)pb;
    
    if (a[0] == b[0]){
        return a[1] - b[1];
    }
    return b[0] - a[0];
    // [7, 0], [7, 1]
    //   a       b    
    // [7, 0], [4, 4]
    //   b       a
}

int** reconstructQueue(int** people, int peopleSize, int* peopleColSize, int* returnSize, int** returnColumnSizes){
    /*
        people.sort(key=lambda l : (-l[0], l[1]))
        answer = []
        for l in people:
            answer.insert(l[1], l)
        return answer
    */
    qsort(people, peopleSize, sizeof(int*), cmp);
    
    int** answer = malloc(peopleSize*sizeof(int*));
    for (int i = 0; i < peopleSize; i++){
        answer[i] = malloc(2*sizeof(int));
    }
    
    for (int i = 0; i < peopleSize; i++){
        for (int j = i; j > people[i][1]; j--){
            answer[j][0] = answer[j-1][0];
            answer[j][1] = answer[j-1][1];
        }
        answer[people[i][1]][0] = people[i][0];
        answer[people[i][1]][1] = people[i][1];
    }
    // [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
    
    // i = 0
    // answer = []
    // answer[0] = [7, 0]
    
    // i = 1
    // answer = [[7, 0]]
    // answer[1] = [7, 1]
    
    // i = 2
    // answer = [[7, 0], [7, 1]]
    // answer[2] = answer[1]
    // answer[1] = [6, 1]
    
    // i = 3
    // answer = [[7, 0], [6, 1], [7, 1]]
    // answer[3] = answer[2]
    // answer[2] = answer[1]
    // answer[1] = answer[0]
    // answer[0] = [5, 0]
    
    // i = 4
    // answer = [[5, 0], [7, 0], [6, 1], [7, 1]]
    // answer[4] = answer[3]
    // answer[3] = answer[2]
    // answer[2] = [5, 2]
    
    // answer[i] = answer[i-1]
    // answer[people[i][1]] = people[i]
    
    *returnSize = peopleSize;
    *returnColumnSizes = malloc(peopleSize*sizeof(int));
    for (int i = 0; i < peopleSize; i++){
        (*returnColumnSizes)[i] = 2;
    }
    return answer;
}
```

### Coin Change 2
![](https://i.imgur.com/ODpNKRZ.png)

```python=
def change(amount, coins, cache):
    # amount : 5
    # coins : [1, 2]
    # change(5, [1])
    # change(5, [2]) = change(5, [1]) + change(5-2, [1, 2])
    # change(amount, coins) = change(amount, coins[:-1]) + change(amount-coins[-1], coins)
    if amount == 0: return 1
    
    if len(coins) == 0: return 0

    if (amount, *coins) in cache:
        return cache[(amount, *coins)]
    
    result = change(amount, coins[:-1], cache)
    
    if (amount-coins[-1]) >= 0:
        result += change(amount-coins[-1], coins, cache)
        
    cache[(amount, *coins)] = result
    
    return result

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        return change(amount, coins, {})
```

降低每次都要複製coins的複雜度

```python=
# 回傳用 coins 裡面前 length 種硬幣面額有多少種不同的方法可以湊出 amount
def change(amount, length, coins, cache):
    
    if amount == 0 : return 1
    if length == 0 : return 0
    
    key = amount, length
    
    if key in cache:
        return cache[key]

    result = change(amount, length-1, coins, cache)
    
    if amount-coins[length-1] >= 0:
        result += change(amount-coins[length-1], length, coins, cache)
        
    cache[key] = result
    
    return result

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        return change(amount, len(coins), coins, {})
```

因為字典查詢比較慢，用陣列比較快

```python=
# 回傳用 coins 裡面前 length 種硬幣面額有多少種不同的方法可以湊出 amount
def change(amount, length, coins, cache):
    
    if amount == 0 : return 1
    if length == 0 : return 0
    
    key = amount, length
    
    if cache[amount][length] != None:
        return cache[amount][length]

    result = change(amount, length-1, coins, cache)
    
    if amount-coins[length-1] >= 0:
        result += change(amount-coins[length-1], length, coins, cache)
        
    cache[amount][length] = result
    
    return result

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        return change(amount, len(coins), coins, [[None]*(len(coins)+1) for i in range(amount+1)])
```

```python=
class Solution:
    def change(self, finalAmount: int, coins: List[int]) -> int:
        cache = [[None]*(len(coins)+1) for i in range(finalAmount+1)]
        length = len(coins)
        for amount in range(0, finalAmount+1):
            for i in range(0, len(coins)+1):

                if amount == 0 : 
                    cache[amount][length] = 1
                    continue
                if length == 0 : 
                    cache[amount][length] = 0
                    continue

                result = cache[amount][length-1]

                if amount-coins[length-1] >= 0:
                    result += cache[amount-coins[length-1]][length]

                cache[amount][length] = result
            
        return cache[finalAmount][len(coins)]

```

Dynamic programming

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

```

```c=
int change(int finalAmount, int* coins, int coinsSize){
    int* cache = calloc(finalAmount+1, sizeof(int));
    cache[0] = 1;
    for (int i = 0; i < coinsSize; i++){
        int coin = coins[i];
        for (int amount = coin; amount <= finalAmount; amount++){
            cache[amount] += cache[amount-coin];
        }
    }
    return cache[finalAmount];
}
```

## Week 2

### Power of Two

```python=
def isPowerOfTwo(n):
    if n <= 0:
        return False
    return math.log2(n).is_integer()

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        return isPowerOfTwo(n)
```

```python=
def isPowerOfTwo(n):
    return  n > 0 and 1073741824 % n == 0

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        return isPowerOfTwo(n)
```

```python=
def isPowerOfTwo(n):
    num_ones = 0
    
    while n > 0:
        if n % 2 == 1:
            num_ones += 1
        if num_ones > 1:
            return False
        n //= 2
    return num_ones == 1

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        return isPowerOfTwo(n)
```

```python=
def isPowerOfTwo(n):
    return n > 0 and n&(n-1) == 0

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        return isPowerOfTwo(n)
```

```c=
bool isPowerOfTwo(int n){
    return n > 0 && (n&(n-1) == 0);
}
```

### Is Subsequence

![](https://i.imgur.com/jq7E9h8.png)

```python=
class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        
        last = -1
        
        for c in s:
            j = t.find(c, last+1)
            if j == -1:
                return False
            last = j
            
        return True
```

Two Pointer 解

```python=
class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        
        i = 0
        j = 0
            
        if len(s) == 0:
            return True
        if len(t) == 0:
            return False
        
        while True:
            if s[i] == t[j]:
                i += 1
                if i == len(s):
                    return True
            j += 1
            if j == len(t):
                return False
```

```c=
bool isSubsequence(char * s, char * t){

    if (*s == '\0'){
        return true;
    }
    
    if (*t == '\0'){
        return false;
    }
    
    while (1) {
        if (*s == *t){
            s++;
            if (*s == '\0') return true;
        }
        t++;
        if (*t == '\0') return false;
    }
    
}
```


### Search Insert Position

![](https://i.imgur.com/ucYMC2K.png)

```python=
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        
        left, right = 0, len(nums)
        
        while True:
            if left == right:
                return left
            
            mid = (left + right) // 2
            
            if (nums[mid] == target):
                return mid

            if (nums[mid] > target):
                right = mid
            else:
                left = mid+1
                
        return searchInsert(nums, 0, len(nums), target)
```

```c=
int searchInsert(int* nums, int numsSize, int target){
    int left = 0;
    int right = numsSize;
    
    while (left != right){
        int mid = (left + right) / 2;
        
        if (nums[mid] == target) 
            return mid;
        
        if (nums[mid] > target) 
            right = mid;
        else
            left = mid + 1;
    }
    return left;
}
```


### Sort Colors

![](https://i.imgur.com/dgWquPR.png)

```python=
class Solution:
    def sortColors(self, nums: List[int]) -> None:
        
        i, l, r = 0, 0, len(nums)-1
        
        while i <= r:
            if nums[i] == 2:
                nums[i], nums[r] = nums[r], nums[i]
                r -= 1
            elif nums[i] == 0:
                nums[i], nums[l] = nums[l], nums[i]
                l += 1
                i += 1
            else:
                i += 1
```


```c=
void swap(int* a, int* b){
    int temp = *a;
    *a = *b;
    *b = temp;
}

void sortColors(int* nums, int numsSize){
    int l = 0;
    int r = numsSize - 1;
    int i = 0;
    
    while (i <= r){
        if (nums[i] == 2)
            swap(&nums[i], &nums[r--]);
        else if (nums[i] == 0)
            swap(&nums[i++], &nums[l++]);
        else
            i++;
    }
}
```

### Insert Delete GetRandom O(1)
![](https://i.imgur.com/zBoi8Uv.png)

```python=
class RandomizedSet:

    def __init__(self):
        self.values = []
        self.check = {}
        

    def insert(self, val: int) -> bool:
        if val in self.check:
            return False
        
        self.values.append(val)
        self.check[val] = len(self.values)-1
        return True
        

    def remove(self, val: int) -> bool:
                                        # values = [0, 3, 2]
        if val in self.check:           # check : {0 : 0, 3 : 1, 2 : 2}
            index = self.check[val]     # 假如我想刪掉 3, index = 1
            lastValue = self.values[-1] 
            self.values[index] = lastValue # values = [0, 2, 2]
            self.values.pop()
            self.check[lastValue] = index # check : {0 : 0, 3 : 1, 2 : 1}
            self.check.pop(val)
            return True
        
        return False
    
    def getRandom(self) -> int:
        return random.choice(self.values)
        


# Your RandomizedSet object will be instantiated and called as such:
# obj = RandomizedSet()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()
```

```c=
#define HASH_SIZE 997

typedef struct HashNodes{
    int value;
    int position;
    struct HashNodes* next;
} HashNodes;

typedef struct RandomizedSet{
    int size;
    int nums[10000];
    HashNodes** hashTable;
} RandomizedSet;

/** Initialize your data structure here. */

RandomizedSet* randomizedSetCreate() {
    RandomizedSet* myArray = (RandomizedSet*)malloc(sizeof(RandomizedSet));
    myArray->size = 0;
    myArray->hashTable = (HashNodes**)malloc(sizeof(HashNodes*)*HASH_SIZE);
    for (int i = 0; i < HASH_SIZE; i++){
        myArray->hashTable[i] = NULL;
    }
    return myArray;
}

/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
bool randomizedSetInsert(RandomizedSet* obj, int val) {
    int index = abs(val % HASH_SIZE);
    HashNodes* ptr = obj->hashTable[index];
    HashNodes* pre = ptr;
    
    while (ptr != NULL){
        if (ptr->value == val)
            return false;
        pre = ptr;
        ptr = ptr->next;
    }
    
    obj->nums[obj->size] = val;
    ptr = (HashNodes*)malloc(sizeof(HashNodes));
    
    if (obj->hashTable[index] == NULL)
        obj->hashTable[index] = ptr;
    
    if (pre!=NULL)
        pre->next = ptr;
    
    ptr->position = obj->size++;
    ptr->value = val;
    ptr->next = NULL;
    
    return true;
}

void updateIndex(RandomizedSet* obj, int target, int newIndex) {
    int index = abs(target % HASH_SIZE);
    HashNodes* ptr = obj->hashTable[index];
    while (ptr != NULL){
        if (ptr->value == target){
            ptr->position = newIndex;
            break;
        }
        ptr = ptr->next;
    }
    return;
}

/** Removes a value from the set. Returns true if the set contained the specified element. */
bool randomizedSetRemove(RandomizedSet* obj, int val) {
  int index = abs(val % HASH_SIZE);
    HashNodes* ptr = obj->hashTable[index];
    HashNodes* pre = ptr;
    
    while (ptr != NULL){
        if (ptr->value == val){
            // updateIndex(RandomizedSet* obj, int target, int newIndex) 
            updateIndex(obj, obj->nums[obj->size-1], ptr->position);
            obj->nums[ptr->position] = obj->nums[--obj->size];
            
            if (pre == ptr)
                obj->hashTable[index] = ptr->next;
            else
                pre->next = ptr->next;
            
            free(ptr);
            ptr = NULL;
            return true;
        }
        pre = ptr;
        ptr = ptr->next;
    }
    return false;
}

/** Get a random element from the set. */
int randomizedSetGetRandom(RandomizedSet* obj) {
    if (obj->size < 1)
        return NULL;
    int random = (rand() % obj->size);
    return obj->nums[random];
}

void randomizedSetFree(RandomizedSet* obj) {
    for (int i = 0; i < obj->size; i++)
        randomizedSetRemove(obj, obj->nums[i]);
    free(obj->hashTable);
    obj->hashTable = NULL;
    free(obj);
    obj = NULL;
}

/**
 * Your RandomizedSet struct will be instantiated and called as such:
 * RandomizedSet* obj = randomizedSetCreate();
 * bool param_1 = randomizedSetInsert(obj, val);
 
 * bool param_2 = randomizedSetRemove(obj, val);
 
 * int param_3 = randomizedSetGetRandom(obj);
 
 * randomizedSetFree(obj);
*/
```


### Largest Divisible Subset
![](https://i.imgur.com/vsCnJgE.png)



```python=
class Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        nums.sort()
        
        cache = [None] * len(nums)
        cache[0] = [nums[0]]
        
            
        for key in range(1, len(nums)):
            maxList = [nums[key]]
            for i in range(key):
                if nums[key] % nums[i] == 0:
                    l = [*cache[i], nums[key]]
                    if len(l) > len(maxList):
                        maxList = l

            cache[key] = maxList 
        
        maxList = []
        for i in range(len(nums)):
            l = cache[i]
            if len(l) > len(maxList):
                maxList = l
                
        return maxList
```


```c=
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int cmp(const void* pa, const void* pb){
    return *(const int*)pa - *(const int*)pb;
}

int* largestDivisibleSubset(int* nums, int numsSize, int* returnSize){
    qsort(nums, numsSize, sizeof(int), cmp);
    
    int** cache = malloc(numsSize * sizeof(int*));
    int* cacheSizes = malloc(numsSize * sizeof(int));
    
    cache[0] = malloc(sizeof(int));
    cacheSizes[0] = 1;
    
    cache[0][0] = nums[0];
    
    for (int key = 1; key < numsSize; key++){
        int maxListSize = 0;
        int maxIndex = -1;

        for (int i = 0; i < key; i++){
            if (nums[key] % nums[i] == 0){
                int lSize = cacheSizes[i] + 1;
                if (lSize > maxListSize){
                    maxListSize = lSize;
                    maxIndex = i;
                }
            }
        }
        if (maxIndex == -1){
            cache[key] = malloc(sizeof(int));
            cache[key][0] = nums[key];
            cacheSizes[key] = 1;
        } else {
            cache[key] = malloc((cacheSizes[maxIndex]+1)*sizeof(int));
            for (int j = 0; j < cacheSizes[maxIndex]; j++){
                cache[key][j] = cache[maxIndex][j];
            }
            
            cache[key][cacheSizes[maxIndex]] = nums[key];
            cacheSizes[key] = maxListSize;
        }
    }
    
    int* maxList = NULL;
    int maxListSize = 0;
    for (int i = 0; i < numsSize; i++){
        int* l = cache[i];
        int lSize = cacheSizes[i];
        if (lSize > maxListSize){
            maxList = l;
            maxListSize = lSize;
        }
    }
    
    for (int i = 0; i < numsSize; i++){
        if (maxList != cache[i]){
            free(cache[i]);
        }
    }
    free(cache);
    free(cacheSizes);
    *returnSize = maxListSize;
    return maxList;
}
```

### Cheapest Flights Within K Stops

![](https://i.imgur.com/DqLiyUK.png)

```python=
class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, K: int) -> int:
        flightMap = [None]*n
        for s in range(n):
            flightMap[s] = []
        for (s, d, p) in flights:
            flightMap[s].append((d,p))
        
        cache = [None]*n
        for s in range(n):
            cache[s] = [None]*(K+1)
        
        for k in range(K+1):
            for s in range(n):
                minPrice = -1

                for (d, p) in flightMap[s]:
                    if d == dst:
                        price = p
                        if minPrice == -1 or price < minPrice:
                            minPrice = price
                    elif k > 0:
                        r = cache[d][k-1]
                        if r != -1:
                            price = p + r
                        if minPrice == -1 or price < minPrice:
                            minPrice = price

                cache[s][k] = minPrice
    
        return cache[src][K]
        
```

```c=
int findCheapestPrice(
    int n, 
    int** flights, 
    int flightsSize, 
    int* flightsColSize, 
    int src, int dst, int K){
    
    int*** flightMap = malloc(sizeof(int**)*n);
    int* flightMapSize = calloc(n, sizeof(int));
    for (int s = 0; s < n; s++){
        flightMap[s] = malloc(sizeof(int*)*n);
        flightMapSize[s] = 0;
        for (int j = 0; j < n; j++){
            flightMap[s][j] = malloc(sizeof(int)*2);
        }
    }
    
    for (int i = 0; i < flightsSize; i++){
        int* flight = flights[i];
        int s = flight[0];
        int d = flight[1];
        int p = flight[2];
        int size = flightMapSize[s];
        flightMap[s][size][0] = d;
        flightMap[s][size][1] = p;
        flightMapSize[s] = size + 1;
    }
    
    int** cache = malloc(sizeof(int*)*n);
    for (int s = 0; s < n; s++){
        cache[s] = malloc(sizeof(int)*(K+1));
    }
    
    for (int k = 0; k <= K; k++){
        for (int s = 0; s < n; s++){
            int minPrice = -1;
            for (int i = 0; i < flightMapSize[s]; i++){
                int* flight = flightMap[s][i];
                int d = flight[0];
                int p = flight[1];
                if (d == dst){
                    int price = p;
                    if (minPrice == -1 || price < minPrice){
                        minPrice = price;
                    } 
                } else if (k > 0){
                    int r = cache[d][k-1];
                    if (r != -1){
                        int price = p + r;
                        if (minPrice == -1 || price < minPrice){
                            minPrice = price;
                        } 
                    }
                }
            }
            cache[s][k] = minPrice;
        }
    }
    
    int res = cache[src][K];
    
    for (int s = 0; s < n; s++){
        free(cache[s]);
    }
    free(cache);
    
    for (int s = 0; s < n; s++){
        for (int j = 0; j < n; j++){
            free(flightMap[s][j]);
        }
        free(flightMap[s]);
    }
    free(flightMapSize);
    free(flightMap);
    return res;
}
```

## Week 3
### Search in a Binary Search Tree

```python=
# 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 searchBST(self, root: TreeNode, val: int) -> TreeNode:
        while root != None:
            if root.val == val:
                return root
            if root.val < val:
                root = root.right
            else:
                root = root.left
                
        return None
```

```c=
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


struct TreeNode* searchBST(struct TreeNode* root, int val){
    while (root != NULL){
        if (root->val == val)
            return root;
        if (root->val < val)
            root = root->right;
        else
            root = root->left;
    }
    return NULL;
}
```

### Validate IP Address

![](https://i.imgur.com/Q3ZjmVX.png)

#### Unique Binary Search Trees

![](https://i.imgur.com/j1ET19W.png)

```python=
class Solution:
    def numTrees(self, n: int) -> int:
        cache = [None]*(n+1)
    
        cache[0] = 1

        for k in range(1, n+1):
            ans = 0
            for i in range(1, k+1):
                ans += cache[i-1]*cache[k-i]
            cache[k] = ans

        return cache[n]
```


```c=
int numTrees(int n){
    int* cache = malloc(sizeof(int)*(n+1));
    cache[0] = 1;
    for (int k = 1; k <= n; k++){
        int ans = 0;
        for (int i = 1; i <= k; i++){
            ans += cache[i-1] * cache[k-i];
        }
        cache[k] = ans;
    }
    int res = cache[n];
    free(cache);
    return res;
}
```