Một trong những cách để lưu cây nhị phân vào file là ta tiến hành ghi kết quả của việc duyệt cây theo thứ tự trước (preorder traversal), với những nút là null, ta ghi giá trị “#”.
Đề bài cho một chuỗi, hãy kiểm tra chuỗi cho trước xem nó có phải là kết quả của việc duyệt cây theo thứ tự trước hay không.
Ví dụ:
Đầu vào: preorder = "9,3,4,#,#,1,#,#,2,#,6,#,#"
Kết quả: true
(by ndaadn)
Bài toán yêu cầu tìm hoán vị tiếp theo trong thứ tự từ điển của một số tự nhiên. Cách tiếp cận đầu tiên ta có thể nghĩ tới là sinh tất cả các hoán vị, sau đó tìm hoán vị tiếp theo của số đã cho theo thứ tự từ điển. Giải thuật này đòi hỏi phải sinh tất cả các hoán vị, vì vậy độ phức tạp về thời gian sẽ là O(n!), bởi với mỗi số tự nhiên, ta có tối đa n! hoán vị.
Để giải bài toán này với độ phức tạp thời gian O(n), ta cần áp dụng cách tiếp cận sinh hoán vị mà Donald Knuth đã nêu trong bộ sách nổi tiếng The Art of Computer Programming (TAOCP). Giải thuật gồm ba bước chính như sau:
- Tìm vị trí i cuối cùng, sao cho
nums[i] < nums[i + 1]
- Từ vị trí
i + 1, tìm k cuối cùng sao cho nums[k] > nums[i], đổi chỗ của số ở i với k
- Đảo ngược mảng con từ vị trí
i + 1
Cần lưu ý ở bước 1, nếu ta không có số i nào thoả mãn điều kiện, ví dụ như mảng: [6, 4, 2, 1], thì đây là số cuối cùng theo thứ tự từ điển, ta tìm số tiếp theo bằng cách đảo ngược toàn bộ mảng.
