LeetCode 641: Design Circular Deque
Tôi đang đăng một giải pháp cho "Design Circular Deque" của LeetCode. Nếu bạn muốn xem lại, vui lòng làm như vậy. Cảm ơn bạn!
Vấn đề
Thiết kế việc triển khai hàng đợi hai đầu tròn (deque) của bạn.
Việc triển khai của bạn phải hỗ trợ các hoạt động sau:
MyCircularDeque(k): Constructor, đặt kích thước của deque là k.insertFront(): Thêm một mục ở phía trước Deque. Trả về true nếu hoạt động thành công.insertLast(): Thêm một mục ở phía sau Deque. Trả về true nếu hoạt động thành công.deleteFront(): Xóa một mục khỏi mặt trước của Deque. Trả về true nếu hoạt động thành công.deleteLast(): Xóa một mục từ phía sau Deque. Trả về true nếu hoạt động thành công.getFront(): Nhận vật phẩm phía trước từ Deque. Nếu deque trống, trả về -1.getRear(): Nhận vật phẩm cuối cùng từ Deque. Nếu deque trống, trả về -1.isEmpty(): Kiểm tra xem Deque có trống hay không.isFull(): Kiểm tra xem Deque đã đầy hay chưa.
Thí dụ:
MyCircularDeque circularDeque = new MycircularDeque(3); // set the size to be 3
circularDeque.insertLast(1); // return true
circularDeque.insertLast(2); // return true
circularDeque.insertFront(3); // return true
circularDeque.insertFront(4); // return false, the queue is full
circularDeque.getRear(); // return 2
circularDeque.isFull(); // return true
circularDeque.deleteLast(); // return true
circularDeque.insertFront(4); // return true
circularDeque.getFront(); // return 4
Ghi chú:
- Tất cả các giá trị sẽ nằm trong khoảng [0, 1000].
- Số lượng các phép toán sẽ nằm trong khoảng [1, 1000].
- Vui lòng không sử dụng thư viện Deque cài sẵn.
Mã:
// The following block might slightly improve the execution time;
// Can be removed;
static const auto __optimize__ = []() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
// Most of headers are already included;
// Can be removed;
#include <cstdint>
#include <vector>
struct MyCircularDeque {
MyCircularDeque(int k): stream(k, 0), counts(0), k(k), head(k - 1), tail(0) {}
const bool insertFront(
const int value
) {
if (isFull()) {
return false;
}
stream[head] = value;
--head;
head += k;
head %= k;
++counts;
return true;
}
const bool insertLast(const int value) {
if (isFull()) {
return false;
}
stream[tail] = value;
++tail;
tail %= k;
++counts;
return true;
}
const bool deleteFront() {
if (isEmpty()) {
return false;
}
++head;
head %= k;
--counts;
return true;
}
const bool deleteLast() {
if (isEmpty()) {
return false;
}
--tail;
tail += k;
tail %= k;
--counts;
return true;
}
const int getFront() {
return isEmpty() ? -1 : stream[(head + 1) % k];
}
const int getRear() {
return isEmpty() ? -1 : stream[(tail - 1 + k) % k];
}
const bool isEmpty() {
return !counts;
}
const bool isFull() {
return counts == k;
}
private:
using ValueType = std::uint_fast16_t;
std::vector<ValueType> stream;
ValueType counts;
ValueType k;
ValueType head;
ValueType tail;
};
Trả lời
Sử dụng cùng một loại cho nội dung deque và các kích thước / chỉ số (
k, count, head, tail) có vẻ sai. Ít nhất,kvàcountnên đượcstd::vector::size_type.Vì bạn đang sao lưu deque với
std::vector, làm choheadvàtailgiaostd::vector::iteratordiện trông có vẻ thành ngữ hơn.kkhông phải là tên mô tả nhiều nhất. Hãy cân nhắccapacity.Tôi không chắc đó
std::vectorlà vật chứa tốt nhất để sao lưu deque có kích thước cố định. Rốt cuộc, vấn đềstd::vectorlà phải có một kích thước động.std::array, hoặc thậm chí một mảng kiểu C cũ đơn giản, trông tự nhiên hơn.
Bạn có thể gọi stream.reserve(k)hàm tạo để cải thiện hiệu quả của vectơ vì bạn biết rằng bạn sẽ chỉ có kcác phần tử, vì vậy .reserve()sẽ cấp phát trước bộ nhớ.
Ưu tiên sử dụng std::size_thơnint
int k sẽ làstd::size_t k
Bạn chưa khai báo hàm tạo bản sao cũng như toán tử gán bản sao . Điều này có thể gây ra sự cố nếu bạn muốn gán cái này Dequecho cái khác.
Nội tuyến một số chức năng thành viên của bạn structnhư isEmpty(), getRear(), getFront() có thể cải thiện hiệu suất của container của bạn, nhưng nó sẽ là một thương mại cho không gian.
Nếu bạn đang làm điều này với mục đích duy nhất là hoàn thành thử thách, bạn có thể bỏ qua phần tiếp theo
Mẫu
Ngay bây giờ, bạn nhất dequeđịnh phải sử dụng std::uint_fast16_t. Nhưng nếu tôi muốn làm một dequecái tên thì sao? Hoặc một dequegiá trị thập phân khác nhau? Tôi không thể chỉ tạo 15 lớp cho mỗi kiểu dữ liệu.
Do đó, tôi sẽ sử dụng các mẫu trong C ++ để tôi có thể tạo một cái chung deque .
Cú pháp đơn giản
template < typename T >
struct deque
{
public:
// public member functions
private:
std::vector< T > stream;
};
Bây giờ khi bạn muốn tạo một deque mới, bạn có thể làm deque<any_data_type> my_deque.
Bất cứ nơi nào bạn muốn sử dụng ValueType, bạn thay thế nó bằng T.
Những gì C ++ làm là nó lấy any_data_typevà thay thế Tbằng kiểu dữ liệu đó trong thời gian biên dịch . Thực hiện điều này trong chương trình của bạn sẽ dạy cho bạn rất nhiều về cách các mẫu hoạt động trong C ++, điều này sẽ hữu ích trong các dự án tương lai của bạn.
Mẫu trong C ++
Tôi nghĩ đây là một chủ đề cho mã của bạn:, constnơi bạn đã đặt nó, không có lợi ích gì; và nó bị thiếu ở những nơi khác mà nó phải ở đó. Mọi hàm đơn lẻ trong MyCircularDequenên bỏ constra trước, bởi vì các giá trị trả về đó là vô hướng nên việc đánh dấu chúng constthực sự không có tác dụng. insertLast(const int value)có tác dụng hơn một chút nhưng thực sự không quan trọng.
Nơi quan trọng nhất cần đặt constlà sửa đổi hằng số thischo phương thức getvà của bạn is. Chúng cần phải constđược thêm vào sau dấu ngoặc đơn. Điều này đăng ký một lời hứa rằng các phương thức không sửa đổi bất kỳ thành viên nào.