Skip to content

Commit 4133885

Browse files
screnaryscrenary
committed
graph exercise
1 parent 273c34b commit 4133885

9 files changed

Lines changed: 337 additions & 0 deletions

‎dfs_802_graph_eventualSafeNodes.py‎

Lines changed: 56 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,56 @@
1+
class Solution:
2+
def eventualSafeNodes(self, graph):
3+
""" input: graph: List[List[int]]
4+
output: List[int]
5+
"""
6+
WHITE, GRAY, BLACK = 0, 1, 2
7+
color = [0] * len(graph)
8+
9+
def dfs(node):
10+
# terminate condition
11+
if color[node] != WHITE:
12+
# if this node has been visited
13+
return color[node] == BLACK
14+
15+
# visit this node
16+
color[node] = GRAY
17+
18+
# search deeper
19+
for next_node in graph[node]:
20+
if color[next_node] == BLACK:
21+
continue # search for next neighbor
22+
if color[next_node] == GRAY:
23+
return False # next node has been visited
24+
if not dfs(next_node):
25+
return False # from next node, result in cycle
26+
color[node] = BLACK
27+
return True # this node is safe
28+
29+
for i in range(len(graph)):
30+
dfs(i)
31+
res = []
32+
for i in range(len(color)):
33+
if color[i]==BLACK:
34+
res.append(i)
35+
return res
36+
37+
def eventualSafeNodes_v2(self, graph):
38+
# reverse graph for topo sort
39+
rev_graph = [[] for _ in range(len(graph))]
40+
safe = [False] * len(graph)
41+
q = []
42+
for st in range(len(graph)):
43+
if len(graph[st])==0:
44+
q.append(st) # if is end node, it's safe
45+
for ed in graph[st]:
46+
rev_graph[ed].append(st)
47+
48+
while len(q) > 0:
49+
j = q.pop(0)
50+
safe[j] = True
51+
for i in rev_graph[j]:
52+
graph[i].remove(j)
53+
if len(graph[i]) == 0:
54+
q.append(i)
55+
safe[i] = True
56+
return [i for i,v in enumerate(safe) if v]

‎dfs_graph_332_findItinerary.py‎

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
import pdb
2+
3+
class Solution:
4+
def findItinerary(self, tickets):
5+
""" input| tickets: List[List[str]]
6+
output| List[str] """
7+
# construct graph
8+
num = len(tickets)
9+
node_dict = {}
10+
for s, t in tickets:
11+
if s not in node_dict:
12+
node_dict[s] = [t]
13+
else:
14+
node_dict[s].append(t)
15+
for key in node_dict:
16+
node_dict[key].sort()
17+
# search and update graph
18+
res = ['JFK'] # init with start station
19+
out = []
20+
def dfs(res, used=0):
21+
nonlocal out
22+
# terminate condition
23+
if used == num:
24+
out.append(res.copy())
25+
return True
26+
cur_node = res[-1]
27+
if cur_node in node_dict:
28+
for _ in range(len(node_dict[cur_node])):
29+
next_node = node_dict[cur_node].pop(0)
30+
res.append(next_node)
31+
if dfs(res, used+1):
32+
return True # prun!
33+
res.pop()
34+
node_dict[cur_node].append(next_node)
35+
return False
36+
37+
dfs(res, 0)
38+
return out[0]
39+
40+
41+
if __name__=='__main__':
42+
tickets = [["JFK","KUL"],["JFK","NRT"],["NRT","JFK"]]
43+
sol = Solution()
44+
res = sol.findItinerary(tickets)
45+
print(res)

