Bài tập lập trình - Luyện thuật toán

Trang này tổng hợp 200 bài tập luyện thuật toán, được biên soạn theo phong cách các bài trên các trang luyện thuật toán nổi tiếng, các ví dụ minh họa (test case) với Input/Output/Giải thích, phần ràng buộc (constraints), và nhãn độ khó. Đây là bước tiếp theo hợp lý nếu bạn đã hoàn thành Bài tập lập trình - Cơ bản và Nâng cao - ở đây trọng tâm là tư duy thuật toán và cấu trúc dữ liệu, không phải cú pháp của một ngôn ngữ cụ thể. Mỗi bài đều có đáp án minh họa bằng nhiều ngôn ngữ lập trình khác nhau.

200 bài được chia thành 60 bài Dễ, 100 bài Trung bình, 40 bài Khó, sắp xếp theo chủ đề từ cơ bản (mảng, chuỗi) đến nâng cao (quy hoạch động, đồ thị, backtracking). Mỗi bài đều có phần đáp án gợi ý ở dưới, mặc định ẩn đi - bạn nên tự làm trước (đọc kỹ các ví dụ và ràng buộc), sau đó bấm vào “Xem đáp án” để đối chiếu. Đáp án chỉ là một cách giải, không phải cách duy nhất và không phải lúc nào cũng tối ưu nhất.

(Đề bài được tham khảo, chuyển ngữ và điều chỉnh từ các bài toán phổ biến trên LeetCode, HackerRank và Codewars.)

Nhóm 1: Mảng & Số học cơ bản

1. Tìm các số bị thiếu trong mảng (Find All Numbers Disappeared in an Array)

Độ khó: Dễ · Chủ đề: Mảng

Cho mảng nums gồm n số nguyên trong khoảng [1, n], mỗi số có thể xuất hiện 1 hoặc 2 lần. Trả về danh sách (tăng dần) tất cả các số trong [1, n] không xuất hiện trong nums.

Ví dụ 1:

Input: nums = [4, 3, 2, 7, 8, 2, 3, 1]
Output: [5, 6]

Ví dụ 2:

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

Ràng buộc:

n == len(nums)
1 <= n <= 10^5
1 <= nums[i] <= n

Xem đáp án

def find_disappeared_numbers(nums):
    present = set(nums)
    return [i for i in range(1, len(nums) + 1) if i not in present]

print(find_disappeared_numbers([4, 3, 2, 7, 8, 2, 3, 1]))  # [5, 6]

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

vector<int> findDisappearedNumbers(vector<int>& nums) {
    unordered_set<int> present(nums.begin(), nums.end());
    vector<int> result;
    for (int i = 1; i <= (int)nums.size(); i++) {
        if (present.find(i) == present.end()) result.push_back(i);
    }
    return result;
}

int main() {
    vector<int> nums = {4, 3, 2, 7, 8, 2, 3, 1};
    for (int x : findDisappearedNumbers(nums)) cout << x << " ";
    cout << endl;  // 5 6
    return 0;
}

import java.util.*;

public class Main {
    static List<Integer> findDisappearedNumbers(int[] nums) {
        Set<Integer> present = new HashSet<>();
        for (int n : nums) present.add(n);
        List<Integer> result = new ArrayList<>();
        for (int i = 1; i <= nums.length; i++) {
            if (!present.contains(i)) result.add(i);
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {4, 3, 2, 7, 8, 2, 3, 1};
        System.out.println(findDisappearedNumbers(nums));  // [5, 6]
    }
}

fun findDisappearedNumbers(nums: List<Int>): List<Int> {
    val present = nums.toHashSet()
    return (1..nums.size).filter { it !in present }
}

fun main() {
    val nums = listOf(4, 3, 2, 7, 8, 2, 3, 1)
    println(findDisappearedNumbers(nums))  // [5, 6]
}

List<int> findDisappearedNumbers(List<int> nums) {
  final present = nums.toSet();
  return [for (var i = 1; i <= nums.length; i++) if (!present.contains(i)) i];
}

void main() {
  final nums = [4, 3, 2, 7, 8, 2, 3, 1];
  print(findDisappearedNumbers(nums)); // [5, 6]
}

2. Thời điểm mua bán cổ phiếu tốt nhất (Best Time to Buy and Sell Stock)

Độ khó: Dễ · Chủ đề: Mảng

Cho mảng prices, trong đó prices[i] là giá cổ phiếu ở ngày thứ i. Bạn chỉ được mua 1 lần và bán 1 lần sau đó. Tìm lợi nhuận lớn nhất có thể đạt được, nếu không thể có lãi thì trả về 0.

Ví dụ 1:

Input: prices = [7, 1, 5, 3, 6, 4]
Output: 5
Giải thích: Mua ngày giá 1, bán ngày giá 6, lãi 5.

Ví dụ 2:

Input: prices = [7, 6, 4, 3, 1]
Output: 0
Giải thích: Giá luôn giảm nên không có lãi, không giao dịch.

Ràng buộc:

1 <= len(prices) <= 10^5
0 <= prices[i] <= 10^4

Xem đáp án

Đang tải lời giải…

3. Kiểm tra phần tử trùng lặp (Contains Duplicate)

Độ khó: Dễ · Chủ đề: Mảng, Hash Set

Cho một mảng số nguyên, trả về True nếu có bất kỳ giá trị nào xuất hiện ít nhất 2 lần, ngược lại trả về False.

Ví dụ 1:

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

Ví dụ 2:

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

Ràng buộc:

1 <= len(nums) <= 10^5

Xem đáp án

Đang tải lời giải…

4. Dãy con liên tiếp có tổng lớn nhất (Maximum Subarray)

Độ khó: Dễ · Chủ đề: Mảng, Quy hoạch động

Cho một mảng số nguyên nums, tìm dãy con liên tiếp (chứa ít nhất 1 phần tử) có tổng lớn nhất, và trả về tổng đó (thuật toán Kadane).

Ví dụ 1:

Input: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6
Giải thích: Dãy con [4, -1, 2, 1] có tổng lớn nhất = 6.

Ví dụ 2:

Input: nums = [-1]
Output: -1

Ràng buộc:

1 <= len(nums) <= 10^5

Xem đáp án

Đang tải lời giải…

5. Đưa các số 0 về cuối mảng (Move Zeroes)

Độ khó: Dễ · Chủ đề: Mảng, Two Pointers

Cho mảng số nguyên nums, di chuyển tất cả các số 0 về cuối mảng, giữ nguyên thứ tự tương đối của các phần tử khác 0. Phải thực hiện tại chỗ (in-place), không tạo mảng mới.

Ví dụ 1:

Input: nums = [0, 1, 0, 3, 12]
Output: [1, 3, 12, 0, 0]

Ví dụ 2:

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

Ràng buộc:

1 <= len(nums) <= 10^4

Xem đáp án

Đang tải lời giải…

6. Xóa phần tử theo giá trị (Remove Element)

Độ khó: Dễ · Chủ đề: Mảng, Two Pointers

Cho mảng nums và một giá trị val. Xóa tại chỗ (in-place) tất cả các phần tử bằng val, trả về độ dài mới k. k phần tử đầu của nums sau biến đổi chứa các phần tử khác val, thứ tự không quan trọng.

Ví dụ 1:

Input: nums = [3, 2, 2, 3], val = 3
Output: k = 2, nums = [2, 2, ...]

Ví dụ 2:

Input: nums = [0, 1, 2, 2, 3, 0, 4, 2], val = 2
Output: k = 5, nums chứa [0, 1, 4, 0, 3] theo thứ tự bất kỳ

Ràng buộc:

0 <= len(nums) <= 100

Xem đáp án

Đang tải lời giải…

7. Cộng thêm 1 vào số biểu diễn dạng mảng (Plus One)

Độ khó: Dễ · Chủ đề: Mảng

Cho một mảng số nguyên digits biểu diễn các chữ số của một số nguyên không âm (chữ số đầu là chữ số hàng cao nhất). Cộng thêm 1 vào số đó và trả về mảng chữ số kết quả.

Ví dụ 1:

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

Ví dụ 2:

Input: digits = [9, 9, 9]
Output: [1, 0, 0, 0]

Ràng buộc:

1 <= len(digits) <= 100
0 <= digits[i] <= 9

Xem đáp án

Đang tải lời giải…

8. Xóa phần tử trùng khỏi mảng đã sắp xếp (Remove Duplicates from Sorted Array)

Độ khó: Dễ · Chủ đề: Mảng, Two Pointers

Cho mảng nums đã sắp xếp tăng dần, xóa các phần tử trùng lặp tại chỗ sao cho mỗi giá trị chỉ xuất hiện 1 lần, trả về độ dài mới k. k phần tử đầu của nums sau khi biến đổi phải chứa các giá trị duy nhất theo đúng thứ tự ban đầu.

Ví dụ 1:

Input: nums = [1, 1, 2]
Output: k = 2, nums = [1, 2, ...]

Ví dụ 2:

Input: nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
Output: k = 5, nums = [0, 1, 2, 3, 4, ...]

Ràng buộc:

1 <= len(nums) <= 3 * 10^4
nums đã được sắp xếp tăng dần.

Xem đáp án

Đang tải lời giải…

9. Số xuất hiện đúng 1 lần (Single Number)

Độ khó: Dễ · Chủ đề: Mảng, Bit Manipulation

Cho một mảng số nguyên, mỗi phần tử xuất hiện đúng 2 lần, ngoại trừ 1 phần tử chỉ xuất hiện đúng 1 lần. Tìm phần tử đó, yêu cầu độ phức tạp O(n) và không dùng thêm bộ nhớ phụ (không dùng set/dict).

Ví dụ 1:

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

Ví dụ 2:

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

Ràng buộc:

1 <= len(nums) <= 3 * 10^4

Xem đáp án

Đang tải lời giải…

10. Phần tử xuất hiện nhiều hơn nửa mảng (Majority Element)

Độ khó: Dễ · Chủ đề: Mảng

Cho mảng nums kích thước n, tìm phần tử xuất hiện nhiều hơn n // 2 lần. Đề bài đảm bảo luôn tồn tại phần tử như vậy. Thử giải với độ phức tạp O(n) và O(1) bộ nhớ phụ (thuật toán Boyer-Moore Voting).

Ví dụ 1:

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

Ví dụ 2:

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

Ràng buộc:

1 <= len(nums) <= 5 * 10^4

Xem đáp án

Đang tải lời giải…

11. Tích lớn nhất của hai phần tử (Maximum Product of Two Elements in an Array)

Độ khó: Dễ · Chủ đề: Mảng

Cho mảng số nguyên dương nums, chọn 2 chỉ số phân biệt i, j sao cho (nums[i] - 1) * (nums[j] - 1) đạt giá trị lớn nhất. Trả về giá trị lớn nhất đó.

Ví dụ 1:

Input: nums = [3, 4, 5, 2]
Output: 12
Giải thích: Chọn 2 phần tử lớn nhất là 5 và 4: (5-1) * (4-1) = 12.

Ví dụ 2:

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

Ràng buộc:

2 <= len(nums) <= 500
1 <= nums[i] <= 10^3

Xem đáp án

Đang tải lời giải…

12. Tìm phần khác biệt của hai mảng (Find the Difference of Two Arrays)

Độ khó: Dễ · Chủ đề: Mảng, Hash Set

Cho 2 mảng số nguyên nums1, nums2. Trả về một danh sách gồm 2 danh sách: danh sách các phần tử phân biệt chỉ có trong nums1 (không có trong nums2), và danh sách các phần tử phân biệt chỉ có trong nums2.

Ví dụ 1:

Input: nums1 = [1, 2, 3], nums2 = [2, 4, 6]
Output: [[1, 3], [4, 6]]

Ví dụ 2:

Input: nums1 = [1, 2, 3, 3], nums2 = [1, 1, 2, 2]
Output: [[3], []]

Ràng buộc:

1 <= len(nums1), len(nums2) <= 1000

Xem đáp án

Đang tải lời giải…

13. Xoay mảng sang phải k vị trí (Rotate Array)

Độ khó: Dễ · Chủ đề: Mảng

Cho mảng nums, xoay mảng sang phải k bước (k có thể lớn hơn độ dài mảng).

Ví dụ 1:

Input: nums = [1, 2, 3, 4, 5, 6, 7], k = 3
Output: [5, 6, 7, 1, 2, 3, 4]

Ví dụ 2:

Input: nums = [-1, -100, 3, 99], k = 2
Output: [3, 99, -1, -100]

Ràng buộc:

1 <= len(nums) <= 10^5
0 <= k <= 10^5

Xem đáp án

Đang tải lời giải…

14. Xáo trộn mảng (Shuffle the Array)

Độ khó: Dễ · Chủ đề: Mảng

Cho mảng nums gồm 2n phần tử theo dạng [x1, x2, ..., xn, y1, y2, ..., yn]. Trả về mảng theo thứ tự xen kẽ [x1, y1, x2, y2, ..., xn, yn].

Ví dụ 1:

Input: nums = [2, 5, 1, 3, 4, 7], n = 3
Output: [2, 3, 5, 4, 1, 7]
Giải thích: x = [2,5,1], y = [3,4,7] -> xen kẽ thành [2,3,5,4,1,7]

Ví dụ 2:

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

Ràng buộc:

1 <= n <= 500
len(nums) == 2 * n

Xem đáp án

Đang tải lời giải…

15. Tam giác Pascal (Pascal’s Triangle)

Độ khó: Dễ · Chủ đề: Mảng, Toán học

Cho số nguyên numRows, sinh ra numRows dòng đầu tiên của tam giác Pascal, mỗi số bằng tổng 2 số ngay phía trên nó ở dòng trước.

Ví dụ 1:

Input: numRows = 5
Output: [[1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1]]

Ví dụ 2:

Input: numRows = 1
Output: [[1]]

Ràng buộc:

1 <= numRows <= 30

Xem đáp án

Đang tải lời giải…

16. Số lớn thứ ba khác nhau (Third Maximum Number)

Độ khó: Dễ · Chủ đề: Mảng

Cho mảng số nguyên nums, trả về số lớn thứ ba trong số các giá trị khác nhau của mảng. Nếu không tồn tại (có ít hơn 3 giá trị khác nhau), trả về số lớn nhất.

Ví dụ 1:

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

Ví dụ 2:

Input: nums = [1, 2]
Output: 2
Giải thích: Không có số lớn thứ 3 (chỉ có 2 giá trị khác nhau), trả về số lớn nhất.

Ràng buộc:

1 <= len(nums) <= 10^4

Xem đáp án

Đang tải lời giải…

17. Kiểm tra tồn tại số gấp đôi (Check If N and Its Double Exist)

Độ khó: Dễ · Chủ đề: Mảng, Hash Set

Cho mảng số nguyên arr, kiểm tra có tồn tại 2 chỉ số i != j sao cho arr[i] == 2 * arr[j] hay không.

Ví dụ 1:

Input: arr = [10, 2, 5, 3]
Output: True
Giải thích: 10 = 2 * 5

Ví dụ 2:

Input: arr = [3, 1, 7, 11]
Output: False

Ràng buộc:

2 <= len(arr) <= 500
-10^3 <= arr[i] <= 10^3

Xem đáp án

Đang tải lời giải…

18. Chỉ số trung tâm của mảng (Find Pivot Index)

Độ khó: Dễ · Chủ đề: Mảng, Prefix Sum

Cho mảng nums, tìm chỉ số “trung tâm” (pivot) sao cho tổng các phần tử bên trái bằng tổng các phần tử bên phải chỉ số đó. Nếu không tồn tại, trả về -1. Nếu có nhiều đáp án, trả về chỉ số nhỏ nhất.

Ví dụ 1:

Input: nums = [1, 7, 3, 6, 5, 6]
Output: 3
Giải thích: Tổng bên trái index 3 = 1+7+3 = 11, tổng bên phải = 5+6 = 11.

Ví dụ 2:

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

Ràng buộc:

1 <= len(nums) <= 10^4

Xem đáp án

Đang tải lời giải…

19. Tổng dồn của mảng (Running Sum of 1d Array)

Độ khó: Dễ · Chủ đề: Mảng, Prefix Sum

Cho mảng nums, trả về mảng result sao cho result[i] là tổng của nums[0] + nums[1] + ... + nums[i].

Ví dụ 1:

Input: nums = [1, 2, 3, 4]
Output: [1, 3, 6, 10]

Ví dụ 2:

Input: nums = [3, 1, 2, 10, 1]
Output: [3, 4, 6, 16, 17]

Ràng buộc:

1 <= len(nums) <= 10^3

Xem đáp án

Đang tải lời giải…

20. Kiểm tra mảng đơn điệu (Monotonic Array)

Độ khó: Dễ · Chủ đề: Mảng

Cho mảng số nguyên nums, kiểm tra mảng có đơn điệu hay không - nghĩa là mảng chỉ tăng dần (không giảm) hoặc chỉ giảm dần (không tăng) trên toàn bộ mảng.

Ví dụ 1:

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

Ví dụ 2:

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

Ràng buộc:

1 <= len(nums) <= 10^5

Xem đáp án

Đang tải lời giải…

Nhóm 2: Chuỗi (String)

21. Ký tự không lặp đầu tiên (First Unique Character)

Độ khó: Dễ · Chủ đề: Chuỗi

Cho một chuỗi s, tìm chỉ số (index) của ký tự đầu tiên không lặp lại trong chuỗi. Nếu không có ký tự nào như vậy, trả về -1.

Ví dụ 1:

Input: s = "leetcode"
Output: 0
Giải thích: Ký tự 'l' ở vị trí 0 chỉ xuất hiện đúng 1 lần và là ký tự không lặp đầu tiên.

Ví dụ 2:

Input: s = "aabb"
Output: -1
Giải thích: Mọi ký tự đều xuất hiện từ 2 lần trở lên.

Ràng buộc:

1 <= len(s) <= 10^5
s chỉ gồm chữ cái thường tiếng Anh.

Xem đáp án

Đang tải lời giải…

22. Tiền tố chung dài nhất (Longest Common Prefix)

Độ khó: Dễ · Chủ đề: Chuỗi

Cho một danh sách các chuỗi, tìm tiền tố chung dài nhất của tất cả chuỗi trong danh sách. Nếu không có tiền tố chung, trả về chuỗi rỗng "".

Ví dụ 1:

Input: strs = ["flower", "flow", "flight"]
Output: "fl"

Ví dụ 2:

Input: strs = ["dog", "racecar", "car"]
Output: ""
Giải thích: Không có tiền tố chung giữa các chuỗi.

Ràng buộc:

1 <= len(strs) <= 200
0 <= len(strs[i]) <= 200

Xem đáp án

Đang tải lời giải…

23. Palindrome chỉ tính chữ và số (Valid Palindrome)

Độ khó: Dễ · Chủ đề: Chuỗi

Cho một chuỗi s, kiểm tra xem chuỗi đó có phải là palindrome hay không, chỉ xét các ký tự chữ cái và chữ số (bỏ qua dấu câu, khoảng trắng), không phân biệt hoa thường.

Ví dụ 1:

Input: s = "A man, a plan, a canal: Panama"
Output: True

Ví dụ 2:

Input: s = "race a car"
Output: False

Ràng buộc:

1 <= len(s) <= 2 * 10^5
s gồm ký tự ASCII in được.

Xem đáp án

Đang tải lời giải…

24. Đảo thứ tự các từ (Reverse Words in a String)

Độ khó: Dễ · Chủ đề: Chuỗi

Cho một câu s có thể chứa nhiều khoảng trắng liên tiếp ở đầu, cuối hoặc giữa các từ. In ra câu đó với thứ tự các từ bị đảo ngược, các từ cách nhau đúng 1 khoảng trắng, không có khoảng trắng thừa ở đầu/cuối.

Ví dụ 1:

Input: s = "the sky is blue"
Output: "blue is sky the"

Ví dụ 2:

Input: s = "  hello   world  "
Output: "world hello"

Ràng buộc:

1 <= len(s) <= 10^4
s chứa chữ cái tiếng Anh và khoảng trắng.

Xem đáp án

Đang tải lời giải…

25. Chuỗi đồng dạng (Isomorphic Strings)

Độ khó: Dễ · Chủ đề: Chuỗi

Cho 2 chuỗi s và t cùng độ dài, kiểm tra chúng có “đồng dạng” hay không: mỗi ký tự trong s có thể được thay thế để tạo thành t, với điều kiện ánh xạ 1-1 (2 ký tự khác nhau trong s không được ánh xạ tới cùng 1 ký tự trong t).

Ví dụ 1:

Input: s = "egg", t = "add"
Output: True
Giải thích: e->a, g->d.

Ví dụ 2:

Input: s = "foo", t = "bar"
Output: False
Giải thích: 'o' phải ánh xạ tới cả 'a' và 'r', vi phạm ánh xạ 1-1.

Ràng buộc:

1 <= len(s) == len(t) <= 5 * 10^4

Xem đáp án

Đang tải lời giải…

26. Thư đe dọa (Ransom Note)

Độ khó: Dễ · Chủ đề: Chuỗi

Cho 2 chuỗi ransom_note và magazine. Kiểm tra ransom_note có thể được “cắt ghép” hoàn toàn từ các ký tự có trong magazine hay không (mỗi ký tự trong magazine chỉ dùng được 1 lần).

Ví dụ 1:

Input: ransom_note = "aa", magazine = "aab"
Output: True

Ví dụ 2:

Input: ransom_note = "aa", magazine = "ab"
Output: False
Giải thích: magazine chỉ có 1 chữ 'a' trong khi ransom_note cần 2 chữ 'a'.

Ràng buộc:

1 <= len(ransom_note), len(magazine) <= 4.5 * 10^4
Chỉ gồm chữ cái thường tiếng Anh.

Xem đáp án

Đang tải lời giải…

27. Số La Mã sang số nguyên (Roman to Integer)

Độ khó: Dễ · Chủ đề: Chuỗi

Cho một chuỗi số La Mã hợp lệ (gồm các ký tự I, V, X, L, C, D, M), chuyển nó thành số nguyên tương ứng. Lưu ý các trường hợp trừ như “IV” = 4, “IX” = 9, “XL” = 40.

Ví dụ 1:

Input: s = "III"
Output: 3

Ví dụ 2:

Input: s = "LVIII"
Output: 58
Giải thích: L = 50, V = 5, III = 3.

Ràng buộc:

1 <= len(s) <= 15
s là số La Mã hợp lệ trong khoảng [1, 3999].

Xem đáp án

Đang tải lời giải…

28. Cộng hai số nhị phân (Add Binary)

Độ khó: Dễ · Chủ đề: Chuỗi

Cho 2 chuỗi nhị phân a và b, trả về tổng của chúng, cũng dưới dạng một chuỗi nhị phân (không dùng int(x, 2) hoặc bin()).

Ví dụ 1:

Input: a = "11", b = "1"
Output: "100"

Ví dụ 2:

Input: a = "1010", b = "1011"
Output: "10101"

Ràng buộc:

1 <= len(a), len(b) <= 10^4
a, b chỉ gồm ký tự ‘0’ hoặc ‘1’, không có số 0 thừa ở đầu (trừ khi bản thân số đó là “0”).

Xem đáp án

Đang tải lời giải…

29. Nén chuỗi (String Compression)

Độ khó: Dễ · Chủ đề: Chuỗi

Cho một chuỗi chỉ gồm chữ cái thường, nén chuỗi bằng cách thay các nhóm ký tự lặp liên tiếp thành <ký tự><số lần> (nếu số lần là 1 thì không ghi số). Ví dụ "aaabbc" thành "a3b2c".

Ví dụ 1:

Input: s = "aaabbc"
Output: "a3b2c"

Ví dụ 2:

Input: s = "abcd"
Output: "abcd"
Giải thích: Không có ký tự nào lặp lại nên chuỗi nén dài hơn hoặc bằng chuỗi gốc, giữ nguyên các nhóm độ dài 1.

Ràng buộc:

1 <= len(s) <= 2 * 10^4
s chỉ gồm chữ cái thường.

Xem đáp án

Đang tải lời giải…

30. Từ dài nhất bao gồm từ nhỏ hơn (Longest Word Built From Others)

Độ khó: Dễ · Chủ đề: Chuỗi

Cho một danh sách từ words, tìm từ dài nhất trong danh sách sao cho từ đó có thể được xây dựng dần dần bằng cách thêm từng ký tự một, mà tại mỗi bước tiền tố đó cũng phải có mặt trong danh sách. Nếu có nhiều đáp án cùng độ dài, trả về từ nhỏ nhất theo thứ tự từ điển.

Ví dụ 1:

Input: words = ["w", "wo", "wor", "worl", "world"]
Output: "world"
Giải thích: "world" có thể xây dần từ "w" -> "wo" -> "wor" -> "worl" -> "world", mỗi bước đều có trong danh sách.

Ví dụ 2:

Input: words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]
Output: "apple"

