Bài 60 Leetcode: Permutation Sequence

Đề bài:

Tập hợp [1, 2, 3, …, n] chứa tổng cộng n! hoán vị duy nhất. Bằng cách liệt kê và đánh dấu tất cả các hoán vị theo thứ tự, chúng ta được dãy sau đối với n = 3:

  1. “123”
  2. “132”
  3. “213”
  4. “231”
  5. “312”
  6. “321”

Cho trước n và k, trả về hoán vị kth trong dãy.

Ví dụ 1:

Input: n = 3, k = 3
Output: "213"

Ví dụ 2:

Input: n = 4, k = 9
Output: "2314"

Ví dụ 3:

Input: n = 3, k = 1
Output: "123"

Ràng buộc:

  • 1 <= n <= 9
  • 1 <= k <= n!

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

class Solution {
 public:
  string getPermutation(int n, int k) {
    string ans;
    vector<int> nums(n);
    vector<int> fact(n + 1, 1);  // fact[i] := i!

    iota(nums.begin(), nums.end(), 1);

    for (int i = 2; i <= n; ++i)
      fact[i] = fact[i - 1] * i;

    --k;  // 0-indexed

    for (int i = n - 1; i >= 0; --i) {
      const int j = k / fact[i];
      k %= fact[i];
      ans += to_string(nums[j]);
      nums.erase(nums.begin() + j);
    }

    return ans;
  }
};

Đoạn mã trên là một phương thức trong lớp `Solution` được viết bằng ngôn ngữ C++ để tìm hoán vị thứ k trong dãy hoán vị của các số từ 1 đến n.

Phương thức `getPermutation` nhận đầu vào là hai số nguyên `n` và `k`. Nó trả về một chuỗi `ans` đại diện cho hoán vị thứ k trong dãy hoán vị của các số từ 1 đến n.

Trước hết, một chuỗi rỗng `ans` được khởi tạo để lưu trữ kết quả cuối cùng.

Một vector `nums` được khởi tạo với các số từ 1 đến n. Vector này đại diện cho tập hợp các số mà chúng ta sẽ tạo hoán vị từ.

Một vector `fact` được khởi tạo với kích thước n+1 và giá trị ban đầu của tất cả các phần tử là 1. Vector này được sử dụng để tính giai thừa của các số từ 1 đến n. `fact[i]` đại diện cho giai thừa của i.

Hàm `iota` được sử dụng để điền giá trị ban đầu của `nums` từ 1 đến n.

Tiếp theo, vòng lặp for đầu tiên được sử dụng để tính giai thừa cho các số từ 2 đến n và lưu trữ kết quả vào vector `fact`.

Sau đó, biến k được giảm đi 1 để chuyển từ kiểu đánh số từ 1 sang kiểu đánh số từ 0.

Vòng lặp for thứ hai được sử dụng để xác định giá trị của các chữ số trong hoán vị thứ k. Vòng lặp này chạy từ n-1 đến 0.

Trong vòng lặp, biến j được tính bằng phép chia k cho `fact[i]`. Điều này sẽ cho chúng ta biết giá trị của chữ số ở vị trí thứ i trong hoán vị thứ k.

Sau đó, biến k được cập nhật bằng phép chia lấy dư k cho `fact[i]`. Điều này sẽ cho biết hoán vị thứ k trong tập còn lại của các số.

Chữ số tại vị trí j trong vector `nums` được thêm vào chuỗi `ans` bằng cách chuyển đổi nó thành chuỗi sử dụng hàm `to_string`.

Cuối cùng, chữ số tại vị trí j trong `nums` được loại bỏ khỏi vector bằng cách sử dụng hàm `erase`.

Sau khi vòng lặp kết thúc, chuỗi `ans` sẽ chứa hoán vị thứ k và được trả về.

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

class Solution {
  public String getPermutation(int n, int k) {
    StringBuilder sb = new StringBuilder();
    List<Integer> nums = new ArrayList<>();
    int[] fact = new int[n + 1]; // fact[i] := i!

    for (int i = 1; i <= n; ++i)
      nums.add(i);

    Arrays.fill(fact, 1);
    for (int i = 2; i <= n; ++i)
      fact[i] = fact[i - 1] * i;

    --k; // 0-indexed

    for (int i = n - 1; i >= 0; --i) {
      final int j = k / fact[i];
      k %= fact[i];
      sb.append(nums.get(j));
      nums.remove(j);
    }

    return sb.toString();
  }
}

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

class Solution:
  def getPermutation(self, n: int, k: int) -> str:
    ans = ''
    nums = [i + 1 for i in range(n)]
    fact = [1] * (n + 1)  # fact[i] := i!

    for i in range(2, n + 1):
      fact[i] = fact[i - 1] * i

    k -= 1  # 0-indexed

    for i in reversed(range(n)):
      j = k // fact[i]
      k %= fact[i]
      ans += str(nums[j])
      nums.pop(j)

    return ans

Leave a Reply

Your email address will not be published. Required fields are marked *

PHP Code Snippets Powered By : XYZScripts.com
.
.
.
.