Smartpointer Trong C++

I. Smartpointer là gì. Tại sao nên sử dụng smartpointer

Smart pointer là một khái niệm trong lập trình, thường được sử dụng trong các ngôn ngữ như C++ để quản lý việc cấp phát và giải phóng bộ nhớ động một cách an toàn và tự động.

Trong C++, khi bạn cấp phát bộ nhớ động bằng từ khóa new, bạn cần chịu trách nhiệm giải phóng bộ nhớ này bằng cách sử dụng từ khóa delete khi bạn không cần dùng đến nữa. Tuy nhiên, việc quản lý bộ nhớ thủ công như vậy có thể dẫn đến các vấn đề như quên giải phóng bộ nhớ, giải phóng bộ nhớ quá sớm hoặc giải phóng bộ nhớ hai lần.

Smart pointer giúp giải quyết các vấn đề này bằng cách cung cấp một giao diện trực quan và tự động quản lý bộ nhớ động. Smart pointer là một lớp đặc biệt, hoạt động như một con trỏ thông thường, nhưng có thêm các tính năng bổ sung. Các smart pointer phổ biến trong C++ bao gồm std::unique_ptr, std::shared_ptr và std::weak_ptr.

  • – std::unique_ptr cho phép quản lý một đối tượng động duy nhất. Khi đối tượng không còn cần thiết, bộ nhớ sẽ tự động được giải phóng.
    – std::shared_ptr cho phép quản lý một đối tượng động được chia sẻ bởi nhiều smart pointer. Nó duy trì một đếm tham chiếu và chỉ giải phóng bộ nhớ khi không còn smart pointer nào sử dụng nó.
    – std::weak_ptr là một phiên bản yếu hơn của std::shared_ptr và thường được sử dụng để tránh vấn đề vòng lặp tham chiếu (circular reference) giữa các đối tượng.

Việc sử dụng smart pointer giúp giảm rủi ro liên quan đến quản lý bộ nhớ và làm cho mã nguồn dễ đọc và bảo trì hơn.

II. Cú Pháp Khai Báo Smartpointer

Trong C++, để khai báo một smart pointer, bạn cần bao bọc kiểu dữ liệu của đối tượng cần quản lý bên trong cặp dấu nhọn (`<>`). Dưới đây là cú pháp để khai báo các smart pointer phổ biến:

1. td::unique_ptr: Để khai báo một std::unique_ptr, bạn cần chỉ định kiểu dữ liệu của đối tượng mà smart pointer sẽ quản lý.

std::unique_ptr<T> ptr;  // Khai báo một unique_ptr quản lý kiểu T

2. std::shared_ptr: Để khai báo một std::shared_ptr, bạn cũng cần chỉ định kiểu dữ liệu của đối tượng.

std::shared_ptr<T> ptr;  // Khai báo một shared_ptr quản lý kiểu T

3. std::weak_ptr: Cũng tương tự, để khai báo một std::weak_ptr, bạn cần chỉ định kiểu dữ liệu của đối tượng.

std::weak_ptr<T> ptr;  // Khai báo một weak_ptr quản lý kiểu T

Trong tất cả các trường hợp trên, `T` đại diện cho kiểu dữ liệu của đối tượng mà smart pointer sẽ quản lý. Bạn có thể thay thế `T` bằng bất kỳ kiểu dữ liệu nào phù hợp với nhu cầu của bạn.

Bên cạnh việc khai báo, bạn cũng có thể khởi tạo một smart pointer cùng lúc với khai báo bằng cách truyền đối tượng được cấp phát động vào smart pointer. Ví dụ:

std::unique_ptr<int> ptr(new int(42));  // Khai báo và khởi tạo unique_ptr quản lý một đối tượng int động
Lưu ý rằng `std::unique_ptr` yêu cầu con trỏ raw (raw pointer) như đối số cho constructor, trong khi `std::shared_ptr` và `std::weak_ptr` có thể khởi tạo từ một con trỏ raw hoặc từ một smart pointer khác.

III. Sự khác biệt giữa unique_ptr, shared_ptr, shared_ptr

Dưới đây là ví dụ minh họa về sự khác biệt giữa `std::unique_ptr`, `std::shared_ptr` và `std::weak_ptr` trong C++:

#include <iostream>
#include <memory>

class MyClass {
public:
    MyClass() {
        std::cout << "Constructor called!" << std::endl;
    }

    ~MyClass() {
        std::cout << "Destructor called!" << std::endl;
    }
};

int main() {
    // Sử dụng std::unique_ptr
    {
        std::unique_ptr<MyClass> uniquePtr(new MyClass());
        // std::unique_ptr sở hữu đối tượng MyClass

        // Sử dụng uniquePtr như một con trỏ thông thường
        uniquePtr->someMethod();

        // uniquePtr tự động giải phóng bộ nhớ khi ra khỏi phạm vi
    }

    // Sử dụng std::shared_ptr
    {
        std::shared_ptr<MyClass> sharedPtr1(new MyClass());
        // sharedPtr1 sở hữu đối tượng MyClass

        std::shared_ptr<MyClass> sharedPtr2 = sharedPtr1;
        // sharedPtr2 cũng sở hữu đối tượng MyClass

        // Sử dụng sharedPtr1 và sharedPtr2 như các con trỏ thông thường
        sharedPtr1->someMethod();
        sharedPtr2->someMethod();

        // sharedPtr1 và sharedPtr2 vẫn giữ quyền sở hữu cho đến khi cả hai ra khỏi phạm vi

    }

    // Sử dụng std::weak_ptr
    {
        std::shared_ptr<MyClass> sharedPtr(new MyClass());
        // sharedPtr sở hữu đối tượng MyClass

        std::weak_ptr<MyClass> weakPtr = sharedPtr;
        // weakPtr không sở hữu đối tượng MyClass, chỉ trỏ tới sharedPtr

        // Sử dụng weakPtr để kiểm tra xem đối tượng có còn sống hay không
        if (auto sharedPtrLocked = weakPtr.lock()) {
            // Đối tượng vẫn còn sống
            sharedPtrLocked->someMethod();
        } else {
            // Đối tượng đã bị giải phóng
        }

        // sharedPtr vẫn giữ quyền sở hữu, nhưng weakPtr không còn trỏ tới đối tượng khi sharedPtr giải phóng đối tượng

    }

    return 0;
}

Trong ví dụ trên:

  • std::unique_ptr được sử dụng để quản lý một đối tượng MyClass duy nhất. Nó sở hữu đối tượng và tự động giải phóng bộ nhớ khi ra khỏi phạm vi.
  • std::shared_ptr được sử dụng để quản lý một đối tượng MyClass được chia sẻ bởi nhiều smart pointer. Nó duy trì một đếm tham chiếu và chỉ giải phóng bộ nhớ khi không còn smart pointer nào sử dụng nó.
  • std::weak_ptr là một phiên bản yếu hơn của std::shared_ptr. Nó không sở hữu đối tượng, chỉ trỏ tới một std::shared_ptr. Bạn có thể dùng std::weak_ptr để kiểm tra xem đối tượng còn sống hay đã bị giải phóng. Khi cần sử dụng đối tượng, bạn cần khóa std::weak_ptr thành std::shared_ptr bằng phương thức lock().

Lưu ý rằng việc in ra thông báo trong hàm constructor và destructor chỉ để minh họa việc giải phóng bộ nhớ. Khi smart pointer ra khỏi phạm vi, destructor sẽ được gọi tự động để giải phóng bộ nhớ.