Ràng buộc:

1 <= len(words) <= 1000
1 <= len(words[i]) <= 30

Xem đáp án

Đang tải lời giải…

31. Chuỗi con không lặp ký tự dài nhất (Longest Substring Without Repeating Characters)

Độ khó: Trung bình · Chủ đề: Chuỗi

Cho một chuỗi s, tìm độ dài của chuỗi con liên tiếp dài nhất mà không có ký tự nào lặp lại.

Ví dụ 1:

Input: s = "abcabcbb"
Output: 3
Giải thích: Chuỗi con dài nhất không lặp là "abc", độ dài 3.

Ví dụ 2:

Input: s = "bbbbb"
Output: 1

Ví dụ 3:

Input: s = "pwwkew"
Output: 3
Giải thích: "wke" độ dài 3. Lưu ý "pwke" không phải chuỗi con liên tiếp.

Ràng buộc:

0 <= len(s) <= 5 * 10^4

Xem đáp án

Đang tải lời giải…

32. Nhóm các từ đồng dạng (Group Anagrams)

Độ khó: Trung bình · Chủ đề: Chuỗi

Cho một danh sách chuỗi, nhóm các chuỗi là anagram của nhau vào cùng một nhóm. Thứ tự các nhóm và thứ tự trong từng nhóm không quan trọng.

Ví dụ 1:

Input: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
Output: [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]

Ví dụ 2:

Input: strs = [""]
Output: [[""]]

Ràng buộc:

1 <= len(strs) <= 10^4
0 <= len(strs[i]) <= 100
strs[i] chỉ gồm chữ cái thường.

Xem đáp án

Đang tải lời giải…

33. Viết theo hình Zigzag (Zigzag Conversion)

Độ khó: Trung bình · Chủ đề: Chuỗi

Cho một chuỗi s và số hàng num_rows, sắp xếp các ký tự theo hình zigzag trên num_rows hàng (đi xuống rồi đi chéo lên, lặp lại), sau đó đọc lần lượt theo từng hàng để tạo thành chuỗi kết quả.

Ví dụ 1:

Input: s = "PAYPALISHIRING", num_rows = 3
Output: "PAHNAPLSIIGYIR"
Giải thích:
P   A   H   N
A P L S I I G
Y   I   R

Ví dụ 2:

Input: s = "AB", num_rows = 1
Output: "AB"
Giải thích: Với 1 hàng, chuỗi không đổi.

Ràng buộc:

1 <= len(s) <= 1000
1 <= num_rows <= 1000

Xem đáp án

Đang tải lời giải…

34. Chuỗi con đối xứng dài nhất (Longest Palindromic Substring)

Độ khó: Trung bình · Chủ đề: Chuỗi

Cho một chuỗi s, tìm chuỗi con liên tiếp dài nhất là palindrome (đối xứng). Nếu có nhiều đáp án cùng độ dài, trả về đáp án bất kỳ.

Ví dụ 1:

Input: s = "babad"
Output: "bab"
Giải thích: "aba" cũng là đáp án hợp lệ.

Ví dụ 2:

Input: s = "cbbd"
Output: "bb"

Ràng buộc:

1 <= len(s) <= 1000

Xem đáp án

Đang tải lời giải…

35. Nhân hai số dạng chuỗi (Multiply Strings)

Độ khó: Trung bình · Chủ đề: Chuỗi

Cho 2 chuỗi số num1 và num2 biểu diễn 2 số nguyên không âm, trả về tích của chúng dưới dạng chuỗi, không dùng int() để chuyển toàn bộ chuỗi thành số hoặc phép nhân lớn có sẵn.

Ví dụ 1:

Input: num1 = "2", num2 = "3"
Output: "6"

Ví dụ 2:

Input: num1 = "123", num2 = "456"
Output: "56088"

Ràng buộc:

1 <= len(num1), len(num2) <= 200
num1, num2 chỉ gồm chữ số, không có số 0 thừa ở đầu (trừ khi bản thân số là “0”).

Xem đáp án

Đang tải lời giải…

36. Cách giải mã (Decode Ways)

Độ khó: Trung bình · Chủ đề: Chuỗi

Một chuỗi số được mã hóa từ chữ cái theo quy tắc 'A' -> "1", 'B' -> "2", …, 'Z' -> "26". Cho một chuỗi số s, đếm xem có bao nhiêu cách giải mã được chuỗi đó thành chữ cái.

Ví dụ 1:

Input: s = "12"
Output: 2
Giải thích: Có thể giải mã thành "AB" (1 2) hoặc "L" (12).

Ví dụ 2:

Input: s = "226"
Output: 3
Giải thích: "BZ" (2 26), "VF" (22 6), "BBF" (2 2 6).

Ví dụ 3:

Input: s = "06"
Output: 0
Giải thích: "06" không hợp lệ vì không có ký tự nào tương ứng số bắt đầu bằng 0.

Ràng buộc:

1 <= len(s) <= 100
s chỉ gồm chữ số.

Xem đáp án

Đang tải lời giải…

37. Ngắt từ (Word Break)

Độ khó: Trung bình · Chủ đề: Chuỗi

Cho một chuỗi s và một danh sách từ điển word_dict, kiểm tra xem s có thể được tách thành một dãy các từ liên tiếp, mỗi từ đều thuộc word_dict hay không (mỗi từ trong từ điển có thể dùng lại nhiều lần).

Ví dụ 1:

Input: s = "leetcode", word_dict = ["leet", "code"]
Output: True
Giải thích: "leetcode" tách được thành "leet code".

Ví dụ 2:

Input: s = "catsandog", word_dict = ["cats", "dog", "sand", "and", "cat"]
Output: False

Ràng buộc:

1 <= len(s) <= 300
1 <= len(word_dict) <= 1000

Xem đáp án

Đang tải lời giải…

38. Máy tính biểu thức cơ bản (Basic Calculator)

Độ khó: Trung bình · Chủ đề: Chuỗi

Cho chuỗi s biểu diễn một biểu thức toán học gồm số nguyên không âm, dấu +, - và dấu ngoặc đơn (, ) (không có *, /). Tính và trả về kết quả của biểu thức.

Ví dụ 1:

Input: s = "1 + 1"
Output: 2

Ví dụ 2:

Input: s = "(1+(4+5+2)-3)+(6+8)"
Output: 23

Ràng buộc:

1 <= len(s) <= 3 * 10^5

Xem đáp án

Đang tải lời giải…

39. Chuỗi ngoặc hợp lệ có ký tự đại diện (Valid Parenthesis String)

Độ khó: Trung bình · Chủ đề: Chuỗi

Cho một chuỗi s chỉ gồm 3 loại ký tự '(', ')' và '*' (ký tự '*' có thể coi là '(', ')', hoặc chuỗi rỗng). Kiểm tra xem s có thể hợp lệ (mọi dấu ngoặc đều được đóng đúng cách) hay không.

Ví dụ 1:

Input: s = "()"
Output: True

Ví dụ 2:

Input: s = "(*)"
Output: True
Giải thích: '*' đóng vai trò chuỗi rỗng.

Ví dụ 3:

Input: s = "(*))"
Output: True

Ràng buộc:

1 <= len(s) <= 100

Xem đáp án

Đang tải lời giải…

40. So khớp mẫu ký tự đại diện (Wildcard Matching)

Độ khó: Trung bình · Chủ đề: Chuỗi

Cho chuỗi s và mẫu p chứa các ký tự thường, '?' (khớp đúng 1 ký tự bất kỳ) và '*' (khớp một dãy ký tự bất kỳ, kể cả chuỗi rỗng). Kiểm tra p có khớp toàn bộ s hay không.

Ví dụ 1:

Input: s = "aa", p = "a"
Output: False
Giải thích: "a" không khớp toàn bộ "aa".

Ví dụ 2:

Input: s = "cb", p = "?a"
Output: False

Ví dụ 3:

Input: s = "adceb", p = "*a*b"
Output: True
Giải thích: '*' khớp chuỗi rỗng, 'a' khớp 'a', '*' khớp "dce", 'b' khớp 'b'.

Ràng buộc:

0 <= len(s), len(p) <= 2000

Xem đáp án

Đang tải lời giải…

Nhóm 3: Hash Map & Two Pointers

41. Tổng hai số (Two Sum)

Độ khó: Trung bình · Chủ đề: Hash Map

Cho một mảng số nguyên nums và một số nguyên target, tìm chỉ số (index) của hai phần tử trong mảng sao cho tổng của chúng bằng target. Giả sử mỗi input có đúng một đáp án, và bạn không được dùng cùng một phần tử hai lần. Trả về hai chỉ số theo thứ tự bất kỳ.

Ví dụ 1:

Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]
Giải thích: nums[0] + nums[1] = 2 + 7 = 9

Ví dụ 2:

Input: nums = [3, 2, 4], target = 6
Output: [1, 2]
Giải thích: nums[1] + nums[2] = 2 + 4 = 6 (không được dùng lại nums[0] = 3)

Ví dụ 3:

Input: nums = [3, 3], target = 6
Output: [0, 1]

Ràng buộc:

2 <= len(nums) <= 10^4
-10^9 <= nums[i] <= 10^9
Luôn tồn tại đúng một cặp thỏa mãn.

Xem đáp án

Đang tải lời giải…

42. Tổng hai số trên mảng đã sắp xếp (Two Sum II)

Độ khó: Trung bình · Chủ đề: Two Pointers

Cho một mảng số nguyên numbers đã sắp xếp tăng dần và một số target. Tìm hai chỉ số (bắt đầu từ 1) sao cho tổng hai phần tử bằng target, dùng kỹ thuật hai con trỏ (two pointers) với độ phức tạp O(n) và O(1) bộ nhớ phụ (không dùng hash map).

Ví dụ 1:

Input: numbers = [2, 7, 11, 15], target = 9
Output: [1, 2]
Giải thích: numbers[1] + numbers[2] = 2 + 7 = 9 (đánh số từ 1)

Ví dụ 2:

Input: numbers = [2, 3, 4], target = 6
Output: [1, 3]

Ràng buộc:

2 <= len(numbers) <= 3 * 10^4
numbers đã sắp xếp tăng dần.
Luôn tồn tại đúng một cặp thỏa mãn.

Xem đáp án

Đang tải lời giải…

43. Tổng ba số bằng 0 (3Sum)

Độ khó: Trung bình · Chủ đề: Two Pointers

Cho một mảng số nguyên nums, tìm tất cả các bộ ba (a, b, c) phân biệt theo chỉ số sao cho a + b + c = 0. Kết quả không được chứa bộ ba trùng lặp (theo giá trị).

Ví dụ 1:

Input: nums = [-1, 0, 1, 2, -1, -4]
Output: [[-1, -1, 2], [-1, 0, 1]]
Giải thích: Hai bộ ba trên có tổng bằng 0, không tính trùng.

Ví dụ 2:

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

Ví dụ 3:

Input: nums = [0, 0, 0]
Output: [[0, 0, 0]]

Ràng buộc:

3 <= len(nums) <= 3000
-10^5 <= nums[i] <= 10^5

Xem đáp án

Đang tải lời giải…

44. Bộ ba gần target nhất (3Sum Closest)

Độ khó: Trung bình · Chủ đề: Two Pointers

Cho mảng số nguyên nums và số target, tìm tổng của 3 phần tử trong nums sao cho tổng đó gần target nhất. Trả về tổng đó.

Ví dụ 1:

Input: nums = [-1, 2, 1, -4], target = 1
Output: 2
Giải thích: Tổng gần 1 nhất là -1 + 2 + 1 = 2

Ví dụ 2:

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

Ràng buộc:

3 <= len(nums) <= 500
-1000 <= nums[i] <= 1000

Xem đáp án

Đang tải lời giải…

45. Tổng bốn số (4Sum)

Độ khó: Trung bình · Chủ đề: Two Pointers

Cho mảng số nguyên nums và số target, tìm tất cả các bộ bốn số phân biệt theo chỉ số có tổng bằng target, không trùng lặp bộ giá trị.

Ví dụ 1:

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

Ví dụ 2:

Input: nums = [2, 2, 2, 2, 2], target = 8
Output: [[2, 2, 2, 2]]

Ràng buộc:

1 <= len(nums) <= 200
-10^9 <= nums[i], target <= 10^9

Xem đáp án

Đang tải lời giải…

46. Chứa nhiều nước nhất (Container With Most Water)

Độ khó: Trung bình · Chủ đề: Two Pointers

Cho mảng số nguyên dương height, trong đó height[i] là chiều cao của cột thứ i. Chọn 2 cột i, j sao cho cùng với trục hoành, chúng tạo thành một cái “thùng” chứa được nhiều nước nhất (diện tích = min(height[i], height[j]) * |i - j|). Trả về diện tích lớn nhất đó.

Ví dụ 1:

Input: height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
Output: 49
Giải thích: Cột index 1 (cao 8) và index 8 (cao 7): min(8,7) * (8-1) = 7*7 = 49

Ví dụ 2:

Input: height = [1, 1]
Output: 1

Ràng buộc:

2 <= len(height) <= 10^5
0 <= height[i] <= 3 * 10^4

Xem đáp án

Đang tải lời giải…

47. Hứng nước mưa (Trapping Rain Water)

Độ khó: Trung bình · Chủ đề: Two Pointers

Cho mảng số nguyên không âm height mô tả biểu đồ cột (bản đồ độ cao), tính tổng lượng nước mưa có thể bị “giữ lại” giữa các cột sau khi trời mưa.

Ví dụ 1:

Input: height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
Output: 6

Ví dụ 2:

Input: height = [4, 2, 0, 3, 2, 5]
Output: 9

Ràng buộc:

1 <= len(height) <= 2 * 10^4
0 <= height[i] <= 10^5

Xem đáp án

Đang tải lời giải…

48. Phân loại 3 màu (Sort Colors)

Độ khó: Trung bình · Chủ đề: Two Pointers

Cho mảng nums chỉ chứa các giá trị 0, 1, 2 (đại diện đỏ, trắng, xanh). Sắp xếp mảng tại chỗ (in-place) sao cho các phần tử cùng màu đứng cạnh nhau, theo thứ tự đỏ (0) → trắng (1) → xanh (2), không dùng hàm sort() có sẵn, chỉ duyệt 1 lần (thuật toán Dutch National Flag).

Ví dụ 1:

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

Ví dụ 2:

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

Ràng buộc:

1 <= len(nums) <= 300
nums[i] chỉ nhận giá trị 0, 1, hoặc 2.

Xem đáp án

Đang tải lời giải…

49. Xóa phần tử trùng lặp, giữ tối đa 2 lần (Remove Duplicates II)

Độ khó: Trung bình · Chủ đề: Two Pointers

Cho mảng nums đã sắp xếp tăng dần, xóa bớt các phần tử trùng lặp tại chỗ sao cho mỗi giá trị xuất hiện tối đa 2 lần, giữ nguyên thứ tự tương đối. Trả về độ dài mảng mới (phần đầu của nums sau khi xử lý).

Ví dụ 1:

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

Ví dụ 2:

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

Ràng buộc:

1 <= len(nums) <= 3 * 10^4
nums đã sắp xếp tăng dần.

Xem đáp án

Đang tải lời giải…

50. Kiểm tra Sudoku hợp lệ (Valid Sudoku)

Độ khó: Trung bình · Chủ đề: Hash Map

Cho một bảng Sudoku 9x9 (dùng "." cho ô trống), kiểm tra bảng đó có hợp lệ hay không theo luật: mỗi hàng, mỗi cột, và mỗi ô vuông 3x3 không được chứa số trùng lặp trong các số 1-9 đã điền. (Không cần kiểm tra bảng có giải được hay không.)

