Vấn đề mã hóa hàng ngày: Xóa chỉ mục thứ k khỏi danh sách được liên kết trong một lượt

Xóa chỉ mục thứ k khỏi danh sách được liên kết trong một lượt Chào mừng trở lại, với một vấn đề khác cần giải quyết! Hôm nay, chúng ta đang giải quyết các danh sách được liên kết và loại bỏ các phần tử của chúng. Chúng ta sẽ thảo luận một chút về danh sách được liên kết là gì, chúng ta sẽ tạo một danh sách và xem cách loại bỏ các phần tử khỏi danh sách đó. Trước khi bắt đầu, các tuyên bố từ chối trách nhiệm thông thường: Những vấn đề này được cung cấp bởi bản tin tuyệt vời Vấn đề mã hóa hàng ngày mà bạn có thể đăng ký . Kiểm tra nó ra, và cố gắng giải quyết những thách thức của bạn quá! đây Tôi không phải là một lập trình viên chuyên nghiệp: Chỉ là một người thích chia sẻ ảnh của mình! Nếu bạn tình cờ có một giải pháp tốt hơn hoặc nhanh hơn cho một thuật toán, vui lòng gửi nó trong phần bình luận! Tôi muốn tìm hiểu thêm về điều này! Đủ ado; hãy chuyển sang vấn đề! Vấn đề này ban đầu được hỏi bởi Amazon , xóa nút thứ k khỏi cuối danh sách và trả về phần đầu của danh sách. Cho một danh sách được liên kết và một số nguyên k được đảm bảo nhỏ hơn độ dài của danh sách. k Làm điều này trong một lần. Được rồi, hãy giải thích một chút điều gì đang xảy ra ở đây: chúng ta được cung cấp một danh sách được liên kết và một phần tử chỉ mục cần xóa khỏi danh sách. Sau đó, chúng ta nên trả lại phần đầu của danh sách được liên kết. k Cuối cùng, chúng ta phải thực hiện tất cả những điều này chỉ trong một lượt, nghĩa là chúng ta không thể lặp lại danh sách nhiều lần. Chúng tôi cũng được đảm bảo rằng chỉ mục được trong danh sách, vì vậy chúng tôi không phải kiểm tra xem nó có vượt quá độ dài thực của danh sách hay không. k chứa Hôm nay chúng ta sẽ sử dụng Go để xây dựng thuật toán vì cú pháp của nó rất tuyệt vời cho loại công việc này, đồng thời, nó vẫn khá đơn giản để hiểu. Hãy bắt đầu lại từ đầu: xây dựng một danh sách liên kết đơn giản. Danh sách liên kết Khái niệm đằng sau danh sách được liên kết khá đơn giản: đó là một danh sách gồm các đối tượng (thường được gọi là ) và mỗi nút phải có ít nhất hai thuộc tính: một (thứ thực sự chứa trong nút đó) và một đến nút tiếp theo. các nút giá trị liên kết Thông thường, một được sử dụng như một liên kết để chuyển từ nút này sang nút khác. con trỏ Ngoài ra, nút đầu tiên của danh sách thường được gọi là danh sách, đây cũng là nút mà chúng tôi được yêu cầu trả về trong bài toán. đầu Đây là một ví dụ đồ họa: Nút đầu tiên bên trái là đầu danh sách, chứa giá trị v₀ và con trỏ bộ nhớ chuyển hướng danh sách đến nút Nút sau sẽ chứa giá trị của nó và một con trỏ tới nút tiếp theo, v.v. P(n₁) n₁ tiếp theo. n₁ P(n₂) Tất nhiên, nút cuối cùng sẽ không có gì để trỏ tới, vì vậy giá trị của con trỏ của nó sẽ là . null Hãy xem mã để tạo một cái! https://Gist.github.com/NicolaM94/03bd49c6f65054a3440e8c9eef3c560c?embedable=true Mã này khá đơn giản: chúng tôi tạo hai cấu trúc, một cho nút bên trong và một cho danh sách được liên kết. Nút, như chúng ta vừa thấy, sẽ có hai thuộc tính, cụ thể là thuộc tính Giá và thuộc tính , chứa loại làm con trỏ tới nút tiếp theo. Value Next *Node Danh sách liên kết, một cấu trúc để “khởi tạo” danh sách liên kết, danh sách này sẽ chỉ có một thuộc tính là danh sách. Head Sau đó, chúng ta chỉ cần khởi tạo danh sách trong hàm chính và đặt cho phần đầu của nó một nút có giá trị ngẫu nhiên là 10. Chìa khóa đằng sau việc hiểu danh sách được liên kết là giờ đây tính thuộc tính này sẽ chứa nút tiếp theo. Nút cuối cùng này sau đó sẽ có thuộc tính của nó để chuyển sang nút tiếp theo, v.v. nút Head , vì thuộc loại Node , vốn dĩ sẽ có thuộc Next , Next Mọi thứ sẽ rõ ràng hơn khi chúng tôi thêm một số nút vào danh sách, vì vậy hãy làm điều đó! Chúng tôi có hai lựa chọn: hoặc chúng tôi thực hiện thủ công, một công việc tẻ nhạt hoặc chúng tôi viết một phương thức cho lớp danh sách được liên kết để thêm một số nút khác. Hãy cùng kiểm tra nào! thực sự Thêm nút: Danh sách có thể thay đổi trong ngụy trang Ngay cả khi bạn có ít kinh nghiệm lập trình, trong hầu hết mọi ngôn ngữ lập trình, một trong những khái niệm đầu tiên bạn nên nghe là sự khác biệt giữa danh sách và danh sách . có thể thay đổi không thể thay đổi Như tên gợi ý, . Thay vào đó, các bất biến có các phần tử mới. Nhưng tại sao lại như vậy? danh sách có thể thay đổi là danh sách mà bạn có thể thao tác và thêm phần tử vào kích thước cố định và không thể thêm Immutable list nằm , nghĩa là các phần tử của chúng được : đối với danh sách có 3 phần tử, nếu phần tử đầu tiên được lưu ở 0x00 thì phần tử thứ hai sẽ ở 0x01 và phần tử cuối cùng ở 0x02. liền kề trong bộ nhớ lưu trong bộ nhớ một cách tuần tự Đó là lý do tại sao việc lặp qua một mảng cố định, một danh sách bất biến hoặc một bộ trong Python rất nhanh bởi vì CPU chỉ đơn giản gọi lại từng chỉ mục bộ nhớ. Mặt khác, các danh sách có thể thay đổi chỉ liền kề trong bộ nhớ khi được khởi tạo lần đầu tiên: tại thời điểm đó, nếu các phần tử được thêm vào, chúng sẽ không còn tuần tự nữa. Vì vậy, làm thế nào chúng ta có thể lặp qua chúng? , con trỏ này sẽ mang đến cho chúng ta phần tử to được nối thêm, v.v. Chà, bởi vì phần tử cuối cùng của lần khởi tạo đầu tiên sẽ có một con trỏ mà phần tử được thêm vào sau nó Vì vậy, có, danh sách có thể thay đổi thực sự thường là danh sách được liên kết trong ngụy trang! Bây giờ, hãy xem mã: https://Gist.github.com/NicolaM94/9f587f4cd675dbbdb098327b22628284?embedable=true Chúng tôi đã thêm phương thức vào các phương thức của danh sách được liên kết của chúng tôi. Quá trình thêm một nút diễn ra như sau: AddNode Đầu tiên, chúng tôi lưu trữ giá trị trong một biến có tên là Head current Tiếp theo, chúng tôi lặp lại danh sách được liên kết cập nhật biến với nút tiếp theo mỗi lần, cho đến khi nút tiếp theo là null. current Khi nút mà chúng tôi hiện đang ở trên có một con trỏ null, chúng tôi biết rằng chúng tôi đang ở nút cuối cùng của danh sách. Cuối cùng, chúng tôi cập nhật nút cuối cùng này bằng một nút mới và một giá trị mới (con trỏ của nút mới này sẽ được đặt thành null nếu chúng tôi để trống) Next Về mặt đồ họa, quá trình này giống như sau: Chúng ta có thể kiểm tra chức năng chính xác của phương thức này trong chức năng chính, in ra các giá trị của các nút trong danh sách được liên kết. Loại bỏ nút Bây giờ là phần cuối cùng và giải pháp cho vấn đề của chúng ta: xóa một nút có chỉ mục chính xác. Trước hết, việc xóa một nút khỏi danh sách được liên kết có nghĩa là gì? Nếu chúng ta nghĩ về nó, , phải không? một nút trong danh sách được liên kết chỉ tồn tại nếu nó được kết nối với nút trước đó Ví dụ: nếu chúng tôi cung cấp cho n-1ᵗʰ giá trị là null, chúng tôi có thể ngắt kết nối giá trị nᵗʰ khỏi danh sách. Next Nếu phần tử chúng ta muốn xóa không phải là phần tử cuối cùng thì sao? Chà, chúng ta có thể ! hủy liên kết phần tử bằng cách kết nối phần trước với phần tiếp theo của nó Vậy để loại bỏ phần tử kᵗʰ ta phải tìm phần tử k-1ᵗʰ và liên kết nó với nút k+1ᵗʰ. Chúng tôi sẽ cần lưu trữ . nút trước đó (k-1ᵗʰ) Rõ ràng, : hãy thử một cái gì đó như sẽ chỉ gây ra lỗi. Mặc dù vậy, với điều này, chúng ta có thể coi phần đầu của danh sách là chỉ mục 0 và nút tiếp theo của nó là chỉ mục 1, v.v. và chúng ta cũng có thể lặp qua các nút, như chúng ta đã làm trước đây. chúng ta không thể lập chỉ mục trực tiếp danh sách linkedlist[n] Những gì chúng ta có thể làm sau đó là triển khai một để theo dõi nút mà chúng ta đang truy cập! bộ đếm Hãy mã nó sau đó. https://Gist.github.com/NicolaM94/e08509c42ede81834ac65ff7aa65828b?embedable=true Hãy xem xét hàm chấp nhận thuộc mục. Sau đó, chúng tôi khởi tạo ba biến: RemoveNode index , sẽ giữ nút trước đó previousNode , nút này sẽ giữ nút mà chúng ta đang bật trong vòng lặp current , ban đầu bằng 0, sẽ giữ vị trí của chúng ta trong danh sách counter Hãy tạm bỏ qua khối if đầu tiên và thay vào đó hãy tập trung vào vòng lặp for. Chúng tôi bắt đầu lặp cho đến khi biến bộ của chúng tôi nhỏ hơn của chúng tôi : mỗi vòng lặp sau đó sẽ counter index cập nhật nút trước đó với nút hiện tại và chuyển sang cập nhật nút hiện tại và bộ đếm. điều đó có nghĩa là Khi vòng lặp bị ngắt, chúng ta đang ở ngay nút trước chỉ mục mong muốn của mình: chúng ta chỉ cần cập nhật con trỏ của nút trước đó, prev.Next , với nút tiếp theo trong danh sách từ nút này mà chúng ta đang ở. sẽ là current.Next . Cuối cùng, chúng tôi trả lại phần đầu của danh sách được liên kết. Bây giờ điều gì sẽ xảy ra nếu chỉ mục cần loại bỏ là phần đầu có chỉ số bằng 0? Vòng lặp sẽ không bao giờ bắt đầu vì nó sẽ bắt đầu với và và điều kiện sẽ sai ngay lập tức. Chúng ta có thể quản lý trường hợp đầu tiên này với khối if ở trên cùng. counter = 0 index = 0 Về cơ bản, nếu chỉ mục là 0, chúng ta có thể cập nhật trực tiếp phần đầu của danh sách được liên kết với nút bên cạnh nó và trả lại nó. Tôi muốn bạn chú ý, đặc biệt là dòng 31: Go, như trong nhiều ngôn ngữ khác, , nghĩa là hàm giữ lại một của đối tượng đã truyền, . chuyển các thuộc tính cho các hàm theo giá trị bản sao không phải đối tượng thực mà bạn đang chuyển Khái niệm này được thấy rõ trong ví dụ này: package main import "fmt" func printMemoryAddress(value int) { fmt.Println(&value) } func main() { a := 10 fmt.Println(&a) printMemoryAddress(a) } // 0xc00010a000 // 0xc00010a008 // Program exited. Chúng tôi tạo một hàm để in địa chỉ bộ nhớ của giá trị được truyền dưới dạng thuộc tính. Sau đó, trong hàm chính, chúng ta tạo một biến a và in ra địa chỉ bộ nhớ của nó. Sau đó, chúng tôi chuyển cùng một biến cho hàm và in địa chỉ bộ nhớ của nó. Như bạn có thể thấy, nếu bạn thử, kết quả sẽ khác: đó là vì các thuộc tính được truyền cho hàm dưới dạng giá trị, nghĩa là một bản sao của được tạo chỉ với mục đích truyền nó cho hàm. a Quay lại danh sách liên kết của chúng ta, chúng ta phải sử dụng con trỏ để lấy đầu thực cho cùng một vấn đề ở trên. “thực”, Vì vậy, để đến được ll.Node chúng ta phải nhớ lại con trỏ của nó, *ll.Node và di chuyển nó xa hơn với *ll.Node = *ll.Node.Next . Trong chức năng chính, chúng tôi thêm các cuộc gọi vào phương thức, ví dụ: gọi và và chúng tôi có thể kiểm tra kết quả xem nút 0 và nút 2 sẽ bị thiếu. ll.RemoveNode(0) ll.RemoveNode(2) Phần kết luận Chúng tôi đã làm cho nó đến cùng! Nếu bạn đọc cho đến thời điểm này, toàn bộ lòng biết ơn của tôi dành cho bạn. Nếu bạn sẵn sàng để lại một hoặc hai lượt thích và chia sẻ bài viết, nó sẽ giúp tôi có một ngày vui vẻ và giúp tôi tiếp tục viết những bài báo này! Hẹn gặp lại bạn trong bài viết tiếp theo, và như mọi khi, cảm ơn vì đã đọc. Nicola