The post Smartpointer Trong C++ first appeared on Techacademy.

source https://techacademy.edu.vn/smartpointer-trong-c/

Bài 33 Leetcode: Search in Rotated Sorted Array

Đề bài:

Cho một mảng số nguyên `nums` đã được sắp xếp theo thứ tự tăng dần (với các giá trị riêng biệt).

Trước khi được truyền vào hàm của bạn, `nums` có thể đã được xoay vòng ở một vị trí không biết `k` (1 <= k < độ dài của nums) sao cho mảng kết quả là [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]] (đánh số từ 0). Ví dụ, [0,1,2,4,5,6,7] có thể đã được xoay vòng ở vị trí `k = 3` và trở thành [4,5,6,7,0,1,2].

Cho mảng `nums` sau khi xoay vòng và một số nguyên `target`, hãy trả về chỉ số của `target` trong `nums` nếu nó có trong mảng, hoặc trả về -1 nếu nó không có trong `nums`.

Bạn phải viết một thuật toán với độ phức tạp thời gian O(log n).

Ví dụ 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Ví dụ 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Ví dụ 3:

Input: nums = [1], target = 0
Output: -1

Ràng buộc:

  • 1 <= độ dài của nums <= 5000
  • -10^4 <= nums[i] <= 10^4
  • Tất cả các giá trị trong nums đều là duy nhất.
  • nums là một mảng tăng dần có thể đã được xoay vòng.
  • -10^4 <= target <= 10^4

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

class Solution {
 public:
  int search(vector<int>& nums, int target) {
    int l = 0;
    int r = nums.size() - 1;

    while (l <= r) {
      const int m = (l + r) / 2;
      if (nums[m] == target)
        return m;
      if (nums[l] <= nums[m]) {  // nums[l..m] are sorted
        if (nums[l] <= target && target < nums[m])
          r = m - 1;
        else
          l = m + 1;
      } else {  // nums[m..n - 1] are sorted
        if (nums[m] < target && target <= nums[r])
          l = m + 1;
        else
          r = m - 1;
      }
    }

    return -1;
  }
};

Đoạn code trên là một đoạn code C++ để tìm chỉ số của một số nguyên `target` trong mảng `nums` đã được sắp xếp và có thể đã được xoay vòng. Dưới đây là giải thích về thuật toán trong đoạn code:

1. Khai báo hai biến `l` và `r`, lần lượt là chỉ số bắt đầu và kết thúc của mảng `nums`.

2. Sử dụng vòng lặp while để thực hiện tìm kiếm trong mảng:

– Tính chỉ số giữa `m` bằng cách lấy trung bình của `l` và `r`: `m = (l + r) / 2`.

– Nếu giá trị `nums[m]` bằng `target`, tức là đã tìm thấy `target`, ta trả về chỉ số `m`.

– Nếu mảng con từ `nums[l]` đến `nums[m]` được sắp xếp (không bị xoay vòng), ta kiểm tra xem `target` có nằm trong khoảng giữa `nums[l]` và `nums[m]` hay không. Nếu có, ta cập nhật `r = m – 1` để thu hẹp phạm vi tìm kiếm trong mảng con này. Nếu không, ta cập nhật `l = m + 1` để bỏ qua mảng con này trong tìm kiếm.

– Ngược lại, nếu mảng con từ `nums[m]` đến `nums[r]` được sắp xếp (không bị xoay vòng), ta kiểm tra xem `target` có nằm trong khoảng giữa `nums[m]` và `nums[r]` hay không. Nếu có, ta cập nhật `l = m + 1` để bỏ qua mảng con này trong tìm kiếm. Nếu không, ta cập nhật `r = m – 1` để thu hẹp phạm vi tìm kiếm trong mảng con này.

3. Nếu không tìm thấy `target` trong mảng `nums`, ta trả về -1.

Thuật toán trên sử dụng phương pháp tìm kiếm nhị phân để tìm chỉ số của `target` trong mảng `nums`. Bằng cách sử dụng các điều kiện kiểm tra và thu hẹp phạm vi tìm kiếm, thuật toán đảm bảo độ phức tạp thời gian O(log n).

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

class Solution {
  public int search(int[] nums, int target) {
    int l = 0;
    int r = nums.length - 1;

    while (l <= r) {
      final int m = (l + r) / 2;
      if (nums[m] == target)
        return m;
      if (nums[l] <= nums[m]) { // nums[l..m] are sorted.
        if (nums[l] <= target && target < nums[m])
          r = m - 1;
        else
          l = m + 1;
      } else { // nums[m..n - 1] are sorted.
        if (nums[m] < target && target <= nums[r])
          l = m + 1;
        else
          r = m - 1;
      }
    }

    return -1;
  }
}

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

class Solution:
  def search(self, nums: List[int], target: int) -> int:
    l = 0
    r = len(nums) - 1

    while l <= r:
      m = (l + r) // 2
      if nums[m] == target:
        return m
      if nums[l] <= nums[m]:  # nums[l..m] are sorted.
        if nums[l] <= target < nums[m]:
          r = m - 1
        else:
          l = m + 1
      else:  # nums[m..n - 1] are sorted.
        if nums[m] < target <= nums[r]:
          l = m + 1
        else:
          r = m - 1

    return -1

The post Bài 33 Leetcode: Search in Rotated Sorted Array first appeared on Techacademy.

source https://techacademy.edu.vn/bai-33-leetcode-search-in-rotated-sorted-array/

Bài 32 Leetcode: Longest Valid Parentheses

Đề bài:

Cho một chuỗi chỉ chứa các ký tự ‘(‘ và ‘)’, trả về độ dài của chuỗi con ngoặc đúng (được hình thành đúng) dài nhất.

Ví dụ 1:

Input: s = "(()"
Output: 2
Giải thích: Chuỗi con ngoặc đúng dài nhất là "()".

Ví dụ 2:

Input: s = ")()())"
Output: 4
Giải thích: Chuỗi con ngoặc đúng dài nhất là "()()".

Ví dụ 3:

Input: s = ""
Output: 0

Ràng buộc:

  • 0 <= độ dài của chuỗi s <= 3 * 10^4
  • s[i] là ‘(‘, hoặc ‘)’.

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

class Solution {
 public:
  int longestValidParentheses(string s) {
    const string s2 = ")" + s;
    // dp[i] := the length of the longest valid parentheses in the substring
    // s2[1..i]
    vector<int> dp(s2.length());

    for (int i = 1; i < s2.length(); ++i)
      if (s2[i] == ')' && s2[i - dp[i - 1] - 1] == '(')
        dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2;

    return ranges::max(dp);
  }
};

Đoạn mã trên triển khai thuật toán để tìm độ dài của dãy ngoặc đúng dài nhất trong một chuỗi.

Thuật toán này hoạt động như sau:

1. Tạo chuỗi `s2` bằng cách thêm một ký tự đặc biệt vào đầu chuỗi `s`. Ký tự này sẽ đảm bảo rằng tất cả các dãy ngoặc đúng bắt đầu từ vị trí 1 của `s2` (loại bỏ trường hợp ngoặc đúng nằm ở đầu chuỗi `s`).

2. Khởi tạo một mảng `dp` có cùng độ dài với `s2`, trong đó `dp[i]` đại diện cho độ dài của dãy ngoặc đúng dài nhất trong đoạn con `s2[1..i]`.