Ví dụ 1:

Input: board với hàng đầu = ["5","3",".",".","7",".",".",".","."], các hàng còn lại hợp lệ
Output: True

Ví dụ 2:

Input: board có hai số "8" trong cùng cột đầu tiên
Output: False

Ràng buộc:

Bảng luôn có kích thước 9x9.
Mỗi ô là ký tự số 1-9 hoặc ".".

Xem đáp án

Đang tải lời giải…

51. Giao của hai mảng, giữ trùng lặp (Intersection of Two Arrays II)

Độ khó: Trung bình · Chủ đề: Hash Map

Cho 2 mảng số nguyên nums1, nums2. Trả về mảng chứa các phần tử là giao của hai mảng, mỗi phần tử xuất hiện đúng số lần nhỏ nhất mà nó xuất hiện ở cả hai mảng. Thứ tự kết quả không quan trọng.

Ví dụ 1:

Input: nums1 = [1, 2, 2, 1], nums2 = [2, 2]
Output: [2, 2]

Ví dụ 2:

Input: nums1 = [4, 9, 5], nums2 = [9, 4, 9, 8, 4]
Output: [4, 9] hoặc [9, 4]

Ràng buộc:

1 <= len(nums1), len(nums2) <= 1000

Xem đáp án

Đang tải lời giải…

52. Dãy con liên tiếp dài nhất (Longest Consecutive Sequence)

Độ khó: Trung bình · Chủ đề: Hash Map

Cho mảng số nguyên nums không sắp xếp, tìm độ dài của dãy các số nguyên liên tiếp dài nhất (không cần liên tiếp trong mảng gốc, chỉ cần giá trị liên tiếp, ví dụ 1,2,3,4). Yêu cầu thuật toán chạy O(n).

Ví dụ 1:

Input: nums = [100, 4, 200, 1, 3, 2]
Output: 4
Giải thích: Dãy liên tiếp dài nhất là [1, 2, 3, 4]

Ví dụ 2:

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

Ràng buộc:

0 <= len(nums) <= 10^5

Xem đáp án

Đang tải lời giải…

53. K phần tử xuất hiện nhiều nhất (Top K Frequent Elements)

Độ khó: Trung bình · Chủ đề: Hash Map

Cho mảng số nguyên nums và số nguyên k, trả về k phần tử xuất hiện nhiều nhất trong mảng, sắp xếp theo tần suất giảm dần.

Ví dụ 1:

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

Ví dụ 2:

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

Ràng buộc:

1 <= len(nums) <= 10^5
k luôn nhỏ hơn hoặc bằng số phần tử phân biệt trong nums.

Xem đáp án

Đang tải lời giải…

54. Tìm tất cả Anagram trong chuỗi (Find All Anagrams in a String)

Độ khó: Trung bình · Chủ đề: Hash Map

Cho 2 chuỗi s và p, tìm tất cả vị trí bắt đầu của các chuỗi con trong s là anagram của p (chứa đúng các ký tự của p, khác thứ tự).

Ví dụ 1:

Input: s = "cbaebabacd", p = "abc"
Output: [0, 6]
Giải thích: "cba" (vị trí 0) và "bac" (vị trí 6) đều là anagram của "abc"

Ví dụ 2:

Input: s = "abab", p = "ab"
Output: [0, 1, 2]

Ràng buộc:

1 <= len(s), len(p) <= 3 * 10^4

Xem đáp án

Đang tải lời giải…

55. Dãy con có tổng bằng K (Subarray Sum Equals K)

Độ khó: Trung bình · Chủ đề: Hash Map · Prefix Sum

Cho mảng số nguyên nums và số nguyên k, đếm số lượng dãy con liên tiếp có tổng đúng bằng k.

Ví dụ 1:

Input: nums = [1, 1, 1], k = 2
Output: 2
Giải thích: [1,1] (đầu) và [1,1] (cuối)

Ví dụ 2:

Input: nums = [1, 2, 3], k = 3
Output: 2
Giải thích: [1,2] và [3]

Ràng buộc:

1 <= len(nums) <= 2 * 10^4
nums[i] có thể âm.

Xem đáp án

Đang tải lời giải…

56. Mảng nhị phân cân bằng (Contiguous Array)

Độ khó: Trung bình · Chủ đề: Hash Map

Cho mảng nhị phân nums chỉ gồm 0 và 1, tìm độ dài dãy con liên tiếp dài nhất có số lượng 0 và 1 bằng nhau.

Ví dụ 1:

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

Ví dụ 2:

Input: nums = [0, 1, 0]
Output: 2
Giải thích: [0, 1] hoặc [1, 0] đều có độ dài 2

Ràng buộc:

1 <= len(nums) <= 10^5

Xem đáp án

Đang tải lời giải…

57. Đếm dãy con có tích nhỏ hơn K (Subarray Product Less Than K)

Độ khó: Trung bình · Chủ đề: Two Pointers · Sliding Window

Cho mảng số nguyên dương nums và số nguyên k, đếm số lượng dãy con liên tiếp có tích các phần tử nhỏ hơn k.

Ví dụ 1:

Input: nums = [10, 5, 2, 6], k = 100
Output: 8
Giải thích: [10], [5], [2], [6], [10,5], [5,2], [2,6], [5,2,6] đều có tích < 100

Ví dụ 2:

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

Ràng buộc:

1 <= len(nums) <= 3 * 10^4
1 <= nums[i] <= 1000
0 <= k <= 10^6

Xem đáp án

Đang tải lời giải…

58. Chuỗi con dài nhất chỉ chứa tối đa 2 ký tự khác nhau

Độ khó: Trung bình · Chủ đề: Sliding Window

Cho chuỗi s, tìm độ dài của chuỗi con liên tiếp dài nhất chỉ chứa tối đa 2 ký tự khác nhau.

Ví dụ 1:

Input: s = "eceba"
Output: 3
Giải thích: Chuỗi con "ece" có độ dài 3

Ví dụ 2:

Input: s = "ccaabbb"
Output: 5
Giải thích: Chuỗi con "aabbb" có độ dài 5

Ràng buộc:

1 <= len(s) <= 10^5

Xem đáp án

Đang tải lời giải…

59. Bình phương mảng đã sắp xếp (Squares of a Sorted Array)

Độ khó: Trung bình · Chủ đề: Two Pointers

Cho mảng số nguyên nums đã sắp xếp tăng dần (có thể chứa số âm). Trả về mảng bình phương của từng phần tử, vẫn sắp xếp tăng dần, với độ phức tạp O(n) (không dùng sort()).

Ví dụ 1:

Input: nums = [-4, -1, 0, 3, 10]
Output: [0, 1, 9, 16, 100]

Ví dụ 2:

Input: nums = [-7, -3, 2, 3, 11]
Output: [4, 9, 9, 49, 121]

Ràng buộc:

1 <= len(nums) <= 10^4
nums đã sắp xếp tăng dần.

Xem đáp án

Đang tải lời giải…

60. Cứu người bằng thuyền (Boats to Save People)

Độ khó: Trung bình · Chủ đề: Two Pointers · Greedy

Cho mảng people là cân nặng của từng người, và limit là trọng tải tối đa mỗi thuyền chở được tối đa 2 người. Tìm số lượng thuyền tối thiểu để chở hết mọi người.

Ví dụ 1:

Input: people = [1, 2], limit = 3
Output: 1
Giải thích: 1 thuyền chở cả 2 người (1 + 2 = 3 <= 3)

Ví dụ 2:

Input: people = [3, 2, 2, 1], limit = 3
Output: 3
Giải thích: (1,2), (2), (3)

Ràng buộc:

1 <= len(people) <= 5 * 10^4
1 <= people[i] <= limit <= 3 * 10^4

Xem đáp án

Đang tải lời giải…

Nhóm 4: Sliding Window & Prefix Sum

61. Trung bình cộng lớn nhất của dãy con độ dài k (Maximum Average Subarray I)

Độ khó: Trung bình · Chủ đề: Sliding Window

Cho mảng số nguyên nums và số nguyên k, tìm dãy con liên tiếp có đúng k phần tử sao cho trung bình cộng của nó là lớn nhất. Trả về giá trị trung bình đó.

Ví dụ 1:

Input: nums = [1,12,-5,-6,50,3], k = 4
Output: 12.75
Giải thích: Dãy con [12,-5,-6,50] có tổng 51, trung bình 51/4 = 12.75, lớn nhất trong các dãy con độ dài 4.

Ví dụ 2:

Input: nums = [5,5,5], k = 1
Output: 5.0
Giải thích: Mọi dãy con độ dài 1 đều có trung bình 5.

Ràng buộc:

1 <= k <= len(nums) <= 10^5
-10^4 <= nums[i] <= 10^4

Xem đáp án

Đang tải lời giải…

62. Thay thế ký tự để chuỗi con dài nhất toàn ký tự giống nhau (Longest Repeating Character Replacement)

Độ khó: Trung bình · Chủ đề: Sliding Window

Cho một chuỗi s chỉ gồm chữ in hoa và một số nguyên k. Bạn được phép thay thế tối đa k ký tự bất kỳ trong chuỗi bằng ký tự khác. Tìm độ dài của chuỗi con liên tiếp dài nhất chứa toàn cùng một ký tự sau khi thay thế.

Ví dụ 1:

Input: s = "ABAB", k = 2
Output: 4
Giải thích: Thay 2 ký tự 'A' (hoặc 'B') để được "AAAA" hoặc "BBBB".

Ví dụ 2:

Input: s = "AABABBA", k = 1
Output: 4
Giải thích: Thay ký tự ở vị trí 3 thành 'A' để được "AABAABA" hoặc "AAAA" liên tiếp, độ dài 4.

Ràng buộc:

1 <= len(s) <= 10^5
s chỉ gồm chữ cái in hoa A-Z
0 <= k <= len(s)

Xem đáp án

Đang tải lời giải…

63. Kiểm tra hoán vị chuỗi con (Permutation in String)

Độ khó: Trung bình · Chủ đề: Sliding Window

Cho 2 chuỗi s1 và s2. Kiểm tra xem s2 có chứa một chuỗi con nào là hoán vị của s1 hay không.

Ví dụ 1:

Input: s1 = "ab", s2 = "eidbaooo"
Output: True
Giải thích: s2 chứa "ba", là một hoán vị của "ab".

Ví dụ 2:

Input: s1 = "ab", s2 = "eidboaoo"
Output: False
Giải thích: Không có chuỗi con nào của s2 là hoán vị của "ab".

Ràng buộc:

1 <= len(s1) <= len(s2) <= 10^4
s1, s2 chỉ gồm chữ thường a-z

Xem đáp án

Đang tải lời giải…

64. Hái trái cây trong giỏ (Fruit Into Baskets)

Độ khó: Trung bình · Chủ đề: Sliding Window

Một hàng cây, mỗi cây cho một loại trái cây fruits[i]. Bạn có đúng 2 giỏ, mỗi giỏ chỉ chứa được một loại trái cây duy nhất (không giới hạn số lượng). Bắt đầu từ một cây bất kỳ, đi sang phải liên tục và hái mỗi cây một trái, dừng lại khi gặp loại trái thứ 3. Tìm số lượng trái cây tối đa có thể hái được.

Ví dụ 1:

Input: fruits = [1,2,1]
Output: 3
Giải thích: Hái được cả 3 cây vì chỉ có 2 loại (1 và 2).

Ví dụ 2:

Input: fruits = [0,1,2,2]
Output: 3
Giải thích: Hái từ cây thứ 2 trở đi: [1,2,2].

Ràng buộc:

1 <= len(fruits) <= 10^5
0 <= fruits[i] <= 10^4

Xem đáp án

Đang tải lời giải…

65. Số lượng tối đa số 1 liên tiếp III (Max Consecutive Ones III)

Độ khó: Trung bình · Chủ đề: Sliding Window

Cho mảng nhị phân nums và số nguyên k. Bạn được phép đổi tối đa k số 0 thành số 1. Trả về số lượng số 1 liên tiếp tối đa có thể đạt được.

Ví dụ 1:

Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
Output: 6
Giải thích: Đổi 2 số 0 ở vị trí 5 và 10 thành 1, dãy con [1,1,1,0,0,1,1,1,1,1,0] có 6 số 1 liên tiếp từ vị trí 5 đến 10.

Ví dụ 2:

Input: nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], k = 3
Output: 10

Ràng buộc:

1 <= len(nums) <= 10^5
nums[i] là 0 hoặc 1
0 <= k <= len(nums)

Xem đáp án

Đang tải lời giải…

66. Đếm dãy con có tổng chia hết cho k (Subarray Sums Divisible by K)

Độ khó: Trung bình · Chủ đề: Prefix Sum

Cho mảng số nguyên nums và số nguyên k, đếm số lượng dãy con liên tiếp (không rỗng) có tổng chia hết cho k.

Ví dụ 1:

Input: nums = [4,5,0,-2,-3,1], k = 5
Output: 7
Giải thích: Có 7 dãy con tổng chia hết cho 5: [4,5,0,-2,-3,1], [5], [5,0], [5,0,-2,-3], [0], [0,-2,-3], [-2,-3].

Ví dụ 2:

Input: nums = [5], k = 9
Output: 0

Ràng buộc:

1 <= len(nums) <= 3*10^4
-10^4 <= nums[i] <= 10^4
2 <= k <= 10^4

Xem đáp án

Đang tải lời giải…

67. Tích của mảng trừ phần tử hiện tại (Product of Array Except Self)

Độ khó: Trung bình · Chủ đề: Prefix Sum

Cho mảng số nguyên nums, trả về mảng result sao cho result[i] bằng tích của tất cả phần tử trong nums trừ nums[i]. Không dùng phép chia, độ phức tạp O(n).

Ví dụ 1:

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

Ví dụ 2:

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

Ràng buộc:

2 <= len(nums) <= 10^5
-30 <= nums[i] <= 30

Xem đáp án

Đang tải lời giải…

68. Truy vấn tổng đoạn - mảng bất biến (Range Sum Query - Immutable)

Độ khó: Trung bình · Chủ đề: Prefix Sum

Thiết kế cấu trúc dữ liệu cho mảng số nguyên bất biến nums, hỗ trợ nhiều truy vấn sum_range(i, j) trả về tổng các phần tử từ chỉ số i đến j (bao gồm cả hai đầu), mỗi truy vấn phải chạy O(1).

Ví dụ 1:

Input: nums = [-2, 0, 3, -5, 2, -1]
sumRange(0, 2) -> 1    (vì -2+0+3 = 1)
sumRange(2, 5) -> -1   (vì 3-5+2-1 = -1)
sumRange(0, 5) -> -3

Ràng buộc:

1 <= len(nums) <= 10^4
0 <= i <= j <= len(nums) - 1
Tối đa 10^4 lượt gọi sumRange

Xem đáp án

Đang tải lời giải…

69. Dãy con liên tục có tổng chia hết cho k (Continuous Subarray Sum)

Độ khó: Trung bình · Chủ đề: Prefix Sum

Cho mảng số nguyên không âm nums và số nguyên k. Kiểm tra xem mảng có chứa một dãy con liên tiếp độ dài ít nhất 2 có tổng là bội số của k hay không (k = 0 nghĩa là tổng phải bằng 0).

Ví dụ 1:

Input: nums = [23,2,4,6,7], k = 6
Output: True
Giải thích: [2,4] có tổng 6, là bội số của 6.

Ví dụ 2:

Input: nums = [23,2,6,4,7], k = 6
Output: True
Giải thích: [23,2,6,4,7] có tổng 42, là bội số của 6, độ dài 5.

Ràng buộc:

1 <= len(nums) <= 10^5
0 <= nums[i] <= 10^9
0 <= sum(nums) <= 2^31 - 1
1 <= k <= 2^31 - 1

Xem đáp án

Đang tải lời giải…

70. Tìm tất cả phần tử trùng lặp trong mảng (Find All Duplicates in an Array)

Độ khó: Trung bình · Chủ đề: Prefix Sum / Mảng

Cho mảng nums gồm n số nguyên trong khoảng [1, n], mỗi số xuất hiện 1 hoặc 2 lần. Tìm tất cả các số xuất hiện 2 lần, độ phức tạp O(n) thời gian và O(1) bộ nhớ phụ (không tính mảng kết quả).

Ví dụ 1:

Input: nums = [4,3,2,7,8,2,3,1]
Output: [2,3]

Ví dụ 2:

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

Ràng buộc:

n == len(nums)
1 <= n <= 10^5
1 <= nums[i] <= n

Xem đáp án

Đang tải lời giải…

71. Dãy con ngắn nhất có tổng >= target (Minimum Size Subarray Sum)

Độ khó: Trung bình · Chủ đề: Sliding Window

Cho mảng số nguyên dương nums và số nguyên dương target, tìm độ dài của dãy con liên tiếp ngắn nhất mà tổng của nó >= target. Nếu không tồn tại, trả về 0.

Ví dụ 1:

Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Giải thích: [4,3] có tổng 7, là dãy con ngắn nhất thỏa mãn.

Ví dụ 2:

Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0
Giải thích: Tổng cả mảng chỉ là 8, không đủ 11.

Ràng buộc:

1 <= target <= 10^9
1 <= len(nums) <= 10^5
1 <= nums[i] <= 10^4

Xem đáp án

Đang tải lời giải…

72. Trung bình cộng của dãy con bán kính k (K Radius Subarray Averages)

Độ khó: Trung bình · Chủ đề: Prefix Sum

Cho mảng nums và số nguyên k. Với mỗi chỉ số i, nếu tồn tại đủ k phần tử ở cả hai bên (tức i - k >= 0 và i + k <= n - 1), tính trung bình cộng làm tròn xuống của 2k + 1 phần tử xung quanh i (từ i-k đến i+k); nếu không đủ, kết quả tại i là -1. Trả về mảng kết quả.

Ví dụ 1:

Input: nums = [7,4,3,9,1,8,5,2,6], k = 3
Output: [-1,-1,-1,5,4,4,-1,-1,-1]
Giải thích: Tại i=3: (7+4+3+9+1+8+5)/7 = 37/7 = 5 (làm tròn xuống).

Ví dụ 2:

Input: nums = [100000], k = 0
Output: [100000]
Giải thích: k=0 nghĩa là mỗi phần tử tự là trung bình của chính nó.

Ràng buộc:

n == len(nums)
1 <= n <= 10^5
0 <= nums[i], k <= 10^5

Xem đáp án

Đang tải lời giải…

73. Số lượng dãy con có giá trị lớn nhất giới hạn trong khoảng (Number of Subarrays with Bounded Maximum)

Độ khó: Trung bình · Chủ đề: Sliding Window

Cho mảng số nguyên dương nums và 2 số left, right. Đếm số dãy con liên tiếp (không rỗng) mà giá trị lớn nhất trong dãy con nằm trong khoảng [left, right].

Ví dụ 1:

Input: nums = [2,1,4,3], left = 2, right = 3
Output: 3
Giải thích: 3 dãy con thỏa mãn: [2], [2,1], [3].

Ví dụ 2:

Input: nums = [2,9,2,5,6], left = 2, right = 8
Output: 7

Ràng buộc:

1 <= len(nums) <= 10^5
0 <= nums[i] <= 10^9
0 <= left <= right <= 10^9

Xem đáp án

Đang tải lời giải…

74. Dãy con nhị phân có tổng bằng goal (Binary Subarrays With Sum)

Độ khó: Trung bình · Chủ đề: Sliding Window

Cho mảng nhị phân nums và số nguyên goal, đếm số lượng dãy con liên tiếp (không rỗng) có tổng đúng bằng goal.

Ví dụ 1:

Input: nums = [1,0,1,0,1], goal = 2
Output: 4
Giải thích: 4 dãy con thỏa mãn: [1,0,1], [1,0,1,0], [0,1,0,1], [1,0,1] (2 vị trí bắt đầu khác nhau).

Ví dụ 2:

Input: nums = [0,0,0,0,0], goal = 0
Output: 15

Ràng buộc:

1 <= len(nums) <= 3*10^4
nums[i] là 0 hoặc 1
0 <= goal <= len(nums)

Xem đáp án

Đang tải lời giải…

75. Điểm số lớn nhất khi lấy k lá bài (Maximum Points You Can Obtain from Cards)

