# Leetcode 032421~052621
###### tags: `刷題`
***
* 題目被分類在某個類別(例如Bit manipulation)不代表那真的是最佳解。
***
## 032421
### #1475. Final Prices With a Special Discount in a Shop
#### first solution:
```cpp=
class Solution:
def finalPrices(self, prices: List[int]) -> List[int]:
discount = []
visited = 0
for x in range(len(prices)):
visited = 0
for y in range(x+1,len(prices)):
if prices[y] <= prices[x]:
discount.append(prices[x] - prices[y])
visited = 1
break
if visited == 0:
discount.append(prices[x])
return discount
```
- Analysis:
- time complexity:
- Best (e.g. [1,2,3,4,5]) $O(n)$
- Worst (e.g. [5,4,3,2,1]) $O(n^2)$
- Space complexity:
- $O(n)$
- Regurgitate: 首先，可以在原list上修改，不必多創建一個，這也可以順便省略判斷變數visited (要注意語言特性，如果是pass by value)
#### HuaHua
###### tags: monotonic_stack
```cpp=
class Solution:
def finalPrices(self, prices: List[int]) -> List[int]:
stack = []
for x in range(len(prices)):
while stack and prices[x] <= prices[stack[-1]]:
prices[stack[-1]] -= prices[x]
stack.pop()
stack.append(x)
return prices
```
## 032621
### #108. Convert Sorted Array to Binary Search Tree
#### first solution
直接看花花。2天後憑印象寫出。
```cpp=
import math
# 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 sortedArrayToBST(self, nums: List[int]) -> TreeNode:
def rc_build_tree(nums, l, r):
if l > r :
return None
mid = floor((l + r) / 2)
n = TreeNode()
n.val = nums[mid]
n.left = rc_build_tree(nums, l, mid - 1)
n.right = rc_build_tree(nums, mid + 1, r)
return n
return rc_build_tree(nums, 0, len(nums)-1)
```
- Analysis:
- time complexity:
- 因為題目給的list已經排好序。所以是固定$O(log(n))$
- space complexity:
- 會建立n個TreeNode，故為$O(n)$
### #78. Subsets
#### first solution
直接看花花。
```cpp=
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
subset = []
def dfs(s, n, cur):
if len(cur) == n:
subset.append([]+cur)
return
for i in range(s, len(nums)):
cur.append(nums[i])
dfs(i+1, n, cur)
cur.pop()
for i in range(len(nums)+1):
dfs(0, i, [])
return subset
```
###### tags: 坑
```cpp=
c = []
d_int = 9
d_list = [9]
c.append(d_int)
c.append(d_list)
d_list.append(10)
d_int = 10
''' c == [9, [9, 10]] '''
```
* Analysis:
* Time: $O(n*2^n)$
*
* Space: $O(n)$
## 033021
### #78. Subsets
- 一樣直接花花
- second solution: Bitwise manipulation
```python=
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
nsize = len(nums)
return [[nums[j] for j in range(nsize) if (1 << j & i)] for i in range(1<<nsize)]
'''verbose implementation
nsize = len(nums)
ans = []
for i in range(1<<nsize):
# e.g. nsize == 10 -> 0~1023
cur = []
for j in range(nsize):
if (i & (1 << j)):
cur.append(nums[j])
ans.append(cur.copy())
return ans
'''
```
* Analysis:
* time: $O(n*2^n)$
* space:$O(1)$
### #1239. Maximum Length of a Concatenated String with Unique Characters
#### first try: (s/p refactoring)
```python=
class Solution:
def maxLength(self, arr: List[str]) -> int:
largest, nsize = 0, len(arr) #e.g. nsize = 10
sub = set() #later, this act as repetition detector
for i in range(1 << nsize): #number of possible combinations:1024 e.g. 1010110000, 0010010110
cur = [] #current set to be test
for j in range(nsize):
if (i & (1 << j)): #j is one hot bit mask
cur.append(arr[j]) # append the element to cur ##actually we can abort the instance here if already unqualified
for list_ele in cur: # TEST cur
for ele in list_ele:
if ele in sub: # recurrence found: break and restart the process
sub.clear()
break
else: #add element to our set
sub.add(ele)
if len(sub) > largest: #update largest
largest = len(sub)
sub.clear()
return largest
```
##### Analysis:
- Time: $O(N*2^N)$
- Space: $O(N)$ (?)
- 看的出來，廢到笑。基本上就是Brute force。但因為數據規模很小，所以可以過。
- by HuaHua: $N<=16$ 說明$O(2^n)$是差不多的；$O(N!)$這個規模仍太慢、而polynomial time不會給這麼小。
#### HuaHua
- 目前是超時，明天再試試看。或許是用了遞歸的原因。
## 033121
### #1239. Maximum Length of a Concatenated String with Unique Characters
#### Second try
嘗試減少冗餘計算，但時間反而稍微變爛。
明天會再試試別的方法。
```python=
class Solution:
def maxLength(self, arr: List[str]) -> int:
tmp, largest, mask, rp_set = [], 0, 0, set()
for a in arr: # filter unqualified element i.e.(a)
for qa in a:
mask |= 1 << (ord(qa) - ord('a'))
if bin(mask).count('1') != len(a):
mask = 0
continue
tmp.append(a)
mask = 0
#tmp is now arr, deprived of unqualified element.
for i in range(1 << len(tmp)):
n_digit, copy_i = 0, i
while(copy_i):
copy_i >>= 1
n_digit += 1
for j in range(n_digit):
if i & (1 << j):
for alpha in tmp[j]:
if alpha in rp_set:
rp_set.clear()
break
rp_set.add(alpha)
if len(rp_set) > largest:
largest = len(rp_set)
rp_set.clear()
return largest
```
##### Analysis
- 跟昨天的一樣。僅常數等級的改變。
#### Third try
網友解
```python=
class Solution:
def maxLength(self, arr: List[str]) -> int:
ans = []
maxlen = 0
for a in arr:
if len(set(a)) < len(a):
continue
aset = set(a)
ans.append(aset)
for iset in ans:
if iset & aset:
continue
ans.append(aset | iset)
for s in ans:
if maxlen < len(s):
maxlen = len(s)
return maxlen
```
##### Analysis
- Time:
- Space:
#### 改網友解:
set()操作改用bitwise operation
```python=
class Solution:
def maxLength(self, arr: List[str]) -> int:
ans = []
maxlen = 0
for a in arr:
flip = 0
for i in a:
flip |= 1 << (ord(i) - ord('a'))
if bin(flip).count('1') < len(a):
continue
ans.append(flip)
for flop in ans:
if flip & flop:
continue
ans.append(flip | flop)
for s in ans:
if maxlen < bin(s).count('1'):
maxlen = bin(s).count('1')
return maxlen
```
### #187. Repeated DNA Sequences
#### first try
```python=
class Solution:
def findRepeatedDnaSequences(self, s: str) -> List[str]:
set_frag, repeated_set = set(), set()
for sub in range(len(s)):
if s[sub : sub + 10] not in set_frag:
set_frag.add(s[sub : sub + 10])
else:
repeated_set.add(s[sub : sub + 10])
return list(repeated_set)
```
##### Analysis
- Time: $O(N)$
- Space: $O(N)$
##### 做法:
用sliding window的方式掃過DNA，再用set看有沒有重複，有的話加到另一個set就可以了。
## 040121
### #393. UTF-8 Validation
#### first try
```python=
class Solution:
def validUtf8(self, data: List[int]) -> bool:
byte_len = 0
for d in data:
if byte_len == 0: #head
#check head and set byte_len by 0123
# if illegal head:continue byte_len = 0
if not d & (1 << 7): #1 byte cide
continue
if not d & (1 << 5) and d & (1 << 6):
byte_len = 1
continue
elif not d & (1 << 4) and d & (1 << 6) and d & (1 << 5):
byte_len = 2
continue
elif not d & (1 << 3) and d & (1 << 6) and d & (1 << 5) and d & (1 << 4):
byte_len = 3
continue
return False
else: #body: behave according to bit_len, bit_len--
if d & (1 << 7) and d ^ (1 << 6): #valid
byte_len -= 1
continue
return False
return True if byte_len == 0 else False
```
- 一開始錯誤很多次，後來發現都是判斷句語意跟預期不符。結果就變成現在這樣。可以work但有點醜，希望再研究看看怎樣寫比較精簡。
##### Analysis
- Time:$O(N)$
- Space:$O(1)$ 因為沒有copy
## 040221
### #547. Number of Provinces
無向圖找SCC，使用DFS
有向圖的話就要用Kosaraju
#### first try
- 題目給adjacency matrix，我看著不順眼，所以先轉成adjacency set
- 接著用~~BFS~~DFS(下面程式碼使用stack)
```python=
class Solution:
def findCircleNum(self, isConnected: List[List[int]]) -> int:
graph_size = len(isConnected)
if not graph_size: return 0
count_prov = 1
vertex_set = set([_ for _ in range(graph_size)])
adj_list = {}
stack = []
for i in range(graph_size):
for j in range(graph_size):
if isConnected[i][j]:
if i in adj_list.keys():
adj_list[i].add(j)
else:
adj_list[i] = set([j])
focus = vertex_set.pop()
stack.append(focus)
while vertex_set:
for neighbor in adj_list[focus]: #vertex_set: not seen yet
if neighbor in vertex_set:
stack.append(neighbor)
vertex_set.remove(neighbor)
if stack:
focus = stack.pop()
continue
count_prov += 1
if vertex_set:
focus = vertex_set.pop()
stack.append(focus)
return count_prov
'''
undirected graph
n by n matrix provided;
self connected;
M[i][j] == M[j][i]
'''
```
##### Analysis
- Time:$O(V^2)$
- 若給的是adjancy list就可縮減為$O(V+E)$
- Space:$O(V+E)$
### #323. Number of Connected Components in an Undirected Graph
跟547完全一樣的做法。不過因為他沒有自連邊，所以造成原本的實作不能work。
費了一些心力調整。
我希望再換其他的方法試看看。
#### first try
```python=
class Solution:
def countComponents(self, n: int, edges: List[List[int]]) -> int:
if not n:
return 0
num_comp = 1
v_edges = {}
stack = []
node_set = set([_ for _ in range(n)])
for e in edges:
if e[0] in v_edges.keys():
v_edges[e[0]].add(e[1])
else:
v_edges[e[0]] = set([e[1]])
if e[1] in v_edges.keys():
v_edges[e[1]].add(e[0])
else:
v_edges[e[1]] = set([e[0]])
for k in range(n):
if k in v_edges.keys():
v_edges[k].add(k)
else:
v_edges[k] = set([k])
focus = node_set.pop()
stack.append(focus)
while node_set:
for x in v_edges[focus]:
if x in node_set:
stack.append(x)
node_set.remove(x)
if stack:
focus = stack.pop()
continue
'''single group exhausted'''
num_comp += 1
if node_set:
focus = node_set.pop()
stack.append(focus)
return num_comp
```
## 041221
### #657. Robot Return to Origin
這題沒什麼好寫的，就太久沒寫題，回復一下手感找信心。
$O(n)$/$O(1)$
```python=
class Solution:
import collections
def judgeCircle(self, moves: str) -> bool:
m_nums = collections.Counter(moves)
if m_nums['U'] == m_nums['D'] and m_nums['L'] == m_nums['R']:
return True
return False
```
### #323. Number of Connected Components in an Undirected Graph
LC論壇裡的UnionFind實作。其實這個沒有很難，應該要馬上可以寫出來。結果有人連抄作業都會抄錯，呵呵
```python=
class Solution:
def countComponents(self, n: int, edges: List[List[int]]) -> int:
uf = UnionFind(n)
for u, v in edges:
uf.union(u,v)
return uf.count
class UnionFind:
def __init__(self, n):
self.parent = [x for x in range(n)]
self.count = n
self.rank = [0] * n
def union(self, x, y):
x_root, y_root = self.find(x), self.find(y)
if x_root != y_root:
if self.rank[x_root] > self.rank[y_root]:
self.parent[y_root] = x_root
elif self.rank[x_root] < self.rank[y_root]:
self.parent[x_root] = y_root
else:
self.parent[y_root] = x_root
self.rank[x_root] += 1
self.count -= 1
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
```
#### Analysis:
- Time:$O(α(N))$
### #210. Course Schedule II
#### first try:
- 試了很久但並不順利。其實是已經有抓到點，但誤以為跟SCC有關，多很多不必要的代碼，導致無法正確完成。
#### HuaHua:
```python=
class Solution:
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
prq = [x[::-1] for x in prerequisites]
nc = numCourses
condition = [0] * nc
ans = []
e_dict = {}
def dfs(v):
if condition[v] == 1:
return True
if condition[v] == 2:
return False
condition[v] = 1
if v not in e_dict.keys():
condition[v] = 2
ans.append(v)
return
for e in e_dict[v]:
if dfs(e):
return True
condition[v] = 2
ans.append(v)
return False
for p in prq:
if p[0] in e_dict.keys():
e_dict[p[0]].append(p[1])
else:
e_dict[p[0]] = [p[1]]
for i in range(nc):
if dfs(i) == True:
return {}
ans = ans[::-1]
return ans
```
此處DFS應用的要點在於，要稍微變化，將原本僅記錄"完成"，改為分成"訪問中"與"訪問完成"兩種狀態。
如果訪問中碰到"訪問中"的節點，說明有環。(因為DFS本身特性，必定如此)
##### Analysis:
- Time:$O(V+E)$ / worst:$O(V^2)$
- Space:$O(V+E)$
這題不需要用到[這篇文章](https://alrightchiu.github.io/SecondRound/graph-li-yong-dfsxun-zhao-dagde-topological-sorttuo-pu-pai-xu.html)的內容
### #231. Power of Two
嗯，又來洗題目數了。
```python=
class Solution:
def isPowerOfTwo(self, n: int) -> bool:
c = 1
for i in range(32):
if c == n: return True
elif c > n: return False
c<<=1
```
### #207. Course Schedule
窮人版210
應該先寫這題=3=
剛剛才寫過，這題只花了2首歌的時間
```python=
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
prq = [x[::-1] for x in prerequisites]
nc = numCourses
e_course = {}
condition = [0] * nc
for p in prq:
if p[0] in e_course.keys():
e_course[p[0]].append(p[1])
else:
e_course[p[0]] = [p[1]]
def dfs(v):
if condition[v] == 2:
return True
elif condition[v] == 1:
return False
if v not in e_course.keys():
condition[v] == 2
return True
condition[v] = 1
for e in e_course[v]:
if not dfs(e): return False
condition[v] = 2
return True
for i in range(nc):
if not dfs(i): return False
return True
```
##### Analysis:
- Time:$O(V+E)$ / worst:$O(V^2)$
- Space:$O(V+E)$
應該跟210一樣，我直接複製貼上的
```c=
char letters[26] = {0}; //Just a simple array to hold the number of times we've seen a letter
while (*str ... // This is false if you get to the null terminator at the end of the string because '0' is false.
... && !letters[(*str | ' ') - 'a']++) //This checks to see if the letter has already been seen, and increments the count for that letter
// Breaking down (*str | ' ') - 'a': The value of 'A' is 65, the value of 'a' is 97.
//So to get an upper case letter we need to add 32, but we only want to do that if we ARE an uppercase letter (we don't want to add 32 to 'q', but we do want to add 32 to 'Q'.
// The | operator does a bitwise OR, in this case with the value of ' ' which is 32. Thus 'A' is 0100 0001 ' ' is 0010 0000 and 'a' is 0110 0001 which is precisely what taking the bitwise OR of 'A' and ' ' gives us.
// The - 'a' is because we want to index into letters starting with 'a' at 0.
++str; //Increment the pointer
return !*str; // This checks to see if we reached the end of the string with the null byte. If we did, we know there were no duplicates. If we didn't, we know that the while loop aborted because of the other condition (i.e. it found a duplicate). So if zero return true, if not return false.
```
## 041621
### #444.Sequence Reconstruction
#### first try
- 基本的邏輯不難懂，但也許是我的判斷方法不夠好，edge case太多了
- 從結果看來，這個實作很爛。
```python=
class Solution:
def sequenceReconstruction(self, org: List[int], seqs: List[List[int]]) -> bool:
pairs = set()
if not org or not seqs:
return False
for s in seqs:
if len(set(s)) != len(s):
return False
for s in seqs:
if len(s) > len(org):
return False
for s in seqs:
for i in range(len(s)-1):
pairs.add((s[i], s[i+1]))
for i in range(len(org)-1):
if (org[i], org[i+1]) not in pairs:
return False
for s in seqs:
cut, flag = 0, False
for i in range(len(s)):
if cut >= len(org):
return False
for j in range(cut, len(org)):
if s[i] == org[j]:
cut = j+1
flag = True
break
if not flag:
return False
flag = False
return True
```
#### 網友解:
- Same algorithm but more pythonic than mine
```python=
class Solution:
def sequenceReconstruction(self, org: List[int], seqs: List[List[int]]) -> bool:
index = {num: i for i, num in enumerate([None] + org)}
pairs = set(zip([None] + org, org))
for s in seqs:
for a, b in zip([None] + s, s):
if index[a] >= index.get(b, 0):
return False
pairs.discard((a, b))
return not pairs
```
### #133. Clone Graph
#### 網友解
- 也許是狀況不好，我想半天還是不確定題目的意思。所以看了網友解
```python=
"""
# Definition for a Node.
class Node:
def __init__(self, val = 0, neighbors = None):
self.val = val
self.neighbors = neighbors if neighbors is not None else []
"""
class Solution:
def cloneGraph(self, node: 'Node') -> 'Node':
if not node:
return node
dp_copy_n = Node(node.val, [])
dic = {node:dp_copy_n}
self.dfs(node, dic)
return dp_copy_n
def dfs(self, node, dic):
for n in node.neighbors:
if n not in dic:
new_n = Node(n.val, [])
dic[n] = new_n
dic[node].neighbors.append(new_n)
self.dfs(n, dic)
else:
dic[node].neighbors.append(dic[n])
```
- 題目要求建一個原圖的deep copy，關鍵只是要遍歷整個圖一遍，要用BFS, DFS, Dijkstra, Bellman-Ford....都可以。最重要的是要重建一個物件(C++的new())
- 已完成解法1快速重現
- 之後目標:
- 解法1延遲重現
- 解法2, 3，包括BFS、DFS iteration ver.
#### Analysis: 即是DFS/BFS的複雜度
- Time:$O(V+E)$
- Space:$O(v+E)$
### #3. Longest Substring Without Repeating Characters
#### first try:
- 暴力解$O(N^2)$，時間只有PR19是意料之中。
- 不過我只花了5分鐘
- 有花花影片
```python=
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
def longest_substring(s):
unique = set()
longest_unique = 1
for c in range(len(s)):
for sub in s[c:]:
if sub not in unique:
unique.add(sub)
continue
else:
if len(unique) > longest_unique:
longest_unique = len(unique)
unique.clear()
break
return longest_unique
return longest_substring(s) if s else 0
```
## 042221
### #3. Longest Substring Without Repeating Characters
#### 花花/網友$O(N)$解
運用記錄各個字元最後出現位置的技巧讓，讓整個字串只須被看過一次即可。
而我原本的方法只使用set紀錄是否出現，卻沒有紀錄出現的位置，以至於每次都需要掃描剩餘的substring，
總共需要檢視 n^2 / 2次，也就是O(N^2)
```python=
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
if not s: return 0
unique = {}
resume, maxL = 0, 0
for i in range(len(s)):
if s[i] in unique and resume <= unique[s[i]]:
resume = unique[s[i]] + 1
else:
maxL = max(maxL, i - resume + 1)
unique[s[i]] = i
return maxL
```
### #989. Add to Array-Form of Integer
#### first try:
約22分鐘
雖然還可以再refactoring一下，不過顯然已是最佳解
```python=
"""把int轉換成array再做運算，注意進位的部分，要預留一位(在尾端添一個0)，
最後如果沒有用到再pop掉"""
class Solution:
def addToArrayForm(self, num: List[int], k: int) -> List[int]:
def int_to_array(self, n):
arr = []
while n:
arr.append(n % 10)
n //= 10
return arr[::-1]
k_arr = int_to_array(self, k)
d = abs(len(k_arr) - len(num))
k_arr, num = k_arr[::-1], num[::-1]
if len(num) > len(k_arr):
k_arr += [0]*d
elif len(k_arr) > len(num):
num += [0]*d
sums = [x+y for x, y in zip(k_arr, num)]
sums.append(0)
for i in range(len(sums)):
if sums[i] > 9:
sums[i+1] += 1
sums[i] -= 10
if not sums[-1]:
sums.pop()
return sums[::-1]
```
##### Analysis
- Time: $O(L)$
- Space: $$
#### first try-2:
```python=
'''很有趣的是，我本來想說那從array轉成int也可以，而且時間應該差不多，說不定array轉int還會更快一點。
結果時間從276ms(int->arr)暴增到860ms(arr->int)，PR90->11
但我用colab測試，並沒有看出兩種方法有明顯差異
'''
class Solution:
def addToArrayForm(self, num: List[int], k: int) -> List[int]:
res = []
def arr_to_int(arr):
arr = arr[::-1]
deci, total = 1, 0
for a in arr:
total += a * deci
deci *= 10
return total
nk = arr_to_int(num) + k
if not nk: return [0]
while nk:
res.append(nk % 10)
nk //= 10
return res[::-1]
```
### #992.Subarrays with K Different Integers
#### first try
超時，失敗。
本來以為這不是Brute force，後來想一想，其實是
```python=
class Solution:
def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
num = 0
for length in range(K, len(A)+1):
for start in range(len(A) - length + 1):
unique = set(A[start:start + length])
if len(unique) == K:
num += 1
if len(unique) > K:
return num
```
#### 花花
```python=
'''這是reduction的技巧；藉由將這個問題轉化為另一個問題，然後求解:
題目原意是要問在原array內，元素種類是k個的subarray有多少，但這樣其實比較難實作。
如果改為找出原array內，元素種類 "不多於" k個的subarray有多少，問題就比較好時做了。解出這個問題後，只要把K的答案減去K-1的答案，就可以得到原本問題的答案了。
'''
class Solution:
def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
def subarraywltkd(k):
count = [0]*(len(A)+1)
ans, i = 0, 0
for j in range(len(A)):
if not count[A[j]]: #A[j] not seen yet
k -= 1
count[A[j]] += 1
while k < 0:
if count[A[i]] == 1:
k += 1
count[A[i]] -= 1
i += 1
ans += j - i + 1
return ans
return subarraywltkd(K) - subarraywltkd(K-1)
```
### #1290. Convert Binary Number in a Linked List to Integer
分類是graph...你確定?不要因為題目有node就說他是graph啊
```python=
'''就...binary to decimal的小變化'''
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def getDecimalValue(self, head: ListNode) -> int:
res = 0
two_power = 1
while head:
res += two_power * head.val
head = head.next
if head:
res *= 2
return res
```
##### Analysis:
- Time: $O(N)$
- Space: $O(1)$
### #89. Gray Code
#### first try:
我還是不知道這跟graph有什麼關係。也許是可以用graph，可是用bitwise operation會更直覺一點吧
然後gray code其實是有規則的，但題目沒有描述清楚。如果不知道gray code的規則直接做這題，可能會有點困惑。
```python=
class Solution:
def grayCode(self, n: int) -> List[int]:
res, ff = [0], 0
while len(res) < 1<<n:
if ff ^ 1:
res.append(res[-1]^1)
ff ^= 1
else:
k = 0
while True:
if res[-1] != res[-1]|(1<<k):
k += 1
continue
break
res.append(res[-1] ^ 1<<(k+1))
ff ^= 1
return res
```
##### Analysis:
- Time: $O(2^n)$
- 題目input給的是n，但其實解答本身的大小就是$2^n$，所以實際上要說是$O(N)$才對
- Space: $O(2^n)$，同上理，應該是$O(N)$的意思。
#### 網友解:
```python=
'''
len(res) = 2^n時，res + (res[::-1]每項加上2^n)就是兩倍長的res
e.g.
0,1,11,10->
00,01,11,10,110, 111, 101, 100
前半reverse:10, 11, 01, 10 --> 每項加上2^n(or equivalently, 1<<n): 110, 111, 101, 100，即是後半。
再concate起來就是長為2^3的解
*前半部也要補0不過不影響值
'''
class Solution:
def grayCode(self, n: int) -> List[int]:
k = 0
res = [0]
while k < n:
res += [x + (1<<k) for x in res[::-1]]
k += 1
return res
```
##### Analysis:
- 同上
#### 網友解2:
其實就是網友解1的高層次解。不過從LC run的結果看來，bitwise op效能還是勝出。
```python=
def grayCode(self, n):
results = [0]
for i in range(n):
results += [x + pow(2, i) for x in reversed(results)]
return results
```
## 042321
### #5. Longest Palindromic Substring
#### first try:
概念對了但是技巧不好，performance太差。超時。
```python=
class Solution:
def longestPalindrome(self, s: str) -> str:
if len(s) < 2:
return s
res = []
for i in range(len(s)+1):
for j in range(i, len(s)+1):
if s[0:i] + s[i:j][::-1] + s[j:] == s:
if len(s[i:j]) > len(res):
res = s[i:j]
return res
```
#### 網友解1:
跟我的差不多概念，但實作細節好一點。主要是區分了奇數和偶數的狀況，減少很多多餘的計算。
```python=
'''用一個helper method分開探討奇數和偶數的情況，讓程式碼比較簡潔'''
class Solution:
def longestPalindrome(self, s: str) -> str:
res = ""
for i in range(len(s)):
tmp = self.helper(s, i, i)
if len(tmp) > len(res):
res = tmp
tmp = self.helper(s, i, i+1)
if len(tmp) > len(res):
res = tmp
return res
def helper(self, s, l, r):
while l > -1 and r < len(s) and s[l] == s[r]:
l-=1; r+=1
return s[l+1:r]
```
#### 網友解2:
```python=
'''DP版本，看來很華麗，但是會TLE
簡單來說就是如果i->j是palindrome，那如果i-1 value == j+1 value，則i-1->j+1也是palindrome
base case就是i+1=j且i value == j value
'''
import numpy as np
class Solution:
def longestPalindrome(self, s: str) -> str:
if len(s) <= 1:
return s
length, longest_ps, longest_plen = len(s), 0, 1
state = np.ones((length, length))
for i in range(length-1, -1, -1):
for dist in range(1, length - i):
j = dist + i
state [i][j] = (s[i] == s[j]) if (dist == 1) \
else (s[i] == s[j]) and state[i+1][j-1]
if state[i][j] and (j-i+1) > longest_plen:
longest_plen = j-i+1
longest_ps = i
return s[longest_ps:longest_ps+longest_plen]
```
#### 網友解3:
```python=
'''因為code不難，加上我大概懂他在幹嘛，所以閉著眼睛可以寫出來。
但我還是沒有完全懂他在幹嘛。
但這個可以到PR98、99
'''
class Solution:
def longestPalindrome(self, s: str) -> str:
if not s:
return ""
maxlen, start = 1, 0
for i in range(len(s)):
if i - maxlen >= 1 and s[i-maxlen-1:i+1] == s[i-maxlen-1:i+1][::-1]:
start = i-maxlen-1
maxlen += 2
continue
if i - maxlen >= 0 and s[i-maxlen:i+1] == s[i-maxlen:i+1][::-1]:
start = i-maxlen
maxlen += 1
return s[start:start+maxlen]
```
#### Analysis:
- Time: $O(N)$ if slicing 是$O(1)$，但有人說python的slicing其實是$O(N)$，所以整體還是$O(N^2)$
### #266. Palindrome Permutation
#### first try:
竟花了我20分鐘，無言了
而且超醜的。
```python=
class Solution:
def canPermutePalindrome(self, s: str) -> bool:
d = {}
for c in s:
if c not in d:
d[c] = 1
else: d[c] += 1
data = sorted([(x,d[x]) for x in d], key = lambda s:s[1])
frequency = list(map(list,zip(*data)))[1]
count = 0
for f in frequency:
if f % 2:
count += 1
return False if count > 1 else True
```
這樣好多了
```python=
class Solution:
def canPermutePalindrome(self, s: str) -> bool:
freq = set()
for c in s:
if c not in freq: freq.add(c)
else: freq.remove(c)
return False if len(freq) > 1 else True
```
## 042621
### #242. Valid Anagram
題目說字母只有包括小寫英文字，因此用陣列儲存字元頻率即可
PR 26
```python=
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
if len(s) != len(t):
return False
count = [0]*26
count_t = [0]*26
for i in range(len(s)):
count[ord(s[i]) - 97] += 1
count_t[ord(t[i]) - 97] += 1
for i in range(len(count)):
if count[i] != count_t[i]:
return False
return True
```
字典，表現一樣後段
```python=
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
if len(s) != len(t):
return False
dict_s = {}
for ss in s:
if ss not in dict_s: dict_s[ss] = 1
else: dict_s[ss] += 1
for tt in t:
if tt not in dict_s: return False
elif dict_s[tt] == 0: return False
else: dict_s[tt] -= 1
return True
```
PR 99:
是不是越短的code時間越短?
這聽起來是不是像廢話?
我上次是不是已經寫過這個了?
```python=
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
char_ord = 'abcdefghijklmnopqrstuvwxyz'
return all( s.count(x) == t.count(x) for x in char_ord )
```
#### Analysis:
- Time: $O(N)$
### #267. Palindrome Permutation II
#### first try:
not completely correct; for i don't know how to raise all combinations as asked in the question.
But other parts were ok.
After understanding how to raice combinations with Counter and recursive call(not gonna work if not used with recursion), it works.
```python=
class Solution:
def generatePalindromes(self, s: str) -> List[str]:
if not s: return ''
abc = 'abcdefghijklmnopqrstuvwxyz'
res = []
n = len(s)
'''sort frequency of letters
For odd palindrome:
find any frq which is odd->possible pivot
(if and only if one odd number is permitted)
split s to be pivot and others
split the rest of s to 2 halves
permutate of 'half' + pivot + inverted first part
For even palindrome:
find freq of all: if it's all even
split to 2 halves
permutate of 'half' + inverted first part
'''
def helper(counter, tmp):
if len(tmp) == n:
res.append(tmp)
for k, v in counter.items():
if v:
counter[k] -= 1
helper(counter, k+tmp+k)
counter[k] += 1
letter_freq = list(s.count(x) for x in abc)
count, pivot = 0, ''
for f in letter_freq:
if f % 2:
count += 1
pivot = chr(letter_freq.index(f)+97)
if count > 1: return ''
'''palindrome with pivot'''
s = s.replace(pivot, '', 1)
half = ''
freq_half = [x//2 for x in letter_freq]
for i in range(len(freq_half)):
if freq_half[i]: half += chr(i+97) * freq_half[i]
h_counter = Counter(half)
helper(h_counter, pivot)
return res
```
#### Analysis:([resource:leetcode forum](https://leetcode.com/problems/palindrome-permutation-ii/discuss/301774/Python-with-comment-and-complexity))
- Time: $O(N^2 * N!)$
- Space:$O(N!)$
## 042721
### #7. Reverse Integer
C版本:
- 直接參考網友寫法，因為我的C退化有點嚴重。
- 學到並練習sprintf()以及strtol()
- 是我的問題嗎?我覺得C規格書 n1570對標準庫函式也沒有講得很詳細(沒有範例)...但是算清楚了。
- ~~範例大概只有小孩子需要吧~~
```c=
#include <limits.h>
#include <stdbool.h>
int reverse(int x){
int tmp, len;
bool negative = false;
if (x > 0) {
if (x < INT_MAX) {}
else {return 0;}
}
else {
if (x > INT_MIN) {}
else {return 0;}
}
if (x < 0)
{
x = -x;
negative = true;
}
char s[20];
sprintf(s, "%d", x);
len = strlen(s);
for (int i = 0; i < len / 2; i++) {
tmp = s[i];
s[i] = s[len -1 -i];
s[len -1 -i] = tmp;
}
long long retval = strtol(s, (char**)NULL, 10);
if (negative) {
if (retval < INT_MAX) {return (int)(-retval);}
return 0;
}
if (retval < INT_MAX) {
return (int)retval;
}
else {return 0;}
}
```
- Python版本:表現不是特別好。
```python=
class Solution:
def reverse(self, x: int) -> int:
if x >= 0:
rev = int(str(x)[::-1])
return rev if rev <= pow(2, 31) - 1 else 0
if x < 0:
minus_rev = (-1)*int(str(-x)[::-1])
return minus_rev if minus_rev >= -pow(2, 31) else 0
```
### #6. ZigZag Conversion
網友解:簡單就是美。優雅。
```python=
class Solution:
def convert(self, s: str, numRows: int) -> str:
if numRows == 1 or len(s) <= numRows:
return s
rows = [''] * numRows
step, index = 1, 0
for c in s:
rows[index] += c
if index == numRows-1:
step = -1
if index == 0:
step = 1
index += step
return "".join(x for x in rows)
```
#### firsy try by me, mostly:
代數解:沒有想像中優雅，其實比較複雜(相對上面的解來說)；即使一樣是代數解，也有不同的思路。
```python=
class Solution:
def convert(self, s: str, numRows: int) -> str:
if len(s) <= numRows or numRows == 1:
return s
rows = [''] * numRows
step = 2 * numRows - 2
for t in range(1 + len(s) // (2*numRows - 2)):
for n in range(numRows):
index1, index2 = n + t * (2 * numRows - 2), 2 * (numRows-1) - n + t * (2 * numRows - 2)
#when n = nR-1, index1 == index2
#when n = 0, omit index2
if index1 < len(s):
rows[n] += s[index1]
else: break
if not n or n == numRows - 1:
continue
if index2 < len(s):
rows[n] += s[index2]
return "".join(x for x in rows)
```
##### Analysis:
- Time: $O(N)$ (N == len(s))
- Space: $O(N)$
### #1496. Path Crossing
#### first try:
練習tuple的使用；tuple is hashable but list is not
也可以用string。(Java沒有tuple，所以string是很合理的作法)
```python=
class Solution:
def isPathCrossing(self, path: str) -> bool:
_ = 'naive way'
direction = {'N':(0,1),'E':(1,0),'S':(0,-1),'W':(-1,0)}
loc = (0,0)
log = set()
log.add(loc)
for p in path:
loc = (loc[0] + direction[p][0], loc[-1] + direction[p][-1])
if loc in log:
return True
log.add(loc)
return False
```
## 042921
### #8. String to Integer (atoi)
logic control or regexp or ?
```python=
class Solution:
def myAtoi(self, s: str) -> int:
res = ''
if not s: return 0
while s:
if s[0] == ' ':
s = s.replace(' ', '', 1)
else: break
sig = '+'
if not s: return 0
if s[0] == '-' or s[0] == '+':
sig = s[0]
s = s[1:]
if not s: return 0
for c in s:
if c.isdigit():
res += c
else: break
if res:
res = sig + res
if int(res) > 2**31-1:
return 2**31-1
elif res and int(res) < -2**31:
return -2**31
return int(res) if res else 0
```
### #9. Palindrome Number
```python=
class Solution:
def isPalindrome(self, x: int) -> bool:
str_x = str(x)
if str_x == str_x[::-1]:
return True
return False
```
### #11. Container With Most Water
#### 網友解
```python=
class Solution:
def maxArea(self, height: List[int]) -> int:
start, end, max_vol = 0, len(height)-1, 0
while end > start:
vol = min(height[start], height[end]) * (end - start)
if vol > max_vol:
max_vol = vol
if height[start] > height[end]:
end -= 1
else: start += 1
return max_vol
```
## 043021
### #155. Min Stack
#### first try
naive寫法，
表現差的主要原因是getMin要sorting
```python=
class MinStack:
def __init__(self):
"""
initialize your data structure here.
"""
self.content = []
self.num_ele = 0
def push(self, val: int) -> None:
self.content.append(val)
self.num_ele += 1
def pop(self) -> None:
self.content.pop()
self.num_ele -= 1
def top(self) -> int:
return self.content[-1]
def getMin(self) -> int:
return sorted(self.content)[0]
# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()
```
#### 網友解
這題的getMin其實不需要sorting，只要另外用一個array存最小值就可以。
min_arr的大小會跟著array變化，但append時append min(val, min_arr[-1])，如此就可以保存最小值以及content規模。
如果單純在initializer加上一個min_val屬性，每次更新，這樣pop()如果剛好是該最小值就沒辦法處哩，因為沒有存"下一個min val"。
```python=
class MinStack:
def __init__(self):
"""
initialize your data structure here.
"""
self.content = []
self.min_arr = []
def push(self, val: int) -> None:
self.content.append(val)
self.min_arr.append(val if not self.min_arr else min(val, self.min_arr[-1]))
def pop(self) -> None:
self.content.pop()
self.min_arr.pop()
def top(self) -> int:
return self.content[-1]
def getMin(self) -> int:
return self.min_arr[-1]
# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()
```
##### Analysis:
- Time: $O(NlogN)$ vs $O(1)$
- Space: $O(N)$ vs $O(N)$
### #716. Max Stack
#### first try
試著用#155的方法，但行不通。因為多了一個popMax的功能，必須知道max_val的index而不只是值。
所以我最後還是先用sorted 提交。雖然沒有TLE，但效能不好是一定的。看來確實有更好的辦法。
```python=
class MaxStack:
def __init__(self):
"""
initialize your data structure here.
"""
self.content = []
def push(self, x: int) -> None:
self.content.append(x)
def pop(self) -> int:
return self.content.pop()
def top(self) -> int:
return self.content[-1]
def peekMax(self) -> int:
return sorted(self.content)[-1]
def popMax(self) -> int:
max_val, max_i = sorted(self.content)[-1], 0
for i in range(len(self.content)-1, -1, -1):
if self.content[i] == max_val:
max_i = i
break
del self.content[max_i]
return max_val
# Your MaxStack object will be instantiated and called as such:
# obj = MaxStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.peekMax()
# param_5 = obj.popMax()
```
#### 網友解
上週因為感冒頭昏腦脹，一直看不進去。今天花了一整天的時間搞懂網友這個解法的邏輯。
雖然他是使用heapq這個套件，但不僅是如此，其中相當重要的就是delayed_recycle這個set。(好啦我知道這個命名很爛)
首先關於heapq，要知道的是: heapq必須要完整地被使用。雖然他的heappop, heappush都可以保證行為符合priorityqueue的要求，但是前提是你要用heappush 來推入所有元素，稍後heappop 才會得到正確的值。例如你先手動建立了一個list，再heappop 個個元素，會發現pop 出來的並不是預期的東西。而且過程中list 會出現一些奇妙的變化:有點像是heapify 的過程但又不完全是這麼回事。
如果你有一個手動建立的list (不是經由heappush 建立的)，必須要先用heapify 整理，然後才能進行其他操作。
再來是delayed_recycle 這個結構。這結構在我們的_collate 函式被調用，可以發現當pop被call 時，stack 接受pop()，但是max_heap 並沒有被修正(事實上只是可能需要)；相反popMax 被call 時，只有max_heap 被pop，stack則沒有改變(也沒辦法立即改變)。
在這兩種pop function中應該被刪掉而未被刪掉的obj，我們就先用delayed_recycle(我下次真的不會用這麼蠢的名字了)存起來，每次pop, popMax 被呼叫時都呼叫_collate 執行檢查任務:如果stack或是max_heap有應該刪掉而沒被刪掉的obj，_collate 就會把他們刪除。而這些元素在從stack 或是max_heap 被刪除之前，雖然還留在各自的data structure 之中，但並不會影響peekMa，top 這兩個操作。
```python=
import heapq as hq
class MaxStack:
def __init__(self):
"""
initialize your data structure here.
"""
self.stack = []
self.max_heap = []
self.delayed_recycle = set()
self.cnt = 0
def push(self, x: int) -> None:
self.stack.append((x, self.cnt))
hq.heappush(self.max_heap, (-x, self.cnt))
self.cnt -= 1
def _collate(self):
while self.stack and self.stack[-1][1] in self.delayed_recycle:
self.delayed_recycle.remove(self.stack.pop()[1])
while self.max_heap and self.max_heap[0][1] in self.delayed_recycle:
self.delayed_recycle.remove(hq.heappop(self.max_heap)[1])
def pop(self) -> int:
x, c = self.stack.pop()
self.delayed_recycle.add(c)
self._collate()
return x
def top(self) -> int:
return self.stack[-1][0]
def peekMax(self) -> int:
return -self.max_heap[0][0]
def popMax(self) -> int:
x, c = hq.heappop(self.max_heap)
self.delayed_recycle.add(c)
self._collate()
return -x
# Your MaxStack object will be instantiated and called as such:
# obj = MaxStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.peekMax()
# param_5 = obj.popMax()
```
##### Analysis:
- Time:
- peekMax, top: $O(1)$
- push: $O(logN)$
- pop , popMax (_collate): $O(N)$ , $O(N+logN) = O(N)$
- Space: $O(N)$
### #70. Climbing Stairs
#### first try:
a banal solution solving this basically being fibonacci problem
```python=
class Solution:
def climbStairs(self, n: int) -> int:
a,b = 1,1
for i in range(n):
a,b = b, a+b
return a
```
#### 網友解:
maybe it's more pythonic
```python=
class Solution:
def climbStairs(self, n: int) -> int:
a,b = 1,1
for i in range(n):
a,b = b, a+b
return a
```
## 050321
### #716\. Max Stack
-> 1607
### #14. Longest Common Prefix
#### first try:
naive, though not brutal
```python=
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
rep = strs[0]
for i in range(1, len(strs)):
common_len = min(len(rep), len(strs[i]))
tmp = ""
for j in range(common_len):
if not ord(rep[j]) ^ ord(strs[i][j]):
tmp+= rep[j]
else: break
rep = tmp
if not rep: return ""
return rep
```
## 050621
### #20. Valid Parentheses
其實就是用stack來做。一開始想了一些奇門遁甲的招式但都太過冗贅。
#### first try
```python=
class Solution:
def isValid(self, s: str) -> bool:
open_prh = set(['(','[','{'])
pair = {']':'[','}':'{',')':'('}
stack = []
for p in s:
if p in open_prh:
stack.append(p)
elif p in pair.keys():
if not stack: return False
if pair[p] != stack.pop():
return False
else: return False #invalid char
if stack:return False
return True
```
##### Analysis:
- Time:$O(N)$
- Space:$O(1)$
### #22. Generate Parentheses
#### first try
暴力中的暴力法，連一點優化都沒有
```python=
from itertools import *
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
def check_val(seq):
stack = 0
for s in seq:
if s == '(': stack += 1
elif s == ')': stack -= 1
if stack < 0: return False
return True if not stack else False
prod = [list(x) for x in list(product('()', repeat = 2 * n))]
ans = [''.join(i for i in x) for x in prod if check_val(x)]
return ans
```
##### Analysis:
- Time: $O(N*2^N)$
- Space:
## 050821
### #232. Implement Queue using Stacks
this is a inductive quest for queue data structure
#### first try( python )
其實作法不符合題目規定。不過這題本來就是針對比較低階的語言。高階語言標準庫支援太豐富。不過還是可以(見下面)。
```python=
class MyQueue:
def __init__(self):
"""
Initialize your data structure here.
"""
self.queue = []
def push(self, x: int) -> None:
"""
Push element x to the back of queue.
"""
self.queue.append(x)
return None
def pop(self) -> int:
"""
Removes the element from in front of queue and returns that element.
"""
if self.queue:
x = self.queue[0]
self.queue = self.queue[1:]
return x
else: return None
def peek(self) -> int:
"""
Get the front element.
"""
if self.queue: return self.queue[0]
else: return None
def empty(self) -> bool:
"""
Returns whether the queue is empty.
"""
return False if self.queue else True
```
#### 網友解 ( C )
試著看完一個function的寫法後自己寫下一個。不過還是不熟基本語法。
```c=
typedef struct {
int stack[100];
int back, front, size;
} MyQueue;
/** Initialize your data structure here. */
MyQueue* myQueueCreate() {
MyQueue *q = malloc(sizeof(MyQueue));
q->back = 0;
q->front = 0;
q->size = 0;
return q;
}
/** Push element x to the back of queue. */
void myQueuePush(MyQueue* obj, int x) {
obj->size++;
obj->stack[obj->back] = x;
obj->back = obj->back + 1;
}
/** Removes the element from in front of queue and returns that element. */
int myQueuePop(MyQueue* obj) {
if (obj->size > 0) obj->size--;
else return 0;
obj->front = obj->front + 1;
return obj->stack[obj->front - 1];
}
/** Get the front element. */
int myQueuePeek(MyQueue* obj) {
return obj->stack[obj->front];
}
/** Returns whether the queue is empty. */
bool myQueueEmpty(MyQueue* obj) {
if (obj->front == obj->back) return true;
else return false;
}
void myQueueFree(MyQueue* obj) {
free(obj);
}
```
#### second try:(python)
類C作法。
似乎有比較快嗎?
```python=
class MyQueue:
def __init__(self):
"""
Initialize your data structure here.
"""
self.queue = []
self.front, self.back = 0, 0;
def push(self, x: int) -> None:
"""
Push element x to the back of queue.
"""
self.queue.append(x);
self.back+=1;
def pop(self) -> int:
"""
Removes the element from in front of queue and returns that element.
"""
self.front += 1
return self.queue[self.front-1]
def peek(self) -> int:
"""
Get the front element.
"""
return self.queue[self.front]
def empty(self) -> bool:
"""
Returns whether the queue is empty.
"""
return True if self.back == self.front else False
```
#### Analysis:
- Time:
- insert, pop, peek, isEmpty: $O(1)$
## 051021
### #21. Merge Two Sorted Lists
#### first try
不能用python 非常強大的list operation，必須用指標操作的方式來做。因為給的list已經sorted好了，所以只是考基本programming能力和邏輯。
其實就是merge sort的部分實作。
###
```python=
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
dumHead = ListNode(-101, None)
curNode = dumHead
while l1 or l2:
if not l1:
curNode.next = l2
break
elif not l2:
curNode.next = l1
break
if l1.val > l2.val:
curNode.next = l2
curNode = curNode.next
l2 = l2.next
elif l2.val >= l1.val:
curNode.next = l1
curNode = curNode.next
l1 = l1.next
return dumHead.next
```
##### Analysis:
- Time: Linear
- Space: Constant
## 051121
### #28. Implement strStr()
#### first try
naive way, 但竟然比KMP快，這可能是這題這麼多倒讚的原因?
```python=
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
if not needle: return 0
if len(haystack) < len(needle): return -1
for i in range(len(haystack) - len(needle) + 1):
if haystack[i:i+len(needle)] == needle:
return i
return -1
```
#### KMP algorithm:
其實我還是沒有很懂，過幾天反芻一下再回來想看看。
想法大致懂了，但怎麼轉換成code還需要思考一下。
我想先讓大腦在背景run個一陣子。
```python=
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
if not needle: return 0
h, n, ff = len(haystack), len(needle), [0] * len(needle)
for i in range(1, n):
j = ff[i-1]
while needle[i] != needle[j]:
if j == 0:
break
j = ff[j-1]
if needle[i] == needle[j]:
ff[i] = j + 1
else: ff[i] = 0
i, j = 0, 0
while i < h:
if haystack[i] != needle[j]:
if j == 0:
i += 1
continue
j = ff[j-1]
else:
i += 1
j += 1
if j == n: return i-j
return -1
```
#### Analysis:
- Time: $O(H*N)$ / $O(H+N)$
- Space: $O(1) / $O(N)$
## 051221
### #
#### HuaHua:
list go-through
```python=
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
if not nums or len(nums) < 3: return []
nums_freq = {}
ans = []
for n in nums:
if n not in nums_freq: nums_freq[n] = 1
else: nums_freq[n] += 1
nums = sorted(nums)
if nums[0] > 0: return []
for i in range(len(nums)):
if i and nums[i] == nums[i-1]: continue # prevent count solution with same value twice (a)
for j in range(i + 1, len(nums)):
k = -(nums[i] + nums[j]) # the third value needed
if j > i + 1 and nums[j] == nums[j-1]: continue # = (a)
if k not in nums_freq or k < nums[j]: continue # k not in nums or k < nums[j], 2nd item
if nums_freq[k] >= 1 + (nums[i] == k) + (nums[j] == k):
ans.append([nums[i], nums[j], k])
return ans
```
#### HuaHua
double pointers
```python=
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums = sorted(nums)
n = len(nums)
if n < 3: return []
ans = []
for i in range(n):
if i and nums[i] == nums[i-1]: continue
j, k = i + 1, n - 1
while(j < ｋ):
if nums[j] + nums[k] > -nums[i]: k -= 1
elif nums[j] + nums[k] < -nums[i]: j += 1
else:
ans.append([nums[i], nums[j],nums[k]])
while j < k and nums[j] == nums[j+1]: j += 1
while j < k and nums[k-1] == nums[k]: k -= 1
j, k = j + 1, k - 1
return ans
```
#### Analysis:
- Time:$O(n^2)$ / $O(n^2)$
- Space: $O(n)$(要存freq dict) / $O(1)$
## 051421
### #1. Two Sum
#### first try
```python=
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
ans = []
for n in range(len(nums)):
t = target - nums[n]
for p in range(n+1, len(nums)):
if nums[p] == t: return [n,p]
```
#### second try:
```python=
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
ndict = {}
for n in nums:
if n not in ndict:
ndict[n] = 1
else: ndict[n] += 1
nums = list(enumerate(nums))
nums = sorted(nums, key = lambda i: i[1])
ndict
j, k = 0, len(nums) - 1
while j < k:
if nums[j][1] + nums[k][1] > target:
k -= 1
continue
elif nums[j][1] + nums[k][1] < target:
j += 1
continue
else: return (nums[j][0], nums[k][0])
```
#### Analysis:
first / second try
- Time: $O(n^2)$ / $O(nlogn)$
- Space: $O(1)$ / $O(n)$
but in reality, first try is faster then second try (or equivalent), and space consumption between them are also comparable, in leetcode environment.
## 051721
### #16. 3Sum Closest
#### 網友解
```python=
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
min_dis = 10**6
nums.sort()
res = sum(nums[:3])
for i in range(len(nums)-2):
j, k = i+1, len(nums)-1
while j < k:
summ = nums[i] + nums[j] + nums[k]
if summ == target:
return summ
if abs(summ-target) < abs(res - target): res = summ
if summ > target: k -= 1
if summ < target: j += 1
return res
```
## 052021
### #18. 4Sum
網友解是網友解2優化版。
自改的版本跟網友解一樣，不會造成額外的空間消耗。(不過LC上是看不出來)
時間複雜度都一樣。
#### 網友解
```python=
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
def findNSum(l, r, target, N, result, results):
if r - l + 1 < N or N < 2 or target < nums[l] * N or target > nums[r] * N:
return
if N == 2:
while l < r:
s = nums[l] + nums[r]
if s == target:
results.append(result + [nums[l], nums[r]])
l += 1
while l < r and nums[l] == nums[l-1]:
l += 1
elif s < target:
l += 1
else:
r -= 1
else:
for i in range(l, r+1):
if i == l or (i > l and nums[i-1] != nums[i]):
findNSum(i+1, r, target - nums[i], N-1, result + [nums[i]], results)
nums.sort()
results = []
findNSum(0, len(nums)-1, target, 4, [], results)
return results
```
#### 網友解2：
```python=
class Solution:
def fourSum(self, nums, target):
nums.sort()
results = []
self.findNsum(nums, target, 4, [], results)
return results
def findNsum(self, nums, target, N, result, results):
if len(nums) < N or N < 2: return
# solve 2-sum
if N == 2:
l,r = 0,len(nums)-1
while l < r:
if nums[l] + nums[r] == target:
results.append(result + [nums[l], nums[r]])
l += 1
r -= 1
while l < r and nums[l] == nums[l - 1]:
l += 1
while r > l and nums[r] == nums[r + 1]:
r -= 1
elif nums[l] + nums[r] < target:
l += 1
else:
r -= 1
else:
for i in range(0, len(nums)-N+1): # careful about range
if target < nums[i]*N or target > nums[-1]*N: # take advantages of sorted list
break
if i == 0 or i > 0 and nums[i-1] != nums[i]: # recursively reduce N
self.findNsum(nums[i+1:], target-nums[i], N-1, result+[nums[i]], results)
return
```
#### 網友解，自改
```python=
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
def nsum(nums, target, N, res, resli, s):
if len(nums) < N or N < 2: return
elif N == 2:
i, j = s, len(nums) - 1
while j > i:
if nums[i] + nums[j] == target:
resli.append(res + [nums[i], nums[j]])
i, j = i + 1, j - 1
while j > i and nums[i] == nums[i - 1]: i += 1
while j > i and nums[j] == nums[j + 1]: j -= 1
elif nums[i] + nums[j] > target:
j -= 1
elif nums[i] + nums[j] < target:
i += 1
return
elif N > 2:
for i in range(s, len(nums) - N + 1):
if N * nums[i] > target or N * nums[-1] < target:
return
if i == s or (i > s and nums[i] != nums[i - 1]):
nsum(nums, target - nums[i], N - 1, res + [nums[i]], resli, i + 1)
nums.sort()
res, resli = [], []
nsum(nums, target, 4, res, resli, 0)
return resli
```
#### Analysis:
- Time:$O(n^2)$
- Space:$O(1)$ / $O(N)$
- 這是不考慮return value的空間且深度固定，即n sum的n固定時。若N不定，會變為$O(1)$ / $O(n*N)$
## 052521
### #259. 3Sum Smaller
#### 論壇解1：
##### Analysis
- Time:$O(N^2logN)$
使用bisect模組在$log(N)$內找出剩餘數組小於target的個數。加上最初雙loop總共用掉$O(N^2)$，故是$O(N^2logN)$
```python=
import bisect as bs
class Solution:
def threeSumSmaller(self, nums: List[int], target: int) -> int:
nums.sort()
n = 0
'''n_dict = {}
for i in nums:
if i not in n_dict: n_dict[n] = 1
else: n_dict[n] += 1'''
for i in range(len(nums) - 2):
for j in range(i + 1, len(nums) - 1):
tg = target - (nums[i] + nums[j])
n += max(bs.bisect_left(nums, tg, j + 1) - 1, j) - j
return n
```
#### 論壇解2:
##### Analysis
- Time: $O(N^2)$
使用雙指針($O(N)$)加上單循環($O(N)$)的方式，只需要$O(N^2)$的時間複雜度。
```python=
class Solution:
def threeSumSmaller(self, nums: List[int], target: int) -> int:
res=0
nums.sort()
for i in range(len(nums)-2):
l,r=i+1,len(nums)-1
while l<r:
current = nums[i]+nums[l]+nums[r]
if current<target:
res+=r-l
l+=1
else:
r-=1
return res
```
Sign in with Wallet
Connect another wallet