Bài 38 Leetcode: Count and Say

Đề bài:

Dãy số “count-and-say” là một dãy các chuỗi chữ số được định nghĩa bằng công thức đệ quy:

• countAndSay(1) = “1”
• countAndSay(n) là cách bạn “nói” chuỗi chữ số từ countAndSay(n-1), sau đó được chuyển đổi thành một chuỗi chữ số khác.

Để xác định cách “nói” một chuỗi chữ số, chia nó thành số lượng tối thiểu các chuỗi con sao cho mỗi chuỗi con chứa chính xác một chữ số duy nhất. Sau đó, đối với mỗi chuỗi con, nói ra số lượng chữ số, sau đó nói ra chữ số đó. Cuối cùng, ghép lại tất cả các chữ số đã nói.

Ví dụ, cách nói và chuyển đổi cho chuỗi chữ số “3322251”:

Cho một số nguyên dương n, trả về thuật ngữ n ^th trong dãy “count-and-say”.

Ví dụ 1:

Input: n = 1
Output: "1"
Giải thích: Đây là trường hợp cơ bản.

Ví dụ 2:

Input: n = 4
Output: "1211"
Explanation:
countAndSay(1) = "1"
countAndSay(2) = say "1" = one 1 = "11"
countAndSay(3) = say "11" = two 1's = "21"
countAndSay(4) = say "21" = one 2 + one 1 = "12" + "11" = "1211"

Ràng buộc:

• 1 <= n <= 30

Giải thích thuật toán bằng C ++

class Solution {
 public:
  string countAndSay(int n) {
    string ans = "1";

    while (--n) {
      string next;
      for (int i = 0; i < ans.length(); ++i) {
        int count = 1;
        while (i + 1 < ans.length() && ans[i] == ans[i + 1]) {
          ++count;
          ++i;
        }
        next += to_string(count) + ans[i];
      }
      ans = move(next);
    }

    return ans;
  }
};

Đoạn code trên là một đoạn code C++ để tính toán và trả về thuật ngữ thứ n trong dãy “count-and-say”. Dưới đây là giải thích về thuật toán trong đoạn code:

1. Hàm `countAndSay` nhận một số nguyên n là chỉ số của thuật ngữ cần tính toán và trả về chuỗi kết quả.

2. Ban đầu, ta khởi tạo chuỗi `ans` bằng chuỗi “1”, đây là thuật ngữ đầu tiên trong dãy.

3. Tiếp theo, ta lặp lại quá trình tính toán cho đến khi giảm giá trị của n về 0. Trong mỗi vòng lặp, ta tính toán thuật ngữ tiếp theo và gán vào chuỗi `next`.

4. Trong vòng lặp tính toán thuật ngữ tiếp theo, ta duyệt qua từng ký tự trong chuỗi `ans`. Ban đầu, ta khởi tạo biến `count` bằng 1 để đếm số lượng ký tự liên tiếp giống nhau. Sau đó, ta kiểm tra ký tự hiện tại và ký tự kế tiếp trong chuỗi `ans`. Nếu chúng giống nhau, ta tăng biến `count` và di chuyển tới ký tự kế tiếp. Quá trình này tiếp tục cho đến khi ký tự hiện tại và ký tự kế tiếp khác nhau.

5. Khi ký tự hiện tại và ký tự kế tiếp khác nhau, ta thêm vào chuỗi `next` số lượng ký tự đã đếm và ký tự đó. Sử dụng hàm `to_string` để chuyển đổi số lượng ký tự thành chuỗi.

6. Sau khi hoàn thành vòng lặp tính toán thuật ngữ tiếp theo, ta gán chuỗi `next` cho chuỗi `ans` bằng cách sử dụng `move` để tránh sao chép không cần thiết.

7. Cuối cùng, ta trả về chuỗi `ans` là kết quả thuật ngữ cần tính toán.

Thuật toán trên sử dụng vòng lặp để tính toán tuần tự các thuật ngữ trong dãy “count-and-say”. Mỗi lần lặp, ta duyệt qua các ký tự trong thuật ngữ trước đó và xây dựng thuật ngữ tiếp theo dựa trên số lượng ký tự liên tiếp và ký tự đó. Quá trình này được lặp lại cho đến khi tính toán được thuật ngữ thứ n.

Giải thích thuật toán bằng Java

class Solution {
  public String countAndSay(int n) {
    StringBuilder sb = new StringBuilder("1");

    while (--n > 0) {
      StringBuilder next = new StringBuilder();
      for (int i = 0; i < sb.length(); ++i) {
        int count = 1;
        while (i + 1 < sb.length() && sb.charAt(i) == sb.charAt(i + 1)) {
          ++count;
          ++i;
        }
        next.append(count).append(sb.charAt(i));
      }
      sb = next;
    }

    return sb.toString();
  }
}

Giải thích thuật toán bằng Python

class Solution:
  def countAndSay(self, n: int) -> str:
    ans = '1'

    for _ in range(n - 1):
      nxt = ''
      i = 0
      while i < len(ans):
        count = 1
        while i + 1 < len(ans) and ans[i] == ans[i + 1]:
          count += 1
          i += 1
        nxt += str(count) + ans[i]
        i += 1
      ans = nxt

    return ans