‎dp_1387_sortIntByPower.py‎

Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
"""我们将整数 x 的 权重 定义为按照下述规则将 x 变成 1 所需要的步数：
2+
3+
如果 x 是偶数，那么 x = x / 2
4+
如果 x 是奇数，那么 x = 3 * x + 1
5+
比方说，x=3 的权重为 7 。因为 3 需要 7 步变成 1 （3 --> 10 --> 5 --> 16 --> 8 --> 4 --> 2 --> 1）。
6+
7+
给你三个整数 lo， hi 和 k 。你的任务是将区间 [lo, hi] 之间的整数按照它们的权重 升序排序 ，如果大于等于 2 个整数有 相同 的权重，那么按照数字自身的数值 升序排序 。
8+
请你返回区间 [lo, hi] 之间的整数按权重排序后的第 k 个数。
9+
注意，题目保证对于任意整数 x （lo <= x <= hi） ，它变成 1 所需要的步数是一个 32 位有符号整数。
10+
链接：https://leetcode-cn.com/problems/sort-integers-by-the-power-value
11+
12+
DP, compute and save smaller integer's power value, which can be used to compute larger value
13+
DFS + Dict
14+
S[n]: the power value of num n
15+
S[n] = S[n*3 + 1], if n%2==1
16+
= S[n/2], if n%2==0
17+
"""
18+
19+
20+
class Solution:
21+
def getKth(self, lo, hi, k):
22+
""" input| lo: int, hi: int, k:int
23+
output| int """
24+
# init the states dict
25+
S_dict = {1:0, 2:1}
26+
27+
def dfs(n):
28+
# update S_dict and output
29+
if n not in S_dict:
30+
if n % 2 == 0:
31+
S_dict[n] = dfs(n/2) + 1
32+
elif n % 2 == 1:
33+
S_dict[n] = dfs(n*3+1) + 1
34+
return S_dict[n]
35+
36+
for n in range(lo, hi+1):
37+
dfs(n)
38+
res_list = sorted(range(lo, hi+1), key=lambda x: S_dict[x])
39+
# print(res_list)
40+
return res_list[k-1]
41+
42+
43+
if __name__ == '__main__':
44+
lo = 7
45+
hi = 11
46+
k = 4
47+
sol = Solution()
48+
res = sol.getKth(lo, hi, k)
49+
print(res)

‎graph_1042_gardenNoAdj.py‎

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
import pdb
2+
3+
class Solution:
4+
def gardenNoAdg(self, N, paths):
5+
""" input| N: int, paths: list[int]
6+
output| res: List[int]
7+
"""
8+
# get adjacent dict, graph={node:[neighbors]}
9+
graph = {i+1:[] for i in range(N)}
10+
for edge in paths:
11+
st, ed = edge
12+
# two-way path
13+
graph[st].append(ed)
14+
graph[ed].append(st)
15+
# paint from larger degree gardens
16+
nodes = sorted(graph, key=lambda x: len(graph[x]), reverse=True)
17+
planted = [0] * (N+1)
18+
for node in nodes:
19+
# init color set
20+
color = [1,2,3,4]
21+
# check neighbors
22+
# pdb.set_trace()
23+
for nei in graph[node]:
24+
if planted[nei] in color:
25+
color.remove(planted[nei])
26+
# we know that, node must can be colored
27+
planted[node] = color[0]
28+
return planted[1:]
29+
30+
31+
if __name__ == '__main__':
32+
sol = Solution()
33+
N = 3
34+
paths = [[1,2],[2,3],[3,1]]
35+
res = sol.gardenNoAdg(N, paths)
36+
print(res)

‎graph_1334_findTheCity.py‎

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
# undirected graph, find the neighbors within the distance threshold; Then return the node with least neighbors
2+
from collections import defaultdict
3+
4+
5+
class Solution:
6+
def findTheCity(self, n, edges, distanceThreshold):
7+
""" input| n: int, edges: List[List[int]], distanceThreshold: int
8+
output| int
9+
"""
10+
# init the undirected graph
11+
graph = [[100000] * n for _ in range(n)]
12+
for i in range(n):
13+
graph[i][i] = 0
14+
for edge in edges:
15+
s, t, w = edge
16+
graph[s][t] = w
17+
graph[t][s] = w
18+
19+
# compute min dist between all nodes
20+
# Floyd-Warshall
21+
for k in range(n):
22+
for i in range(n):
23+
for j in range(n):
24+
if graph[i][j] > graph[i][k] + graph[k][j]:
25+
graph[i][j] = graph[i][k] + graph[k][j]
26+
# output
27+
min_nei = n
28+
min_node = 0
29+
for i in range(n):
30+
cur_nei = 0
31+
for j in range(n):
32+
if graph[i][j] <= distanceThreshold:
33+
cur_nei += 1
34+
if cur_nei <= min_nei:
35+
min_nei = cur_nei
36+
min_node = i
37+
38+
return min_node