3. Duyệt qua từng ký tự của `s2`, bắt đầu từ vị trí 1 đến cuối chuỗi.

4. Nếu ký tự tại vị trí `i` là `’)’` và ký tự tại vị trí `i – dp[i – 1] – 1` là `'(‘`, có nghĩa là ta đã tìm thấy một dãy ngoặc đúng. Ta cập nhật `dp[i]` bằng cách tính toán độ dài của dãy ngoặc đúng tại vị trí `i`.

– `dp[i]` được tính bằng `dp[i – 1] + dp[i – dp[i – 1] – 2] + 2`. Độ dài của dãy ngoặc đúng tại vị trí `i` được tính bằng tổng độ dài của dãy ngoặc đúng tại vị trí `i – 1`, độ dài của dãy ngoặc đúng trước dãy ngoặc đúng tại vị trí `i`, và 2 (độ dài của dãy ngoặc đúng hiện tại).

5. Trả về giá trị lớn nhất trong mảng `dp` là độ dài của dãy ngoặc đúng dài nhất trong chuỗi `s`.

Ví dụ, nếu chuỗi `s` là `”()(()”`, sau khi áp dụng thuật toán, giá trị trả về sẽ là 2, tương ứng với dãy ngoặc đúng `”()”` trong chuỗi.

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

class Solution {
  public int longestValidParentheses(String s) {
    final String s2 = ")" + s;
    // dp[i] := the length of the longest valid parentheses in the substring
    // s2[1..i]
    int dp[] = new int[s2.length()];

    for (int i = 1; i < s2.length(); ++i)
      if (s2.charAt(i) == ')' && s2.charAt(i - dp[i - 1] - 1) == '(')
        dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2;

    return Arrays.stream(dp).max().getAsInt();
  }
}

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

class Solution:
  def longestValidParentheses(self, s: str) -> int:
    s2 = ')' + s
    # dp[i] := the length of the longest valid parentheses in the substring
    # s2[1..i]
    dp = [0] * len(s2)

    for i in range(1, len(s2)):
      if s2[i] == ')' and s2[i - dp[i - 1] - 1] == '(':
        dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2

    return max(dp)

The post Bài 32 Leetcode: Longest Valid Parentheses first appeared on Techacademy.

source https://techacademy.edu.vn/bai-32-leetcode-longest-valid-parentheses/

Bài 31 Leetcode: Next Permutation

Đề bài:

Một hoán vị của một mảng số nguyên là một sắp xếp các thành viên của nó thành một chuỗi hoặc thứ tự tuyến tính.

  • Ví dụ, với arr = [1,2,3], dưới đây là tất cả các hoán vị của arr: [1,2,3], [1,3,2], [2, 1, 3], [2, 3, 1], [3,1,2], [3,2,1].

Hoán vị kế tiếp của một mảng số nguyên là hoán vị kế tiếp lớn hơn trong thứ tự từ điển của số nguyên đó. Cụ thể hơn, nếu tất cả các hoán vị của mảng được sắp xếp trong một container theo thứ tự từ điển của chúng, thì hoán vị kế tiếp của mảng đó là hoán vị tiếp theo trong container đã sắp xếp. Nếu sắp xếp như vậy không khả thi, mảng phải được sắp xếp lại theo thứ tự thấp nhất có thể (tức là sắp xếp tăng dần).

  • Ví dụ, hoán vị kế tiếp của arr = [1,2,3] là [1,3,2].
  • Tương tự, hoán vị kế tiếp của arr = [2,3,1] là [3,1,2].
  • Trong khi hoán vị kế tiếp của arr = [3,2,1] là [1,2,3] vì [3,2,1] không có một sắp xếp lại lớn hơn theo thứ tự từ điển.

Cho một mảng số nguyên nums, tìm hoán vị kế tiếp của nums.

Việc thay thế phải được thực hiện tại chỗ và chỉ sử dụng bộ nhớ phụ hằng số.

Ví dụ 1:

Input: nums = [1,2,3]
Output: [1,3,2]

Ví dụ 2:

Input: nums = [3,2,1]
Output: [1,2,3]

Ví dụ 3:

Input: nums = [1,1,5]
Output: [1,5,1]

Ràng buộc:

  • 1 <= độ dài của nums <= 100
  • 0 <= nums[i] <= 100

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

class Solution {
 public:
  void nextPermutation(vector<int>& nums) {
    const int n = nums.size();

    // From back to front, find the first number < nums[i + 1].
    int i;
    for (i = n - 2; i >= 0; --i)
      if (nums[i] < nums[i + 1])
        break;

    // From back to front, find the first number > nums[i], swap it with
    // nums[i].
    if (i >= 0)
      for (int j = n - 1; j > i; --j)
        if (nums[j] > nums[i]) {
          swap(nums[i], nums[j]);
          break;
        }

    // Reverse nums[i + 1..n - 1].
    reverse(nums, i + 1, n - 1);
  }

 private:
  void reverse(vector<int>& nums, int l, int r) {
    while (l < r)
      swap(nums[l++], nums[r--]);
  }
};

Đoạn mã trên triển khai thuật toán để tạo ra hoán vị kế tiếp của một mảng số nguyên.

Thuật toán này hoạt động như sau:

1. Tính kích thước `n` của mảng `nums`.

2. Tìm vị trí `i` sao cho `nums[i] < nums[i + 1]` từ phải qua trái. Ý nghĩa của bước này là tìm điểm dừng để thực hiện các bước tiếp theo để tạo ra hoán vị kế tiếp. Nếu không tìm thấy `i`, tức là mảng đã được sắp xếp giảm dần, ta đảo ngược toàn bộ mảng để tạo hoán vị đầu tiên và kết thúc thuật toán.

3. Từ phải qua trái, tìm phần tử đầu tiên lớn hơn `nums[i]` và ghi nhận vị trí `j`. Sau đó, hoán đổi `nums[i]` với `nums[j]`.

4. Đảo ngược phần còn lại của mảng `nums` từ `i + 1` tới `n – 1`. Điều này sẽ đảo ngược thứ tự của các phần tử từ vị trí `i + 1` đến cuối mảng, tạo ra hoán vị kế tiếp.

Ví dụ, nếu mảng ban đầu là `[1, 2, 3]`, sau khi áp dụng thuật toán, mảng sẽ trở thành `[1, 3, 2]`, là hoán vị kế tiếp của mảng ban đầu.

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

class Solution {
  public void nextPermutation(int[] nums) {
    final int n = nums.length;

    // From back to front, find the first number < nums[i + 1].
    int i;
    for (i = n - 2; i >= 0; --i)
      if (nums[i] < nums[i + 1])
        break;

    // From back to front, find the first number > nums[i], swap it with
    // nums[i].
    if (i >= 0)
      for (int j = n - 1; j > i; --j)
        if (nums[j] > nums[i]) {
          swap(nums, i, j);
          break;
        }

    // Reverse nums[i + 1..n - 1].
    reverse(nums, i + 1, n - 1);
  }

  private void reverse(int[] nums, int l, int r) {
    while (l < r)
      swap(nums, l++, r--);
  }

  private void swap(int[] nums, int i, int j) {
    final int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
  }
}

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