Độ khó: Trung bình · Chủ đề: Sliding Window

Có n lá bài xếp thành hàng, cardPoints[i] là điểm của lá thứ i. Mỗi lượt bạn chỉ được lấy 1 lá từ đầu hoặc cuối hàng, phải lấy đúng k lượt. Tìm điểm số lớn nhất có thể đạt được.

Ví dụ 1:

Input: cardPoints = [1,2,3,4,5,6,1], k = 3
Output: 12
Giải thích: Lấy 3 lá cuối cùng: 1+6+5 = 12.

Ví dụ 2:

Input: cardPoints = [2,2,2], k = 2
Output: 4

Ràng buộc:

1 <= len(cardPoints) <= 10^5
1 <= cardPoints[i] <= 10^4
1 <= k <= len(cardPoints)

Xem đáp án

Đang tải lời giải…

76. Giá trị lớn nhất trong từng cửa sổ trượt (Sliding Window Maximum)

Độ khó: Khó · Chủ đề: Sliding Window

Cho mảng nums và một cửa sổ kích thước k trượt từ trái sang phải, mỗi lần trượt 1 bước. Với mỗi vị trí cửa sổ, trả về giá trị lớn nhất trong cửa sổ đó. Yêu cầu độ phức tạp O(n).

Ví dụ 1:

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Giải thích: Cửa sổ [1,3,-1]->3, [3,-1,-3]->3, [-1,-3,5]->5, [-3,5,3]->5, [5,3,6]->6, [3,6,7]->7.

Ví dụ 2:

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

Ràng buộc:

1 <= len(nums) <= 10^5
-10^4 <= nums[i] <= 10^4
1 <= k <= len(nums)

Xem đáp án

Đang tải lời giải…

77. Cửa sổ nhỏ nhất chứa toàn bộ ký tự (Minimum Window Substring)

Độ khó: Khó · Chủ đề: Sliding Window

Cho 2 chuỗi s và t. Tìm chuỗi con ngắn nhất của s sao cho chứa tất cả các ký tự của t (kể cả trùng lặp, không quan tâm thứ tự). Nếu không tồn tại, trả về chuỗi rỗng.

Ví dụ 1:

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Giải thích: "BANC" là chuỗi con ngắn nhất chứa cả 'A', 'B', 'C'.

Ví dụ 2:

Input: s = "a", t = "aa"
Output: ""
Giải thích: t cần 2 ký tự 'a' nhưng s chỉ có 1 -> không tồn tại.

Ràng buộc:

1 <= len(s), len(t) <= 10^5
s, t gồm chữ cái Latin (hoa và thường)

Xem đáp án

Đang tải lời giải…

78. Chuỗi con dài nhất có tối đa k ký tự khác nhau (Longest Substring with At Most K Distinct Characters)

Độ khó: Khó · Chủ đề: Sliding Window

Cho chuỗi s và số nguyên k, tìm độ dài của chuỗi con liên tiếp dài nhất chứa tối đa k ký tự khác nhau. Xử lý cả trường hợp k = 0 (kết quả phải là 0) và k lớn hơn số ký tự khác nhau trong s.

Ví dụ 1:

Input: s = "eceba", k = 2
Output: 3
Giải thích: Chuỗi con "ece" có 2 ký tự khác nhau ('e', 'c'), độ dài 3.

Ví dụ 2:

Input: s = "aa", k = 1
Output: 2

Ví dụ 3 (biên):

Input: s = "abc", k = 0
Output: 0
Giải thích: Không được phép có ký tự khác nhau nào nên không có cửa sổ hợp lệ.

Ràng buộc:

0 <= len(s) <= 5*10^4
0 <= k <= 50

Xem đáp án

Đang tải lời giải…

79. Đếm dãy con có đúng k số nguyên khác nhau (Subarrays with K Different Integers)

Độ khó: Khó · Chủ đề: Sliding Window

Cho mảng nums và số nguyên k, đếm số lượng dãy con liên tiếp có đúng k giá trị khác nhau (không phải “tối đa”).

Ví dụ 1:

Input: nums = [1,2,1,2,3], k = 2
Output: 7
Giải thích: Các dãy con thỏa mãn: [1,2],[2,1],[1,2],[2,3],[1,2,1],[2,1,2],[1,2,1,2].

Ví dụ 2:

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

Ràng buộc:

1 <= len(nums) <= 2*10^4
1 <= nums[i], k <= len(nums)

Xem đáp án

Đang tải lời giải…

80. Chuỗi con là ghép nối của tất cả các từ (Substring with Concatenation of All Words)

Độ khó: Khó · Chủ đề: Sliding Window

Cho chuỗi s và một danh sách từ words, tất cả các từ có cùng độ dài. Tìm mọi vị trí bắt đầu trong s mà chuỗi con bắt đầu từ đó là một cách ghép nối (không dư, không thiếu, không chồng chéo) của toàn bộ các từ trong words theo bất kỳ thứ tự nào, kể cả khi words có từ trùng lặp.

Ví dụ 1:

Input: s = "barfoothefoobarman", words = ["foo","bar"]
Output: [0,9]
Giải thích: Từ vị trí 0: "barfoo" = "bar"+"foo". Từ vị trí 9: "foobar" = "foo"+"bar".

Ví dụ 2:

Input: s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
Output: []
Giải thích: Không có vị trí nào ghép đủ và đúng số lượng từng từ (words có "word" xuất hiện 2 lần).

Ví dụ 3 (biên - từ trùng lặp):

Input: s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
Output: [6,9,12]

Ràng buộc:

1 <= len(s) <= 10^4
1 <= len(words) <= 5000
1 <= len(words[i]) <= 30
s và words[i] chỉ gồm chữ thường

Xem đáp án

Đang tải lời giải…

Nhóm 5: Stack, Queue & Linked List

81. Kiểm tra ngoặc hợp lệ (Valid Parentheses)

Độ khó: Dễ · Chủ đề: Stack

Cho một chuỗi s chỉ chứa các ký tự (, ), {, }, [, ]. Kiểm tra chuỗi ngoặc đó có “hợp lệ” hay không: mỗi dấu mở phải được đóng bởi đúng loại dấu đóng tương ứng, và theo đúng thứ tự.

Ví dụ 1:

Input: s = "()[]{}"
Output: True
Giải thích: Mỗi cặp ngoặc đều đóng đúng loại và đúng thứ tự.

Ví dụ 2:

Input: s = "(]"
Output: False
Giải thích: Dấu "(" bị đóng bởi "]" sai loại.

Ràng buộc:

1 <= len(s) <= 10^4
s chỉ gồm các ký tự trong "()[]{}"

Xem đáp án

Đang tải lời giải…

82. Cài đặt Queue bằng hai Stack (Implement Queue using Two Stacks)

Độ khó: Dễ · Chủ đề: Stack, Queue

Cài đặt một hàng đợi (queue - FIFO) chỉ dùng hai ngăn xếp (stack - LIFO), hỗ trợ các thao tác push(x) (thêm vào cuối hàng đợi), pop() (lấy ra và xóa phần tử đầu hàng đợi), peek() (xem phần tử đầu hàng đợi).

Ví dụ 1:

Input: push(1), push(2), peek(), pop(), pop()
Output: peek() -> 1, pop() -> 1, pop() -> 2
Giải thích: Hàng đợi hoạt động theo nguyên tắc vào trước ra trước (FIFO).

Ví dụ 2:

Input: push(5), pop(), push(6), push(7), pop()
Output: pop() -> 5, pop() -> 6

Ràng buộc:

Tối đa 100 lệnh gọi các thao tác.
pop/peek chỉ được gọi khi hàng đợi không rỗng.

Xem đáp án

Đang tải lời giải…

83. Min Stack (Stack hỗ trợ lấy giá trị nhỏ nhất)

Độ khó: Dễ · Chủ đề: Stack

Thiết kế một ngăn xếp (stack) hỗ trợ các thao tác push(x), pop(), top() (xem đỉnh stack), và get_min() - trả về phần tử nhỏ nhất hiện có trong stack, tất cả đều chạy trong thời gian O(1).

Ví dụ 1:

Input: push(-2), push(0), push(-3), get_min(), pop(), top(), get_min()
Output: get_min() -> -3, top() -> 0, get_min() -> -2

Ví dụ 2:

Input: push(5), push(3), push(7), get_min()
Output: 3

Ràng buộc:

-2^31 <= x <= 2^31 - 1
pop, top, get_min chỉ được gọi khi stack không rỗng.

Xem đáp án

Đang tải lời giải…

84. Tính điểm bóng chày (Baseball Game)

Độ khó: Dễ · Chủ đề: Stack

Bạn đang ghi lại điểm số của một trận đấu qua danh sách các “hành động” ops. Mỗi phần tử có thể là: một số nguyên (dạng chuỗi) là điểm số của lượt đó; "+" nghĩa là điểm bằng tổng 2 lượt điểm gần nhất; "D" nghĩa là điểm gấp đôi lượt điểm gần nhất; "C" nghĩa là hủy lượt điểm gần nhất. Tính tổng điểm sau khi thực hiện hết các hành động.

Ví dụ 1:

Input: ops = ["5", "2", "C", "D", "+"]
Output: 30
Giải thích: 5 -> [5], 2 -> [5,2], C hủy 2 -> [5], D nhân đôi 5 -> [5,10], + = 5+10 -> [5,10,15]. Tổng = 5+10+15 = 30.

Ví dụ 2:

Input: ops = ["5", "-2", "4", "C", "D", "9", "+", "+"]
Output: 27

Ràng buộc:

1 <= len(ops) <= 1000
Dữ liệu vào luôn hợp lệ (không cần xử lý lỗi).

Xem đáp án

Đang tải lời giải…

85. Xóa phần tử trùng lặp trong danh sách liên kết đã sắp xếp

Độ khó: Dễ · Chủ đề: Linked List

Cho một danh sách liên kết đơn (singly linked list) đã sắp xếp tăng dần, xóa các node trùng giá trị sao cho mỗi giá trị chỉ xuất hiện một lần, giữ nguyên thứ tự.

Ví dụ 1:

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

Ví dụ 2:

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

Ràng buộc:

Số node trong khoảng [0, 300].
Danh sách đầu vào đã được sắp xếp tăng dần.

Xem đáp án

Đang tải lời giải…

86. Phát hiện chu trình trong danh sách liên kết (Linked List Cycle)

Độ khó: Dễ · Chủ đề: Linked List

Cho một danh sách liên kết đơn, xác định xem danh sách đó có tồn tại chu trình (cycle - một node trỏ ngược về node đã đi qua trước đó) hay không. Dùng thuật toán “rùa và thỏ” (hai con trỏ, một chạy chậm một chạy nhanh) để giải quyết với bộ nhớ O(1).

Ví dụ 1:

Input: [3,2,0,-4], vị trí node cuối trỏ về index 1 (tạo chu trình)
Output: True

Ví dụ 2:

Input: [1,2], không có chu trình
Output: False

Ràng buộc:

Số node trong khoảng [0, 10^4].
Không dùng thêm cấu trúc dữ liệu phụ để lưu các node đã thăm (yêu cầu O(1) bộ nhớ).

Xem đáp án

Đang tải lời giải…

87. Tìm phần tử giữa danh sách liên kết (Middle of the Linked List)

Độ khó: Dễ · Chủ đề: Linked List

Cho một danh sách liên kết đơn, trả về node ở giữa danh sách. Nếu có 2 node ở giữa (danh sách có số chẵn phần tử), trả về node giữa thứ hai. Dùng kỹ thuật hai con trỏ (nhanh - chậm), không đếm số phần tử trước.

Ví dụ 1:

Input: [1,2,3,4,5]
Output: [3,4,5]
Giải thích: Node giữa là 3, phần còn lại của danh sách kể từ đó là [3,4,5].

Ví dụ 2:

Input: [1,2,3,4,5,6]
Output: [4,5,6]
Giải thích: Có 2 node giữa (3 và 4), trả về node giữa thứ hai là 4.

Ràng buộc:

Số node trong khoảng [1, 100].

Xem đáp án

Đang tải lời giải…

88. Đảo ngược danh sách liên kết (Reverse Linked List)

Độ khó: Dễ · Chủ đề: Linked List

Cho phần đầu (head) của một danh sách liên kết đơn, đảo ngược danh sách và trả về phần đầu mới. Giải cả hai cách: lặp (iterative) và đệ quy.

Ví dụ 1:

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

Ví dụ 2:

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

Ràng buộc:

Số node trong khoảng [0, 5000].

Xem đáp án

Đang tải lời giải…

89. Gộp hai danh sách liên kết đã sắp xếp (Merge Two Sorted Lists)

Độ khó: Dễ · Chủ đề: Linked List

Cho hai danh sách liên kết đơn list1 và list2 đã sắp xếp tăng dần. Gộp chúng thành một danh sách liên kết mới cũng sắp xếp tăng dần, bằng cách nối lại các node có sẵn (không tạo node mới).

Ví dụ 1:

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Ví dụ 2:

Input: list1 = [], list2 = []
Output: []

Ràng buộc:

Tổng số node trong khoảng [0, 50].
-100 <= giá trị node <= 100

Xem đáp án

Đang tải lời giải…

90. Danh sách liên kết đối xứng (Palindrome Linked List)

Độ khó: Dễ · Chủ đề: Linked List

Cho phần đầu của một danh sách liên kết đơn, kiểm tra danh sách đó có phải là “palindrome” (đối xứng, đọc xuôi và đọc ngược giống nhau) hay không.

Ví dụ 1:

Input: [1,2,2,1]
Output: True

Ví dụ 2:

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

Ràng buộc:

Số node trong khoảng [1, 10^5].
Cố gắng đạt độ phức tạp thời gian O(n) và bộ nhớ O(1).

Xem đáp án

Đang tải lời giải…

91. Tính biểu thức hậu tố (Evaluate Reverse Polish Notation)

Độ khó: Trung bình · Chủ đề: Stack

Cho một mảng tokens biểu diễn biểu thức số học viết dưới dạng hậu tố (Reverse Polish Notation). Các toán tử hợp lệ là +, -, *, / (chia lấy phần nguyên hướng về 0). Tính giá trị của biểu thức.

Ví dụ 1:

Input: tokens = ["2","1","+","3","*"]
Output: 9
Giải thích: (2 + 1) * 3 = 9

Ví dụ 2:

Input: tokens = ["4","13","5","/","+"]
Output: 6
Giải thích: 4 + (13 / 5) = 4 + 2 = 6

Ràng buộc:

1 <= len(tokens) <= 10^4
Biểu thức đầu vào luôn hợp lệ.

Xem đáp án

Đang tải lời giải…

92. Nhiệt độ hàng ngày (Daily Temperatures)

Độ khó: Trung bình · Chủ đề: Stack

Cho mảng temperatures là nhiệt độ mỗi ngày. Với mỗi ngày, tìm xem phải chờ bao nhiêu ngày nữa mới có một ngày ấm hơn. Nếu không có ngày nào ấm hơn trong tương lai, đáp án cho ngày đó là 0. Yêu cầu độ phức tạp O(n) bằng cách dùng stack đơn điệu (monotonic stack).

Ví dụ 1:

Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

Ví dụ 2:

Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]

Ràng buộc:

1 <= len(temperatures) <= 10^5
30 <= temperatures[i] <= 100

Xem đáp án

Đang tải lời giải…

93. Phần tử lớn hơn kế tiếp II (Next Greater Element II)

Độ khó: Trung bình · Chủ đề: Stack

Cho một mảng số nguyên nums dạng vòng tròn (circular - phần tử cuối liền kề phần tử đầu). Với mỗi phần tử, tìm phần tử lớn hơn kế tiếp gần nhất theo chiều duyệt vòng tròn. Nếu không tồn tại, trả về -1.

Ví dụ 1:

Input: nums = [1,2,1]
Output: [2,-1,2]
Giải thích: Phần tử lớn hơn kế tiếp của 1 (index 0) là 2. Của 2 (index 1) không có. Của 1 (index 2) là 2 (đi vòng lại đầu mảng).

Ví dụ 2:

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

Ràng buộc:

1 <= len(nums) <= 10^4
-10^9 <= nums[i] <= 10^9

Xem đáp án

Đang tải lời giải…

94. Xóa node thứ n từ cuối danh sách (Remove Nth Node From End of List)

Độ khó: Trung bình · Chủ đề: Linked List

Cho phần đầu của một danh sách liên kết đơn, xóa node thứ n tính từ cuối danh sách, rồi trả về phần đầu danh sách. Yêu cầu chỉ duyệt danh sách một lần (dùng kỹ thuật hai con trỏ cách nhau n bước).

Ví dụ 1:

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]
Giải thích: Node thứ 2 từ cuối (giá trị 4) bị xóa.

Ví dụ 2:

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

Ràng buộc:

Số node trong khoảng [1, 30].
1 <= n <= số node

Xem đáp án

Đang tải lời giải…

95. Cộng hai số biểu diễn bằng danh sách liên kết (Add Two Numbers)

Độ khó: Trung bình · Chủ đề: Linked List

Cho hai danh sách liên kết đơn không rỗng biểu diễn hai số nguyên không âm, mỗi node chứa một chữ số, các chữ số được lưu theo thứ tự ngược (chữ số hàng đơn vị ở đầu danh sách). Cộng hai số lại và trả về kết quả cũng dưới dạng danh sách liên kết theo thứ tự ngược.

Ví dụ 1:

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Giải thích: 342 + 465 = 807, biểu diễn ngược là [7,0,8].

Ví dụ 2:

Input: l1 = [9,9], l2 = [1]
Output: [0,0,1]
Giải thích: 99 + 1 = 100.

Ràng buộc:

Số node mỗi danh sách trong khoảng [1, 100].
0 <= giá trị node <= 9

Xem đáp án

Đang tải lời giải…

96. Hoán đổi từng cặp node (Swap Nodes in Pairs)

Độ khó: Trung bình · Chủ đề: Linked List

Cho phần đầu của một danh sách liên kết đơn, hoán đổi từng cặp node liền kề và trả về phần đầu mới. Chỉ được thay đổi các liên kết giữa các node (không được đổi giá trị val của node).

Ví dụ 1:

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

Ví dụ 2:

Input: [1,2,3]
Output: [2,1,3]
Giải thích: Node cuối lẻ ra (giá trị 3) giữ nguyên vị trí.

Ràng buộc:

Số node trong khoảng [0, 100].

Xem đáp án

Đang tải lời giải…

97. Sắp xếp lại danh sách liên kết chẵn lẻ (Odd Even Linked List)

Độ khó: Trung bình · Chủ đề: Linked List

Cho phần đầu của một danh sách liên kết đơn, nhóm tất cả các node ở vị trí lẻ (1, 3, 5, … tính theo chỉ số bắt đầu từ 1) lại với nhau, tiếp theo là tất cả node ở vị trí chẵn, rồi trả về danh sách kết quả. Chỉ được dùng O(1) bộ nhớ phụ (không tạo node mới).

Ví dụ 1:

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

Ví dụ 2:

Input: [2,1,3,5,6,4,7]
Output: [2,3,6,7,1,5,4]

Ràng buộc:

Số node trong khoảng [0, 10^4].

Xem đáp án

Đang tải lời giải…

98. Sắp xếp lại danh sách liên kết theo thứ tự zigzag (Reorder List)

Độ khó: Trung bình · Chủ đề: Linked List

Cho danh sách liên kết L0 -> L1 -> ... -> Ln-1 -> Ln, sắp xếp lại thành L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2 -> ... (xen kẽ đầu - cuối). Chỉ được thay đổi liên kết giữa các node.

Ví dụ 1:

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

Ví dụ 2:

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

Ràng buộc:

Số node trong khoảng [1, 5 * 10^4].

Xem đáp án

Đang tải lời giải…

99. Xoay danh sách liên kết (Rotate List)

Độ khó: Trung bình · Chủ đề: Linked List

Cho phần đầu của một danh sách liên kết đơn, xoay danh sách sang phải k vị trí.

Ví dụ 1:

Input: head = [1,2,3,4,5], k = 2
Output: [4,5,1,2,3]

Ví dụ 2:

Input: head = [0,1,2], k = 4
Output: [2,0,1]
Giải thích: k = 4 nhưng danh sách chỉ có 3 phần tử nên tương đương xoay k % 3 = 1 vị trí.

