Review List
5 min readFeb 23, 2020
class Solution:
def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
if not matrix or not matrix[0]:return 0
R, C = len(matrix), len(matrix[0])
dp = [[0]*C for _ in range(R)]
from functools import lru_cache
@lru_cache(None)
def dfs(i,j):
if dp[i][j]:return dp[i][j]
res = 1
for di,dj in [(1,0),(-1,0),(0,1),(0,-1)]:
r, c = i+di, j+dj
if 0<=r<R and 0<=c<C and matrix[r][c]>matrix[i][j]:
res = max(res, 1+dfs(r,c))
return res
res = -float('inf')
for i in range(R):
for j in range(C):
if dp[i][j]==0:
dp[i][j] = dfs(i,j)
res = max(res, dp[i][j])
return reshttps://leetcode.com/problems/copy-list-with-random-pointer/
"""
# Definition for a Node.
class Node:
def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
self.val = int(x)
self.next = next
self.random = random
"""
class Solution:
def copyRandomList(self, head: 'Node') -> 'Node':
if head is None:return None
d = {}
node = head
while node:
d[node] = Node(node.val)
node = node.next
new_head = d[head]
node = head
while node:
if node.next:d[node].next = d[node.next]
if node.random:d[node].random = d[node.random]
node = node.next
return new_headOr more concise
"""
# Definition for a Node.
class Node:
def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
self.val = int(x)
self.next = next
self.random = random
"""
class Solution:
def copyRandomList(self, head: 'Node') -> 'Node':
if head is None:return None
d = {}
node = head
while node:
d[node] = Node(node.val)
node = node.next
node = head
while node:
d[node].next = d.get(node.next, None)
d[node].random = d.get(node.random,None)
node = node.next
return d[head]https://leetcode.com/problems/lru-cache/
class LRUCache {
private:
int capacity_;
map<int, list<pair<int,int>>::iterator> m_;
list<pair<int,int>> cache_;
public:
LRUCache(int capacity): capacity_(capacity) {}int get(int key) {
auto it = m_.find(key);
//find
if(it!=m_.end()){
int val = it->second->second;
cache_.splice(cache_.begin(), cache_, it->second);
m_[key] = cache_.begin();
return val;
}
//not find
return -1;
}
void put(int key, int value) {
//if it is already in the chache
auto it = m_.find(key);
if(it!=m_.end()){
it->second->second = value;
cache_.splice(cache_.begin(), cache_, it->second);
return;
}
//if not in the cache
//update if reach the capacity
if(cache_.size()==capacity_){
auto last = cache_.back();
cache_.pop_back();
m_.erase(last.first);
}
cache_.emplace_front(key, value);
m_[key] = cache_.begin();
return;
}
};
/*
void put(int key, int value) {
const auto it=m_.find(key);
//if find: update list and update value
if(it != m_.cend()){
it->second->second=value;
cache_.splice(cache_.begin(), cache_, it->second);
//m_[key] = cache_.begin();
return;
}
//if not find
// reach capacity
if(cache_.size()==capacity_){
const auto & node = cache_.back();
m_.erase(node.first);
cache_.pop_back();
}
cache_.emplace_front(key, value);
m_[key] = cache_.begin();
}
};
*/
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache* obj = new LRUCache(capacity);
* int param_1 = obj->get(key);
* obj->put(key,value);
*/
Attention: how to use find. How to use splice. cache_.splice(cache_.begin(), cache_, it->second);
Don’t forget this line “for i in range(n):dis[i][i] = 0”
class Solution:
def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
dis = [[float('inf')]*n for _ in range(n)]
for u,v,c in edges:
dis[u][v] = dis[v][u] = c
for i in range(n):dis[i][i] = 0
for k in range(n):
for i in range(n):
for j in range(n):
dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j])
min_reach, min_city = float('inf'), -1
for city in range(n):
this_reach =sum(dis[city][other_city]<=distanceThreshold for other_city in range(n))
if this_reach <= min_reach:
min_reach, min_city = this_reach, city
return min_cityOr we can write a shorter version
class Solution:
def findTheCity(self, n: int, edges: List[List[int]], T: int) -> int:
dis = [[float('inf')]*n for _ in range(n)]
for u,v,c in edges:
dis[u][v] = dis[v][u] = c
for i in range(n):dis[i][i] = 0
for k in range(n):
for i in range(n):
for j in range(n):
dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j])
res = {sum(dis[i][j]<=T for j in range(n)):i for i in range(n) }
return res[min(res)]Above solutions are using Floyd Warshall algorithm and the complexity is O(n³). We can also use naive Dijkstra
class Solution:
def findTheCity(self, n: int, edges: List[List[int]], T: int) -> int:
cost = [[float('inf')]*n for _ in range(n)]
graph = collections.defaultdict(list)
for u,v,c in edges:
cost[u][v] = cost[v][u] = c
graph[u].append(v)
graph[v].append(u)
def dijkstra(i):
dis = [float('inf')]*n
dis[i], pq = 0, [(0, i)]
heapq.heapify(pq)
while pq:
c, i = heapq.heappop(pq)
if c> dis[i]:continue
for j in graph[i]:
this_cost = c+cost[i][j]
if this_cost<dis[j]:
dis[j] = this_cost
heapq.heappush(pq, (this_cost, j))
print(i, dis)
return sum(dis[i]<=T for i in range(n))
#for i in range(n):print(dijkstra(i))
res = {dijkstra(i):i for i in range(n)}
return res[min(res)]Below code is good
if c> dis[i]:continue for test case
5
[[0,1,2],[0,4,8],[1,2,3],[1,4,2],[2,3,1],[3,4,1]]
2we have
4 [0, 2, 5, 5, 4]
3 [2, 0, 3, 3, 2]
0 [5, 3, 0, 1, 2]
0 [5, 3, 1, 0, 1]
0 [4, 2, 2, 1, 0]If we change the code to
if c>= dis[i]:continue
we will get the wrong answer as
0 [0, inf, inf, inf, inf]
1 [inf, 0, inf, inf, inf]
2 [inf, inf, 0, inf, inf]
3 [inf, inf, inf, 0, inf]
4 [inf, inf, inf, inf, 0]If we change the code a little bit as follows.
class Solution:
def findTheCity(self, n: int, edges: List[List[int]], T: int) -> int:
cost = [[float('inf')]*n for _ in range(n)]
graph = collections.defaultdict(list)
for u,v,c in edges:
cost[u][v] = cost[v][u] = c
graph[u].append(v)
graph[v].append(u)
def dijkstra(i):
dis = [float('inf')]*n
#dis[i] = 0
pq = [(0, i)]
heapq.heapify(pq)
while pq:
c, i = heapq.heappop(pq)
if c>= dis[i]:continue
else:dis[i] = c
for j in graph[i]:
this_cost = c+cost[i][j]
if this_cost<dis[j]:
dis[j] = this_cost
heapq.heappush(pq, (this_cost, j))
print(i, dis)
return sum(dis[i]<=T for i in range(n))
#for i in range(n):print(dijkstra(i))
res = {dijkstra(i):i for i in range(n)}
return res[min(res)]still, we get an error.
It is very subtle. However, we cannot continue when it is equal as we should keep on exploring.
4 [0, 2, inf, inf, 8]
2 [2, 0, 3, inf, 2]
1 [inf, 3, 0, 1, inf]
4 [inf, inf, 1, 0, 1]
0 [8, 2, inf, 1, 0]https://leetcode.com/problems/validate-binary-search-tree/
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = Noneclass Solution:
def isValidBST(self, root, floor=float('-inf'), ceiling=float('inf')):
if not root:return True
if root.val <= floor or root.val >= ceiling:return False
# in the left branch, root is the new ceiling; contrarily root is the new floor in right branch
return self.isValidBST(root.left, floor, root.val) and self.isValidBST(root.right, root.val, ceiling)
https://leetcode.com/problems/all-paths-from-source-to-target/
class Solution:
def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
paths = []
def dfs():
open_list = [[0]]
while open_list:
path = open_list.pop()
if path[-1]==len(graph)-1:paths.append(path)
for j in graph[path[-1]]:
open_list.append( path+[j])
dfs()
return pathshttps://leetcode.com/problems/decode-string/
class Solution:
def decodeString(self, s: str) -> str:
stack = []
res = ""
for c in s:
if c!=']':
stack.append(c)
else:
temp = ""
while stack:
if stack[-1]=='[':
stack.pop()
if not stack:
stack.append(temp[::-1])
break
n = ""
while stack and stack[-1].isdigit():
n+=stack.pop()
stack.append(int(n[::-1])*temp[::-1])
break
else:
temp += stack.pop()[::-1]
return "".join(stack)class Solution:
def lastRemaining(self, n: int) -> int:
def helper(n, left=True):
if n==1:return 1
if left:
return 2*helper(n//2, False)
else:
# right
if n%2==1:
#[1,2,3,4,5] -> [2,4]
return 2*helper(n//2)
else:
#[1,2,3,4] -> [1,3] -> 2*[1,2]-1
return 2*helper(n//2)-1
return helper(n)
