Thiết kế giải pháp leetcode danh sách liên kết C++

Một nút trong danh sách liên kết đơn phải có hai thuộc tính. val và 2. val là giá trị của nút hiện tại và next là con trỏ/tham chiếu đến nút tiếp theo

Nếu muốn sử dụng danh sách liên kết kép thì cần thêm 1 thuộc tính prev để chỉ nút trước đó trong danh sách liên kết. Giả sử tất cả các nút trong danh sách được liên kết đều được lập chỉ mục 0

Triển khai lớp MyLinkedList

Cấu trúc của MyLinkedList của chúng tôi

• MyLinkedList() Khởi tạo đối tượng MyLinkedList
• val0 Lấy giá trị của nút val1 trong danh sách liên kết. Nếu chỉ mục không hợp lệ, hãy trả lại val2
• val3 Thêm một nút có giá trị val trước phần tử đầu tiên của danh sách liên kết. Sau khi chèn, nút mới sẽ là nút đầu tiên của danh sách liên kết
• val5 Nối một nút có giá trị val làm phần tử cuối cùng của danh sách liên kết
• val7 Thêm một nút có giá trị val trước nút val1 trong danh sách liên kết. Nếu next0 bằng độ dài của danh sách được liên kết, nút sẽ được thêm vào cuối danh sách được liên kết. Nếu next0 lớn hơn chiều dài, nút sẽ không được chèn
• next2 Xóa nút val1 trong danh sách liên kết, nếu chỉ mục hợp lệ

ví dụ 1

Input
["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"]
[[], [1], [3], [1, 2], [1], [1], [1]]
Output
[null, null, null, null, 2, null, 3]Explanation
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addAtHead(1);
myLinkedList.addAtTail(3);
myLinkedList.addAtIndex(1, 2);    // linked list becomes 1->2->3
myLinkedList.get(1);              // return 2
myLinkedList.deleteAtIndex(1);    // now the linked list is 1->3
myLinkedList.get(1);              // return 3

Hạn chế

• next4
• Vui lòng không sử dụng thư viện LinkedList tích hợp
• Tối đa next5 cuộc gọi sẽ được thực hiện tới next6, next7, next8, next9 và val0

Suy nghĩ của tôi

Cá nhân tôi thích những nhiệm vụ như thế này. Nó có thể được giải quyết bằng một số cách khác nhau mà nếu chúng tôi mô tả chúng, bạn sẽ cảm thấy nhàm chán và mệt mỏi khi đọc từng ấy thông tin. Nhiệm vụ này có thể giúp bạn xây dựng hoặc cải thiện kỹ năng chia nhiệm vụ thành các phần nhỏ hơn. Một lần nữa, đó là kỹ năng cực kỳ quan trọng nếu bạn muốn trở thành một kỹ sư phần mềm giỏi. Nếu bạn đã có kinh nghiệm về thuật toán và cấu trúc dữ liệu, bạn có thể làm một số thứ như thế này

Giải pháp đơn giản nhất cho nhiệm vụ

Hoàn toàn ổn khi giải quyết vấn đề theo cách này nhưng nó chỉ hoạt động khi bạn đã biết cách LinkedList hoạt động và bạn có thể triển khai nó từ đầu. Trong khi cách tiếp cận trên có thể giúp bạn tiết kiệm thời gian. Tôi khuyên bạn nên tìm hiểu sâu hơn và triển khai phiên bản LinkedList của riêng mình. Tôi khá chắc rằng nhiều bạn biết nó hoạt động như thế nào nhưng khi tôi yêu cầu bạn thực hiện thì một số bạn có thể gặp khó khăn

Tôi nghĩ rằng sau khi bạn đọc hoặc học một cái gì đó, bạn nên thực hiện những gì bạn vừa học. Nó sẽ giúp bạn hiểu cấu trúc dữ liệu này hoạt động như thế nào và nó có thể được sử dụng ở đâu. Kiến thức bạn có sẽ được ghi nhớ tốt hơn

lý luận

Như tôi đã nói, nhiệm vụ này là một ví dụ hoàn hảo về việc chúng ta có thể chia một nhiệm vụ lớn thành những nhiệm vụ nhỏ hơn. Vì vậy, hãy cố gắng hiểu làm thế nào để làm điều đó