‎graph_1514_maxProbabilityPath.py‎

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
from collections import defaultdict
2+
import heapq
3+
import math
4+
5+
6+
class Solution:
7+
def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
8+
""" input| n: int, edges: List[List[int]], succProb: List[float], start: int, end: int
9+
output| float """
10+
# construct nondirection graph
11+
graph = defaultdict(dict)
12+
for i, edge in enumerate(edges):
13+
prob = succProb[i]
14+
s, t = edge
15+
graph[s][t] = prob
16+
graph[t][s] = prob
17+
q = [(0, start)] # (dist=-log(prob), node), the Source Set in Dijkstra algorithm
18+
visited = {start}
19+
while q:
20+
prob, node = heapq.heappop(q)
21+
if node == end:
22+
return math.exp(-prob)
23+
visited.add(node)
24+
for nxt in graph[node]:
25+
if nxt not in visited:
26+
heapq.heappush(q, (prob - math.log(graph[node][nxt]), nxt)) # dist[node] + dist[node][nxt] as dist[nxt]
27+
return 0

‎graph_743_networkDelayTime.py‎

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
from collections import defaultdict
2+
import heapq
3+
4+
class Solution:
5+
def networkDelayTime(self, times, N, K):
6+
""" input| times: List[List[int]], N: int, K: int
7+
output| int
8+
"""
9+
# Dijkstra
10+
# init graph
11+
graph = defaultdict(dict)
12+
for time in times:
13+
u, v, w = time
14+
graph[u][v] = w
15+
q = [(0, K)] # source node inqueue, heap
16+
visited = set() # source set
17+
# borad first search
18+
while q:
19+
time, node = heapq.heappop(q)
20+
visited.add(node)
21+
if len(visited) == N:
22+
return time
23+
for nei in graph[node]:
24+
if nei not in visited:
25+
heapq.heappush(q, (time + graph[node][nei], nei))
26+
if len(visited) < N:
27+
return -1

‎sort_quick.py‎

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
import pdb
2+
3+
class Solution:
4+
def sortArray(self, nums):
5+
# quick sort, in-place, search in [left, right]
6+
def quick_sort(nums, left, right):
7+
# print(left, right, nums)
8+
# pdb.set_trace()
9+
if left < right:
10+
pivot = partition(nums, left, right) # operation
11+
quick_sort(nums, left, pivot-1) # dive deeper
12+
quick_sort(nums, pivot+1, right)
13+
14+
def partition(nums, left, right):
15+
# get the partition idx
16+
base = nums[left]
17+
while left < right:
18+
while (left < right) and (nums[right] >= base):
19+
right -= 1 # stop when met smaller or equal val
20+
nums[left] = nums[right]
21+
while (left < right) and (nums[left] < base):
22+
left += 1 # stop when met greater val
23+
nums[right] = nums[left]
24+
# when left == right, and nums[left]<=base
25+
nums[left] = base
26+
# pdb.set_trace()
27+
return left
28+
29+
quick_sort(nums, 0, len(nums)-1)
30+
return nums
31+
32+
if __name__ == '__main__':
33+
sol = Solution()
34+
nums = [5,2,3,1]
35+
res = sol.sortArray(nums)
36+
print(nums)

