Cài đặt Queue với hàm min
algorithm
33
White

kiennt viết ngày 08/10/2016

Queue với hàm min

Yêu cầu: cài đặt cấu trúc dữ liệu Queue với 3 hàm

  • enqueue
  • dequeue
  • min

Một cách dễ thấy, nếu sử dụng PriorityQueue ở đây, thì tất cả 3 hàm trên đều có độ phức tạp là O(logN). Vậy làm sao chúng ta có thể cài đặt Queue vởi cả 3 thao tác trên bằng O(1)

Để làm bài toán này, hãy xét 2 bài toán nhỏ hơn:

  1. Cài đặt MinStack với 3 hàm push, pop, min
  2. Cài đặt Queue bằng 2 Stack.

Cài đặt MinStack

Để cài đặt MinStack, chúng ta để ý nếu chúng ta lưu lại min_value của Stack, tại head, thì khi push, và pop, chúng ta vẫn có thể thao tác bằng O(1)

Vậy nên, để cài MinStack, chúng ta sẽ lưu Node bằng một cấu trúc dữ liệu như sau

class Node(object):

    def __init__(self, value):
        self.value = value
        self.min_value = None
        self.next = None

    def set_next(self, next):
        if next is not None:
            self.min_value = min(self.value, next.min_value)
        self.next = next

Sau khi cài đặt Node như trên, MinStack có thể cài đặt như sau

class MinStack(object):

    def __init__(self):
        self.head = None

    def is_empty(self):
        return self.head is None

    def push(self, value):
        node = Node(value)
        if self.head is None:
            node.min_value = value
        else:
            node.set_next(self.head)
        self.head = node

    def pop(self):
        if self.head is None:
            raise Exception
        old_head = self.head
        self.head = old_head.next
        return old_head.value

    def min(self):
        if self.head is None:
            raise Exception
        return self.head.min_value

MinStack cả 3 thao tác push, pop, min đều có độ phức tạp O(1)

Cài đặt MinQueue bằng 2 MinStack

Bài toán này đã được anh em ở #hardcore discuss hôm trước

class MinQueue(object):

    def __init__(self):
        self.stack1 = MinStack()
        self.stack2 = MinStack()

    def enqueue(self, value):
        self.stack1.push(value)

    def dequeue(self):
        if self.stack2.is_empty():
            while not self.stack1.is_empty():
                value = self.stack1.pop()
                self.stack2.push(value)

        if self.stack2.is_empty():
            raise Exception

        return self.stack2.pop()

    def min(self):
        is_empty1 = self.stack1.is_empty()
        is_empty2 = self.stack2.is_empty()
        if is_empty1 and is_empty2:
            raise Exception
        if is_empty1:
            return self.stack2.min()
        elif is_empty2:
            return self.stack1.min()
        return min(self.stack1.min(), self.stack2.min())

Bình luận


White
{{ comment.user.name }}
Bỏ hay Hay
{{comment.like_count}}
Male avatar
{{ comment_error }}
Hủy
   

Hiển thị thử

Chỉnh sửa

White

kiennt

30 bài viết.
288 người follow
Kipalog
{{userFollowed ? 'Following' : 'Follow'}}
Cùng một tác giả
White
93 18
Mọi chuyện bắt đầu từ nắm 2013 trong quá trình xây dựng chức năng login với Facebook, tôi đã tìm ra một cách để tấn công vào các hệ thống login với...
kiennt viết hơn 2 năm trước
93 18
White
64 4
Trong tuần vừa rồi, mình có đọc chương 7 cuốn sách (Link). Bài viết này nhằm mục đích giúp mình tổng hợp lại những kiến thức đã học được về chương ...
kiennt viết 6 tháng trước
64 4
White
29 5
1. Đặt vấn đề Một trong các vấn đề của một hệ thống backend là bài toán điều phối request tới các nguồn dữ liệu. Xét bài toán với một hệ thống bl...
kiennt viết 2 năm trước
29 5
Bài viết liên quan
White
44 7
Là một người thường xuyên đọc Quora, có một điểm cá nhân tôi thấy rất ấn tượng ở quora chính là khả năng autocomplete với tốc độ ánh sáng. (Ảnh) ...
huydx viết 10 tháng trước
44 7
White
3 0
What is competitive programming? Sites like CodeForces, TopCoder, HackerRank, CodeChef,... ACMICPC, Olympiad in Informatics (for high school stude...
Nguyễn Lê Vũ Long viết hơn 1 năm trước
3 0
White
76 34
Bài viết thuộc chủ đề nghiên cứu trong nhóm hardcore của Cộng đồng Ruby Việt Nam Đọc manga trên mobile là một nhu cầu rất lớn, nhưng hiện nay chư...
Huy Trần viết gần 2 năm trước
76 34
{{like_count}}

kipalog

{{ comment_count }}

bình luận

{{liked ? "Đã kipalog" : "Kipalog"}}


White
{{userFollowed ? 'Following' : 'Follow'}}
30 bài viết.
288 người follow

 Đầu mục bài viết

Vẫn còn nữa! x

Kipalog vẫn còn rất nhiều bài viết hay và chủ đề thú vị chờ bạn khám phá!