Leetcode 六月挑戰
===
[TOC]
## Week 1
### Invert Binary Tree
```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
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
```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
#### 法一 :
```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
```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
```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
```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
```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
```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
```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)
```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
```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
```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
#### Unique Binary Search Trees
```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;
}
```
Sign in with Wallet
Connect another wallet