class Solution:
  def nextPermutation(self, nums: List[int]) -> None:
    n = len(nums)

    # From back to front, find the first number < nums[i + 1].
    i = n - 2
    while i >= 0:
      if nums[i] < nums[i + 1]:
        break
      i -= 1

    # From back to front, find the first number > nums[i], swap it with nums[i].
    if i >= 0:
      for j in range(n - 1, i, -1):
        if nums[j] > nums[i]:
          nums[i], nums[j] = nums[j], nums[i]
          break

    def reverse(nums: List[int], l: int, r: int) -> None:
      while l < r:
        nums[l], nums[r] = nums[r], nums[l]
        l += 1
        r -= 1

    # Reverse nums[i + 1..n - 1].
    reverse(nums, i + 1, len(nums) - 1)

The post Bài 31 Leetcode: Next Permutation first appeared on Techacademy.

source https://techacademy.edu.vn/bai-31-leetcode-next-permutation/

Bài 30 Leetcode: Substring with Concatenation of All Words

Đề bài:

Cho một chuỗi s và một mảng các chuỗi words. Tất cả các chuỗi trong mảng words có cùng độ dài.

Một chuỗi con nối trong s là một chuỗi con chứa tất cả các chuỗi của bất kỳ hoán vị nào của words được nối lại.

  • Ví dụ, nếu words = [“ab”, “cd”, “ef”], thì “abcdef”, “abefcd”, “cdabef”, “cdefab”, “efabcd” và “efcdab” đều là các chuỗi con nối. “acdbef” không phải là một chuỗi con nối vì nó không phải là sự nối của bất kỳ hoán vị nào của words.

Trả về chỉ mục bắt đầu của tất cả các chuỗi con nối trong s. Bạn có thể trả về kết quả theo bất kỳ thứ tự nào.

Ví dụ 1:

Input: s = "barfoothefoobarman", words = ["foo","bar"]
Output: [0,9]
Giải thích: Vì words.length == 2 và words[i].length == 3, nên chuỗi con nối phải có độ dài là 6.
Chuỗi con bắt đầu từ vị trí 0 là "barfoo". Nó là sự nối của ["bar", "foo"] và là một hoán vị của words.
Chuỗi con bắt đầu từ vị trí 9 là "foobar". Nó là sự nối của ["foo", "bar"] và là một hoán vị của words.
Thứ tự đầu ra không quan trọng. Trả về [0,9] cũng đúng.

Ví dụ 2:

Input: s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
Output: []
Giải thích: Vì words.length == 4 và words[i].length == 4, nên chuỗi con nối phải có độ dài là 16.
Không có chuỗi con có độ dài 16 trong s mà bằng với sự nối của bất kỳ hoán vị nào của words.
Chúng ta trả về một mảng rỗng.

Ví dụ 3:

Input: s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
Output: [6,9,12]
Giải thích: Vì words.length == 3 và words[i].length == 3, nên chuỗi con nối phải có độ dài là 9.
Chuỗi con bắt đầu từ vị trí 6 là "foobarthe". Nó là sự nối của ["foo","bar","the"] và là một hoán vị của words.
Chuỗi con bắt đầu từ vị trí 9 là "barthefoo". Nó là sự nối của ["bar","the","foo"] và là một hoán vị của words.
Chuỗi con bắt đầu từ vị trí 12 là "thefoobar". Nó là sự nối của ["the","foo","bar"] và là một hoán vị của words.

Ràng buộc:

  • 1 <= độ dài của chuỗi s <= 10^4
  • 1 <= số lượng từ trong mảng words <= 5000
  • 1 <= độ dài của từ words[i] <= 30
  • s và words[i] chỉ chứa các ký tự tiếng Anh viết thường.

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

class Solution {
 public:
  vector<int> findSubstring(string s, vector<string>& words) {
    if (s.empty() || words.empty())
      return {};

    const int k = words.size();
    const int n = words[0].length();
    vector<int> ans;
    unordered_map<string, int> count;

    for (const string& word : words)
      ++count[word];

    for (int i = 0; i < s.length() - k * n + 1; ++i) {
      unordered_map<string, int> seen;
      int j;
      for (j = 0; j < k; ++j) {
        const string& word = s.substr(i + j * n, n);
        if (++seen[word] > count[word])
          break;
      }
      if (j == k)
        ans.push_back(i);
    }

    return ans;
  }
};

Đây là một đoạn code C++ để tìm các chỉ mục bắt đầu của các chuỗi con nối trong chuỗi s. Dưới đây là một giải thích về thuật toán trong đoạn code:

1. Kiểm tra xem chuỗi s hoặc mảng words có rỗng không. Nếu có, trả về một mảng rỗng.

2. Khởi tạo các biến k và n. Biến k đại diện cho số lượng từ trong mảng words, và biến n đại diện cho độ dài của mỗi từ trong words. Đây là những thông số quan trọng để xác định độ dài của chuỗi con nối.

3. Khởi tạo một vector ans để lưu trữ các chỉ mục bắt đầu của chuỗi con nối.

4. Khởi tạo một unordered_map count để đếm số lượng từ xuất hiện trong words. Với mỗi từ trong words, tăng giá trị tương ứng trong unordered_map count lên 1.

5. Sử dụng vòng lặp for để duyệt qua các vị trí trong chuỗi s để tìm chuỗi con nối. Tham số i đại diện cho chỉ mục bắt đầu của chuỗi con nối. Vòng lặp chạy từ 0 đến độ dài của chuỗi s trừ đi k * n + 1, với k là số lượng từ trong words và n là độ dài của từ trong words.

6. Trong vòng lặp, khởi tạo một unordered_map seen để đếm số lượng từ xuất hiện trong chuỗi con nối hiện tại. Biến j được sử dụng để đánh dấu số lượng từ hợp lệ đã được tìm thấy trong chuỗi con nối.

7. Trong vòng lặp for lồng nhau, duyệt qua từng từ trong words. Sử dụng hàm substr để trích xuất từ tại vị trí i + j * n với độ dài n. Kiểm tra từ này có xuất hiện nhiều hơn số lần cho phép trong unordered_map count không. Nếu có, thoát khỏi vòng lặp.

8. Nếu biến j sau vòng lặp for lồng nhau bằng k, tức là đã tìm thấy một chuỗi con nối hợp lệ, thêm chỉ mục bắt đầu i vào vector ans.

9. Trả về vector ans chứa các chỉ mục bắt đầu của các chuỗi con nối hợp lệ trong chuỗi s.

Đây là một thuật toán tương đối đơn giản và hiệu quả để giải quyết bài toán tìm chuỗi con nối trong một chuỗi cho trước.

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

class Solution {
  public List<Integer> findSubstring(String s, String[] words) {
    if (s.isEmpty() || words.length == 0)
      return new ArrayList<>();

    final int k = words.length;
    final int n = words[0].length();
    List<Integer> ans = new ArrayList<>();
    Map<String, Integer> count = new HashMap<>();

    for (final String word : words)
      count.merge(word, 1, Integer::sum);

    for (int i = 0; i <= s.length() - k * n; ++i) {
      Map<String, Integer> seen = new HashMap<>();
      int j = 0;
      for (; j < k; ++j) {
        final String word = s.substring(i + j * n, i + j * n + n);
        seen.merge(word, 1, Integer::sum);
        if (seen.get(word) > count.getOrDefault(word, 0))
          break;
      }
      if (j == k)
        ans.add(i);
    }

    return ans;
  }
}

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

class Solution:
  def findSubstring(self, s: str, words: List[str]) -> List[int]:
    if len(s) == 0 or words == []:
      return []

    k = len(words)
    n = len(words[0])
    ans = []
    count = collections.Counter(words)

    for i in range(len(s) - k * n + 1):
      seen = collections.defaultdict(int)
      j = 0
      while j < k:
        word = s[i + j * n: i + j * n + n]
        seen[word] += 1
        if seen[word] > count[word]:
          break
        j += 1
      if j == k:
        ans.append(i)

    return ans

