Hard Graph

  1. build graph
  2. prune infeasible branches in an early stage by comparing the steps to move to a specified node. Do not add them if move steps of new node are larger than before.
  3. Then follow standard BFS approach and recording the number of new generated nodes for the new graph from both i to j and j to i. Then the final results of reachable new added nodes will be min(n, i to j + j to i) as they may have overlaps.
from collections import deque
class Solution:
def reachableNodes(self, edges: List[List[int]], M: int, N: int) -> int:
edg = {}
graph = collections.defaultdict(list)
dp = collections.defaultdict(int)
for a,b,n in edges:
graph[a].append(b)
graph[b].append(a)
edg[(a,b)] = n
edg[(b,a)] = n
def bfs():
Q = deque([(0, 0)])
seen = collections.defaultdict(lambda: float('inf'))
seen[0] = 0
while Q:
i, d = Q.popleft()
for j in graph[i]:
n = edg[(i,j)]
if d+n+1<=M:
dp[(i,j)] = n
if seen[j] >d+n+1:
seen[j] = d+n+1
Q.append((j, d+n+1))
else:
dp[(i,j)] = max(M-d, dp[(i,j)])
return seen
seen = bfs()
res = len(seen.keys())
return res+sum(min(n, dp[(a,b)]+dp[(b,a)]) for a, b, n in edges)

864. Shortest Path to Get All Keys

class Solution:
def shortestPathAllKeys(self, grid: List[str]) -> int:
R, C = len(grid), len(grid[0])
ii, jj =0 ,0
target = 0
for i in range(R):
for j in range(C):
if grid[i][j]=='@':
ii, jj = i, j
if grid[i][j].islower():
target+=1
def bfs(i, j):
from collections import deque
Q = deque([(i,j, 0 ,set())])
seen = {(i,j,tuple(sorted(set())))}
while Q:
i,j, d, s = Q.popleft()
for di, dj in [(0,1),(1,0),(0,-1),(-1,0)]:
r, c = i+di, j+dj
if 0<=r<R and 0<=c<C:
if grid[r][c].islower():
#s1 = s
s1 = s.copy()
s1.add(grid[r][c])
if len(s1)==target:return d+1
tuple_s = tuple(sorted(set(s1)))
if (r,c,tuple_s) not in seen:
seen.add((r,c,tuple_s))
Q.append((r,c, d+1,s1))
elif grid[r][c].isupper():
if grid[r][c].lower() in s:
tuple_s = tuple(sorted(set(s)))
if (r,c,tuple_s) not in seen:
seen.add((r,c,tuple_s))
Q.append((r,c, d+1, s))
elif grid[r][c]!='#':
tuple_s = tuple(sorted(set(s)))
if (r,c,tuple_s) not in seen:
seen.add((r,c,tuple_s))
Q.append((r,c, d+1, s))
return -1
return bfs(ii,jj)
s1 = s.copy()

854. K-Similar Strings

class Solution:
def kSimilarity(self, A: str, B: str) -> int:
def graph(x: str) -> str:
i, xarr = 0, list(x)
while x[i] == B[i]:i += 1
# it means that xarr[i]!=B[i], we need find xarr[j]==B[i] and swap, at the same time, xarr[j] should not equal to B[j]
for j in range(i + 1, len(A)):
if xarr[j] == B[i] and xarr[j] != B[j]:
this_xarr = xarr[:]
this_xarr[i], this_xarr[j] = xarr[j], xarr[i]
yield ''.join(this_xarr)

def bfs():
Q, seen = collections.deque([(A, 0)]), {A}
while Q:
x, d = Q.popleft()
for y in graph(x):
if y not in seen:
if y == B:return d + 1
seen.add(y)
Q.append((y, d+1))
if A==B:return 0
return bfs()

847. Shortest Path Visiting All Nodes

