bạn trên dùng F# mà, tôi khá chắc luôn.
Nhưng mà mấy cái này không phổ biến lắm nhỉ, k biết thim kia học làm gìbạn trên dùng F# mà, tôi khá chắc luôn.
hai thằng này syntax gần như tương tự, nhưng F# thì có name convention của C# là function là pascal case :v
p/s: thực ra cũng chả có gì to tát, cơ mà vấn đề là bảo sai language paste vào nó không chạy
ocaml thì đúng là không phổ biến, nhưng F# thì đang lên ngon, thi thoảng vẫn leo vào top 10.
FP code ngắn hơn OOP ~50%
Mà code cái gì cảm thấy vui là được, quan trọng gì.
xài cái hàm sort thì O gì nữa phen, ông có biết ở dưới hàm sort đó nó implement cái thuật toán sort nào đâu. bài này O(n) được. Duyệt từng phần tử rồi add vào một cái mảng có 3 phần tử. nếu mảng full rồi thì so sánh với 3 phần tử(result) đó rồi thay thế số vừa so sánh cho phần tử nhỏ nhất. lúc return thì if result[1] = result[2] return result[0] else return result[2].
Mới xong phần learn Array 101. Thôi tui quay về với chính đạo đây. Chiều giờ muốn banh não
dễ thế này cũng hỏi à fen
Thấy không ai nhận nên mình thử làm cho vui (Bảo đảm chỉ đúng với 2 test cases trong bài
, anh em chém nhè nhẹ @Nipin ):
from collections import defaultdict
def make_rooted_tree(list_of_lists):
element_dict = defaultdict(list)
root = 0
ret = []
print("Input: {}".format(list_of_lists))
for i in range(0, len(list_of_lists)):
element_dict[list_of_lists[i][0]].append(list_of_lists[i][1])
# find root and candidates to delete
# find root node
parents = list(element_dict.keys())
children = list(element_dict.values())
children = [item for sublist in children for item in sublist]
children = list(set(children))
print("List of parent nodes: {}".format(parents))
print("List of children nodes: {}".format(children))
# case A: if node in parents but not in children, it's a root
for value in parents:
if value not in children:
root = value
break
# case B: if root cannot be found above, choose the node with the most children
if root == 0:
max_children = 0
for key in element_dict:
number_of_chidlren = len(element_dict[key])
if number_of_chidlren > max_children:
max_children = number_of_chidlren
root = key
print("Root node is {}".format(root))
# find candidate edges to delete
children_of_root = element_dict[root]
print(children_of_root)
# if both nodes of an edge are children of root, then it should be removed
for key in element_dict:
if key in children_of_root:
list_of_key_children = element_dict[key]
for child in list_of_key_children:
if child in children_of_root:
ret.append([key, child])
# if root is a child of a node, edge [node,root] should be removed
for key in element_dict:
if root in element_dict[key]:
ret.append([key, root])
return ret
if __name__ == "__main__":
a = [[1, 2], [1, 3], [2, 3]]
b = [[1, 2], [2, 3], [3, 4], [4, 1], [1, 5]]
deleted_edge_a = make_rooted_tree(a)
print("Edge to be deleted: {} \n ==========================================================".format(deleted_edge_a))
deleted_edge_b = make_rooted_tree(b)
print("Edge to be deleted: {} \n ==========================================================".format(deleted_edge_b))
Dùng Disjoint Set:
class Solution:
def findRedundantConnection(self, edges):
arr = [i for i in range(len(edges))]
for a, b in edges:
if self.find(arr, a-1, b-1):
return [a, b]
self.union(arr, a-1, b-1)
return "lmao"
def root(self, arr, a):
while arr[a] != a:
a = arr[a]
return a
def union(self, arr, a, b):
arr[self.root(arr, a)] = arr[self.root(arr, b)]
def find(self, arr, a, b):
return self.root(arr, a) == self.root(arr, b)Thank you. Hôm nay học thêm được 1 cái data structure mới
Này là tìm cạnh mà 2 đầu nó có chung 1 root thôi bácthực sự là đọc code này tui ko hiểu gì
À ok fen, khá hay, tui hiểu rùi
Cách này sai nhé, bài này là directed graph, phản ví dụ: [[2,3],[3,4],[1,4],[1,2]]
Tôi nghĩ vẫn áp dụng được cho DAG, khi duyệt các cạnh của đồ thị ví dụ cạnh e: u->v. nếu u và v chưa trong một cây thì việc chọn root cho một DisjoinSet sẽ là u mà không phải v. Như vậy là thỏa mãn.
Cái ví dụ [[2,3],[3,4],[1,4],[1,2]] là DAG chứ j nữa?
Ý là thuật toán dùng DU vẫn đúng ấy, fix tẹo thôi
Cách làm như thế thì chỉ xét cái edge có connect 2 node cùng thuộc connected component hay ko, nếu chọn root khác thì cũng vậy thôi. Thứ 2 là hướng của edge cũng ko xử lý. Ví dụ: 1->2, 2<-3, chẳng lẽ 1 vs 3 cùng thuộc component?
