Phát hiện danh sách phát tuần hoàn trong JavaScript
Tìm chu kỳ hoặc sự lặp lại là một vấn đề phổ biến khi trả lời các câu hỏi phỏng vấn viết mã, đặc biệt là những câu hỏi yêu cầu cấu trúc dữ liệu như danh sách liên kết. Vấn đề này thường phát sinh trong danh sách phát, nơi các bài hát có thể liên kết với nhau theo chuỗi tham chiếu. Danh sách phát được cho là lặp lại nếu bài hát tham chiếu đến bài hát trước đó.
Mục tiêu của bài tập viết mã JavaScript này là viết một hàm xác định xem có bài hát nào trong danh sách phát được lặp lại hay không. Việc này sẽ xem xét từng bài hát một và xem liệu có tài liệu tham khảo nào lặp lại bài hát trước đó hay không. Ngay cả những lập trình viên dày dạn kinh nghiệm cũng có thể gặp phải sự phức tạp của tham chiếu đối tượng và điều khiển vòng lặp trong khi cố gắng giải quyết vấn đề có vẻ đơn giản này trong JavaScript.
Thông thường, vấn đề bắt nguồn từ cách thể hiện logic lặp, đặc biệt là từ cách xử lý các tham chiếu giữa các đối tượng. Trong trường hợp này, giải pháp phụ thuộc vào khả năng hiểu cách JavaScript quản lý các tham chiếu đối tượng bên trong vòng lặp của bạn. Chúng tôi sẽ tập trung vào cách chỉ định lại và theo dõi các tham chiếu này trong danh sách phát một cách thích hợp khi chúng tôi kiểm tra giải pháp.
Chúng tôi sẽ mổ xẻ vấn đề một cách chi tiết, xem xét những thiếu sót của giải pháp hiện có và đưa ra giải pháp khả thi cho trở ngại danh sách phát tái diễn này trong cuộc thảo luận tiếp theo. Với bản sửa lỗi này, hàm sẽ có thể nhận dạng chính xác các tham chiếu tuần hoàn trong danh sách phát và tạo ra kết quả mong muốn.
| Yêu cầu | Ví dụ về sử dụng |
|---|---|
| Set() | Đối tượng JavaScript Set() được sử dụng để lưu trữ dữ liệu duy nhất. Để giúp xác định chu kỳ danh sách phát, nó được sử dụng trong ví dụ này để theo dõi các bài hát được xem, đảm bảo không có bài hát nào được phát lại. |
| has() | Đối tượng Set() có hàm has(). Nó kiểm tra xem một phần tử cụ thể có tồn tại trong tập hợp hay không. Tại đây, nó sẽ kiểm tra xem bài hát đã được nghe chưa, cho biết danh sách phát đang lặp lại. |
| add() | Đối tượng Set() có hàm has(). Nó kiểm tra xem một phần tử nhất định có tồn tại trong tập hợp hay không. Tại đây, nó sẽ kiểm tra xem bài hát đã được nghe chưa, cho biết danh sách phát đang lặp lại. |
| two-pointer technique | Phương pháp này, đôi khi được gọi là thuật toán phát hiện chu kỳ Floyd-Warshall, điều hướng danh sách phát bằng hai con trỏ: chậm và nhanh. Để phát hiện vòng lặp một cách hiệu quả, con trỏ chậm di chuyển một bước trong khi con trỏ nhanh di chuyển hai bước. |
| nextSong | Lớp Song có một thuộc tính duy nhất được gọi là nextSong tham chiếu đến bài hát đứng sau nó trong danh sách phát. Nó cho phép bắt chước cấu trúc danh sách liên kết trong đó mỗi bài hát đề cập đến từng bài hát khác một cách tuần tự. |
| describe() | Chức năng mô tả() của khung thử nghiệm Mocha được sử dụng để tổ chức các bài kiểm tra đơn vị liên quan. Nó chia các bài kiểm tra thành các danh mục hợp lý, các danh sách phát lặp lại và những danh sách không lặp lại. |
| it() | Trong Mocha, định nghĩa trường hợp thử nghiệm được gọi là it(). Nó chỉ ra một trường hợp cụ thể cần được kiểm tra, chẳng hạn như đảm bảo chức năng nhận dạng danh sách phát định kỳ một cách thích hợp. |
| assert.strictEqual() | Phương thức này lấy từ mô-đun khẳng định trong Node.js. Trong trường hợp này, nó xác minh kết quả dự đoán của hàm lặp lại danh sách phát bằng cách xác định xem hai giá trị có hoàn toàn bằng nhau hay không. |
Tìm hiểu tính năng phát hiện chu kỳ danh sách phát trong JavaScript
Tập lệnh đầu tiên được cung cấp sử dụng cách tiếp cận danh sách liên kết để xác định các bài hát được lặp lại trong danh sách phát bằng cách coi mỗi bài hát là một nút. Cấu trúc lớp của JavaScript được sử dụng để xây dựng một Bài hát đối tượng bắt chước luồng danh sách phát từ bản nhạc này sang bản nhạc khác bằng cách lưu trữ tên bài hát và tham chiếu đến bài hát tiếp theo. Thành phần chính của giải pháp theo dõi âm nhạc đã gặp trước đây bằng cách sử dụng Bộ. Chúng tôi sử dụng vòng lặp while để lặp qua các bài hát, kiểm tra xem bài hát hiện tại đã được nghe trước đó chưa. Nếu vậy, chúng tôi cho biết rằng danh sách phát đang lặp lại bằng cách trả về giá trị đúng.
Thuật toán phát hiện chu trình của Floyd, thường được gọi là kỹ thuật hai con trỏ, được sử dụng theo cách thứ hai. Sử dụng phương pháp này, hai con trỏ di chuyển qua danh sách phát ở tốc độ riêng biệt: một con trỏ bỏ qua hai bài hát và di chuyển tiếp một bài hát cùng một lúc. Những con trỏ này cuối cùng sẽ gặp nhau nếu có một chu kỳ, cho biết danh sách phát lặp lại. Vì không bắt buộc phải lưu các bài hát đã xem nên phương pháp này tiết kiệm không gian hơn và do đó là lựa chọn tốt hơn cho danh sách phát lớn hơn.
Các giải pháp này cũng chỉ ra cách tạo danh sách liên kết trong JavaScript vì bài hát tiếp theo thuộc tính liên kết mỗi Bài hát phản đối người khác. Phát hiện chu kỳ trong tập lệnh đầu tiên tận dụng cấu trúc đã định sẵn. Vì các bộ đảm bảo tính duy nhất nên chúng tôi có thể xác định ngay liệu một bài hát đã được phát hay chưa sau khi nó được thêm vào bộ. Điều này làm cho các bộ đặc biệt hữu ích. Điều này giúp chúng ta nhận biết khi nào một chu kỳ bắt đầu và giúp chúng ta không bị cuốn vào một vòng lặp vô tận.
Cuối cùng, các bài kiểm tra đơn vị được đưa vào cho cả hai chiến lược đều đảm bảo rằng giải pháp là chính xác trong nhiều cài đặt khác nhau. Để kiểm tra mã của chúng tôi, chúng tôi đã sử dụng khung thử nghiệm Mocha. Node.js khẳng định mô-đun được sử dụng để xác nhận rằng kết quả đầu ra như mong đợi và của Mocha mô tả Và Nó các hàm được sử dụng để cấu trúc các bài kiểm tra một cách hợp lý. Kiểm thử đơn vị đóng vai trò quan trọng trong quá trình phát triển vì chúng xác thực rằng chức năng này hoạt động như mong đợi đối với cả danh sách phát định kỳ và không lặp lại, mang lại sự đảm bảo về khả năng phục hồi của giải pháp.
Phát hiện các bài hát lặp lại trong danh sách phát bằng JavaScript
Lập trình hướng đối tượng trong JavaScript với vòng lặp while
class Song {constructor(name) {this.name = name;this.nextSong = null;}/* @return {boolean} true if the playlist is repeating, false if not.*/isRepeatingPlaylist() {let seenSongs = new Set();let current = this;while (current) {if (seenSongs.has(current)) {return true; // Playlist is repeating}seenSongs.add(current);current = current.nextSong;}return false; // Playlist is not repeating}}// Testing the solutionlet first = new Song("Hello");let second = new Song("Eye of the Tiger");let third = new Song("Third");first.nextSong = second;second.nextSong = third;third.nextSong = first; // Creates a loopconsole.log(first.isRepeatingPlaylist()); // true
Phương pháp thay thế: Sử dụng hai con trỏ để phát hiện chu kỳ
Phát hiện chu trình danh sách liên kết với thuật toán Floyd-Warshall
class Song {constructor(name) {this.name = name;this.nextSong = null;}/* @return {boolean} true if the playlist is repeating, false if not.*/isRepeatingPlaylist() {let slow = this;let fast = this;while (fast !== null && fast.nextSong !== null) {slow = slow.nextSong; // move slow pointer by 1 stepfast = fast.nextSong.nextSong; // move fast pointer by 2 stepsif (slow === fast) {return true; // Loop detected}}return false; // No loop}}// Testing the solutionlet first = new Song("Hello");let second = new Song("Eye of the Tiger");let third = new Song("Third");first.nextSong = second;second.nextSong = third;third.nextSong = first; // Creates a loopconsole.log(first.isRepeatingPlaylist()); // true
Kiểm tra đơn vị để phát hiện vòng lặp danh sách phát
Kiểm tra hàm isRepeatingPlaylist với Node.js và Mocha
const assert = require('assert');describe('isRepeatingPlaylist', function () {it('should return true for a repeating playlist', function () {let first = new Song('Song A');let second = new Song('Song B');let third = new Song('Song C');first.nextSong = second;second.nextSong = third;third.nextSong = first; // Creates a loopassert.strictEqual(first.isRepeatingPlaylist(), true);});it('should return false for a non-repeating playlist', function () {let first = new Song('Song A');let second = new Song('Song B');let third = new Song('Song C');first.nextSong = second;second.nextSong = third;assert.strictEqual(first.isRepeatingPlaylist(), false);});});
Kỹ thuật phát hiện vòng lặp danh sách phát nâng cao trong JavaScript
Hiểu cấu trúc cơ bản của danh sách phát về mặt danh sách liên kết là một phần thú vị của việc phát hiện vòng lặp danh sách phát. Mỗi bài hát trong danh sách phát không lặp lại sẽ liên kết với bài hát trước đó cho đến khi không còn tham chiếu nào đến bài hát đó và danh sách kết thúc. Chúng tôi bắt đầu một chu kỳ khi một bài hát quay trở lại bài hát trước đó, do đó, theo một nghĩa nào đó, danh sách này là "vô hạn". Việc tìm ra các loại chu trình này không chỉ quan trọng đối với danh sách phát mà còn đối với các thuật toán định tuyến và phân bổ bộ nhớ.
Các chu trình này có thể được phát hiện một cách hiệu quả trong JavaScript bằng cách sử dụng các kỹ thuật và cấu trúc con trỏ như Bộ. Bởi vì nó đảm bảo tính duy nhất và ngăn chặn việc xem lại các bài hát mà không bắt đầu một chu kỳ, Bộ đặc biệt hữu ích. Ngược lại, cách tiếp cận hai con trỏ Floyd-Warshall là một giải pháp tối ưu hóa không gian trong đó hai tham chiếu chuyển động hoặc con trỏ có tốc độ khác nhau. Nếu chúng đến với nhau, một mô hình sẽ được tìm thấy.
Bằng cách làm cho các thuật toán này hiệu quả hơn, có thể kiểm tra danh sách phát chứa hàng nghìn bài hát một cách nhanh chóng. Kỹ thuật hai con trỏ hoàn hảo cho các tình huống khi việc sử dụng bộ nhớ là một vấn đề vì nó có độ phức tạp về thời gian O(n) và độ phức tạp về không gian O(1). Hơn nữa, các giải pháp của chúng tôi được xác minh là hoạt động bình thường bằng cách sử dụng các thử nghiệm đơn vị, chẳng hạn như các giải pháp được thực hiện bằng Mocha, giúp phát hiện danh sách phát lặp và không lặp trong nhiều cài đặt khác nhau.
Các câu hỏi thường gặp về Phát hiện chu kỳ danh sách phát
- Chu kỳ trong danh sách phát là gì?
- Khi một bài hát trong danh sách phát tham chiếu đến bài hát trước đó, một chuỗi lặp được gọi là chu kỳ sẽ được tạo.
- Kỹ thuật hai con trỏ phát hiện một chu kỳ như thế nào?
- Con trỏ nhanh di chuyển hai bước và con trỏ chậm di chuyển từng bước một bằng cách sử dụng kỹ thuật hai con trỏ. Nếu chúng đến với nhau thì sẽ có một vòng lặp.
- Tại sao là một Set được sử dụng để phát hiện chu kỳ?
- trong một Set, các giá trị riêng biệt được lưu trữ. Ghi chú âm nhạc đã nghe là hữu ích. Một vòng lặp được xác định nếu một bản nhạc được phát lại.
- Tôi có thể sử dụng thuật toán này cho các ứng dụng khác không?
- Thật vậy, rất nhiều công việc liên quan đến việc xác định các vòng lặp trong danh sách liên kết, quản lý bộ nhớ và định tuyến mạng bằng kỹ thuật phát hiện chu trình.
- Tại sao chúng ta sử dụng while vòng lặp trong quá trình truyền tải danh sách phát?
- Chúng ta có thể lặp đi lặp lại danh sách phát bằng cách sử dụng while lặp lại cho đến khi chúng ta tìm thấy một chu trình hoặc đi đến cuối danh sách.
Suy nghĩ cuối cùng về việc phát hiện danh sách phát lặp lại
Có thể khó xác định chu kỳ trong danh sách phát, đặc biệt khi điều hướng quản lý tham chiếu đối tượng của JavaScript. Tuy nhiên, chúng tôi có thể xử lý vấn đề này một cách hiệu quả và hợp lý hóa mã của mình bằng cách sử dụng các kỹ thuật như áp dụng kỹ thuật hai con trỏ hoặc theo dõi tham chiếu bài hát bằng Tập hợp.
Biết cách thức hoạt động của các kỹ thuật này sẽ giúp bạn giải quyết vấn đề hiệu quả hơn, cho dù bạn đang giải quyết vấn đề này trong một cuộc phỏng vấn viết mã hay cho mục đích sử dụng thực tế. Sử dụng các cấu trúc hiệu quả như Bộ và hiểu cách con trỏ hỗ trợ phát hiện chu trình là những bài học chính cần rút ra.
Tài nguyên và tài liệu tham khảo để phát hiện chu kỳ danh sách phát
- Cảm hứng cho các thuật toán phát hiện chu kỳ danh sách phát được rút ra từ các vấn đề và kỹ thuật phổ biến về danh sách liên kết như thuật toán Floyd-Warshall. Tìm hiểu thêm về danh sách liên kết và phát hiện chu kỳ trong tài nguyên toàn diện này: Phát hiện chu kỳ trên Wikipedia .
- Một tài nguyên tuyệt vời khác được sử dụng là tài liệu JavaScript dành cho các đối tượng Set, tài liệu này đóng vai trò chính trong cách tiếp cận giải pháp đầu tiên: Đặt JavaScript trên MDN .
- Để biết thêm các kỹ thuật kiểm tra chi tiết hơn trong JavaScript, tài liệu chính thức của Mocha là nguồn chính để hiểu cấu trúc và xác nhận kiểm tra: Khung thử nghiệm Mocha .
- Khám phá hướng dẫn này về kỹ thuật hai con trỏ, kỹ thuật này thường được sử dụng cho các vấn đề phát hiện chu kỳ và là một trong những phương pháp hiệu quả được sử dụng ở đây: Phát hiện vòng lặp trong danh sách liên kết .