Leetcode 287: Tìm các số trùng lặp với thuật toán Floyd

Trong bài viết này, mình sẽ giới thiệu qua về thuật toán quy trình của Floyd hay còn còn được gọi với tên phổ biến là thuật toán rùa và thỏ (Tortoise and Hare Algorithm) và giải thích 2 phương pháp để giải quyết bài Leetcode 287: Finding the Duplicate Number. Một bài mà mình thấy khá cần thiết để giải bài này mà các bạn nên làm qua là Finding a Linked-list cycle

Vì mình không phải là một người có nhiều kinh nghiệm và nghiên cứu chuyên sâu về giải thuật, do đó mục đích mình viết blog này nhằm ghi chép lại các kiến thức mình học được trong quá trình ôn luyện thuật toán. Nếu có sai sót gì, mong các bạn góp ý nhẹ nhàng 🥲

Thuật toán phát hiện quy trình của Floyd (Thuật toán Rùa và Thỏ)

Định nghĩa

Thuật toán phát hiện quy trình của Floyd (Floyd's algorithm) hay còn gọi là thuật toán "Rùa và Thỏ" (Tortoise and Hare algorithm) là thuật toán được thiết kế nhằm giải quyết các vấn đề về phát hiện chu trình trong đồ thị và linked-list. Hiểu một cách đơn giản thì để cài đặt thuật toán, chúng ta sẽ có 2 con trỏ (pointer) tương ứng với rùa và thỏ. Thỏ sẽ có tốc độ nhanh hơn rùa và nhanh hơn n lần với n là chênh lệch giữa tốc độ của rùa và thỏ. Thông thường, rùa sẽ có tốc độ là 1 và thỏ sẽ có tốc độ là s với s = 1 + n và s lớn hơn hoặc bằng 1.

Mục đích của các bài về phát hiện chu trình sẽ là tìm ra điểm bắt đầu của vòng lặp. Trước khi đào sâu thêm ở các phần tiếp theo, chúng ta sẽ định danh cho các biến như sau:

• x1: Rùa
• x1': Rùa sau j bước tiến
• x2: Thỏ
• x2': Thỏ sau j bước tiến
• λ: Độ dài của chu trình

Giả sử rùa x1 có điểm xuất phát tại i và sau j bước tiến, x1 lúc này có vị trí tương ứng là x1`: i + j. Trong khi đó, vì thỏ x2 có tốc độ là s nên vị trí sau j bước tiến của x2 lúc này là x2`: i + sj. Do đó, nhằm đạt mục đích cuối cùng của bài toán, chúng ta phải thoả được điều kiện sao cho vị trí của x1 và x2 sau j bước tiến sẽ bằng nhau hay x1' = x2'. Điều này xảy ra khi x1' và x2 cách một số lần nguyên độ dài kλ.

Dựa vào công thức sau ta có thể suy ra được là với k=2 sẽ thoả j=kλ.

Áp dụng thuật toán Floyd để tìm quy trình của Linked-list

Nếu các bạn đã giải qua bài Finding a Linked-list cycle mà mình nhắc đến ở trên, bạn sẽ hiểu về khái niệm rùa và thỏ hay đơn giản hơn là hai con trỏ mà mình vừa giải thích. Mình sẽ giải thích ngắn gọn thuật toán Rùa và Thỏ hoạt động thông qua bài Finding a Linked-list cycle dưới đây

func hasCycle(head *ListNode) bool {
    if head == nil {
		return false
	}
	tortoise, hare := head, head
	for {
		if tortoise.Next == nil || tortoise.Next.Next == nil {
			break
		}
		tortoise, hare = walker.Next, runner.Next.Next
		if tortoise == hare {
			return true
		}
	}
	return false
}

Áp dụng thuật toán vào bài "Finding a linked-list cycle", chúng ta sẽ có hai pointer tương ứng là tortoise và hare. Sau đó, chúng ta sẽ chạy vòng lặp với số bước của tortoise tương ứng là 1 và số bước của hare tương ứng là 2, sau j lần lặp, chắc chắn sẽ tìm ra điểm xuất hiện quy trình nếu Linked-list có quy trình.

Leetcode 287: Finding the Duplicate Number

Leetcode 287 có rất nhiều cách giải. Tuy nhiên, để có thể giải được bài này và đáp ứng được các yêu cầu mà đề đưa ra thì không thể nào áp dụng các cách thông thường được. Yêu cầu của bài này là chúng ta phải giải những không được sử dụng thêm bộ nhớ để lưu trữ dữ liệu hay độ phức tạp thời gian quá O(n).

Input: [1, 3, 4, 2, 1]
Output: 1

Từ các dữ liệu đầu vào ở trên, chúng ta có thể map trực tiếp các dữ liệu với các index của chuỗi. Sau khi map dữ liệu, chúng ta có được là

1 -> 0
3 -> 1
4 -> 2
2 -> 3
1 -> 4

Lý do vì sao chúng ta phải map dữ liệu như này nhằm mục đích đưa bài này thành bài Finding a linked list cycle. Sau khi map dữ liệu, theo cách mình hình dung thì đây là linked-list có các vị trí là 0-> 1 -> 2 -> 3 -> 4 với mỗi vị trí sẽ trỏ đến một nhánh nhất định. Như tại vị trí số 0 sẽ trỏ đến nhánh số 1, và vị trí số 1 sẽ chỏ đến nhánh số 3. Map dữ liệu một lần nữa và linked-list cuối cùng mà chúng ta có được sẽ là 1 -> 3 -> 2 -> 4 -> 1

Sau khi đã có linked-list, chúng ta sẽ cần chạy thuật toán Rùa và Thỏ để tìm ra điểm bắt đầu của quy trình. Chỗ này thì mình cần mượn hình của Neetcode một chút.

Dựa vào giải thích ở trên từ Neetcode, bạn có thể hiểu là khoảng cách từ điểm đầu tiên tới điểm bắt đầu quy trình được gọi là P và khoảng cách từ điểm mà chúng ta tìm ra bằng thuật toán Rùa và Thỏ được gọi là X và độ dài của quy trình lúc này sẽ là C. Và theo như lý thuyết, bước đi của Thỏ lúc này là 2, do đó là có 2*d1 = d2 với d1 = các bước cần đi để đến điểm cận quy trình của Rùa và d2 = các bước cần đi để đến điểm cận quy trình của Thỏ

• d1 = P + C - X: Để đến được điểm cận quy trình, rùa phải đi P bước và C - X bước (1 quy trình trừ đi số bước từ điểm cận đến điểm bắt đầu)
• d2 = P + 2C - X: Với Thỏ, Thỏ cũng cần phải đi P + C - X. Tuy nhiên, do thỏ nhanh hơn rùa 2 bước nên thỏ sẽ cần phải đi thêm 1 quy trình nữa để đón kịp với rùa

Rút gọn phương trình ta sẽ có được kết quả cuối cùng là P=X. Do đó, sau khi đã tìm được điểm cận quy trình, rùa cần phải quy về điểm bắt đầu và cả rùa lẫn thỏ phải tiến thêm 1 bước để tìm ra điểm bắt đầu. Đây là hình minh hoạ cho bước đi của rùa và thỏ.

Triển khai thuật toán

impl Solution {
 pub fn find_duplicate(nums: Vec<i32>) -> i32 {
  let (mut tortoise, mut hare) = (nums[0], nums[nums[0] as usize]);
  while tortoise != hare {
   tortoise = nums[tortoise as usize];
   hare = nums[nums[hare as usize] as usize];
  }

  tortoise = 0;
  while tortoise != hare {
   tortoise = nums[tortoise as usize];
   hare = nums[hare as usize]
  }
  tortoise
 }
}

Code của chúng ta sẽ gồm 2 phần chính, đầu tiên là phần tìm điểm cận quy trình. Áp dụng lý thuyết của thuật toán Floyd thì thỏ sẽ nhanh hơn rùa là s lần và s=2. Do đó, trong linked-list, tortoise (hay rùa) sẽ trỏ đến nums[tortoise] (phần tử tiếp theo) còn hare (thỏ) sẽ trỏ đến nums[nums[hare] (phần tử tiếp tới). Vòng lặp sẽ kết thúc khi thỏ và rùa gặp nhau.  

let (mut tortoise, mut hare) = (nums[0], nums[nums[0] as usize]);
  while tortoise != hare {
   tortoise = nums[tortoise as usize];
   hare = nums[nums[hare as usize] as usize];
  }
  

Phần tiếp theo là reset vị trí của rùa về điểm bắt đầu của linked-list, trong khi đó thì thỏ sẽ giữ nguyên vị trí. Như đã giải thích ở trên, rùa cần tiến thêm P bước và thỏ cần tiến thêm X bước với P = X. Do đó, ta sẽ chạy 1 vòng lặp nữa nhưng lúc này thỏ và rùa sẽ có số bước bằng nhau ứng với P = X.

tortoise = 0;
while tortoise != hare {
   tortoise = nums[tortoise as usize];
   hare = nums[hare as usize]
}
tortoise
  

Kết quả cuối cùng là phần tử trong linked-list tại vị trí của rùa hoặc thỏ.