The post Bài 30 Leetcode: Substring with Concatenation of All Words first appeared on Techacademy.

source https://techacademy.edu.vn/bai-30-leetcode-substring-with-concatenation-of-all-words/

Bài 29 Leetcode: Divide Two Integers

Đề bài:

Cho hai số nguyên dividend và divisor, chia hai số nguyên mà không sử dụng các phép nhân, chia và lấy phần dư.

Phép chia nguyên này sẽ cắt giảm phần thập phân của nó. Ví dụ, 8.345 sẽ được cắt giảm thành 8 và -2.7335 sẽ được cắt giảm thành -2.

Trả về phần nguyên sau khi chia dividend cho divisor.

Lưu ý: Giả sử chúng ta đang làm việc trong một môi trường chỉ có thể lưu trữ các số nguyên trong khoảng số nguyên có dấu 32 bit: [-2^31, 2^31 – 1]. Đối với bài toán này, nếu phần nguyên là nghiêm ngặt lớn hơn 2^31 – 1, thì trả về 2^31 – 1, và nếu phần nguyên nhỏ hơn nghiêm ngặt hơn -2^31, thì trả về -2^31.

Ví dụ 1:

Input: dividend = 10, divisor = 3
Output: 3
Giải thích: 10/3 = 3.33333.. nhưng bị cắt giảm thành 3.

Ví dụ 2:

Input: dividend = 7, divisor = -3
Output: -2
Giải thích: 7/-3 = -2.33333.. nhưng bị cắt giảm thành -2.

Ràng buộc:

  • -2^31 <= dividend, divisor <= 2^31 – 1
  • divisor != 0

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

class Solution {
 public:
  int divide(int dividend, int divisor) {
    // -2^{31} / -1 = 2^31 -> overflow so return 2^31 - 1
    if (dividend == INT_MIN && divisor == -1)
      return INT_MAX;

    const int sign = dividend > 0 ^ divisor > 0 ? -1 : 1;
    long ans = 0;
    long dvd = labs(dividend);
    long dvs = labs(divisor);

    while (dvd >= dvs) {
      long k = 1;
      while (k * 2 * dvs <= dvd)
        k *= 2;
      dvd -= k * dvs;
      ans += k;
    }

    return sign * ans;
  }
};

Đây là một phương thức trong lớp `Solution` được sử dụng để thực hiện phép chia hai số nguyên `dividend` và `divisor` mà không sử dụng các phép nhân, chia và lấy phần dư.

Dưới đây là cách thuật toán hoạt động:

1. Kiểm tra trường hợp đặc biệt khi `dividend` là -2^31 và `divisor` là -1. Khi thực hiện phép chia này, sẽ xảy ra tràn số (overflow), vì vậy trả về giá trị INT_MAX (2^31 – 1).

2. Xác định dấu của kết quả phép chia bằng cách kiểm tra dấu của `dividend` và `divisor`. Nếu dấu khác nhau, kết quả sẽ có dấu âm, ngược lại sẽ có dấu dương. Gán giá trị `sign` tương ứng (-1 hoặc 1).

3. Khởi tạo biến `ans` với giá trị ban đầu là 0, đại diện cho phần nguyên của kết quả phép chia.

4. Sử dụng hàm `labs` để lấy giá trị tuyệt đối của `dividend` và `divisor`, gán cho biến `dvd` và `dvs`. Điều này đảm bảo rằng chúng ta đang làm việc với các giá trị không âm.

5. Thực hiện vòng lặp while cho đến khi `dvd` lớn hơn hoặc bằng `dvs`. Trong mỗi lần lặp, tiến hành tìm giá trị `k`, lần lượt nhân `k` với 2 và `dvs`, cho đến khi `k * 2 * dvs` lớn hơn `dvd`. Điều này giúp chúng ta tìm được giá trị lớn nhất của `k` sao cho `k * dvs` vẫn nhỏ hơn hoặc bằng `dvd`.

6. Giảm giá trị `dvd` đi `k * dvs` và tăng giá trị `ans` lên `k`. Điều này đại diện cho việc trừ đi một phần của `dvd` và cộng thêm một phần vào `ans`.

7. Trả về kết quả của phép chia, nhân với giá trị `sign` để đảm bảo đúng dấu.

Thuật toán trên sử dụng phép chia theo phương pháp tìm kiếm nhị phân để tìm ra phần nguyên của kết quả phép chia. Nó lặp đi lặp lại việc tìm giá trị `k` lớn nhất mà `k * dvs` vẫn nhỏ hơn hoặc bằng `dvd`, sau đó trừ `k * dvs` từ `dvd` và cộng `k` vào `ans`. Quá trình này tiếp tục cho đến khi `dvd` không còn lớn hơn hoặc bằng `dvs`.

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

class Solution {
  public int divide(long dividend, long divisor) {
    // -2^{31} / -1 = 2^31 will overflow, so return 2^31 - 1.
    if (dividend == Integer.MIN_VALUE && divisor == -1)
      return Integer.MAX_VALUE;

    final int sign = dividend > 0 ^ divisor > 0 ? -1 : 1;
    long ans = 0;
    long dvd = Math.abs(dividend);
    long dvs = Math.abs(divisor);

    while (dvd >= dvs) {
      long k = 1;
      while (k * 2 * dvs <= dvd)
        k *= 2;
      dvd -= k * dvs;
      ans += k;
    }

    return sign * (int) ans;
  }
}

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

class Solution:
  def divide(self, dividend: int, divisor: int) -> int:
    # -2^{31} / -1 = 2^31 will overflow, so return 2^31 - 1.
    if dividend == -2**31 and divisor == -1:
      return 2**31 - 1

    sign = -1 if (dividend > 0) ^ (divisor > 0) else 1
    ans = 0
    dvd = abs(dividend)
    dvs = abs(divisor)

    while dvd >= dvs:
      k = 1
      while k * 2 * dvs <= dvd:
        k <<= 1
      dvd -= k * dvs
      ans += k

    return sign * ans

The post Bài 29 Leetcode: Divide Two Integers first appeared on Techacademy.

source https://techacademy.edu.vn/bai-29-leetcode-divide-two-integers/

Bài 28 Leetcode: Find the Index of the First Occurrence in a String

Đề bài:

Cho hai chuỗi needle và haystack, trả về chỉ số của lần xuất hiện đầu tiên của needle trong haystack, hoặc -1 nếu needle không là một phần của haystack.

Ví dụ 1:

Input: haystack = "sadbutsad", needle = "sad"
Output: 0
Giải thích: "sad" xuất hiện tại vị trí 0 và 6.
Lần xuất hiện đầu tiên là tại vị trí 0, vì vậy chúng ta trả về 0.

Ví dụ 2:

Input: haystack = "leetcode", needle = "leeto"
Output: -1
Giải thích: "leeto" không xuất hiện trong "leetcode", vì vậy chúng ta trả về -1.

Ràng buộc:

  • 1 <= độ dài của haystack, needle <= 10^4
  • haystack và needle chỉ chứa các ký tự tiếng Anh viết thường.

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

class Solution {
 public:
  int strStr(string haystack, string needle) {
    const int m = haystack.length();
    const int n = needle.length();

    for (int i = 0; i < m - n + 1; i++)
      if (haystack.substr(i, n) == needle)
        return i;

    return -1;
  }
};