Có vẻ như chúng ta cần triển khai ít nhất 5 phương pháp khác nhau. Đó là một điểm khởi đầu tuyệt vời. Trong khi có bức tranh toàn cảnh hơn trong đầu, chúng ta có thể tập trung vào bài toán con cụ thể mà mọi phương pháp đều phải giải quyết. Hãy giải quyết từng vấn đề nhỏ hơn

Theo phương thức mô tả, val1có thể nhận chỉ mục của phần tử và trả về phần tử tại chỉ mục này nếu chúng ta có nó trong danh sách của mình. Nghe có vẻ khá đơn giản. Chúng tôi có danh sách với các phần tử, hãy lặp lại nó và theo dõi chỉ mục và chỉ mục hiện tại mà chúng tôi đã cung cấp. Nếu chúng bằng nhau, chúng tôi đã tìm thấy phần tử và có thể quay lại. Trong tất cả các trường hợp khác, chúng tôi trả về -1. Chú ý đến dòng 11. Chúng tôi sử dụng đầu vì nó lưu liên kết đến phần đầu của danh sách. Hãy ghi nhớ điều đó, chúng ta sẽ quay lại với nó

Ví dụ. chúng tôi có danh sách 1 -> 2 -> 3 -> 4 ->5

1 có chỉ số 0, 2 có chỉ số 1, v.v. Nếu chúng tôi đưa ra chỉ số 3, chúng tôi phải trả lại 4

val0

Phương pháp tiếp theo trong danh sách của chúng tôi là val3, nó phải chèn giá trị vào phía trước danh sách của chúng tôi. cái này hơi khó. Chúng tôi có phần đầu lưu trữ liên kết đến phần đầu, vì vậy chúng tôi muốn đẩy phần tử tiếp theo và chèn giá trị được cung cấp ngay sau phần đầu. Điều đầu tiên chúng tôi làm là tạo Liên kết mới sẽ lưu trữ giá trị được cung cấp (sơ đồ bên dưới). Đồng thời, chúng ta cần cập nhật mối quan hệ giữa các liên kết hiện có và liên kết mới. Thay vì sử dụng các từ, hãy xem một số hình ảnh, tôi hy vọng tôi sẽ giúp bạn hiểu khái niệm này

Trạng thái ban đầu của MyLinkedList

Chúng tôi đã tạo Liên kết mới với giá trị 5

Trạng thái của MyLinkedList sau khi chúng tôi cập nhật tất cả các liên kết

Chúng tôi cũng có một kích thước thay đổi ở đây để lưu trữ số lượng phần tử trong danh sách của chúng tôi

val3

lớp liên kết

Phương pháp tiếp theo là val5, nó thực hiện gần giống như phương pháp trước, điểm khác biệt duy nhất là chúng tôi chèn giá trị của mình vào trước phần đuôi của danh sách

val5

Trạng thái ban đầu của MyLinkedList

Chúng tôi đã tạo một Liên kết mới với giá trị 7

Trạng thái của MyLinkedList sau khi chúng tôi cập nhật tất cả các liên kết

Phương thức tiếp theo là val7 nó phải chèn một giá trị trong LinkedList tại một chỉ mục cụ thể được cung cấp dưới dạng tham số. Nút đầu tiên sau nút đầu có chỉ số 0, nút tiếp theo có chỉ số 1, v.v.

Giá trị và chỉ số của các nút trong MyLinkedList

Mục tiêu của chúng tôi là lặp lại chỉ mục đích và chèn giá trị vào chỉ mục đó. Hãy chèn giá trị 5 vào chỉ mục 1

Chúng tôi đã tạo một Liên kết mới với giá trị 5

Trạng thái của MyLinkedList sau khi chúng tôi cập nhật tất cả các liên kết

Phương pháp cuối cùng của chúng tôi để thực hiện là next2. Nó thực hiện gần giống như chèn vào chỉ mục, ngoại trừ một điều, lần này chúng tôi xóa Liên kết. Bài này dài quá nên mình cung cấp ít ảnh và code cho dễ hiểu. Hãy xóa nút tại chỉ số 3