Ràng buộc:

Số node trong khoảng [0, 500].
0 <= k <= 2 * 10^9

Xem đáp án

Đang tải lời giải…

100. Sắp xếp danh sách liên kết bằng Merge Sort (Sort List)

Độ khó: Trung bình · Chủ đề: Linked List

Cho phần đầu của một danh sách liên kết đơn, sắp xếp nó theo thứ tự tăng dần và trả về danh sách đã sắp xếp. Yêu cầu độ phức tạp thời gian O(n log n) - dùng thuật toán merge sort (chia danh sách làm đôi bằng kỹ thuật hai con trỏ, sắp xếp đệ quy rồi trộn lại).

Ví dụ 1:

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

Ví dụ 2:

Input: [-1,5,3,4,0]
Output: [-1,0,3,4,5]

Ràng buộc:

Số node trong khoảng [0, 5 * 10^4].
-10^5 <= giá trị node <= 10^5

Xem đáp án

Đang tải lời giải…

Nhóm 6: Cây nhị phân & BST

101. Độ sâu lớn nhất của cây nhị phân (Maximum Depth of Binary Tree)

Độ khó: Dễ · Chủ đề: Cây nhị phân

Cho gốc của một cây nhị phân, tính độ sâu lớn nhất (số node trên đường đi dài nhất từ gốc đến lá).

Ví dụ 1:

Input: root = [3,9,20,null,null,15,7]
Output: 3
Giải thích: Đường đi dài nhất: 3 -> 20 -> 15 (hoặc 3 -> 20 -> 7), có 3 node.

Ràng buộc:

Số lượng node từ 0 đến 10^4.
-100 <= Node.val <= 100.

Xem đáp án

Đang tải lời giải…

102. Hai cây có giống nhau không (Same Tree)

Độ khó: Dễ · Chủ đề: Cây nhị phân

Cho gốc của 2 cây nhị phân p và q, kiểm tra chúng có giống hệt nhau không (cùng cấu trúc và cùng giá trị mỗi node).

Ví dụ 1:

Input: p = [1,2,3], q = [1,2,3]
Output: True

Ràng buộc:

Số node mỗi cây từ 0 đến 100.
-10^4 <= Node.val <= 10^4.

Xem đáp án

Đang tải lời giải…

103. Lật ngược cây nhị phân (Invert Binary Tree)

Độ khó: Dễ · Chủ đề: Cây nhị phân

Cho gốc của một cây nhị phân, đảo (mirror) toàn bộ cây - nghĩa là hoán đổi cây con trái và phải tại mọi node. Trả về gốc của cây đã đảo.

Ví dụ 1:

Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]

Ràng buộc:

Số lượng node từ 0 đến 100.
-100 <= Node.val <= 100.

Xem đáp án

Đang tải lời giải…

104. Cây đối xứng (Symmetric Tree)

Độ khó: Dễ · Chủ đề: Cây nhị phân

Cho gốc của một cây nhị phân, kiểm tra cây đó có đối xứng qua tâm hay không (cây con trái là ảnh gương của cây con phải).

Ví dụ 1:

Input: root = [1,2,2,3,4,4,3]
Output: True

Ví dụ 2:

Input: root = [1,2,2,null,3,null,3]
Output: False

Ràng buộc:

Số lượng node từ 1 đến 1000.
-100 <= Node.val <= 100.

Xem đáp án

Đang tải lời giải…

105. Đường đi tổng cho trước (Path Sum)

Độ khó: Dễ · Chủ đề: Cây nhị phân

Cho gốc của một cây nhị phân và một số nguyên target_sum, kiểm tra cây có tồn tại đường đi từ gốc đến lá sao cho tổng giá trị các node trên đường đi bằng target_sum hay không.

Ví dụ 1:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], target_sum = 22
Output: True
Giải thích: Đường đi 5 -> 4 -> 11 -> 2 có tổng bằng 22.

Ràng buộc:

Số lượng node từ 0 đến 5000.
-1000 <= Node.val <= 1000.

Xem đáp án

Đang tải lời giải…

106. Duyệt cây theo tầng (Binary Tree Level Order Traversal)

Độ khó: Trung bình · Chủ đề: Cây nhị phân

Cho gốc của một cây nhị phân, trả về danh sách các giá trị node theo thứ tự duyệt theo từng tầng (từ trái sang phải), mỗi tầng là một list con.

Ví dụ 1:

Input: root = [3,9,20,null,null,15,7]
Output: [[3], [9, 20], [15, 7]]

Ví dụ 2:

Input: root = [1]
Output: [[1]]

Ràng buộc:

Số lượng node từ 0 đến 2000.
-1000 <= Node.val <= 1000.

Xem đáp án

Đang tải lời giải…

107. Kiểm tra cây tìm kiếm nhị phân hợp lệ (Validate Binary Search Tree)

Độ khó: Trung bình · Chủ đề: BST

Cho gốc của một cây nhị phân, kiểm tra đó có phải là cây tìm kiếm nhị phân (BST) hợp lệ hay không: với mọi node, toàn bộ cây con trái nhỏ hơn giá trị node, toàn bộ cây con phải lớn hơn.

Ví dụ 1:

Input: root = [2,1,3]
Output: True

Ví dụ 2:

Input: root = [5,1,4,null,null,3,6]
Output: False
Giải thích: Node gốc có giá trị 5, nhưng node con phải của node 4 lại là 3 (< 5), vi phạm điều kiện BST.

Ràng buộc:

Số lượng node từ 1 đến 10^4.
-2^31 <= Node.val <= 2^31 - 1.

Xem đáp án

Đang tải lời giải…

108. Tổ tiên chung gần nhất trong BST (Lowest Common Ancestor of a BST)

Độ khó: Trung bình · Chủ đề: BST

Cho gốc của một cây BST và 2 node p, q (đều tồn tại trong cây), tìm tổ tiên chung gần nhất (LCA) của p và q.

Ví dụ 1:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Giải thích: Tổ tiên chung gần nhất của node 2 và node 8 là gốc 6.

Ví dụ 2:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
Giải thích: Node 2 chính là tổ tiên của node 4 (và của chính nó).

Ràng buộc:

Số lượng node từ 2 đến 10^5.
Các giá trị node là duy nhất; p và q khác nhau và đều tồn tại trong cây.

Xem đáp án

Đang tải lời giải…

109. Phần tử nhỏ thứ k trong BST (Kth Smallest Element in a BST)

Độ khó: Trung bình · Chủ đề: BST

Cho gốc của một cây BST và số nguyên k, tìm giá trị nhỏ thứ k (1-indexed) trong cây.

Ví dụ 1:

Input: root = [3,1,4,null,2], k = 1
Output: 1

Ví dụ 2:

Input: root = [5,3,6,2,4,null,null,1], k = 3
Output: 3

Ràng buộc:

Số lượng node từ 1 đến 10^4.
1 <= k <= số lượng node trong cây.

Xem đáp án

Đang tải lời giải…

110. Dựng cây từ duyệt trước và duyệt giữa (Construct Binary Tree from Preorder and Inorder Traversal)

Độ khó: Trung bình · Chủ đề: Cây nhị phân

Cho 2 mảng preorder và inorder là kết quả duyệt trước (Node - Trái - Phải) và duyệt giữa (Trái - Node - Phải) của cùng một cây nhị phân (giá trị các node là duy nhất). Dựng lại cây và trả về gốc.

Ví dụ 1:

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

Ràng buộc:

1 <= preorder.length <= 3000.
inorder.length == preorder.length.
Các giá trị trong preorder và inorder là duy nhất.

Xem đáp án

Đang tải lời giải…

111. Duyệt cây zigzag theo tầng (Binary Tree Zigzag Level Order Traversal)

Độ khó: Trung bình · Chủ đề: Cây nhị phân

Cho gốc của một cây nhị phân, trả về danh sách các giá trị node theo thứ tự duyệt zigzag theo tầng: tầng 1 từ trái sang phải, tầng 2 từ phải sang trái, xen kẽ như vậy.

Ví dụ 1:

Input: root = [3,9,20,null,null,15,7]
Output: [[3], [20, 9], [15, 7]]

Ràng buộc:

Số lượng node từ 0 đến 2000.
-100 <= Node.val <= 100.

Xem đáp án

Đang tải lời giải…

112. Đường kính cây nhị phân (Diameter of Binary Tree)

Độ khó: Trung bình · Chủ đề: Cây nhị phân

Cho gốc của một cây nhị phân, tính đường kính của cây - độ dài (số cạnh) của đường đi dài nhất giữa 2 node bất kỳ, đường đi này có thể đi qua hoặc không đi qua gốc.

Ví dụ 1:

Input: root = [1,2,3,4,5]
Output: 3
Giải thích: Đường đi dài nhất là [4,2,1,3] hoặc [5,2,1,3], có độ dài 3 cạnh.

Ràng buộc:

Số lượng node từ 1 đến 10^4.
-100 <= Node.val <= 100.

Xem đáp án

Đang tải lời giải…

113. Kiểm tra cây cân bằng (Balanced Binary Tree)

Độ khó: Trung bình · Chủ đề: Cây nhị phân

Cho gốc của một cây nhị phân, kiểm tra đó có phải là cây cân bằng chiều cao hay không: với mọi node, chênh lệch chiều cao giữa cây con trái và cây con phải không quá 1.

Ví dụ 1:

Input: root = [3,9,20,null,null,15,7]
Output: True

Ví dụ 2:

Input: root = [1,2,2,3,3,null,null,4,4]
Output: False

Ràng buộc:

Số lượng node từ 0 đến 5000.
-10^4 <= Node.val <= 10^4.

Xem đáp án

Đang tải lời giải…

114. Đổi mảng đã sắp xếp thành BST cân bằng (Convert Sorted Array to Binary Search Tree)

Độ khó: Trung bình · Chủ đề: BST

Cho một mảng số nguyên nums đã sắp xếp tăng dần, xây dựng một cây BST cân bằng chiều cao từ mảng đó và trả về gốc.

Ví dụ 1:

Input: nums = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Giải thích: [0,-10,5,null,-3,null,9] cũng là một đáp án hợp lệ khác vì đề bài chấp nhận nhiều cây cân bằng khác nhau.

Ràng buộc:

1 <= nums.length <= 10^4.
nums được sắp xếp tăng dần nghiêm ngặt.

Xem đáp án

Đang tải lời giải…

115. Tổng hợp các đường đi có tổng bằng target (Path Sum II)

Độ khó: Trung bình · Chủ đề: Cây nhị phân

Cho gốc của một cây nhị phân và một số nguyên target_sum, trả về tất cả các đường đi từ gốc đến lá sao cho tổng giá trị các node trên đường đi bằng target_sum. Mỗi đường đi là một list các giá trị node.

Ví dụ 1:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], target_sum = 22
Output: [[5, 4, 11, 2], [5, 8, 4, 5]]

Ràng buộc:

Số lượng node từ 0 đến 5000.
-1000 <= Node.val <= 1000.

Xem đáp án

Đang tải lời giải…

116. Tổng đường đi lớn nhất trong cây (Binary Tree Maximum Path Sum)

Độ khó: Khó · Chủ đề: Cây nhị phân

Cho gốc của một cây nhị phân, đường đi được định nghĩa là một chuỗi node liên tiếp qua các cạnh, không nhất thiết đi qua gốc, mỗi node xuất hiện tối đa 1 lần. Tính tổng giá trị lớn nhất có thể của một đường đi như vậy.

Ví dụ 1:

Input: root = [1,2,3]
Output: 6
Giải thích: Đường đi tối ưu là 2 -> 1 -> 3 với tổng 2 + 1 + 3 = 6.

Ví dụ 2:

Input: root = [-10,9,20,null,null,15,7]
Output: 42
Giải thích: Đường đi tối ưu là 15 -> 20 -> 7 với tổng 15 + 20 + 7 = 42.

Ràng buộc:

Số lượng node từ 1 đến 3*10^4.
-1000 <= Node.val <= 1000.

Xem đáp án

Đang tải lời giải…

117. Serialize và Deserialize cây nhị phân (Serialize and Deserialize Binary Tree)

Độ khó: Khó · Chủ đề: Cây nhị phân

Thiết kế 2 hàm serialize(root) chuyển một cây nhị phân thành một chuỗi, và deserialize(data) khôi phục lại cây từ chuỗi đó. Đảm bảo cây khôi phục giống hệt cây gốc.

Ví dụ 1:

Input: root = [1,2,3,null,null,4,5]
Output: [1,2,3,null,null,4,5]
Giải thích: serialize(root) rồi deserialize(chuỗi đó) phải cho lại cây có cùng cấu trúc và giá trị như root ban đầu.

Ràng buộc:

Số lượng node từ 0 đến 10^4.
-1000 <= Node.val <= 1000.

Xem đáp án

Đang tải lời giải…

118. Nhìn cây từ bên phải (Binary Tree Right Side View)

Độ khó: Khó · Chủ đề: Cây nhị phân

Cho gốc của một cây nhị phân, tưởng tượng bạn đứng ở phía bên phải của cây, trả về danh sách giá trị các node bạn nhìn thấy được, xếp theo thứ tự từ trên xuống (tại mỗi tầng, node ngoài cùng bên phải là node nhìn thấy được).

Ví dụ 1:

Input: root = [1,2,3,null,5,null,4]
Output: [1, 3, 4]

Ví dụ 2:

Input: root = [1,null,3]
Output: [1, 3]

Ràng buộc:

Số lượng node từ 0 đến 100.
-100 <= Node.val <= 100.

Xem đáp án

Đang tải lời giải…

119. Sửa lại BST bị hoán đổi 2 node (Recover Binary Search Tree)

Độ khó: Khó · Chủ đề: BST

Cho gốc của một cây BST, đúng 2 node của nó đã bị hoán đổi giá trị cho nhau một cách nhầm lẫn. Sửa lại cây (in-place, không tạo cây mới) để nó trở thành BST hợp lệ trở lại, không dùng cấu trúc dữ liệu phụ để lưu toàn bộ giá trị.

Ví dụ 1:

Input: root = [1,3,null,null,2]
Output: [3,1,null,null,2]
Giải thích: Node 3 và node 1 bị hoán đổi so với BST đúng.

Ràng buộc:

Số lượng node từ 2 đến 1000.
-2^31 <= Node.val <= 2^31 - 1.

Xem đáp án

Đang tải lời giải…

120. Đếm số phần tử nhỏ hơn bên phải (Count of Smaller Numbers After Self)

Độ khó: Khó · Chủ đề: BST

Cho mảng số nguyên nums, với mỗi phần tử nums[i], đếm số lượng phần tử nhỏ hơn nó nằm bên phải nó trong mảng. Trả về mảng kết quả counts cùng độ dài.

Ví dụ 1:

Input: nums = [5,2,6,1]
Output: [2, 1, 1, 0]
Giải thích: Bên phải số 5 có 2 và 1 nhỏ hơn (2 phần tử); bên phải số 2 có 1 nhỏ hơn (1 phần tử); bên phải số 6 có 1 nhỏ hơn (1 phần tử); số 1 không có phần tử nào bên phải.

Ràng buộc:

1 <= nums.length <= 10^5.
-10^4 <= nums[i] <= 10^4.

Xem đáp án

Đang tải lời giải…

Nhóm 7: Sắp xếp & Tìm kiếm nhị phân

121. Tìm kiếm nhị phân (Binary Search)

Độ khó: Dễ · Chủ đề: Tìm kiếm nhị phân

Cho một mảng số nguyên nums đã được sắp xếp tăng dần (không có phần tử trùng lặp) và một số target. Trả về chỉ số (index) của target trong nums, hoặc -1 nếu không tìm thấy. Yêu cầu độ phức tạp O(log n).

Ví dụ 1:

Input: nums = [-1, 0, 3, 5, 9, 12], target = 9
Output: 4
Giải thích: 9 xuất hiện ở nums[4]

Ví dụ 2:

Input: nums = [-1, 0, 3, 5, 9, 12], target = 2
Output: -1
Giải thích: 2 không có trong nums nên trả về -1

Ràng buộc:

1 <= len(nums) <= 10^4
nums đã sắp xếp tăng dần, các phần tử phân biệt
Bắt buộc giải với độ phức tạp O(log n)

Xem đáp án

Đang tải lời giải…

122. Căn bậc hai của một số (Sqrt(x))

Độ khó: Dễ · Chủ đề: Tìm kiếm nhị phân

Cho số nguyên không âm x, trả về phần nguyên của căn bậc hai của x (làm tròn xuống). Không được dùng hàm lũy thừa hoặc math.sqrt, phải dùng tìm kiếm nhị phân.

Ví dụ 1:

Input: x = 4
Output: 2

Ví dụ 2:

Input: x = 8
Output: 2
Giải thích: căn bậc hai của 8 là 2.828..., phần nguyên là 2

Ràng buộc:

0 <= x <= 2^31 - 1
Không dùng math.sqrt hoặc x ** 0.5

Xem đáp án

Đang tải lời giải…

123. Phiên bản lỗi đầu tiên (First Bad Version)

Độ khó: Dễ · Chủ đề: Tìm kiếm nhị phân

Bạn có n phiên bản sản phẩm đánh số từ 1 đến n, đã kiểm thử tuần tự. Có một hàm is_bad_version(version) cho biết phiên bản đó có lỗi hay không; từ phiên bản lỗi đầu tiên trở đi, mọi phiên bản sau đều lỗi. Tìm phiên bản lỗi đầu tiên, gọi is_bad_version càng ít lần càng tốt.

Ví dụ 1:

Input: n = 5, phiên bản lỗi bắt đầu từ 4 (tức [False, False, False, True, True])
Output: 4

Ví dụ 2:

Input: n = 1, phiên bản lỗi bắt đầu từ 1
Output: 1

Ràng buộc:

1 <= n <= 2^31 - 1
Bắt buộc dùng tìm kiếm nhị phân, không gọi is_bad_version cho từng phiên bản một

Xem đáp án

Đang tải lời giải…

124. Trộn 2 mảng đã sắp xếp tại chỗ (Merge Sorted Array)

Độ khó: Dễ · Chủ đề: Sắp xếp

Cho 2 mảng đã sắp xếp tăng dần nums1 (có đủ khoảng trống ở cuối) và nums2, với m, n là số phần tử thực sự của mỗi mảng. Trộn nums2 vào nums1 sao cho nums1 trở thành một mảng đã sắp xếp, thực hiện tại chỗ (in-place).

Ví dụ 1:

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]

Ví dụ 2:

Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]
Giải thích: nums2 rỗng nên nums1 giữ nguyên

Ràng buộc:

nums1.length == m + n, nums2.length == n
nums1, nums2 đã sắp xếp tăng dần

Xem đáp án

Đang tải lời giải…

125. Vị trí chèn trong mảng đã sắp xếp (Search Insert Position)

Độ khó: Dễ · Chủ đề: Tìm kiếm nhị phân

Cho mảng nums đã sắp xếp tăng dần, không trùng lặp, và một số target. Trả về chỉ số của target nếu tìm thấy; nếu không, trả về chỉ số mà target sẽ được chèn vào để mảng vẫn sắp xếp đúng thứ tự. Yêu cầu O(log n).

Ví dụ 1:

Input: nums = [1, 3, 5, 6], target = 5
Output: 2

Ví dụ 2:

Input: nums = [1, 3, 5, 6], target = 2
Output: 1
Giải thích: 2 nên được chèn vào giữa 1 và 3, tức chỉ số 1

Ràng buộc:

1 <= len(nums) <= 10^4
nums sắp xếp tăng dần, các phần tử phân biệt
Bắt buộc O(log n)

Xem đáp án

Đang tải lời giải…

126. Tìm kiếm trong mảng xoay (Search in Rotated Sorted Array)

Độ khó: Trung bình · Chủ đề: Tìm kiếm nhị phân

Mảng nums ban đầu tăng dần, không trùng lặp, sau đó bị xoay tại một điểm chưa biết. Cho nums sau khi xoay và một số target, trả về chỉ số của target, hoặc -1 nếu không có. Yêu cầu 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

Ràng buộc:

1 <= len(nums) <= 5000
Mọi giá trị trong nums là duy nhất
Bắt buộc O(log n)

Xem đáp án

Đang tải lời giải…