Đây là một phương thức trong lớp `Solution` được sử dụng để tìm kiếm và trả về chỉ số đầu tiên của chuỗi con `needle` trong chuỗi `haystack`. Nếu `needle` không xuất hiện trong `haystack`, phương thức sẽ trả về -1.

Dưới đây là cách thuật toán hoạt động:

1. Khởi tạo hai biến hằng `m` và `n` lần lượt là độ dài của `haystack` và `needle`.

2. Thực hiện vòng lặp `for` từ `i = 0` đến `m – n + 1`. Vòng lặp này sẽ duyệt qua các vị trí trong `haystack` mà có thể chứa được `needle`.

3. Trong mỗi lần lặp, kiểm tra xem chuỗi con của `haystack` bắt đầu từ vị trí `i` và có độ dài `n` có bằng `needle` không bằng cách sử dụng hàm `substr`.

4. Nếu chuỗi con bằng `needle`, trả về giá trị của `i` là chỉ số của lần xuất hiện đầu tiên của `needle` trong `haystack`.

5. Nếu không tìm thấy `needle` trong `haystack` sau khi duyệt qua tất cả các vị trí, trả về -1.

Thuật toán trên hoạt động bằng cách duyệt qua từng vị trí trong `haystack` mà có thể chứa được `needle`, và so sánh chuỗi con tại mỗi vị trí đó với `needle` để xác định xem có khớp hay không. Nếu tìm thấy khớp, trả về chỉ số của lần xuất hiện đầu tiên, nếu không tìm thấy, trả về -1.

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

class Solution {
  public int strStr(String haystack, String needle) {
    final int m = haystack.length();
    final int n = needle.length();

    for (int i = 0; i < m - n + 1; ++i)
      if (haystack.substring(i, i + n).equals(needle))
        return i;

    return -1;
  }
}

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

class Solution:
  def strStr(self, haystack: str, needle: str) -> int:
    m = len(haystack)
    n = len(needle)

    for i in range(m - n + 1):
      if haystack[i:i + n] == needle:
        return i

    return -1

The post Bài 28 Leetcode: Find the Index of the First Occurrence in a String first appeared on Techacademy.

source https://techacademy.edu.vn/bai-28-leetcode-find-the-index-of-the-first-occurrence-in-a-string/

Bài 27 Leetcode: Remove Element

Đề bài:

Cho một mảng số nguyên `nums` và một số nguyên `val`, loại bỏ tất cả các lần xuất hiện của `val` trong `nums` ngay tại chỗ. Thứ tự của các phần tử có thể thay đổi. Sau đó, trả về số lượng phần tử trong `nums` không bằng `val`.

Giả sử số lượng phần tử trong `nums` không bằng `val` là `k`, để được chấp nhận, bạn cần thực hiện các bước sau:

1. Thay đổi mảng `nums` sao cho `k` phần tử đầu tiên của `nums` chứa các phần tử không bằng `val`. Các phần tử còn lại của `nums` không quan trọng cũng như kích thước của `nums`.

2. Trả về `k`.

Trình đánh giá tùy chỉnh:

Trình đánh giá sẽ kiểm tra giải pháp của bạn bằng đoạn mã sau:

int[] nums = [...]; // Mảng đầu vào
int val = ...; // Giá trị cần loại bỏ
int[] expectedNums = [...]; // Kết quả mong đợi với độ dài chính xác.
// Mảng này đã được sắp xếp và không có giá trị nào bằng val.

int k = removeElement(nums, val); // Gọi triển khai của bạn

assert k == expectedNums.length;
sort(nums, 0, k); // Sắp xếp k phần tử đầu tiên của nums
for (int i = 0; i < actualLength; i++) {
assert nums[i] == expectedNums[i];
}

Nếu tất cả các khẳng định đều thành công, thì giải pháp của bạn sẽ được chấp nhận.

Ví dụ 1:

Input: nums = [3,2,2,3], val = 3
Output: 2, nums = [2,2,_,_]
Giải thích: Hàm của bạn nên trả về k = 2, với hai phần tử đầu tiên của nums là 2.
Các phần tử bên ngoài kết quả trả về k (do đó chúng được đánh dấu dưới dạng gạch dưới) không quan trọng.

Ví dụ 2:

Input: nums = [0,1,2,2,3,0,4,2], val = 2
Output: 5, nums = [0,1,4,0,3,_,_,_]
Giải thích: Hàm của bạn nên trả về k = 5, với năm phần tử đầu tiên của nums chứa 0, 0, 1, 3 và 4.
Lưu ý rằng năm phần tử có thể được trả về trong bất kỳ thứ tự nào.
Các phần tử bên ngoài kết quả trả về k (do đó chúng được đánh dấu dưới dạng gạch dưới) không quan trọng.

Ràng buộc:

  • 0 <= độ dài của nums <= 100
  • 0 <= nums[i] <= 50
  • 0 <= val <= 100

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

class Solution {
 public:
  int removeElement(vector<int>& nums, int val) {
    int i = 0;

    for (const int num : nums)
      if (num != val)
        nums[i++] = num;

    return i;
  }
};

Đây là một phương thức trong lớp `Solution` được sử dụng để loại bỏ tất cả các lần xuất hiện của một giá trị `val` trong một vector số nguyên `nums` và trả về số lượng phần tử còn lại sau khi loại bỏ.

Dưới đây là cách thuật toán hoạt động:

1. Khởi tạo một biến `i` với giá trị ban đầu là 0. Biến này sẽ được sử dụng để theo dõi vị trí hiện tại để ghi lại các phần tử khác `val` trong `nums`.

2. Thực hiện vòng lặp `for` để duyệt qua từng phần tử `num` trong `nums`.

3. Trong mỗi lần lặp, kiểm tra điều kiện: nếu `num` khác `val`, có nghĩa là `num` là một phần tử cần được giữ lại.

4. Trong trường hợp điều kiện trên đúng, ghi lại phần tử `num` vào vị trí `nums[i]` và tăng giá trị của `i` lên 1.

5. Sau khi kết thúc vòng lặp, giá trị của `i` sẽ là số lượng phần tử còn lại trong `nums` sau khi loại bỏ các lần xuất hiện của `val`.

6. Trả về giá trị `i`.

Thuật toán trên hoạt động bằng cách duyệt qua từng phần tử trong `nums` và chỉ ghi lại các phần tử khác `val` vào vị trí mới trong `nums`, đồng thời tăng giá trị của `i` để theo dõi số lượng phần tử còn lại. Các phần tử bị xóa (các lần xuất hiện của `val`) sẽ không được ghi lại và sẽ bị bỏ qua.

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

class Solution {
  public int removeElement(int[] nums, int val) {
    int i = 0;

    for (final int num : nums)
      if (num != val)
        nums[i++] = num;

    return i;
  }
}

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

class Solution:
  def removeElement(self, nums: List[int], val: int) -> int:
    i = 0

    for num in nums:
      if num != val:
        nums[i] = num
        i += 1

    return i

The post Bài 27 Leetcode: Remove Element first appeared on Techacademy.

source https://techacademy.edu.vn/bai-27-leetcode-remove-element/

Bài 25 Leetcode: Reverse Nodes in k-Group

Đề bài:

Cho head của một danh sách liên kết, đảo ngược các nút của danh sách theo từng nhóm k nút và trả về danh sách đã được thay đổi.