class Solution:
def shortestPathLength(self, graph: List[List[int]]) -> int:
if any(len(g)==0 for g in graph):return 0
N = len(graph)
def bfs():
from collections import deque
Q = deque([(i, 0, {i}) for i in range(N)])
while Q:
i, d, seen = Q.popleft()
if len(seen)==N:return d
for j in graph[i]:
this_seen = seen | {j}
Q.append((j, d+1, this_seen))
return bfs()
class Solution:
def shortestPathLength(self, graph: List[List[int]]) -> int:
if any(len(g)==0 for g in graph):return 0
N = len(graph)
def bfs():
from collections import deque
Q = deque([(i, 0, {i}) for i in range(N)])
pruning = collections.defaultdict(lambda : float('inf'))
while Q:
i, d, seen = Q.popleft()
#pruning[tuple(sorted(seen))+(i,)]=d
if len(seen)==N:return d
for j in graph[i]:
this_seen = seen | {j}
this_key = tuple(sorted(this_seen))+(j,)
if pruning[this_key]>d+1:
pruning[this_key] = d+1
Q.append((j, d+1, this_seen))
return bfs()

842. Split Array into Fibonacci Sequence

class Solution:
def splitIntoFibonacci(self, S: str) -> List[int]:
L = len(S)
def dfs(fin_res, pre_val, val, i, cur_len):
fin_res = fin_res[:]
if len(val)>L-i:return False, []
elif len(val)==L-i:
if val == S[i:] and cur_len+1>=3:
fin_res.append(int(val))
if len(val)==1:return True, fin_res
elif S[i]!='0':return True, fin_res
else:return False, []
else:
if val == S[i:i+len(val)]:
new_val = int(val)+int(pre_val)
fin_res.append(int(val))
return dfs(fin_res, val, str(new_val), i+len(val), cur_len+1)
else:
return False, []
for i in range(1, len(S)-1):
if i>1 and S[0]=='0':continue
for j in range(1, len(S)-i):
if j>1 and S[i]=='0':continue
if i+j-1>=L:continue
pre_val, val = S[:i], S[i:i+j]
new_val = int(pre_val)+int(val)
#print(i,j, pre_val, val, new_val)
fin_res = [int(pre_val), int(val)]
good, res = dfs(fin_res, val, str(new_val), i+j, 2)
if good:
if max(res)<=2**31-1:return res
return []

834. Sum of Distances in Tree

class Solution:
def sumOfDistancesInTree(self, N: int, edges: List[List[int]]) -> List[int]:
tree = collections.defaultdict(set)
for a,b in edges:
tree[a].add(b)
tree[b].add(a)
root_nodes = [0]*N
def dfs_root_nodes(node, d,seen):
root_nodes[node] = d
seen.add(node)
for nxt_node in tree[node]:
if nxt_node not in seen:
dfs_root_nodes(nxt_node, d+1, seen.copy())
dfs_root_nodes(0, 0, set())
res = [0]*N
def node_counter(nxt_node, seen):
#print(seen)
if len(tree[nxt_node])==1:return 1
seen.add(nxt_node)
return 1+sum(node_counter(node, seen.copy()) for node in tree[nxt_node] if node not in seen)
def dfs_node_rest_nodes(node, d, seen):
#print(node)
res[node] = d
seen.add(node)
for nxt_node in tree[node]:
if nxt_node not in seen:
counter = node_counter(nxt_node, {node})
this_d = d - counter + (N-counter)
dfs_node_rest_nodes(nxt_node, this_d, seen.copy())
dfs_node_rest_nodes(0, sum(root_nodes), set())
return res
class Solution:
def sumOfDistancesInTree(self, N: int, edges: List[List[int]]) -> List[int]:
tree = collections.defaultdict(set)
res = [0] * N
count = [1] * N
for i, j in edges:
tree[i].add(j)
tree[j].add(i)
def dfs(root, pre):
for i in tree[root]:
if i != pre:
dfs(i, root)
count[root] += count[i]
res[root] += res[i] + count[i]
def dfs2(root, pre):
for i in tree[root]:
if i != pre:
res[i] = res[root] - count[i] + N - count[i]
dfs2(i, root)
dfs(0, -1)
dfs2(0, -1)
return res

