Luận bàn về Fast & Slow Pointers

Pattern này sử dụng 2 pointers với tốc độ khác nhau để duyệt các cấu trúc dữ liệu kiểu iterable, ví dụ như 1 vòng tuần hoàn trong linked list. Trong các dạng bài yêu cầu mình phải duyệt cycle của linked list, array, etc... thì ta nên nghĩ tới pattern này đầu tiên.

Ở đây, ta sẽ được tiếp cận tới 1 cấu trúc dữ liệu mới, gọi là linked list. Để ôn lại về linked list, anh em có thể qua đây

Nhìn chung, mấy cái pointer cần phải được đảm bảo điều kiện là 1 pointer nhanh và 1 pointer chậm, và dễ thấy trong các problem phổ biến nhất là pointer fast sẽ nhanh gấp đôi pointer slow. Ta sẽ có cách giải phổ biến nhất như sau:

Initialize fast and slow pointers

For each iteration traversing the linked list/array,
  fast = fast->next->next or fast = array[fast[fast]]
  slow = slow->next or slow = array[slow]
  do something with the fast and slow

Snippet:

fast, slow = head, head
while True:
  fast = fast.next.next
  slow = slow.next
  if fast is None or fast.next is None:
    break
# Each node represents an index in the arr
# 2 node are connected together in the format arr[i], which means node i connects to node arr[i]
# arr[i] == -1 means node i connects to NULL
arr = [-1,3,2,6,2,5,4,-1]
fast, slow = 0, 0
while True:
  fast = arr[fast[fast]]
  slow = arr[slow]
  if fast != -1 or arr[fast] != -1:
    break

Follow up:

trên nhưng vẫn được giải bằng fast & slow pointers. Thế nên là chủ yếu ta cần xác định xem liệu có cycle nào ta cần phải duyệt theo đề bài không

n = 12
1^2 + 2^2 = 5
5^2 = 25
2^2 + 5^2 = 29
2^2 + 9^2 = 85
8^2 + 5^2 = 89
8^2 + 9^2 = 145
1^2 + 4^2 + 5^2 = 42
4^2 + 2^2 = 20
2^2 + 0^2 = 4
4^2 = 16
1^2 + 6^2 = 37
3^2 + 7^2 = 58
5^2 + 8^2 = 89
=> n=12 is not a happy number

Dễ thấy ở trên ta tạo đươc 1 cycle tại số 89, nên fast & slow pointer sẽ giải được bài này.