k là một số nguyên dương và nhỏ hơn hoặc bằng độ dài của danh sách liên kết. Nếu số lượng nút không chia hết cho k, thì các nút còn lại ở cuối danh sách sẽ được giữ nguyên.

Bạn không được thay đổi các giá trị trong các nút của danh sách, chỉ có thể thay đổi các nút chính nó.

Ví dụ 1:

Reverse Nodes in k-Group
Reverse Nodes in k-Group
Input: head = [1,2,3,4,5], k = 2
Output: [2,1,4,3,5]

Ví dụ 2:

Reverse Nodes in k-Group
Reverse Nodes in k-Group
Input: head = [1,2,3,4,5], k = 3
Output: [3,2,1,4,5]

Ràng buộc:

  • Số lượng nút trong danh sách là n.
  • 1 <= k <= n <= 5000
  • 0 <= giá trị của nút <= 1000.

Cách 1: Recursive

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

class Solution {
 public:
  ListNode* reverseKGroup(ListNode* head, int k) {
    if (head == nullptr)
      return nullptr;

    ListNode* tail = head;

    for (int i = 0; i < k; ++i) {
      // There are less than k nodes in the list, do nothing.
      if (tail == nullptr)
        return head;
      tail = tail->next;
    }

    ListNode* newHead = reverse(head, tail);
    head->next = reverseKGroup(tail, k);
    return newHead;
  }

 private:
  // Reverses [head, tail).
  ListNode* reverse(ListNode* head, ListNode* tail) {
    ListNode* prev = nullptr;
    ListNode* curr = head;
    while (curr != tail) {
      ListNode* next = curr->next;
      curr->next = prev;
      prev = curr;
      curr = next;
    }
    return prev;
  }
};

Đoạn mã trên triển khai một thuật toán để đảo ngược từng nhóm gồm k nút trong một danh sách liên kết.

Thuật toán này sử dụng đệ quy để đảo ngược danh sách liên kết theo nhóm k nút. Thuật toán được triển khai trong hàm `reverseKGroup`, nhận vào con trỏ `head` trỏ đến đầu danh sách liên kết và một số nguyên `k` đại diện cho số lượng nút trong mỗi nhóm.

Trước khi thực hiện đảo ngược, thuật toán kiểm tra xem danh sách liên kết có đủ nút để tạo thành một nhóm k không. Nếu không đủ, nghĩa là danh sách đã được đảo ngược hoàn toàn hoặc còn lại ít hơn k nút, thuật toán trả về `head` ban đầu và kết thúc đệ quy.

Nếu danh sách liên kết có đủ nút để tạo thành một nhóm k, thuật toán tiến hành đảo ngược nhóm này bằng cách gọi hàm `reverse` với `head` và `tail`. Hàm `reverse` sẽ đảo ngược danh sách từ `head` đến trước `tail` và trả về con trỏ đến nút đầu sau khi đảo ngược.

Sau khi đảo ngược nhóm, con trỏ `next` của `head` được gán bằng kết quả của đệ quy `reverseKGroup` trên `tail` (nhóm tiếp theo). Điều này để liên kết nhóm đã đảo ngược với nhóm tiếp theo sau khi đảo ngược danh sách liên kết.

Cuối cùng, thuật toán trả về con trỏ đến nút đầu của danh sách liên kết đã được đảo ngược.

Hàm `reverse` được triển khai để đảo ngược danh sách liên kết từ `head` đến trước `tail`. Nó sử dụng hai con trỏ `prev` và `curr` để theo dõi nút trước và nút hiện tại trong quá trình đảo ngược. Thuật toán duyệt từ `head` đến `tail` và thực hiện việc cập nhật liên kết giữa các nút để đảo ngược danh sách liên kết. Cuối cùng, hàm trả về con trỏ đến nút đầu sau khi đảo ngược.

Ví dụ, nếu danh sách liên kết ban đầu là 1 -> 2 -> 3 -> 4 -> 5 và k = 2, sau khi áp dụng thuật toán, danh sách liên kết sẽ trở thành 2 -> 1 -> 4 -> 3 -> 5.

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

class Solution {
  public ListNode reverseKGroup(ListNode head, int k) {
    if (head == null)
      return null;

    ListNode tail = head;

    for (int i = 0; i < k; ++i) {
      // There are less than k nodes in the list, do nothing.
      if (tail == null)
        return head;
      tail = tail.next;
    }

    ListNode newHead = reverse(head, tail);
    head.next = reverseKGroup(tail, k);
    return newHead;
  }

  // Reverses [head, tail).
  private ListNode reverse(ListNode head, ListNode tail) {
    ListNode prev = null;
    ListNode curr = head;
    while (curr != tail) {
      ListNode next = curr.next;
      curr.next = prev;
      prev = curr;
      curr = next;
    }
    return prev;
  }
}

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

class Solution:
  def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
    if not head:
      return None

    tail = head

    for _ in range(k):
      # There are less than k nodes in the list, do nothing.
      if not tail:
        return head
      tail = tail.next

    newHead = self._reverse(head, tail)
    head.next = self.reverseKGroup(tail, k)
    return newHead

  def _reverse(self, head: Optional[ListNode], tail: Optional[ListNode]) -> Optional[ListNode]:
    """Reverses [head, tail)."""
    prev = None
    curr = head
    while curr != tail:
      next = curr.next
      curr.next = prev
      prev = curr
      curr = next
    return prev

Cách 2: Iterative

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

class Solution {
 public:
  ListNode* reverseKGroup(ListNode* head, int k) {
    if (!head || k == 1)
      return head;

    const int length = getLength(head);
    ListNode dummy(0, head);
    ListNode* prev = &dummy;
    ListNode* curr = head;

    for (int i = 0; i < length / k; ++i) {
      for (int j = 0; j < k - 1; ++j) {
        ListNode* next = curr->next;
        curr->next = next->next;
        next->next = prev->next;
        prev->next = next;
      }
      prev = curr;
      curr = curr->next;
    }

    return dummy.next;
  }

 private:
  int getLength(ListNode* head) {
    int length = 0;
    for (ListNode* curr = head; curr; curr = curr->next)
      ++length;
    return length;
  }
};

Đoạn mã trên triển khai một thuật toán để đảo ngược từng nhóm gồm k nút trong một danh sách liên kết.

Thuật toán này sử dụng một con trỏ `dummy` để làm đầu và một con trỏ `prev` để theo dõi nút trước nhóm hiện tại. Ban đầu, con trỏ `prev` được khởi tạo để trỏ đến nút `dummy`, còn con trỏ `curr` được khởi tạo để trỏ đến nút đầu tiên của danh sách liên kết (`head`).

Thuật toán sử dụng một vòng lặp bên ngoài để xử lý từng nhóm k nút. Số lượng nhóm được xác định bằng cách tính độ dài của danh sách liên kết (`length`) và chia cho k.

Trong vòng lặp bên ngoài, thuật toán sử dụng một vòng lặp bên trong để đảo ngược từng nhóm k nút. Trong vòng lặp bên trong, con trỏ `next` được sử dụng để lưu trữ con trỏ tới nút tiếp theo sau `curr` (tức là nút thứ hai trong nhóm). Các liên kết giữa các nút được điều chỉnh để đảo ngược thứ tự của chúng. Cụ thể, `curr->next` được gán bằng `next->next` để liên kết với nút sau nút tiếp theo. `next->next` được gán bằng `prev->next` để liên kết với nút trước đó. Cuối cùng, `prev->next` được gán bằng `next` để liên kết với nút đảo ngược đầu tiên trong nhóm.

