Một số kiến thức về lập trình ICPC

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
class MinHeap:
    def __init__(self):
        self.heap = []

    def parent(self, i):
        return (i - 1) // 2

    def left_child(self, i):
        return 2*i + 1

    def right_child(self, i):
        return 2*i + 2

    def insert(self, value):
        self.heap.append(value)
        index = len(self.heap) - 1

        while index > 0 and self.heap[self.parent(index)] > self.heap[index]:
            self.heap[self.parent(index)], self.heap[index] = self.heap[index], self.heap[self.parent(index)]
            index = self.parent(index)

    def extract_min(self):
        if not self.heap:
            return None

        min_element = self.heap[0]
        last_element = self.heap.pop()

        if len(self.heap) > 0:
            self.heap[0] = last_element
            self.heapify(0)

        return min_element

    def heapify(self, i):
        smallest = i
        left = self.left_child(i)
        right = self.right_child(i)

        if left < len(self.heap) and self.heap[left] < self.heap[smallest]:
            smallest = left

        if right < len(self.heap) and self.heap[right] < self.heap[smallest]:
            smallest = right

        if smallest != i:
            self.heap[i], self.heap[smallest] = self.heap[smallest], self.heap[i]
            self.heapify(smallest)
            
    def remove_element(self, value):
        index = self.heap.index(value)

        # Thay thế phần tử cần xóa bằng phần tử cuối cùng của heap
        self.heap[index] = self.heap[-1]
        self.heap.pop()

        # Gọi lại heapify từ vị trí thay thế
        self.heapify(index)

# Tạo một heap min
min_heap = MinHeap()

# Thêm các phần tử vào heap
min_heap.insert(4)
min_heap.insert(1)
min_heap.insert(7)
min_heap.insert(3)
min_heap.insert(13)
min_heap.insert(-3)
min_heap.insert(0)


# Trích xuất phần tử nhỏ nhất
min_element = min_heap.extract_min()

print(f"Phần tử nhỏ nhất là: {min_element}")



print("Heap trước khi xóa:", min_heap.heap)

# Xóa phần tử có giá trị 7
min_heap.remove_element(4)

print("Heap sau khi xóa:", min_heap.heap)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end_of_word = True

    def search(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end_of_word

    def starts_with(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True
    def display(self, node, prefix=""):
        if node.is_end_of_word:
            print(prefix)
        for char, child_node in node.children.items():
            self.display(child_node, prefix + char)


# Sử dụng Trie
trie = Trie()

# Thêm các từ vào trie
words = ["hello", "world", "trie", "python", "code"]
for word in words:
    trie.insert(word)

# Hiển thị thông tin của cây Trie
trie.display(trie.root)


# Kiểm tra các từ trong trie
print(trie.search("python"))  # True
print(trie.search("worlds"))  # False
print(trie.starts_with("cod"))  # True
print(trie.starts_with("abc"))  # False