827. Making A Large Island

class Solution:
def largestIsland(self, grid: List[List[int]]) -> int:
R, C = len(grid), len(grid[0])
self.uf = {}
def find(x):
self.uf.setdefault(x,x)
if x!=self.uf[x]:
self.uf[x]=find(self.uf[x])
return self.uf[x]
def union(x ,y):
self.uf[find(y)] = find(x)
ones = set()
for i in range(R):
for j in range(C):
if grid[i][j]:
x= C*i+j
ones.add(x)
neighbors = [(i+di,j+dj) for di, dj in [(1,0),(-1,0),(0,1),(0,-1)]]
for r, c in neighbors:
if 0<=r<R and 0<=c<C and grid[r][c]:
y = C*r+c
ones.add(y)
union(x,y)

cnt = collections.defaultdict(int)
for i in ones:
cnt[find(i)]+=1
if not cnt:return 1
M = max(cnt.values())
if M==0:return 1
for i in range(R):
for j in range(C):
if not grid[i][j]:
neighbors = [(i+di,j+dj) for di, dj in [(1,0),(-1,0),(0,1),(0,-1)]]
good_nei = [(r,c) for r,c in neighbors if 0<=r<R and 0<=c<C and grid[r][c]]
if good_nei:
roots = set()
for r, c in good_nei:
y = C*r+c
roots.add(find(y))
new_M = 1+sum(cnt[key] for key in roots)
M =max(M, new_M)
return M

815. Bus Routes

class Solution:
def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:
stop_bus = collections.defaultdict(set)
begin_bus = []
for i, route in enumerate(routes):
for stop in route:
if stop==S:
begin_bus.append(i)
stop_bus[stop].add(i)
if S ==T:return 0

def bfs(b):
if T in routes[b]:return 1
from collections import deque
Q = deque([(S,b, 1)])
seen_bus = {0}
while Q:
stop, bus, d = Q.popleft()
for stop in routes[bus]:
for nxt_bus in stop_bus[stop]:
if nxt_bus not in seen_bus:
if T in routes[nxt_bus]:return d+1
seen_bus.add(nxt_bus)
Q.append((stop, nxt_bus, d+1))
return -1

res = [bfs(b) for b in begin_bus]
fin_res = [r for r in res if r!=-1]
return min(fin_res) if fin_res else -1
class Solution:
def isBipartite(self, graph: List[List[int]]) -> bool:
color = {}
def dfs(pos):
for i in graph[pos]:
if i in color:
if color[i] == color[pos]:
return False
else:
color[i] = 1 - color[pos]
if not dfs(i):
return False
return True
for i in range(len(graph)):
if i not in color:
color[i] = 0
if not dfs(i):
return False
return True

--

--

--

Data Scientist/MLE/SWE @takemobi

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

App Academy W3D4

Reimagining the customer onboarding experience with Box, Salesforce, DocParser, Twilio, and…

Interview with Arnold Bansemer, Particl Desktop’s Lead Developer

Like on #Instagram #foto: http://ift.tt/2jIC4TP | @Regrann from…

OAK Network — Dapp Contest and Grant Program Launch

Vultr vs Linode vs Digitalocean: disk performance

Homebaked | Raspberry Pi + Django Home Server

The Simplest Math Problem We Still Can’t Solve — Part 1

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Jimmy Shen

Jimmy Shen

Data Scientist/MLE/SWE @takemobi

More from Medium

Fraud Prevention: Exploration-Exploitation Tradeoff in AI-based Systems

AI-powered Expert Network… What does this mean?

A look into Hierarchical clustering

What is Accuracy, Precision, Recall & F1 Score?