‎xiang_nan.py‎

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
2+
a = ['69', '159', '253', '325', '98', '509', '125', '364', '129', '205', '304', '299', '164', '174', '182', '142', '13', '220', '296', '85', '106', '462', '238', '118', '291', '165', '256', '198', '89', '213', '117', '156', '76', '49', '16', '232', '110', '331', '620', '447', '467', '463', '193', '120', '312', '114', '405', '278', '626', '276', '260', '183', '128', '247', '418', '206', '339', '72', '36', '303', '327', '302', '273', '338', '172', '211', '74', '26', '38', '194', '113', '268', '288', '3', '41', '192', '401', '84', '173', '240', '77', '53', '44', '224', '374', '163', '87', '223', '257', '230', '31', '96', '59', '57', '58', '219', '180', '112', '46', '130', '50', '75', '137', '286', '297', '239', '153', '115', '321', '143', '340', '449', '148', '184', '300', '293', '140', '93', '337', '254', '231', '506', '510', '310', '61', '176', '210', '316', '134', '341', '227', '24', '423', '349', '107', '453', '175', '55', '169', '292', '246', '343', '188', '181', '186', '17', '307', '7', '35', '195', '18', '168', '277', '241', '14', '100', '289', '138', '80', '520', '166', '67', '178', '515', '126', '141', '522', '332', '149', '263', '282', '4', '29', '56', '94', '5', '22', '119', '145', '48', '133', '66', '243', '309', '127', '459', '342', '261', '344', '503', '454', '160', '290', '491', '233', '25', '97', '451', '157', '354', '37', '15', '283', '313', '52', '575', '574', '414', '103', '144', '214', '502', '199', '90', '251', '51', '116', '258', '507', '123', '71', '394', '280', '279', '322', '86', '490', '426', '54', '365', '30', '570', '571', '359', '60', '328', '472', '471', '32', '217', '152', '330', '68', '376', '43', '21', '264', '131', '334', '20', '597', '335', '255', '40', '108', '47', '42', '91', '45', '244', '236', '73', '191', '284', '39', '323', '27', '161', '287', '274', '333', '487', '489', '346', '383', '484', '146', '294', '319', '34', '177', '197', '226', '111', '596', '605', '190', '619', '317', '623', '81', '33', '497', '229', '345', '413', '420', '488', '591', '494', '476', '23', '242', '158', '212', '624', '109', '464', '225', '505', '493', '460', '461', '305', '527', '234', '468', '600', '432', '167', '202', '590', '385', '482', '478', '326', '154', '88', '196', '406', '314', '272', '28', '252', '121', '275', '486', '514', '318', '285', '350', '99', '308', '315', '366', '417', '298', '511', '170', '92', '320', '135', '457', '353', '523', '458', '425', '203', '381', '306', '62', '301', '237', '442', '348', '259', '492', '311', '402', '501', '19', '208', '228', '504', '248', '218', '347', '295', '222', '370', '324', '124', '465', '245', '329', '477', '439', '437', '470', '598', '185', '625', '281', '207', '481', '250', '434', '204', '604', '416', '622', '441', '444', '508', '500', '475', '594', '551', '419', '132', '427', '162', '122', '485', '171', '495', '474', '552', '547', '215', '422', '499', '9', '603', '373', '483', '599', '448', '368', '572', '267', '589', '136', '382', '216', '179', '201', '147', '456', '6', '518', '532', '524', '2', '150', '498', '412', '411', '531', '496', '526', '352', '102', '378', '550', '573', '440', '438', '249', '375', '351', '403', '446', '356', '270', '431', '11', '525', '209', '602', '601', '377', '577', '559', '262', '400', '466', '469', '399', '436', '479', '424', '12', '580', '480', '592', '519', '517', '445', '576', '452', '265', '443', '421', '392', '393', '200', '428', '450', '455', '544', '336', '388', '390', '95', '553', '367', '410', '407', '583', '535', '415', '433', '429', '391', '564', '563', '555', '588', '101', '409', '569', '538', '541', '546', '369', '408', '554', '271', '543', '540', '430', '355', '557', '435', '579', '593', '386', '585', '536', '587', '542', '549', '528', '384', '595', '566', '530', '567', '396', '395', '627', '545', '533', '586', '584', '562', '578', '398', '534', '548', '529', '537', '621', '560', '568', '539', '558', '561', '582', '581', '628', '631', '630', '659', '657', '639', '636', '635', '638', '637', '643', '655', '641', '658', '660', '646', '640', '644', '654', '650', '656', '662', '661', '663', '632', '664']
3+
4+
b = ['69', '159', '253', '325', '98', '509', '125', '364', '129', '205', '304', '299', '164', '174', '182', '142', '13', '220', '296', '85', '106', '462', '238', '118', '291', '165', '256', '198', '89', '213', '117', '156', '76', '49', '16', '232', '110', '331', '620', '447', '467', '463', '193', '120', '312', '114', '405', '278', '626', '276', '260', '183', '128', '247', '418', '206', '339', '72', '36', '303', '327', '302', '273', '338', '172', '211', '74', '26', '38', '194', '113', '288', '3', '41', '192', '401', '84', '173', '240', '77', '53', '44', '224', '374', '163', '87', '223', '257', '230', '31', '96', '59', '57', '58', '219', '180', '112', '46', '130', '50', '75', '137', '286', '297', '239', '153', '115', '321', '143', '340', '449', '148', '184', '300', '293', '140', '93', '337', '254', '231', '506', '510', '310', '61', '176', '210', '316', '134', '227', '24', '423', '349', '107', '453', '175', '55', '169', '292', '246', '343', '188', '181', '186', '17', '307', '7', '195', '18', '168', '277', '241', '14', '100', '289', '138', '80', '520', '166', '67', '178', '515', '126', '141', '522', '332', '149', '282', '4', '29', '56', '94', '5', '22', '119', '145', '48', '133', '66', '243', '309', '127', '459', '342', '261', '344', '503', '454', '160', '290', '491', '233', '25', '97', '451', '157', '354', '37', '15', '283', '313', '52', '575', '574', '414', '103', '144', '214', '502', '199', '90', '251', '51', '116', '258', '507', '123', '71', '394', '280', '279', '322', '86', '490', '426', '54', '365', '30', '570', '571', '359', '60', '328', '472', '471', '32', '217', '152', '330', '68', '376', '43', '21', '264', '131', '334', '20', '335', '255', '40', '108', '47', '42', '91', '45', '244', '236', '73', '191', '284', '39', '323', '27', '161', '287', '274', '333', '487', '489', '346', '383', '484', '146', '294', '319', '34', '177', '197', '226', '111', '596', '605', '190', '317', '623', '81', '33', '497', '229', '345', '413', '420', '488', '494', '476', '23', '242', '158', '212', '624', '109', '464', '225', '505', '493', '460', '461', '305', '527', '234', '468', '432', '167', '202', '590', '385', '482', '478', '326', '154', '88', '196', '406', '314', '272', '28', '252', '121', '275', '486', '514', '318', '285', '350', '99', '308', '315', '366', '417', '298', '511', '170', '92', '320', '135', '457', '353', '523', '458', '425', '203', '381', '306', '62', '301', '237', '442', '348', '259', '492', '311', '402', '501', '19', '208', '228', '504', '248', '218', '347', '295', '222', '370', '324', '124', '465', '245', '329', '477', '439', '437', '470', '598', '185', '281', '207', '481', '250', '434', '604', '416', '622', '441', '444', '508', '500', '475', '594', '551', '419', '132', '427', '162', '122', '485', '171', '495', '474', '552', '547', '215', '422', '499', '373', '483', '448', '368', '267', '589', '136', '382', '216', '179', '201', '147', '456', '6', '518', '532', '524', '2', '150', '498', '412', '411', '531', '496', '526', '352', '102', '378', '249', '351', '403', '446', '356', '270', '431', '11', '525', '209', '602', '601', '377', '559', '262', '400', '466', '469', '399', '436', '479', '424', '480', '592', '519', '517', '445', '576', '265', '443', '421', '392', '393', '200', '428', '450', '544', '336', '388', '390', '95', '367', '407', '583', '433', '391', '564', '563', '555', '588', '101', '541', '546', '408', '554', '271', '543', '430', '355', '435', '579', '593', '585', '542', '549', '528', '566', '530', '395', '627', '545', '586', '584', '578', '534', '548', '537', '621', '568', '558', '561', '628', '631', '630', '659', '657', '639', '636', '635', '638', '637', '643', '655', '641', '658', '660', '640', '644', '654', '656', '661', '663', '632']
5+
6+
if __name__ == '__main__':
7+
print(len(a), len(b))
8+
# for s in b:
9+
# if s not in a:
10+
# print(s)
11+
# temp = []
12+
# for s in a:
13+
# if s not in temp:
14+
# temp.append(s)
15+
# print(len(temp))
16+
temp = 0
17+
for s in a:
18+
if s not in b:
19+
temp += 1
20+
# print(temp)
21+
i = a.index(s)
22+
# del a[i]
23+
print(temp)

0 commit comments

Comments
 (0)