Sau khi hoàn thành vòng lặp bên trong, nhóm nút k đã được đảo ngược. Con trỏ `prev` và `curr` được cập nhật để trỏ đến nút cuối cùng của nhóm đã đảo ngược và nút tiếp theo của nhóm tiếp theo trong danh sách.

Cuối cùng, sau khi hoàn thành vòng lặp bên ngoài, danh sách liên kết đã được đảo ngược theo từng nhóm k nút. Con trỏ `dummy` không thay đổi, vì vậy ta trả về `dummy.next` là con trỏ đến danh sách liên kết đã đảo ngược.

Hàm `getLength` được sử dụng để tính độ dài của danh sách liên kết. Nó duyệt qua danh sách và đếm số lượng nút để trả về kết quả.

Ví dụ, nếu danh sách liên kết ban đầu là 1 -> 2 -> 3 -> 4 -> 5 và k = 2, sau khi áp dụng thuật toán, danh sách liên kết sẽ trở thành 2 -> 1 -> 4 -> 3 -> 5.

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

class Solution {
  public ListNode reverseKGroup(ListNode head, int k) {
    if (head == null || k == 1)
      return head;

    final int length = getLength(head);
    ListNode dummy = new ListNode(0, head);
    ListNode prev = dummy;
    ListNode curr = head;

    for (int i = 0; i < length / k; ++i) {
      for (int j = 0; j < k - 1; ++j) {
        ListNode next = curr.next;
        curr.next = next.next;
        next.next = prev.next;
        prev.next = next;
      }
      prev = curr;
      curr = curr.next;
    }

    return dummy.next;
  }

  private int getLength(ListNode head) {
    int length = 0;
    for (ListNode curr = head; curr != null; curr = curr.next)
      ++length;
    return length;
  }
}

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

class Solution:
  def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
    if not head or k == 1:
      return head

    def getLength(head: ListNode) -> int:
      length = 0
      while head:
        length += 1
        head = head.next
      return length

    length = getLength(head)
    dummy = ListNode(0, head)
    prev = dummy
    curr = head

    for _ in range(length // k):
      for _ in range(k - 1):
        next = curr.next
        curr.next = next.next
        next.next = prev.next
        prev.next = next
      prev = curr
      curr = curr.next

    return dummy.next

 

The post Bài 25 Leetcode: Reverse Nodes in k-Group first appeared on Techacademy.

source https://techacademy.edu.vn/bai-25-leetcode-reverse-nodes-in-k-group/

Bài 24 Leetcode: Swap Nodes in Pairs

Đề bài:

Cho một danh sách liên kết, hoán đổi mỗi cặp nút liên tiếp nhau và trả về đầu của danh sách liên kết đó. Bạn phải giải quyết bài toán mà không thay đổi các giá trị trong các nút của danh sách (nghĩa là chỉ có thể thay đổi các nút chính nó).

Ví dụ 1:

Swap Nodes in Pairs
Swap Nodes in Pairs
Input: head = [1,2,3,4]
Output: [2,1,4,3]

Ví dụ 2:

Input: head = []
Output: []

Ví dụ 3:

Input: head = [1]
Output: [1]

Ràng buộc:

  • Số lượng nút trong danh sách nằm trong khoảng [0, 100].
  • 0 <= giá trị của nút <= 100.

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

class Solution {
 public:
  ListNode* swapPairs(ListNode* head) {
    const int length = getLength(head);
    ListNode dummy(0, head);
    ListNode* prev = &dummy;
    ListNode* curr = head;

    for (int i = 0; i < length / 2; ++i) {
      ListNode* next = curr->next;
      curr->next = next->next;
      next->next = prev->next;
      prev->next = next;
      prev = curr;
      curr = curr->next;
    }

    return dummy.next;
  }

 private:
  int getLength(ListNode* head) {
    int length = 0;
    for (ListNode* curr = head; curr; curr = curr->next)
      ++length;
    return length;
  }
};

Đây là một phương thức trong lớp `Solution`. Phương thức này được sử dụng để hoán đổi các cặp nút liên tiếp trong danh sách liên kết và trả về đầu của danh sách liên kết đã được hoán đổi.

Dưới đây là cách thuật toán hoạt động:

1. Phương thức `swapPairs` nhận đầu vào là một con trỏ `head` đến đầu của danh sách liên kết.

2. Sử dụng phương thức `getLength` để tính độ dài của danh sách liên kết.

3. Khởi tạo một nút giả `dummy` với giá trị 0 và con trỏ `next` trỏ tới `head`.

4. Khởi tạo hai con trỏ `prev` và `curr` trỏ tới `dummy` và `head` tương ứng.

5. Với mỗi vòng lặp từ 0 đến `length / 2`, thực hiện các bước sau:

a. Lấy con trỏ `next` trỏ tới nút kế tiếp của `curr`.

b. Gán con trỏ `next` vào nút tiếp theo của `curr`.

c. Gán con trỏ `prev` vào nút tiếp theo của `next`.

d. Gán con trỏ `next` vào nút tiếp theo của `prev`.

e. Di chuyển con trỏ `prev` và `curr` tới nút tiếp theo trong danh sách liên kết.

6. Trả về con trỏ đến nút đầu tiên của danh sách liên kết sau khi hoán đổi.

Thuật toán này sử dụng một phương pháp lặp để hoán đổi các cặp nút liên tiếp trong danh sách liên kết. Bắt đầu bằng việc khởi tạo một nút giả và hai con trỏ `prev` và `curr` trỏ tới nút đầu tiên của danh sách. Trong mỗi bước, ta lấy con trỏ `next` trỏ tới nút kế tiếp của `curr`, sau đó hoán đổi các liên kết giữa các nút để hoán đổi cặp nút hiện tại. Sau đó, di chuyển con trỏ `prev` và `curr` tới cặp nút tiếp theo và tiếp tục quá trình hoán đổi cho đến khi không còn cặp nút để hoán đổi. Cuối cùng, trả về đầu của danh sách liên kết đã được hoán đổi.

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

class Solution {
  public ListNode swapPairs(ListNode head) {
    final int length = getLength(head);
    ListNode dummy = new ListNode(0, head);
    ListNode prev = dummy;
    ListNode curr = head;

    for (int i = 0; i < length / 2; ++i) {
      ListNode next = curr.next;
      curr.next = next.next;
      next.next = curr;
      prev.next = next;
      prev = curr;
      curr = curr.next;
    }

    return dummy.next;
  }

  private int getLength(ListNode head) {
    int length = 0;
    for (ListNode curr = head; curr != null; curr = curr.next)
      ++length;
    return length;
  }
}

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

class Solution:
  def swapPairs(self, head: ListNode) -> ListNode:
    def getLength(head: ListNode) -> int:
      length = 0
      while head:
        length += 1
        head = head.next
      return length

    length = getLength(head)
    dummy = ListNode(0, head)
    prev = dummy
    curr = head

    for _ in range(length // 2):
      next = curr.next
      curr.next = next.next
      next.next = prev.next
      prev.next = next
      prev = curr
      curr = curr.next

    return dummy.next

 

The post Bài 24 Leetcode: Swap Nodes in Pairs first appeared on Techacademy.

source https://techacademy.edu.vn/bai-24-leetcode-swap-nodes-in-pairs/