127. Vị trí đầu và cuối của phần tử (Find First and Last Position)

Độ khó: Trung bình · Chủ đề: Tìm kiếm nhị phân

Cho mảng nums đã sắp xếp tăng dần và số target, tìm vị trí xuất hiện đầu tiên và cuối cùng của target. Nếu không có, trả về [-1, -1]. Yêu cầu O(log n).

Ví dụ 1:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3, 4]

Ví dụ 2:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1, -1]

Ràng buộc:

0 <= len(nums) <= 10^5
nums sắp xếp tăng dần
Bắt buộc O(log n)

Xem đáp án

Đang tải lời giải…

128. Tìm đỉnh cực đại (Find Peak Element)

Độ khó: Trung bình · Chủ đề: Tìm kiếm nhị phân

Một “đỉnh” là phần tử lớn hơn cả hai phần tử liền kề. Cho mảng nums (coi nums[-1] = nums[n] = -infinity), tìm chỉ số của bất kỳ một đỉnh nào. Yêu cầu O(log n).

Ví dụ 1:

Input: nums = [1, 2, 3, 1]
Output: 2
Giải thích: nums[2] = 3 là đỉnh vì lớn hơn cả nums[1]=2 và nums[3]=1

Ví dụ 2:

Input: nums = [1, 2, 1, 3, 5, 6, 4]
Output: 1 hoặc 5
Giải thích: nums[1]=2 là đỉnh (so với 1 và 1), nums[5]=6 cũng là đỉnh (so với 5 và 4)

Ràng buộc:

1 <= len(nums) <= 1000
nums[i] != nums[i+1] với mọi i liền kề hợp lệ
Bắt buộc O(log n)

Xem đáp án

Đang tải lời giải…

129. Phần tử lớn thứ k (Kth Largest Element in an Array)

Độ khó: Trung bình · Chủ đề: Sắp xếp

Cho mảng số nguyên nums chưa sắp xếp và số k, tìm phần tử lớn thứ k (tính theo thứ tự sắp xếp, không phải phần tử phân biệt thứ k).

Ví dụ 1:

Input: nums = [3,2,1,5,6,4], k = 2
Output: 5

Ví dụ 2:

Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4

Ràng buộc:

1 <= k <= len(nums) <= 10^5
Nên giải với độ phức tạp tốt hơn O(n log n) bằng heap kích thước k

Xem đáp án

Đang tải lời giải…

130. Gộp các khoảng chồng lấp (Merge Intervals)

Độ khó: Trung bình · Chủ đề: Sắp xếp

Cho danh sách các khoảng intervals, trong đó intervals[i] = [start_i, end_i]. Gộp tất cả các khoảng chồng lấp lên nhau, trả về danh sách khoảng không chồng lấp bao phủ toàn bộ các khoảng ban đầu.

Ví dụ 1:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Giải thích: [1,3] và [2,6] chồng lấp, gộp thành [1,6]

Ví dụ 2:

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Giải thích: [1,4] và [4,5] được coi là chồng lấp vì chạm nhau tại 4

Ràng buộc:

1 <= len(intervals) <= 10^4
start_i <= end_i

Xem đáp án

Đang tải lời giải…

131. Chèn khoảng mới (Insert Interval)

Độ khó: Trung bình · Chủ đề: Sắp xếp

Cho danh sách các khoảng intervals không chồng lấp, đã sắp xếp theo điểm bắt đầu, và một khoảng mới new_interval. Chèn new_interval vào danh sách, gộp lại nếu cần, sao cho các khoảng vẫn không chồng lấp và vẫn sắp xếp.

Ví dụ 1:

Input: intervals = [[1,3],[6,9]], new_interval = [2,5]
Output: [[1,5],[6,9]]

Ví dụ 2:

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], new_interval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Giải thích: [4,8] chồng lấp với [3,5],[6,7],[8,10], gộp thành [3,10]

Ràng buộc:

0 <= len(intervals) <= 10^4
intervals không chồng lấp và đã sắp xếp theo start

Xem đáp án

Đang tải lời giải…

132. Xóa bớt khoảng để không còn chồng lấp (Non-overlapping Intervals)

Độ khó: Trung bình · Chủ đề: Sắp xếp

Cho danh sách khoảng intervals, tìm số lượng khoảng tối thiểu cần xóa để các khoảng còn lại không chồng lấp nhau.

Ví dụ 1:

Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Giải thích: xóa [1,3] thì các khoảng còn lại không chồng lấp

Ví dụ 2:

Input: intervals = [[1,2],[1,2],[1,2]]
Output: 2
Giải thích: cần xóa 2 trong 3 khoảng [1,2] trùng nhau

Ràng buộc:

1 <= len(intervals) <= 10^5

Xem đáp án

Đang tải lời giải…

133. Cài đặt Merge Sort (Sort an Array)

Độ khó: Trung bình · Chủ đề: Sắp xếp

Viết hàm merge_sort(nums) sắp xếp mảng tăng dần bằng thuật toán trộn (merge sort), không dùng sorted()/.sort(). Yêu cầu độ phức tạp O(n log n).

Ví dụ 1:

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

Ví dụ 2:

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

Ràng buộc:

1 <= len(nums) <= 5 * 10^4
Bắt buộc O(n log n), không dùng hàm sắp xếp có sẵn

Xem đáp án

Đang tải lời giải…

134. Cài đặt Quick Sort (Sort an Array bằng phân hoạch)

Độ khó: Trung bình · Chủ đề: Sắp xếp

Viết hàm quick_sort(nums) sắp xếp mảng tăng dần bằng thuật toán sắp xếp nhanh (quick sort, dùng phân hoạch Lomuto hoặc Hoare), không dùng sorted()/.sort().

Ví dụ 1:

Input: nums = [10, 7, 8, 9, 1, 5]
Output: [1, 5, 7, 8, 9, 10]

Ví dụ 2:

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

Ràng buộc:

1 <= len(nums) <= 5 * 10^4
Không dùng hàm sắp xếp có sẵn
Trung bình O(n log n), tệ nhất O(n^2)

Xem đáp án

Đang tải lời giải…

135. Giá trị nhỏ nhất trong mảng xoay (Find Minimum in Rotated Sorted Array)

Độ khó: Trung bình · Chủ đề: Tìm kiếm nhị phân

Mảng nums tăng dần, không trùng lặp, bị xoay tại một điểm chưa biết. Tìm phần tử nhỏ nhất trong mảng. Yêu cầu O(log n).

Ví dụ 1:

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

Ví dụ 2:

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

Ràng buộc:

1 <= len(nums) <= 5000
Mọi phần tử trong nums là duy nhất
Bắt buộc O(log n)

Xem đáp án

Đang tải lời giải…

136. Chỉ số H (H-Index)

Độ khó: Trung bình · Chủ đề: Sắp xếp

Cho mảng citations với citations[i] là số trích dẫn của bài báo thứ i. Chỉ số H là số lớn nhất h sao cho nhà nghiên cứu có ít nhất h bài báo được trích dẫn ít nhất h lần mỗi bài. Tính chỉ số H.

Ví dụ 1:

Input: citations = [3, 0, 6, 1, 5]
Output: 3
Giải thích: có 3 bài với ít nhất 3 trích dẫn (6, 5, 3) nên h = 3

Ví dụ 2:

Input: citations = [1, 3, 1]
Output: 1

Ràng buộc:

1 <= len(citations) <= 5000
0 <= citations[i] <= 1000

Xem đáp án

Đang tải lời giải…

137. Số phòng họp cần thiết (Meeting Rooms II)

Độ khó: Trung bình · Chủ đề: Sắp xếp

Cho danh sách các cuộc họp intervals với intervals[i] = [start_i, end_i]. Tính số phòng họp tối thiểu cần có để tổ chức tất cả các cuộc họp mà không bị trùng giờ.

Ví dụ 1:

Input: intervals = [[0,30],[5,10],[15,20]]
Output: 2
Giải thích: [0,30] và [5,10] chồng giờ nên cần 2 phòng, sau đó [15,20] dùng lại 1 trong 2 phòng

Ví dụ 2:

Input: intervals = [[7,10],[2,4]]
Output: 1
Giải thích: 2 cuộc họp không chồng giờ nhau, dùng chung 1 phòng

Ràng buộc:

1 <= len(intervals) <= 10^4
0 <= start_i < end_i

Xem đáp án

Đang tải lời giải…

138. Sắp xếp lượn sóng (Wiggle Sort)

Độ khó: Trung bình · Chủ đề: Sắp xếp

Sắp xếp lại mảng nums sao cho nums[0] <= nums[1] >= nums[2] <= nums[3] >= ... (tăng giảm xen kẽ, “lượn sóng”).

Ví dụ 1:

Input: nums = [3, 5, 2, 1, 6, 4]
Output: [3, 5, 1, 6, 2, 4]
Giải thích: 3<=5, 5>=1, 1<=6, 6>=2, 2<=4 - một trong nhiều đáp án hợp lệ

Ví dụ 2:

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

Ràng buộc:

1 <= len(nums) <= 5 * 10^4

Xem đáp án

Đang tải lời giải…

139. Phần tử nhỏ thứ k trong ma trận đã sắp xếp (Kth Smallest Element in a Sorted Matrix)

Độ khó: Trung bình · Chủ đề: Tìm kiếm nhị phân

Cho ma trận vuông matrix kích thước n x n, mỗi hàng và mỗi cột đều được sắp xếp tăng dần. Tìm phần tử nhỏ thứ k trong ma trận (tính theo thứ tự sắp xếp toàn bộ các phần tử).

Ví dụ 1:

Input: matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
Output: 13

Ví dụ 2:

Input: matrix = [[-5]], k = 1
Output: -5

Ràng buộc:

n == len(matrix) == len(matrix[0])
1 <= n <= 300, 1 <= k <= n^2
Nên giải tốt hơn O(n^2 log(n^2)) bằng binary search trên giá trị

Xem đáp án

Đang tải lời giải…

140. Tìm kiếm trong ma trận đã sắp xếp (Search a 2D Matrix)

Độ khó: Trung bình · Chủ đề: Tìm kiếm nhị phân

Cho ma trận matrix kích thước m x n: mỗi hàng sắp xếp tăng dần, và phần tử đầu tiên của mỗi hàng lớn hơn phần tử cuối cùng của hàng trước đó (coi như một mảng tăng dần “gấp khúc”). Kiểm tra target có trong ma trận không. Yêu cầu O(log(m*n)).

Ví dụ 1:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: True

Ví dụ 2:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: False

Ràng buộc:

1 <= m, n <= 100
Bắt buộc O(log(m*n))

Xem đáp án

Đang tải lời giải…

Nhóm 8: Quy hoạch động (Dynamic Programming)

141. Leo cầu thang (Climbing Stairs)

Độ khó: Trung bình · Chủ đề: Quy hoạch động

Bạn đang ở bậc thang thứ 0, cần lên đến bậc thứ n. Mỗi bước bạn có thể leo 1 hoặc 2 bậc. Hỏi có bao nhiêu cách khác nhau để lên đến bậc n?

Ví dụ 1:

Input: n = 2
Output: 2
Giải thích: Có 2 cách: (1 bậc + 1 bậc), (2 bậc).

Ví dụ 2:

Input: n = 5
Output: 8
Giải thích: dp[5] = dp[4] + dp[3] = 5 + 3 = 8.

Ràng buộc:

1 <= n <= 45

Xem đáp án

Đang tải lời giải…

142. Tên trộm thông minh (House Robber)

Độ khó: Trung bình · Chủ đề: Quy hoạch động

Cho một dãy số nums là giá trị tiền tại mỗi nhà dọc theo một con phố. Nếu trộm 2 nhà liền kề nhau, chuông báo động sẽ kêu. Tìm số tiền tối đa có thể trộm được mà không trộm 2 nhà liền kề.

Ví dụ 1:

Input: nums = [1, 2, 3, 1]
Output: 4
Giải thích: Trộm nhà 0 (1) và nhà 2 (3) -> tổng 4.

Ví dụ 2:

Input: nums = [2, 7, 9, 3, 1]
Output: 12
Giải thích: Trộm nhà 0 (2) + nhà 2 (9) + nhà 4 (1) = 12.

Ràng buộc:

1 <= len(nums) <= 100
0 <= nums[i] <= 400

Xem đáp án

Đang tải lời giải…

143. Đổi tiền xu - ít đồng nhất (Coin Change)

Độ khó: Trung bình · Chủ đề: Quy hoạch động

Cho các loại tiền xu coins (số lượng mỗi loại là vô hạn) và số tiền amount. Tìm số lượng đồng xu ít nhất để đủ số tiền amount. Nếu không thể, trả về -1.

Ví dụ 1:

Input: coins = [1, 2, 5], amount = 11
Output: 3
Giải thích: 11 = 5 + 5 + 1.

Ví dụ 2:

Input: coins = [2], amount = 3
Output: -1
Giải thích: Không thể tạo ra 3 chỉ với đồng xu 2.

Ràng buộc:

1 <= len(coins) <= 12
1 <= coins[i] <= 2^31 - 1
0 <= amount <= 10^4

Xem đáp án

Đang tải lời giải…

144. Dãy con tăng dài nhất (Longest Increasing Subsequence)

Độ khó: Trung bình · Chủ đề: Quy hoạch động

Cho một mảng số nguyên nums, tìm độ dài của dãy con tăng dần dài nhất (các phần tử không cần liên tiếp trong mảng gốc, nhưng phải giữ thứ tự).

Ví dụ 1:

Input: nums = [10, 9, 2, 5, 3, 7, 101, 18]
Output: 4
Giải thích: Dãy con tăng dài nhất là [2, 3, 7, 101] hoặc [2, 3, 7, 18], độ dài 4.

Ví dụ 2:

Input: nums = [0, 1, 0, 3, 2, 3]
Output: 4
Giải thích: [0, 1, 2, 3].

Ràng buộc:

1 <= len(nums) <= 2500
-10^4 <= nums[i] <= 10^4

Xem đáp án

Đang tải lời giải…

145. Số đường đi trong lưới (Unique Paths)

Độ khó: Trung bình · Chủ đề: Quy hoạch động

Một robot đứng ở góc trên-trái của lưới m x n. Robot chỉ có thể di chuyển xuống hoặc sang phải mỗi bước. Tìm số đường đi khác nhau để robot đến được góc dưới-phải.

Ví dụ 1:

Input: m = 3, n = 7
Output: 28

Ví dụ 2:

Input: m = 3, n = 2
Output: 3
Giải thích: 3 đường đi: Phải->Xuống->Xuống, Xuống->Phải->Xuống, Xuống->Xuống->Phải.

Ràng buộc:

1 <= m, n <= 100

Xem đáp án

Đang tải lời giải…

146. Đường đi tổng nhỏ nhất (Minimum Path Sum)

Độ khó: Trung bình · Chủ đề: Quy hoạch động

Cho lưới grid chứa các số không âm, tìm đường đi từ góc trên-trái đến góc dưới-phải sao cho tổng các số trên đường đi là nhỏ nhất. Mỗi bước chỉ được đi xuống hoặc sang phải.

Ví dụ 1:

Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Giải thích: Đường đi 1->3->1->1->1 có tổng nhỏ nhất là 7.

Ví dụ 2:

Input: grid = [[1,2,3],[4,5,6]]
Output: 12

Ràng buộc:

1 <= len(grid), len(grid[0]) <= 200
0 <= grid[i][j] <= 200

Xem đáp án

Đang tải lời giải…

147. Tích lớn nhất của dãy con liên tiếp (Maximum Product Subarray)

Độ khó: Trung bình · Chủ đề: Quy hoạch động

Cho một mảng số nguyên nums, tìm dãy con liên tiếp có tích các phần tử lớn nhất, trả về tích đó.

Ví dụ 1:

Input: nums = [2, 3, -2, 4]
Output: 6
Giải thích: Dãy con [2, 3] có tích lớn nhất là 6.

Ví dụ 2:

Input: nums = [-2, 0, -1]
Output: 0
Giải thích: Kết quả không thể là 2 vì -2 và -1 không liền kề nhau.

Ràng buộc:

1 <= len(nums) <= 2*10^4
-10 <= nums[i] <= 10

Xem đáp án

Đang tải lời giải…

148. Số lượng số chính phương ít nhất (Perfect Squares)

Độ khó: Trung bình · Chủ đề: Quy hoạch động

Cho số nguyên dương n, tìm số lượng ít nhất các số chính phương (1, 4, 9, 16, …) có tổng bằng n.

Ví dụ 1:

Input: n = 12
Output: 3
Giải thích: 12 = 4 + 4 + 4.

Ví dụ 2:

Input: n = 13
Output: 2
Giải thích: 13 = 4 + 9.

Ràng buộc:

1 <= n <= 10^4

Xem đáp án

Đang tải lời giải…

149. Chia tập hợp thành 2 phần bằng nhau (Partition Equal Subset Sum)

Độ khó: Trung bình · Chủ đề: Quy hoạch động

Cho mảng số nguyên dương nums, xác định xem có thể chia mảng thành 2 tập con sao cho tổng 2 tập con bằng nhau hay không.

Ví dụ 1:

Input: nums = [1, 5, 11, 5]
Output: True
Giải thích: Chia thành [1, 5, 5] và [11], mỗi tập có tổng 11.

Ví dụ 2:

Input: nums = [1, 2, 3, 5]
Output: False
Giải thích: Tổng mảng là 11 (lẻ), không thể chia đôi bằng nhau.

Ràng buộc:

1 <= len(nums) <= 200
1 <= nums[i] <= 100

Xem đáp án

Đang tải lời giải…

150. Cắt số để tích lớn nhất (Integer Break)

Độ khó: Trung bình · Chủ đề: Quy hoạch động

Cho số nguyên n >= 2, chia n thành tổng của ít nhất 2 số nguyên dương sao cho tích của các số đó là lớn nhất có thể. Trả về tích lớn nhất đó.

Ví dụ 1:

Input: n = 2
Output: 1
Giải thích: 2 = 1 + 1, tích = 1.

Ví dụ 2:

Input: n = 10
Output: 36
Giải thích: 10 = 3 + 3 + 4, tích = 3 * 3 * 4 = 36.

Ràng buộc:

2 <= n <= 58

Xem đáp án

Đang tải lời giải…

151. Dãy con chung dài nhất (Longest Common Subsequence)

Độ khó: Khó · Chủ đề: Quy hoạch động

Cho 2 chuỗi text1 và text2, tìm độ dài dãy con chung dài nhất giữa chúng (các ký tự không cần liên tiếp nhưng phải giữ đúng thứ tự).

Ví dụ 1:

Input: text1 = "abcde", text2 = "ace"
Output: 3
Giải thích: Dãy con chung dài nhất là "ace", độ dài 3.

Ví dụ 2:

Input: text1 = "abc", text2 = "abc"
Output: 3

Ví dụ 3:

Input: text1 = "abc", text2 = "def"
Output: 0
Giải thích: Không có ký tự chung nào.

Ràng buộc:

1 <= len(text1), len(text2) <= 1000

Xem đáp án

Đang tải lời giải…

152. Khoảng cách chỉnh sửa (Edit Distance)

Độ khó: Khó · Chủ đề: Quy hoạch động

Cho 2 chuỗi word1 và word2, tìm số thao tác tối thiểu (thêm, xóa, thay thế 1 ký tự) để biến word1 thành word2.

Ví dụ 1:

Input: word1 = "horse", word2 = "ros"
Output: 3
Giải thích: horse -> rorse (thay h->r) -> rose (xóa r) -> ros (xóa e).

Ví dụ 2:

Input: word1 = "intention", word2 = "execution"
Output: 5

Ràng buộc:

0 <= len(word1), len(word2) <= 500

Xem đáp án

Đang tải lời giải…

153. Cái túi 0/1 (0/1 Knapsack)

Độ khó: Khó · Chủ đề: Quy hoạch động

Cho n món đồ, món thứ i có trọng lượng weights[i] và giá trị values[i]. Một cái túi chịu được trọng lượng tối đa capacity. Mỗi món chỉ được chọn tối đa 1 lần. Tìm giá trị lớn nhất có thể mang theo.

Ví dụ 1:

Input: weights = [1, 3, 4, 5], values = [1, 4, 5, 7], capacity = 7
Output: 9
Giải thích: Chọn món có weight=3 (value=4) và weight=4 (value=5) -> tổng weight 7, value 9.

Ví dụ 2:

Input: weights = [2, 2, 3], values = [3, 4, 5], capacity = 4
Output: 7
Giải thích: Chọn 2 món weight=2 (value 3 và 4) -> weight 4, value 7.

Ràng buộc:

1 <= n <= 1000
1 <= capacity <= 1000

Xem đáp án

Đang tải lời giải…

154. Dãy con đối xứng dài nhất (Longest Palindromic Subsequence)

Độ khó: Khó · Chủ đề: Quy hoạch động

Cho chuỗi s, tìm độ dài dãy con đối xứng (palindrome) dài nhất của s (các ký tự không cần liên tiếp).

Ví dụ 1:

Input: s = "bbbab"
Output: 4
Giải thích: Dãy con đối xứng dài nhất là "bbbb".

Ví dụ 2:

Input: s = "cbbd"
Output: 2
Giải thích: "bb".

Ràng buộc:

1 <= len(s) <= 1000

Xem đáp án

Đang tải lời giải…

155. Nổ bóng bay (Burst Balloons)

Độ khó: Khó · Chủ đề: Quy hoạch động

Cho n quả bóng bay xếp thành hàng, quả thứ i có giá trị nums[i]. Khi nổ quả bóng i, bạn nhận được nums[left] * nums[i] * nums[right] (với left, right là 2 quả liền kề còn lại tại thời điểm đó; nếu ngoài biên coi như giá trị 1). Tìm số điểm tối đa có thể đạt được khi nổ hết tất cả bóng.

Ví dụ 1:

Input: nums = [3, 1, 5, 8]
Output: 167
Giải thích: Nổ theo thứ tự 1, 5, 3, 8: 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 15+120+24+8 = 167.

Ví dụ 2:

Input: nums = [1, 5]
Output: 10
Giải thích: Nổ 1 trước: 1*1*5 + 1*5*1 = 5+5 = 10.

Ràng buộc:

1 <= len(nums) <= 300
0 <= nums[i] <= 100

Xem đáp án

Đang tải lời giải…

156. So khớp biểu thức chính quy đơn giản (Regular Expression Matching)

Độ khó: Khó · Chủ đề: Quy hoạch động

Cho chuỗi s và mẫu p chỉ chứa chữ cái thường, '.' (khớp 1 ký tự bất kỳ) và '*' (khớp 0 hoặc nhiều lần ký tự đứng trước nó). Kiểm tra p có khớp toàn bộ s hay không.

Ví dụ 1:

Input: s = "aa", p = "a*"
Output: True
Giải thích: "a*" khớp 0 hoặc nhiều 'a', ở đây khớp "aa".

Ví dụ 2:

Input: s = "mississippi", p = "mis*is*p*."
Output: False

Ràng buộc:

1 <= len(s) <= 20, 1 <= len(p) <= 30

Xem đáp án

Đang tải lời giải…

157. Xen kẽ chuỗi (Interleaving String)

Độ khó: Khó · Chủ đề: Quy hoạch động

Cho 3 chuỗi s1, s2, s3. Kiểm tra s3 có được tạo thành bằng cách xen kẽ (giữ nguyên thứ tự nội bộ) các ký tự của s1 và s2 hay không.

Ví dụ 1:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: True

Ví dụ 2:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: False

Ràng buộc:

0 <= len(s1), len(s2) <= 100
len(s3) = len(s1) + len(s2)

Xem đáp án

Đang tải lời giải…

158. Ngục tối tử thần (Dungeon Game)

Độ khó: Khó · Chủ đề: Quy hoạch động

Một hiệp sĩ cần cứu công chúa trong ngục, di chuyển từ ô trên-trái đến ô dưới-phải của lưới dungeon (chỉ đi phải hoặc xuống). Mỗi ô có giá trị dương (hồi máu) hoặc âm (mất máu). Hiệp sĩ chết nếu HP <= 0 tại bất kỳ thời điểm nào. Tìm HP khởi điểm tối thiểu để đến được công chúa.

Ví dụ 1:

Input: dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
Output: 7
Giải thích: Đi theo đường RIGHT -> RIGHT -> DOWN -> DOWN cần HP khởi điểm 7.

Ví dụ 2:

Input: dungeon = [[0]]
Output: 1
Giải thích: HP tối thiểu luôn phải >= 1.

Ràng buộc:

1 <= m, n <= 200

Xem đáp án

Đang tải lời giải…

159. Mua bán cổ phiếu có thời gian nghỉ (Best Time to Buy and Sell Stock with Cooldown)

Độ khó: Khó · Chủ đề: Quy hoạch động

Cho mảng prices là giá cổ phiếu mỗi ngày. Bạn có thể thực hiện nhiều giao dịch (mua rồi bán), nhưng sau khi bán phải nghỉ ít nhất 1 ngày trước khi mua lại (không được giữ nhiều hơn 1 cổ phiếu cùng lúc). Tìm lợi nhuận tối đa.

Ví dụ 1:

Input: prices = [1, 2, 3, 0, 2]
Output: 3
Giải thích: Mua(1)->Bán(2, lãi 1)->Nghỉ->Mua(0)->Bán(2, lãi 2). Tổng 3.

Ví dụ 2:

Input: prices = [1]
Output: 0

Ràng buộc:

1 <= len(prices) <= 5000

Xem đáp án

Đang tải lời giải…

160. Hình vuông lớn nhất trong ma trận (Maximal Square)

Độ khó: Khó · Chủ đề: Quy hoạch động

Cho ma trận nhị phân matrix chỉ gồm 0 và 1, tìm diện tích của hình vuông lớn nhất chỉ chứa toàn số 1.

Ví dụ 1:

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 4
Giải thích: Hình vuông lớn nhất có cạnh 2, diện tích 4.

Ví dụ 2:

Input: matrix = [["0","1"],["1","0"]]
Output: 1

Ràng buộc:

1 <= m, n <= 300

Xem đáp án

Đang tải lời giải…

Nhóm 9: Đồ thị (Graph) & Backtracking

161. Số lượng đảo (Number of Islands)

Độ khó: Trung bình · Chủ đề: Đồ thị (BFS/DFS trên lưới)

Cho một lưới 2 chiều gồm '1' (đất) và '0' (nước), đếm số lượng “đảo”. Một đảo là nhóm các ô đất liền kề theo 4 hướng (trên/dưới/trái/phải), bao quanh bởi nước.

Ví dụ 1:

Input:
grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3
Giải thích: Có 3 nhóm đất liền kề tách biệt nhau.

Ví dụ 2:

Input:
grid = [
  ["1","1","1"],
  ["0","1","0"],
  ["1","0","1"]
]
Output: 2
Giải thích: Nhóm trên (5 ô đất nối liền) là 1 đảo, ô góc dưới phải tách biệt là đảo thứ 2.

Ràng buộc:

1 <= số hàng, số cột <= 300
Mỗi ô chỉ chứa '0' hoặc '1'.

Xem đáp án

Đang tải lời giải…

162. Tô màu vùng (Flood Fill)

Độ khó: Trung bình · Chủ đề: Đồ thị (DFS trên lưới)

Cho một ảnh biểu diễn bằng lưới số image, một điểm bắt đầu (sr, sc) và màu mới color. Tô lại toàn bộ vùng liên thông (4 hướng) chứa điểm bắt đầu, có cùng màu ban đầu, bằng màu mới.

Ví dụ 1:

Input: image=[[1,1,1],[1,1,0],[1,0,1]], sr=1, sc=1, color=2
Output: [[2,2,2],[2,2,0],[2,0,1]]
Giải thích: Vùng chứa (1,1) có màu 1, tô toàn bộ vùng đó thành 2.

Ví dụ 2:

Input: image=[[0,0,0],[0,0,0]], sr=0, sc=0, color=0
Output: [[0,0,0],[0,0,0]]
Giải thích: Màu mới trùng màu cũ nên không đổi gì (tránh lặp vô hạn).

Ràng buộc:

1 <= số hàng, số cột <= 50
0 <= sr < số hàng, 0 <= sc < số cột

Xem đáp án

Đang tải lời giải…

163. Sao chép đồ thị (Clone Graph)

Độ khó: Trung bình · Chủ đề: Đồ thị (DFS/BFS)

Cho một đồ thị vô hướng liên thông, biểu diễn bằng dictionary adj (đỉnh -> list đỉnh kề), và đỉnh bắt đầu start. Viết hàm tạo ra một bản sao độc lập (deep copy) của đồ thị, trả về dictionary kề mới.

Ví dụ 1:

Input: adj={1: [2, 4], 2: [1, 3], 3: [2, 4], 4: [1, 3]}, start=1
Output: {1: [2, 4], 2: [1, 3], 3: [2, 4], 4: [1, 3]}
Giải thích: Cấu trúc giống hệt bản gốc nhưng là các object/dictionary khác nhau trong bộ nhớ.

Ví dụ 2:

Input: adj={1: []}, start=1
Output: {1: []}
Giải thích: Đồ thị chỉ có 1 đỉnh, không có cạnh nào.

Ràng buộc:

Số đỉnh tối đa 100, đồ thị không có khuyên (self-loop) trùng lặp.
Đồ thị liên thông, không có đỉnh cô lập ngoài start.

Xem đáp án

Đang tải lời giải…

164. Lịch học có thể hoàn thành (Course Schedule)

Độ khó: Trung bình · Chủ đề: Đồ thị (Topological Sort / phát hiện chu trình)

Có numCourses môn học đánh số từ 0. Danh sách prerequisites chứa các cặp [a, b] nghĩa là muốn học a phải học b trước. Kiểm tra có thể hoàn thành tất cả các môn học hay không (đồ thị có chu trình hay không).

Ví dụ 1:

Input: numCourses=2, prerequisites=[[1,0]]
Output: True
Giải thích: Học 0 trước, rồi học 1. Không có chu trình.

Ví dụ 2:

Input: numCourses=2, prerequisites=[[1,0],[0,1]]
Output: False
Giải thích: Học 1 cần 0, học 0 cần 1 -> chu trình, không thể hoàn thành.

Ràng buộc:

1 <= numCourses <= 2000
0 <= a, b < numCourses

Xem đáp án

Đang tải lời giải…

165. Tập con (Subsets)

Độ khó: Trung bình · Chủ đề: Backtracking

Cho một list các số nguyên phân biệt nums, trả về tất cả các tập con (power set), bao gồm tập rỗng và chính nó.

Ví dụ 1:

Input: nums=[1,2,3]
Output: [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]
Giải thích: Có 2^3 = 8 tập con.

Ví dụ 2:

Input: nums=[0]
Output: [[], [0]]
Giải thích: Có 2^1 = 2 tập con.

Ràng buộc:

1 <= len(nums) <= 10
Các phần tử trong nums là duy nhất.

Xem đáp án

Đang tải lời giải…

166. Tìm kiếm từ trên lưới (Word Search)

Độ khó: Khó · Chủ đề: Backtracking trên lưới

Cho một lưới ký tự 2 chiều board và một chuỗi word, kiểm tra word có thể được tạo thành từ các ký tự liền kề (4 hướng, không dùng lại 1 ô 2 lần) trên lưới hay không.

Ví dụ 1:

Input: board=[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word="ABCCED"
Output: True

Ví dụ 2:

Input: board=[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word="ABCB"
Output: False
Giải thích: Chữ B thứ 2 sẽ phải dùng lại ô B đầu tiên, không hợp lệ.

Ràng buộc:

1 <= số hàng, số cột <= 6
1 <= len(word) <= 15

Xem đáp án

Đang tải lời giải…

167. Bài toán N-Quân hậu (N-Queens)

Độ khó: Khó · Chủ đề: Backtracking

Cho số nguyên n, đặt n quân hậu trên bàn cờ n x n sao cho không có 2 quân hậu nào tấn công nhau (cùng hàng, cùng cột, cùng đường chéo). Trả về số lượng cách đặt khác nhau.

Ví dụ 1:

Input: n=4
Output: 2
Giải thích: Có đúng 2 cách đặt 4 quân hậu hợp lệ trên bàn cờ 4x4.

Ví dụ 2:

Input: n=1
Output: 1

Ràng buộc:

1 <= n <= 9

Xem đáp án

Đang tải lời giải…

168. Hoán vị không trùng lặp (Permutations II)

Độ khó: Khó · Chủ đề: Backtracking

Cho một list số nguyên nums có thể chứa phần tử trùng lặp, trả về tất cả các hoán vị khác nhau (không lặp lại hoán vị giống hệt nhau).

Ví dụ 1:

Input: nums=[1,1,2]
Output: [[1,1,2], [1,2,1], [2,1,1]]
Giải thích: Dù có 3! = 6 cách sắp xếp vị trí, chỉ có 3 hoán vị thực sự khác nhau vì có 2 số 1 trùng nhau.

Ví dụ 2:

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

Ràng buộc:

1 <= len(nums) <= 8

Xem đáp án

Đang tải lời giải…

169. Tổng tổ hợp (Combination Sum)

Độ khó: Khó · Chủ đề: Backtracking

Cho list số nguyên dương phân biệt candidates và target, tìm tất cả các tổ hợp (được phép dùng lại phần tử nhiều lần) có tổng bằng target.

Ví dụ 1:

Input: candidates=[2,3,6,7], target=7
Output: [[2,2,3], [7]]

Ví dụ 2:

Input: candidates=[2,3,5], target=8
Output: [[2,2,2,2], [2,3,3], [3,5]]

Ràng buộc:

1 <= len(candidates) <= 30, các phần tử phân biệt và dương.
1 <= target <= 40

Xem đáp án

Đang tải lời giải…

170. Giải Sudoku (Sudoku Solver)

Độ khó: Khó · Chủ đề: Backtracking

Cho một bảng Sudoku 9x9 với một số ô đã điền số ('1'-'9') và các ô trống là '.'. Điền các ô trống sao cho thỏa quy tắc Sudoku (mỗi hàng, cột, khối 3x3 chứa đủ 1-9 không lặp). Trả về bảng đã giải.

Ví dụ 1:

Input: board có nhiều ô "." và một số số đã điền sẵn hợp lệ
Output: board đầy đủ, mỗi hàng/cột/khối 3x3 chứa các số 1-9 không lặp lại

Ví dụ 2:

Input: board đã điền đầy đủ và hợp lệ sẵn (không có ô ".")
Output: giữ nguyên board vì không cần điền gì thêm

Ràng buộc:

Bảng luôn có kích thước cố định 9x9.
Đề bài đảm bảo có đúng 1 lời giải.

Xem đáp án

Đang tải lời giải…

171. Thứ tự học môn học (Course Schedule II)

Độ khó: Khó · Chủ đề: Đồ thị (Topological Sort)

Tương tự bài “Lịch học có thể hoàn thành”, nhưng thay vì trả về True/False, hãy trả về một thứ tự học hợp lệ của tất cả các môn. Nếu không thể hoàn thành (có chu trình), trả về list rỗng.

Ví dụ 1:

Input: numCourses=4, prerequisites=[[1,0],[2,0],[3,1],[3,2]]
Output: [0, 1, 2, 3]
Giải thích: Học 0 trước, rồi 1 và 2 (theo thứ tự nào cũng được), cuối cùng học 3.

Ví dụ 2:

Input: numCourses=2, prerequisites=[[1,0],[0,1]]
Output: []
Giải thích: Có chu trình 0 -> 1 -> 0, không thể hoàn thành.

Ràng buộc:

1 <= numCourses <= 2000

Xem đáp án

Đang tải lời giải…

172. Độ trễ mạng lưới (Network Delay Time)

Độ khó: Khó · Chủ đề: Đồ thị (Dijkstra)

Có n node đánh số từ 1 đến n. times[i] = (u, v, w) nghĩa là tín hiệu đi từ u đến v mất w đơn vị thời gian (đồ thị có hướng, có trọng số). Gửi tín hiệu từ node k, tìm thời gian tối thiểu để tất cả các node nhận được tín hiệu. Nếu không thể, trả về -1.

Ví dụ 1:

Input: times=[(2,1,1),(2,3,1),(3,4,1)], n=4, k=2
Output: 2
Giải thích: Từ node 2, mất 1 đơn vị đến node 1 và 3, rồi từ 3 mất thêm 1 đơn vị đến 4 -> tổng 2.

Ví dụ 2:

Input: times=[(1,2,1)], n=2, k=1
Output: 1

Ràng buộc:

1 <= k <= n <= 100
1 <= w <= 100

Xem đáp án

Đang tải lời giải…

173. Chuyến bay rẻ nhất với K điểm dừng (Cheapest Flights Within K Stops)

Độ khó: Khó · Chủ đề: Đồ thị (Bellman-Ford biến thể)

Có n thành phố (0 đến n-1) và flights[i] = (from, to, price). Tìm giá vé rẻ nhất từ src đến dst với tối đa k điểm dừng (tức tối đa k+1 chặng bay). Nếu không thể đến, trả về -1.

Ví dụ 1:

Input: n=4, flights=[(0,1,100),(1,2,100),(2,0,100),(1,3,600),(2,3,200)], src=0, dst=3, k=1
Output: 700
Giải thích: Đường đi 0 -> 1 -> 3 (1 điểm dừng) giá 100+600=700, rẻ hơn đường 3 chặng.

Ví dụ 2:

Input: n=3, flights=[(0,1,100),(1,2,100),(0,2,500)], src=0, dst=2, k=1
Output: 200
Giải thích: 0 -> 1 -> 2 với đúng 1 điểm dừng, giá 200, rẻ hơn bay thẳng 500.

Ràng buộc:

1 <= n <= 100, 0 <= k <= n-1

Xem đáp án

Đang tải lời giải…

174. Cạnh dư thừa (Redundant Connection)

Độ khó: Khó · Chủ đề: Đồ thị (Union-Find)

Cho một cây có n đỉnh, thêm 1 cạnh thừa tạo thành 1 chu trình. Cho list edges với đúng n cạnh, tìm cạnh thừa đó (cạnh cuối cùng trong edges mà khi thêm vào sẽ tạo chu trình).

Ví dụ 1:

Input: edges=[[1,2],[1,3],[2,3]]
Output: [2, 3]
Giải thích: Cạnh [2,3] khi thêm vào sau cùng tạo ra chu trình 1-2-3-1.

Ví dụ 2:

Input: edges=[[1,2],[2,3],[3,4],[1,4],[1,5]]
Output: [1, 4]

Ràng buộc:

3 <= n <= 1000
Đảm bảo edges có đúng 1 cạnh thừa tạo chu trình.

Xem đáp án

Đang tải lời giải…

175. Số thành phần liên thông (Number of Connected Components)

Độ khó: Khó · Chủ đề: Đồ thị (Union-Find)

Cho n đỉnh đánh số từ 0 đến n-1 và list các cạnh vô hướng edges, đếm số thành phần liên thông của đồ thị.

Ví dụ 1:

Input: n=5, edges=[[0,1],[1,2],[3,4]]
Output: 2
Giải thích: {0,1,2} là 1 thành phần, {3,4} là 1 thành phần khác.

Ví dụ 2:

Input: n=5, edges=[[0,1],[1,2],[2,3],[3,4]]
Output: 1

Ràng buộc:

1 <= n <= 2000

Xem đáp án

Đang tải lời giải…

176. Chuỗi biến đổi từ (Word Ladder)

Độ khó: Khó · Chủ đề: Đồ thị (BFS tìm đường ngắn nhất)

Cho beginWord, endWord và một wordList. Tìm độ dài đường biến đổi ngắn nhất từ beginWord đến endWord, mỗi bước chỉ được đổi 1 ký tự, và từ mới sau khi đổi phải nằm trong wordList. Nếu không thể, trả về 0.

Ví dụ 1:

Input: beginWord="hit", endWord="cog", wordList=["hot","dot","dog","lot","log","cog"]
Output: 5
Giải thích: hit -> hot -> dot -> dog -> cog (5 từ, 4 bước biến đổi).

Ví dụ 2:

Input: beginWord="hit", endWord="cog", wordList=["hot","dot","dog","lot","log"]
Output: 0
Giải thích: "cog" không có trong wordList nên không thể đến đích.

Ràng buộc:

1 <= len(beginWord) <= 10, tất cả các từ cùng độ dài.
1 <= len(wordList) <= 5000

Xem đáp án

Đang tải lời giải…

177. Dòng nước chảy tới 2 đại dương (Pacific Atlantic Water Flow)

Độ khó: Khó · Chủ đề: Đồ thị (DFS/BFS đa nguồn)

Cho lưới độ cao heights, Thái Bình Dương giáp cạnh trên và trái, Đại Tây Dương giáp cạnh dưới và phải. Nước chảy từ ô cao xuống ô thấp hơn hoặc bằng (4 hướng). Tìm các ô mà nước từ đó có thể chảy tới cả 2 đại dương.

Ví dụ 1:

Input: heights=[[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]
Output: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]

Ví dụ 2:

Input: heights=[[1]]
Output: [[0,0]]
Giải thích: Lưới chỉ có 1 ô, nó giáp cả 2 đại dương cùng lúc.

Ràng buộc:

1 <= số hàng, số cột <= 200

Xem đáp án

Đang tải lời giải…

178. Xây dựng lại lịch trình (Reconstruct Itinerary)

Độ khó: Khó · Chủ đề: Đồ thị (Đường đi Euler)

Cho list vé máy bay tickets = [[from, to], ...], xây dựng lại hành trình bắt đầu từ "JFK" sử dụng tất cả vé đúng 1 lần, sao cho hành trình có thứ tự từ điển nhỏ nhất.

Ví dụ 1:

Input: tickets=[["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
Output: ["JFK","MUC","LHR","SFO","SJC"]

Ví dụ 2:

Input: tickets=[["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Output: ["JFK","ATL","JFK","SFO","ATL","SFO"]
Giải thích: Có nhiều hành trình hợp lệ dùng hết vé, chọn hành trình nhỏ nhất theo thứ tự từ điển.

Ràng buộc:

1 <= len(tickets) <= 300
Đề bài đảm bảo luôn tồn tại ít nhất 1 hành trình hợp lệ.

Xem đáp án

Đang tải lời giải…

179. Cây khung nhỏ nhất (Minimum Spanning Tree)

Độ khó: Khó · Chủ đề: Đồ thị (Kruskal, Union-Find)

Cho n đỉnh và list cạnh có trọng số edges = [(u, v, w), ...] của một đồ thị liên thông, tìm tổng trọng số nhỏ nhất để nối tất cả các đỉnh thành 1 cây khung (dùng thuật toán Kruskal).

Ví dụ 1:

Input: n=4, edges=[(0,1,10),(0,2,6),(0,3,5),(1,3,15),(2,3,4)]
Output: 19
Giải thích: Cây khung nhỏ nhất gồm các cạnh (2,3,4), (0,3,5), (0,1,10) -> tổng 19.

Ví dụ 2:

Input: n=3, edges=[(0,1,1),(1,2,2),(0,2,3)]
Output: 3
Giải thích: Chọn 2 cạnh nhẹ nhất (0,1,1) và (1,2,2) -> tổng 3.

Ràng buộc:

1 <= n <= 1000, đồ thị liên thông.

Xem đáp án

Đang tải lời giải…

180. Kiểm tra cây hợp lệ (Graph Valid Tree)

Độ khó: Khó · Chủ đề: Đồ thị (Union-Find)

Cho n đỉnh đánh số 0 đến n-1 và list cạnh vô hướng edges, kiểm tra đồ thị này có phải là một cây hợp lệ hay không (liên thông và không có chu trình).

Ví dụ 1:

Input: n=5, edges=[[0,1],[0,2],[0,3],[1,4]]
Output: True
Giải thích: 5 đỉnh, 4 cạnh, liên thông, không có chu trình -> là cây hợp lệ.

Ví dụ 2:

Input: n=5, edges=[[0,1],[1,2],[2,3],[1,3],[1,4]]
Output: False
Giải thích: Có chu trình 1-2-3-1, không phải cây hợp lệ.

Ràng buộc:

1 <= n <= 2000

Xem đáp án

Đang tải lời giải…

Nhóm 10: Greedy & Bit Manipulation

181. Đếm số bit 1 (Number of 1 Bits)

Độ khó: Dễ · Chủ đề: Bit Manipulation

Cho một số nguyên không âm n, đếm số lượng bit 1 trong biểu diễn nhị phân của nó (còn gọi là Hamming weight).

Ví dụ 1:

Input: n = 11
Output: 3
Giải thích: 11 = 1011 (nhị phân), có 3 bit 1.

Ví dụ 2:

Input: n = 128
Output: 1
Giải thích: 128 = 10000000 (nhị phân), có 1 bit 1.

Ràng buộc:

0 <= n <= 2^31 - 1

Xem đáp án

Đang tải lời giải…

182. Đếm bit 1 cho dãy số (Counting Bits)

Độ khó: Dễ · Chủ đề: Bit Manipulation, Quy hoạch động

Cho số nguyên n, trả về một mảng ans độ dài n + 1, trong đó ans[i] là số bit 1 trong biểu diễn nhị phân của i, với mọi 0 <= i <= n.

Ví dụ 1:

Input: n = 2
Output: [0, 1, 1]
Giải thích: 0 -> 0, 1 -> 1, 2 -> 10 (1 bit 1).

Ví dụ 2:

Input: n = 5
Output: [0, 1, 1, 2, 1, 2]

Ràng buộc:

0 <= n <= 10^5

Xem đáp án

Đang tải lời giải…

183. Chia kẹo cho trẻ em (Assign Cookies)

Độ khó: Dễ · Chủ đề: Greedy

Mỗi trẻ em i có một “mức thèm ăn” g[i] - chiếc bánh quy nhỏ nhất có thể làm trẻ hài lòng. Mỗi chiếc bánh quy j có kích thước s[j]. Trẻ i hài lòng với bánh j nếu s[j] >= g[i]. Mỗi trẻ nhận tối đa 1 bánh. Tìm số trẻ tối đa có thể làm hài lòng.

Ví dụ 1:

Input: g = [1, 2, 3], s = [1, 1]
Output: 1
Giải thích: Chỉ đủ bánh làm hài lòng 1 trẻ (trẻ có mức thèm ăn 1).

Ví dụ 2:

Input: g = [1, 2], s = [1, 2, 3]
Output: 2

Ràng buộc:

1 <= g.length, s.length <= 3 * 10^4

Xem đáp án

Đang tải lời giải…

184. Giao dịch cổ phiếu nhiều lần (Best Time to Buy and Sell Stock II)

Độ khó: Dễ · Chủ đề: Greedy

Cho mảng prices với prices[i] là giá cổ phiếu ngày thứ i. Bạn có thể mua và bán nhiều lần (mua rồi bán trước khi mua lại), nhưng không được giữ nhiều hơn 1 cổ phiếu cùng lúc. Tìm lợi nhuận tối đa có thể đạt được.

Ví dụ 1:

Input: prices = [7, 1, 5, 3, 6, 4]
Output: 7
Giải thích: Mua ngày giá 1 bán ngày giá 5 (lãi 4), mua ngày giá 3 bán ngày giá 6 (lãi 3). Tổng 7.

Ví dụ 2:

Input: prices = [1, 2, 3, 4, 5]
Output: 4

Ràng buộc:

1 <= prices.length <= 3 * 10^4

Xem đáp án

Đang tải lời giải…

185. Tìm số bị thiếu (Missing Number)

Độ khó: Dễ · Chủ đề: Bit Manipulation

Cho mảng nums chứa n số phân biệt lấy từ đoạn [0, n]. Tìm số duy nhất trong đoạn đó không xuất hiện trong mảng. Hãy giải với độ phức tạp thời gian O(n) và không dùng thêm bộ nhớ ngoài O(1) (gợi ý: dùng XOR).

Ví dụ 1:

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

Ví dụ 2:

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

Ràng buộc:

n == nums.length, 1 <= n <= 10^4
Tất cả các số trong nums đều phân biệt

Xem đáp án

Đang tải lời giải…

186. Trò chơi nhảy ô (Jump Game)

Độ khó: Trung bình · Chủ đề: Greedy

Cho mảng nums, ban đầu bạn đứng ở chỉ số 0. nums[i] là bước nhảy xa nhất có thể thực hiện từ vị trí i. Trả về True nếu có thể đến được chỉ số cuối cùng, ngược lại trả về False.

Ví dụ 1:

Input: nums = [2, 3, 1, 1, 4]
Output: True
Giải thích: Nhảy 1 bước từ index 0 đến 1, rồi 3 bước đến index cuối.

Ví dụ 2:

Input: nums = [3, 2, 1, 0, 4]
Output: False
Giải thích: Luôn bị kẹt tại index 3 (nums[3] = 0), không thể đến index 4.

Ràng buộc:

1 <= nums.length <= 10^4
0 <= nums[i] <= 10^5

Xem đáp án

Đang tải lời giải…

187. Số bước nhảy ít nhất (Jump Game II)

Độ khó: Trung bình · Chủ đề: Greedy

Cũng với mảng nums như bài trên (luôn đến được đích), tìm số bước nhảy ít nhất để đi từ chỉ số 0 đến chỉ số cuối cùng.

Ví dụ 1:

Input: nums = [2, 3, 1, 1, 4]
Output: 2
Giải thích: Nhảy 1 bước từ index 0 đến index 1, rồi nhảy 3 bước đến index cuối.

Ví dụ 2:

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

Ràng buộc:

1 <= nums.length <= 10^4
Đảm bảo luôn có thể đến được chỉ số cuối

Xem đáp án

Đang tải lời giải…

188. Trạm xăng (Gas Station)

Độ khó: Trung bình · Chủ đề: Greedy

Có n trạm xăng trên một vòng tròn, trạm i cho gas[i] lít xăng. Để đi từ trạm i đến i+1 cần tốn cost[i] lít. Xe bắt đầu với bình rỗng. Tìm chỉ số trạm xuất phát để có thể đi hết 1 vòng mà không hết xăng, hoặc trả về -1 nếu không tồn tại (đảm bảo nếu tồn tại thì đáp án là duy nhất).

Ví dụ 1:

Input: gas = [1, 2, 3, 4, 5], cost = [3, 4, 5, 1, 2]
Output: 3
Giải thích: Bắt đầu tại trạm 3, đi hết vòng vẫn còn dư xăng ở mỗi chặng.

Ví dụ 2:

Input: gas = [2, 3, 4], cost = [3, 4, 3]
Output: -1

Ràng buộc:

n == gas.length == cost.length, 1 <= n <= 10^5

Xem đáp án

Đang tải lời giải…

189. Lên lịch tác vụ CPU (Task Scheduler)

Độ khó: Trung bình · Chủ đề: Greedy

Cho mảng ký tự tasks biểu diễn các tác vụ CPU cần thực hiện (mỗi ký tự là 1 loại tác vụ) và số nguyên n - thời gian nghỉ tối thiểu (số chu kỳ) giữa 2 lần thực hiện cùng 1 loại tác vụ. Mỗi chu kỳ CPU chạy 1 tác vụ hoặc nghỉ (idle). Tìm số chu kỳ CPU ít nhất để hoàn thành tất cả tác vụ.

Ví dụ 1:

Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
Giải thích: A -> B -> idle -> A -> B -> idle -> A -> B

Ví dụ 2:

Input: tasks = ["A","A","A","B","B","B"], n = 0
Output: 6
Giải thích: n = 0 nên không cần nghỉ giữa các lần lặp cùng tác vụ.

Ràng buộc:

1 <= tasks.length <= 10^4
0 <= n <= 100

Xem đáp án

Đang tải lời giải…

190. Số xuất hiện một lần II (Single Number II)

Độ khó: Trung bình · Chủ đề: Bit Manipulation

Cho mảng số nguyên nums, mọi phần tử xuất hiện đúng 3 lần, ngoại trừ đúng 1 phần tử xuất hiện đúng 1 lần. Tìm phần tử đó, không dùng thêm bộ nhớ vượt O(1).

Ví dụ 1:

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

Ví dụ 2:

Input: nums = [0, 1, 0, 1, 0, 1, 99]
Output: 99

Ràng buộc:

1 <= nums.length <= 3 * 10^4

Xem đáp án

Đang tải lời giải…

191. Số xuất hiện một lần III (Single Number III)

Độ khó: Trung bình · Chủ đề: Bit Manipulation

Cho mảng số nguyên nums, đúng 2 phần tử xuất hiện đúng 1 lần, còn lại đều xuất hiện đúng 2 lần. Tìm 2 phần tử đó (thứ tự trả về tùy ý).

Ví dụ 1:

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

Ví dụ 2:

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

Ràng buộc:

2 <= nums.length <= 3 * 10^4

Xem đáp án

Đang tải lời giải…

192. Tổng hai số không dùng dấu + (Sum of Two Integers)

Độ khó: Trung bình · Chủ đề: Bit Manipulation

Cho 2 số nguyên a, b. Tính tổng a + b mà không dùng toán tử + hoặc -.

Ví dụ 1:

Input: a = 1, b = 2
Output: 3

Ví dụ 2:

Input: a = 2, b = 3
Output: 5

Ràng buộc:

-1000 <= a, b <= 1000

Xem đáp án

Đang tải lời giải…

193. Đảo ngược bit (Reverse Bits)

Độ khó: Trung bình · Chủ đề: Bit Manipulation

Cho một số nguyên không dấu 32-bit n, đảo ngược thứ tự các bit của nó và trả về số nguyên không dấu tương ứng.

Ví dụ 1:

Input: n = 00000010100101000001111010011100 (binary)
Output: 964176192 (00111001011110000010100101000000 binary)

Ví dụ 2:

Input: n = 11111111111111111111111111111101 (binary)
Output: 3221225471 (10111111111111111111111111111111 binary)

Ràng buộc:

Input là một số nguyên không dấu 32-bit

Xem đáp án

Đang tải lời giải…

194. Chia nhãn phân vùng (Partition Labels)

Độ khó: Trung bình · Chủ đề: Greedy

Cho chuỗi s, chia s thành số lượng phần (partition) tối đa sao cho mỗi ký tự chỉ xuất hiện trong đúng 1 phần. Trả về danh sách độ dài các phần theo đúng thứ tự.

Ví dụ 1:

Input: s = "ababcbacadefegdehijhklij"
Output: [9, 7, 8]
Giải thích: "ababcbaca", "defegde", "hijhklij".

Ví dụ 2:

Input: s = "eccbbbbdec"
Output: [10]

Ràng buộc:

1 <= s.length <= 500
s chỉ gồm chữ cái thường

Xem đáp án

Đang tải lời giải…

195. Số mũi tên tối thiểu bắn bóng bay (Minimum Number of Arrows to Burst Balloons)

Độ khó: Trung bình · Chủ đề: Greedy

Có các quả bóng bay hình cầu được biểu diễn dạng khoảng points[i] = [xstart, xend] trên trục ngang. Bắn mũi tên thẳng đứng tại tọa độ x sẽ làm nổ mọi bóng có xstart <= x <= xend. Tìm số mũi tên tối thiểu để làm nổ hết tất cả bóng.

Ví dụ 1:

Input: points = [[10,16],[2,8],[1,6],[7,12]]
Output: 2
Giải thích: Bắn tại x=6 nổ [2,8] và [1,6]; bắn tại x=11 nổ [10,16] và [7,12].

Ví dụ 2:

Input: points = [[1,2],[3,4],[5,6],[7,8]]
Output: 4

Ràng buộc:

1 <= points.length <= 10^5

Xem đáp án

Đang tải lời giải…

196. Kẹo cho học sinh (Candy)

Độ khó: Khó · Chủ đề: Greedy

Có n học sinh đứng thành hàng, mỗi em có điểm đánh giá ratings[i]. Mỗi em nhận ít nhất 1 viên kẹo. Học sinh có điểm cao hơn bạn đứng cạnh phải nhận nhiều kẹo hơn bạn đó. Tìm số kẹo tối thiểu cần phát.

Ví dụ 1:

Input: ratings = [1, 0, 2]
Output: 5
Giải thích: Phát [2, 1, 2].

Ví dụ 2:

Input: ratings = [1, 2, 2]
Output: 4
Giải thích: Phát [1, 2, 1]. Vị trí thứ 3 chỉ cần 1 kẹo vì không có yêu cầu tăng nghiêm ngặt so với vị trí thứ 2.

Ràng buộc:

n == ratings.length, 1 <= n <= 2 * 10^4

Xem đáp án

Đang tải lời giải…

197. Bitwise AND của một dải số (Bitwise AND of Numbers Range)

Độ khó: Khó · Chủ đề: Bit Manipulation

Cho 2 số nguyên left và right biểu diễn một dải [left, right], trả về kết quả phép AND theo bit của tất cả các số nguyên trong dải đó (tính cả 2 đầu).

Ví dụ 1:

Input: left = 5, right = 7
Output: 4
Giải thích: 5 & 6 & 7 = 4 (0101 & 0110 & 0111 = 0100).

Ví dụ 2:

Input: left = 0, right = 0
Output: 0

Ràng buộc:

0 <= left <= right <= 2^31 - 1

Xem đáp án

Đang tải lời giải…

198. XOR lớn nhất của hai số trong mảng (Maximum XOR of Two Numbers in an Array)

Độ khó: Khó · Chủ đề: Bit Manipulation, Trie

Cho mảng số nguyên không âm nums, tìm giá trị lớn nhất của nums[i] XOR nums[j] với 0 <= i, j < nums.length. Yêu cầu độ phức tạp O(n) (dùng Trie theo bit).

Ví dụ 1:

Input: nums = [3, 10, 5, 25, 2, 8]
Output: 28
Giải thích: 5 XOR 25 = 28.

Ví dụ 2:

Input: nums = [14, 70, 53, 83, 49, 91, 36, 80, 92, 51, 66, 70]
Output: 127

Ràng buộc:

1 <= nums.length <= 2 * 10^5
0 <= nums[i] <= 2^31 - 1

Xem đáp án

Đang tải lời giải…

199. Tối đa hóa vốn (IPO)

Độ khó: Khó · Chủ đề: Greedy, Heap

Bạn có vốn ban đầu w và có thể thực hiện tối đa k dự án (mỗi dự án chỉ làm 1 lần). Dự án i cần vốn tối thiểu capital[i] và mang lại lợi nhuận thuần profits[i]. Chọn tối đa k dự án (chỉ làm được dự án nếu vốn hiện có >= capital[i], sau khi làm vốn tăng thêm profits[i]) để tối đa hóa vốn cuối cùng.

Ví dụ 1:

Input: k = 2, w = 0, profits = [1, 2, 3], capital = [0, 1, 1]
Output: 4
Giải thích: Làm dự án 0 (vốn 0 -> 1), rồi dự án 2 (vốn 1 -> 4).

Ví dụ 2:

Input: k = 3, w = 0, profits = [1, 2, 3], capital = [0, 1, 2]
Output: 6

Ràng buộc:

1 <= k <= 10^5
0 <= w <= 10^9
n == profits.length == capital.length, 1 <= n <= 10^5

Xem đáp án

Đang tải lời giải…

200. Gộp k danh sách liên kết đã sắp xếp (Merge k Sorted Lists)

Độ khó: Khó · Chủ đề: Tổng hợp (Heap, Linked List, Divide & Conquer)

Cho một mảng gồm k danh sách liên kết, mỗi danh sách đã được sắp xếp tăng dần. Gộp tất cả thành một danh sách liên kết duy nhất đã sắp xếp, rồi trả về danh sách đó. Đây là bài tổng hợp - vừa dùng cấu trúc dữ liệu (linked list), vừa dùng heap để chọn phần tử nhỏ nhất hiệu quả.

Ví dụ 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]

Ví dụ 2:

Input: lists = []
Output: []

Ràng buộc:

k == lists.length, 0 <= k <= 10^4
Tổng số node trên tất cả các danh sách không vượt quá 5 * 10^4

Xem đáp án

Đang tải lời giải…

Chúc mừng bạn đã hoàn thành 200 bài luyện thuật toán! Đây là nền tảng vững chắc để bạn tự tin giải các bài toán trên LeetCode, HackerRank hay chuẩn bị cho phỏng vấn kỹ thuật.

Th.S Trần Huy Phúc

Kỹ sư phần mềm @Adnovum & Bumbii Academy

Học Tiếng Anh với Bumbii English