# LandIsland-LeetCode+English Project
## [Recursion]2021.12.05 21:00 Host: David
### [347. Top K Frequent Elements](https://leetcode.com/problems/powx-n/)(David)
SOL 1:
```js=
var myPow = function(x, n) {
if (n == 0){
return 1;
}
if (n == 1){
return x;
}
if (n == -1) {
return 1/x;
}
if(n%2 == 0){
return myPow(x*x, n/2) ;
}else{
return x * myPow(x*x, (n-1)/2) ;
}
};
```
## [HashMap]2021.11.21 21:00 Host: JinWei
### [347. Top K Frequent Elements](https://leetcode.com/problems/top-k-frequent-elements)(Jinwei)
SOL 1: JW
```js=
function topKFrequent(nums, k) {
let map = new Map();
nums.forEach((eachNum) => {
if (map.get(eachNum)) {
const numAmount = map.get(eachNum);
map.set(eachNum, numAmount + 1);
} else {
map.set(eachNum, 1);
}
});
// sort
const sortMap = new Map([...map.entries()].sort((a, b) => b[1] - a[1]));
const finalArr = [];
sortMap.forEach((val, key) => {
let idx = 0;
if (idx < k) {
finalArr.push(key);
idx++;
}
});
return finalArr;
}
```
SOL2 : Online
```js=
var topKFrequent = function(nums, k) {
const count = new Map()
const bucket = Array.from({ length: nums.length + 1 }, _ => [])
for (const n of nums) {
count.set(n, (count.get(n) || 0) + 1)
}
for (const entry of count.entries()) {
const [n, freq] = entry
bucket[freq].push(n)
}
return bucket.flat().slice(-k)
};
```
### [1282. Group the People Given the Group Size They Belong To](https://leetcode.com/problems/group-the-people-given-the-group-size-they-belong-to/)(Even Pan)
#### solution 1 (Even)
```python=
class Solution:
def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
self.room = {} # key: seat, value: List[list]
for idx, menber_group in enumerate(groupSizes):
self.check_room_seat(menber_group, idx)
result = []
for i in self.room.values():
result.extend(i)
return result
def check_room_seat(self, seat, idx):
self.room.setdefault(seat, [[]])
if len(self.room.get(seat)[-1]) < seat:
self.room[seat][-1].append(idx)
else:
self.create_new_room(seat, idx)
def create_new_room(self, seat, idx):
self.room[seat].append([idx])
```
#### solution 2 source:[ online](https://leetcode.com/problems/group-the-people-given-the-group-size-they-belong-to/discuss/448447/Python-Simple.-Hashmap.-With-comments-(beats-99))
```python=
class Solution:
def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
'''
Example input-> groupSizes=[3,3,3,3,3,1,3]
Store in a dictionary[i] the list of indices of input array groupSizes that belong to a group size i
'''
_dict_=collections.defaultdict(list)
for idx,i in enumerate(groupSizes):
_dict_[i].append(idx)
'''
print (_dict_)-> defaultdict(<class 'list'>, {3: [0, 1, 2, 3, 4, 6], 1: [5]})
_dict_[i] has list of indices of input array groupSizes that belong to groupsize i
Next, create lists of size i parsing through _dict_[i], and append them to answer[].
Further since a solution is guaranteed to exist, len(_dict_[i])/i will always be perfectly divisible.
Infact, len(_dict_[i])/i gives exactly the number of groups of size i
'''
answer=[]
for key, lst in _dict_.items():
for idx in range(0, len(lst), key):
answer.append(lst[idx:idx + key])
return (answer)
```
## [Array]2021.11.14 21:00 Host: Rosy
### [807. Max Increase to Keep City Skyline](https://leetcode.com/problems/max-increase-to-keep-city-skyline/)(Even Pan)
```python=
# slow solution
# time = O(n^2)
# space = O(n)
class Solution:
def maxIncreaseKeepingSkyline(self, grid: List[List[int]]) -> int:
grid_copy = [[0]*len(grid) for _ in range(len(grid[0]))]
additional_level = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
max_x = max(grid[i])
max_y = max([i[j] for i in grid])
# print('x: ', max_x, ';y: ', max_y)
grid_copy[i][j] = min(max_x, max_y)
additional_level += grid_copy[i][j] - grid[i][j]
print(grid_copy)
print(grid)
return additional_level
# fast solution
# time = O(n)
# space = O(log(n))
class Solution:
def maxIncreaseKeepingSkyline(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
ops = 0
max1=[]
max2=[]
# print(zip(*grid))
# print([i for i in zip(*grid)])
for i in grid:
max1.append(max(i))
print(max1)
for j in list(zip(*grid)):
max2.append(max(j))
print(max2)
for i1, val1 in enumerate(max1):
for i2, val2 in enumerate(max2):
ops+=(min(val1, val2)-grid[i1][i2])
return ops
```
## [Hash Table]2021.11.7 21:00 Host: Iris
### [480. Sliding Window Median](https://leetcode.com/problems/sliding-window-median/)(Even Pan)
```python=
class Solution:
def median(self, nums):
""" calculate median in a list of sorted numbers
Argument:
nums: list, list of numbers which is sorted
Return:
return median number if it list have odd length
else return average of two median numbers
"""
mid = len(nums) // 2
if len(nums) % 2:
return nums[mid]
return (nums[mid-1] + nums[mid]) / 2
def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:
if not nums:
return []
window = sorted(nums[:k-1])
result = []
for idx, n in enumerate(nums[(k-1):]):
self.insert_new_num(window,n)
result.append(self.median(window))
self.remove_old_num(window, nums[idx])
return result
@staticmethod
def find_insert_loc(li , num):
""" find the index for num in a sorted list
Argument:
li: list, sorted list to be insert
num: int, num to be insert
Return:
lo: int, index for insert in the list
Example:
case1: [1,2,3,4], 2 -> ([1,2,(2),3,3]) ... 2
case2: [1,4,5,7,10], 8 -> ([1,4,5,7,8,10]) ... 4
case3: [1,4,5,7,10], 6 -> ([1,4,5,6,7,10]) ... 3
psudo
mid = 2, << lo= 2+1
mid = (3+5) =4 num[min] = 10 >> hi = 4
mid = 3 num[3] = 7 >> hi = 3 , hi == lo break
case 3 output example:
mid: 2 , li[mid]: 5
0 5 2 5
update lo 0 to 3
mid: 4 , li[mid]: 10
3 5 4 10
update hi 5 to 4
mid: 3 , li[mid]: 7
3 4 3 7
update hi 4 to 3
3
"""
hi = len(li)
lo = 0
while lo < hi:
mid = (lo + hi) // 2
# print('mid: ', mid, ', li[mid]: ', li[mid])
if num < li[mid]:
# print(lo, hi, mid, li[mid])
# print(f'update hi {hi} to {mid}')
hi = mid
else:
# print(lo, hi, mid, li[mid])
# print(f'update lo {lo} to {mid + 1}')
lo = mid + 1
return lo
def insert_new_num(self, li, num):
""" insert num in the sorted list
Arguments:
li: list, input sorted list
num: int, input number
Example:
case1: ([1,2,3,4], 2) -> [1,2,(2),3,3]
case2: ([1,4,5,7,10], 8) -> [1,4,5,7,(8),10]
case3: ([1,4,5,7,10], 6) -> [1,4,5,(6),7,10]
"""
loc = self.find_insert_loc(li, num)
li.insert(loc, num)
def remove_old_num(self, li, num):
""" remove num in sorted list
Arguments:
li: list, input sorted list
num: int, number to be remove
Example:
case1: ([1,2,2,3,3], 2) -> [1,2,3,3]
case2: ([1,4,5,7,8,10], 8) -> [1,4,5,7,10]
case3: ([1,4,5,6,7,10], 6) -> [1,4,5,7,10]
"""
loc = self.find_insert_loc(li, num) - 1
del li[loc]
```
### [1817. Finding the Users Active Minutes](https://leetcode.com/problems/finding-the-users-active-minutes/) (Iris)
- Solution1
```javascript=
var findingUsersActiveMinutes = function(logs, k) {
const m = new Map();
const result = new Array(k).fill(0)
logs.forEach((arr)=>{
const id = arr[0];
const minute = arr[1];
if(!m.has(id)){
m.set(id,[minute])
}else{
const prev = m.get(id);
if(!prev.includes(minute)){
// arr.includes time complexity = O(n)
prev.push(minute);
m.set(id,prev);
}
}
})
for(let i of m){
const len = i[1].length;
result[len-1]++;
}
return result;
};
//Space Complexity = O(n + k)
```
- Solution2
use set and conditional operator to polish
```javascript=
var findingUsersActiveMinutes = function(logs, k) {
const map = new Map();
logs.forEach(([id, time]) => {
const set = map.has(id) ? map.get(id) : new Set();
set.add(time);
map.set(id, set);
})
const result = new Array(k).fill(0);
map.forEach((value, key) => {
if(value.size <= k) {
result[value.size - 1] ++;
}
})
return result;
};
```
## [Dynamic Prog.]2021.10.31 9:00 Host: Aaron
### [96. Unique Binary Search Tree](https://leetcode.com/problems/unique-binary-search-trees/submissions/)
G(n) the number of unique BST for a sequence of length n
F(i,n): the number of unique BST, where the number i is the root of BST, and the sequence ranges from 1 to n.
G(n)= F(1,n)+F(2,n)+.....F(n,n)
G(3)= F(1,3)+F(2,3)+F(3,3)
G(0)=1, G(1)=1
F(3,7)=G(2)*G(4) [1,2] [4,5,6,7]
F(i,n)=G(i-1)*G(n-i) 1 <= i <= n
G(n)=G(0)*G(n-1)+G(1)*G(n-2)....G(n-1)*G(0)
- Solution 1
Explaination:https://leetcode.com/problems/unique-binary-search-trees/discuss/31666/DP-Solution-in-6-lines-with-explanation.-F(i-n)-G(i-1)-*-G(n-i)
```python=
class Solution(object):
def numTrees(self, n):
"""
:type n: int
:rtype: int
"""
g={}
for i in range(n+1):
g[i]=0
g[0]=1
g[1]=1
for i in range(2,(n+1)):
for j in range(1,(i+1)):
g[i]+=g[j-1]*g[i-j]
return g[n]
```
range(1,5) 1 2 3 4
---
### [877. Stone Game](https://leetcode.com/problems/stone-game/) (Tim)
- Solution 1
```cpp=
class Solution{
public:
bool stoneGame(vector<int>& piles){
int n = piles.size();
// dparray[i][j] represents # of stones which Alice has
// more than Bob when playing game from piles i to j.
int dparray[n][n];
// initialize dparray with zero
memset(dparray, 0, sizeof(dparray));
// initialize last step (only 1 pile left)
for(int i=0; i<n; i++) dparray[i][i] = -piles[i];
// fill out the dparray
for(int i=0; i<n; i++){
for(int j=i+1; j<n; j++){
if((i+j)%2==0){
// Alice's turn, try to maximise final result
dparray[i][j] = max(piles[i]+dparray[i+1][j],
piles[j]+dparray[i][j-1]);
} else{
// Bob's turn, try to minimise final result
dparray[i][j] = min(piles[i]+dparray[i+1][j],
piles[j]+dparray[i][j-1]);
}
}
}
return dparray[0][n-1];
}
}
```
- Solution 2
```cpp=
class Solution{
public:
bool stoneGame(vector<int>& piles){
// since the first one to play the game can always
// take all the odd or even piles, he/she can easily
// sum up and choose the subset with more stones
// and win.
return true;
}
}
```
---
### [581. Coin Change 2](https://leetcode.com/problems/coin-change-2/) (Jinwei)
---
### [64. Minimum Path Sum](https://leetcode.com/problems/minimum-path-sum/) (Rosy)
---
### [119. Pascal's Triangle II](https://leetcode.com/problems/pascals-triangle-ii/) (Jing)
---
### [22. Generate Parentheses](https://leetcode.com/problems/generate-parentheses/) (Aaron)
---
### [338. Counting Bits](https://leetcode.com/problems/counting-bits/) (Iris)
---
## [Array]2021.10.24 12:00 Host:Iris
### [78. Subsets](https://leetcode.com/problems/subsets/solution/)(Iris)
- Solution 1 (cascading)
```javascript=
var subsets = function(nums) {
let output = [[]]
for (num of nums) {
output.forEach((el)=>{
const newArr = [...el, num]
output.push(el)
}
)
}
return output
};
```
- Solution 2 (Backtracking)recursion
```javascript=
const subsets = function(nums) {
const output = [];
function backtrack(start, list){
if(start > nums.length) return;
output.push([...list])
for(let idx = start; idx < nums.length; idx++){
list.push(nums[idx])
backtrack(idx+1, list)
list.pop()
}
}
backtrack(0,[])
return output
};
```
## [Array]2021.10.24 21:00 Host:Even
### [68. Text Justification](https://leetcode.com/problems/text-justification/)(Even)
```py
from typing import List
class Solution:
def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
print(self.better_spacer(room=3, count_words=3))
self.maxWidth = maxWidth
result = []
new_line = []
current_loading = 0
all_length = len(words)
for i, word in enumerate(words):
word_length = len(word)
if current_loading + word_length > maxWidth:
print('need next line')
result.append(new_line.copy())
new_line = []
current_loading = 0
new_line.append(word)
current_loading += word_length + 1
print('newline = ', new_line, 'current loading: ',current_loading)
if i == all_length - 1:
result.append(new_line.copy())
result = self.format_result(result)
return result
def format_result(self, result: List[List[str]]) -> List[str]:
last_line = result[-1]
standard_lines = result[:-1]
formated_lines = []
for line in standard_lines:
formated_lines.append(self.justify_space(line))
formated_lines.append(self.justify_space(last_line, True))
return formated_lines
def justify_space(self, line: list, is_last: bool=False) -> str:
count_words = len(line)
room = self.maxWidth - sum(len(word) for word in line)
if is_last:
formated_line = " ".join(line) + " " * (room - (count_words - 1))
else:
# # use self.better_spacer
space_list = self.better_spacer(room, count_words)
formated_line = self.format_spaces(space_list, line, count_words)
# old method 如果空格不能整除，會失效，引入better spacer 跟 format space解決
# spaces = round(room/(count_words - 1))
# formated_line = (" "*spaces).join(line)
return formated_line
@staticmethod
def better_spacer(room, count_words) -> list:
# 最後一格只有餘數個空格
# aaabb floor(room/count_words) = b , n個a , room%count_words
if count_words == 1:
return [room]
space_list = [floor(room/(count_words - 1))] * (count_words - 1)
for i in range(room%(count_words - 1)):
space_list[i] += 1
return space_list
@staticmethod
def format_spaces(space_list, line, count_words):
formated_line = line[0]
for i in range(len(space_list)):
formated_line += " " * space_list[i]
try:
formated_line += line[i+1]
except Exception:
pass
return formated_line
```
## [Linked list]2021.10.17 21:00 Host: David
### [142. Linked List Cycle II](https://leetcode.com/problems/linked-list-cycle-ii/) (David)
- Solution 1
```javascript=
var detectCycle = function(head) {
let node_pointers = []
let node = head
while(1){
if(node_pointers.indexOf(node) !== -1){
return node
}
if(node == null){
return null
}
node_pointers.push(node)
node = node.next
}
}
```
- Solution 2
(https://medium.com/@ChYuan/leetcode-no-142-linked-list-cycle-ii-%E5%BF%83%E5%BE%97-medium-c5b53dcca804)
```javascript=
var detectCycle = function(head) {
let dummy = new ListNode();
dummy.next = head;
let node_slow = dummy;
let node_fast = dummy;
while(1){
if( node_fast == null){
return null
}
if( node_fast.next == null){
return null
}
node_slow = node_slow.next;
node_fast = node_fast.next.next;
if (node_slow == node_fast){
node_slow = dummy;
while(1){
node_slow = node_slow.next
node_fast = node_fast.next
if(node_slow == node_fast){
return node_slow
}
}
}
}
};
```
Comment
Jinwei: Super Brilliant! 👍
---
### [83. Remove Duplicates from Sorted List](https://leetcode.com/problems/remove-duplicates-from-sorted-list/) (Jinwei)
<a href="shorturl.at/givLV">
Visualization Process</a>
```javascript=
var deleteDuplicates = function(head) {
let cur = head;
while (cur && cur.next) {
let nextNextNode = cur.next.next;
if (cur.val === cur.next.val) {
cur.next.next = null;
cur.next = nextNextNode;
} else {
cur = cur.next;
}
}
return head;
};
```
---
### [234. Palindrome Linked List](https://leetcode.com/problems/palindrome-linked-list/) (Aaron)
- Solution 1
```javascript=
var isPalindrome = function(head) {
var sequence = "";
var reverse = "";
while(head != null){
sequence += head.val;
reverse = head.val + reverse;
head = head.next;
}
return sequence == reverse;
};
// space complexity: O(n)
// time complexity: O(n)
```
- Solution 2
```javascript=
var isPalindrome = function(head) {
var middle = findMiddle(head);
var rNode = reverseNode(middle);
while(rNode != null){
if(head.val != rNode.val) {
return false;
}
head = head.next;
rNode = rNode.next;
}
return true;
function findMiddle(node){
var fast = node;
var slow = node;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
function reverseNode(node){
if(node==null || node.next==null) return node;
var prev = null;
var cur = node;
while(cur != null){
var temp = cur;
cur = cur.next;
temp.next = prev;
prev = temp;
}
return prev;
}
};
// space complexity: O(1)
// time complexity: O(n)
```
---
## [Array]2021.10.10 21:00 Host: Iris
### [134. Gas Station](https://leetcode.com/problems/gas-station/) (Iris)
- Solution1
```javascript=
var canCompleteCircuit = function(gas, cost) {
let start = 0, tank = 0, total = 0;
// best option = a gas station that allows us to arrive the next station
// find a optimal strat point
for(let i = 0; i < gas.length; i++) {
const consume = gas[i] - cost[i];
tank += consume;
if(tank < 0) {
tank = 0;
start = i + 1;
}
// tank > 0 = find a start station => start will stay in that index
// to calculate if we can complete the curcuit
total += consume;
}
return total < 0 ? -1 : start;
};
```
- Solution2
```
var canCompleteCircuit = function(gas, cost) {
.....
};
```
Sign in with Wallet
Connect another wallet