Bài tập lập trình - Nâng cao
Trang này tổng hợp 100 bài tập lập trình nâng cao, dành cho bạn nào đã làm quen với các kiến thức cơ bản ở trang Bài tập lập trình - Cơ bản. Nội dung xoay quanh thuật toán sắp xếp/tìm kiếm, đệ quy & backtracking, quy hoạch động, cấu trúc dữ liệu, lập trình hướng đối tượng, lập trình hàm và các thư viện chuẩn hữu ích của từng ngôn ngữ. Mỗi bài có đáp án bằng nhiều ngôn ngữ lập trình khác nhau để bạn tiện đối chiếu.
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, 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.
Nhóm 1: Thuật toán sắp xếp nâng cao
Phần tiêu đề “Nhóm 1: Thuật toán sắp xếp nâng cao”1. Selection Sort
Cài đặt thuật toán sắp xếp chọn (selection sort) để sắp xếp tăng dần một list số.
Ví dụ:
Input: [64, 25, 12, 22, 11]Output: [11, 12, 22, 25, 64]Xem đáp án
def selection_sort(arr): n = len(arr) for i in range(n): # Tìm vị trí phần tử nhỏ nhất trong phần chưa sắp xếp min_idx = i for j in range(i + 1, n): if arr[j] < arr[min_idx]: min_idx = j arr[i], arr[min_idx] = arr[min_idx], arr[i] return arr
print(selection_sort([64, 25, 12, 22, 11]))#include <iostream>#include <vector>using namespace std;
vector<int> selectionSort(vector<int> arr) { int n = arr.size(); for (int i = 0; i < n; i++) { int minIdx = i; for (int j = i + 1; j < n; j++) { if (arr[j] < arr[minIdx]) minIdx = j; } swap(arr[i], arr[minIdx]); } return arr;}
int main() { vector<int> arr = {64, 25, 12, 22, 11}; arr = selectionSort(arr); for (int x : arr) cout << x << " "; cout << endl; return 0;}import java.util.Arrays;
public class Main { static int[] selectionSort(int[] arr) { int n = arr.length; for (int i = 0; i < n; i++) { int minIdx = i; for (int j = i + 1; j < n; j++) { if (arr[j] < arr[minIdx]) minIdx = j; } int tmp = arr[i]; arr[i] = arr[minIdx]; arr[minIdx] = tmp; } return arr; }
public static void main(String[] args) { int[] arr = {64, 25, 12, 22, 11}; System.out.println(Arrays.toString(selectionSort(arr))); }}fun selectionSort(arr: MutableList<Int>): MutableList<Int> { val n = arr.size for (i in 0 until n) { var minIdx = i for (j in i + 1 until n) { if (arr[j] < arr[minIdx]) minIdx = j } val tmp = arr[i] arr[i] = arr[minIdx] arr[minIdx] = tmp } return arr}
fun main() { val arr = mutableListOf(64, 25, 12, 22, 11) println(selectionSort(arr))}List<int> selectionSort(List<int> arr) { int n = arr.length; for (int i = 0; i < n; i++) { int minIdx = i; for (int j = i + 1; j < n; j++) { if (arr[j] < arr[minIdx]) minIdx = j; } int tmp = arr[i]; arr[i] = arr[minIdx]; arr[minIdx] = tmp; } return arr;}
void main() { var arr = [64, 25, 12, 22, 11]; print(selectionSort(arr));}2. Insertion Sort
Cài đặt thuật toán sắp xếp chèn (insertion sort) để sắp xếp tăng dần một list số.
Ví dụ:
Input: [12, 11, 13, 5, 6]Output: [5, 6, 11, 12, 13]Xem đáp án
def insertion_sort(arr): for i in range(1, len(arr)): key = arr[i] j = i - 1 while j >= 0 and arr[j] > key: arr[j + 1] = arr[j] j -= 1 arr[j + 1] = key return arr
print(insertion_sort([12, 11, 13, 5, 6]))#include <iostream>#include <vector>using namespace std;
vector<int> insertionSort(vector<int> arr) { for (int i = 1; i < (int)arr.size(); i++) { int key = arr[i]; int j = i - 1; while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = key; } return arr;}
int main() { vector<int> arr = {12, 11, 13, 5, 6}; arr = insertionSort(arr); for (int x : arr) cout << x << " "; cout << endl; return 0;}import java.util.Arrays;
public class Main { static int[] insertionSort(int[] arr) { for (int i = 1; i < arr.length; i++) { int key = arr[i]; int j = i - 1; while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = key; } return arr; }
public static void main(String[] args) { int[] arr = {12, 11, 13, 5, 6}; System.out.println(Arrays.toString(insertionSort(arr))); }}fun insertionSort(arr: MutableList<Int>): MutableList<Int> { for (i in 1 until arr.size) { val key = arr[i] var j = i - 1 while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j] j-- } arr[j + 1] = key } return arr}
fun main() { val arr = mutableListOf(12, 11, 13, 5, 6) println(insertionSort(arr))}List<int> insertionSort(List<int> arr) { for (int i = 1; i < arr.length; i++) { int key = arr[i]; int j = i - 1; while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = key; } return arr;}
void main() { var arr = [12, 11, 13, 5, 6]; print(insertionSort(arr));}3. Merge Sort
Cài đặt thuật toán sắp xếp trộn (merge sort) theo kiểu chia để trị (divide and conquer).
Ví dụ:
Input: [38, 27, 43, 3, 9, 82, 10]Output: [3, 9, 10, 27, 38, 43, 82]Xem đáp án
def merge_sort(arr): if len(arr) <= 1: return arr
mid = len(arr) // 2 left = merge_sort(arr[:mid]) right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right): result = [] i = j = 0 while i < len(left) and j < len(right): if left[i] <= right[j]: result.append(left[i]) i += 1 else: result.append(right[j]) j += 1 result.extend(left[i:]) result.extend(right[j:]) return result
print(merge_sort([38, 27, 43, 3, 9, 82, 10]))#include <iostream>#include <vector>using namespace std;
vector<int> merge(vector<int> left, vector<int> right) { vector<int> result; int i = 0, j = 0; while (i < (int)left.size() && j < (int)right.size()) { if (left[i] <= right[j]) result.push_back(left[i++]); else result.push_back(right[j++]); } while (i < (int)left.size()) result.push_back(left[i++]); while (j < (int)right.size()) result.push_back(right[j++]); return result;}
vector<int> mergeSort(vector<int> arr) { if (arr.size() <= 1) return arr;
int mid = arr.size() / 2; vector<int> left(arr.begin(), arr.begin() + mid); vector<int> right(arr.begin() + mid, arr.end());
return merge(mergeSort(left), mergeSort(right));}
int main() { vector<int> arr = {38, 27, 43, 3, 9, 82, 10}; arr = mergeSort(arr); for (int x : arr) cout << x << " "; cout << endl; return 0;}import java.util.*;
public class Main { static List<Integer> merge(List<Integer> left, List<Integer> right) { List<Integer> result = new ArrayList<>(); int i = 0, j = 0; while (i < left.size() && j < right.size()) { if (left.get(i) <= right.get(j)) result.add(left.get(i++)); else result.add(right.get(j++)); } result.addAll(left.subList(i, left.size())); result.addAll(right.subList(j, right.size())); return result; }
static List<Integer> mergeSort(List<Integer> arr) { if (arr.size() <= 1) return arr;
int mid = arr.size() / 2; List<Integer> left = mergeSort(new ArrayList<>(arr.subList(0, mid))); List<Integer> right = mergeSort(new ArrayList<>(arr.subList(mid, arr.size())));
return merge(left, right); }
public static void main(String[] args) { List<Integer> arr = Arrays.asList(38, 27, 43, 3, 9, 82, 10); System.out.println(mergeSort(new ArrayList<>(arr))); }}fun merge(left: List<Int>, right: List<Int>): List<Int> { val result = mutableListOf<Int>() var i = 0 var j = 0 while (i < left.size && j < right.size) { if (left[i] <= right[j]) result.add(left[i++]) else result.add(right[j++]) } result.addAll(left.subList(i, left.size)) result.addAll(right.subList(j, right.size)) return result}
fun mergeSort(arr: List<Int>): List<Int> { if (arr.size <= 1) return arr
val mid = arr.size / 2 val left = mergeSort(arr.subList(0, mid)) val right = mergeSort(arr.subList(mid, arr.size))
return merge(left, right)}
fun main() { val arr = listOf(38, 27, 43, 3, 9, 82, 10) println(mergeSort(arr))}List<int> merge(List<int> left, List<int> right) { List<int> result = []; int i = 0, j = 0; while (i < left.length && j < right.length) { if (left[i] <= right[j]) { result.add(left[i++]); } else { result.add(right[j++]); } } result.addAll(left.sublist(i)); result.addAll(right.sublist(j)); return result;}
List<int> mergeSort(List<int> arr) { if (arr.length <= 1) return arr;
int mid = arr.length ~/ 2; var left = mergeSort(arr.sublist(0, mid)); var right = mergeSort(arr.sublist(mid));
return merge(left, right);}
void main() { var arr = [38, 27, 43, 3, 9, 82, 10]; print(mergeSort(arr));}4. Quick Sort
Cài đặt thuật toán sắp xếp nhanh (quick sort) dùng phần tử cuối làm chốt (pivot).
Ví dụ:
Input: [10, 7, 8, 9, 1, 5]Output: [1, 5, 7, 8, 9, 10]Xem đáp án
def quick_sort(arr): if len(arr) <= 1: return arr
pivot = arr[-1] smaller = [x for x in arr[:-1] if x <= pivot] greater = [x for x in arr[:-1] if x > pivot]
return quick_sort(smaller) + [pivot] + quick_sort(greater)
print(quick_sort([10, 7, 8, 9, 1, 5]))#include <iostream>#include <vector>using namespace std;
vector<int> quickSort(vector<int> arr) { if (arr.size() <= 1) return arr;
int pivot = arr.back(); vector<int> smaller, greater; for (int i = 0; i < (int)arr.size() - 1; i++) { if (arr[i] <= pivot) smaller.push_back(arr[i]); else greater.push_back(arr[i]); }
vector<int> result = quickSort(smaller); result.push_back(pivot); vector<int> right = quickSort(greater); result.insert(result.end(), right.begin(), right.end()); return result;}
int main() { vector<int> arr = {10, 7, 8, 9, 1, 5}; arr = quickSort(arr); for (int x : arr) cout << x << " "; cout << endl; return 0;}import java.util.*;
public class Main { static List<Integer> quickSort(List<Integer> arr) { if (arr.size() <= 1) return arr;
int pivot = arr.get(arr.size() - 1); List<Integer> smaller = new ArrayList<>(); List<Integer> greater = new ArrayList<>(); for (int i = 0; i < arr.size() - 1; i++) { if (arr.get(i) <= pivot) smaller.add(arr.get(i)); else greater.add(arr.get(i)); }
List<Integer> result = new ArrayList<>(quickSort(smaller)); result.add(pivot); result.addAll(quickSort(greater)); return result; }
public static void main(String[] args) { List<Integer> arr = Arrays.asList(10, 7, 8, 9, 1, 5); System.out.println(quickSort(new ArrayList<>(arr))); }}fun quickSort(arr: List<Int>): List<Int> { if (arr.size <= 1) return arr
val pivot = arr.last() val smaller = arr.dropLast(1).filter { it <= pivot } val greater = arr.dropLast(1).filter { it > pivot }
return quickSort(smaller) + pivot + quickSort(greater)}
fun main() { val arr = listOf(10, 7, 8, 9, 1, 5) println(quickSort(arr))}List<int> quickSort(List<int> arr) { if (arr.length <= 1) return arr;
int pivot = arr.last; var rest = arr.sublist(0, arr.length - 1); var smaller = rest.where((x) => x <= pivot).toList(); var greater = rest.where((x) => x > pivot).toList();
return [...quickSort(smaller), pivot, ...quickSort(greater)];}
void main() { var arr = [10, 7, 8, 9, 1, 5]; print(quickSort(arr));}5. Counting Sort
Cài đặt thuật toán sắp xếp đếm (counting sort), áp dụng cho list số nguyên không âm.
Ví dụ:
Input: [4, 2, 2, 8, 3, 3, 1]Output: [1, 2, 2, 3, 3, 4, 8]Xem đáp án
def counting_sort(arr): if not arr: return arr
max_val = max(arr) count = [0] * (max_val + 1)
for num in arr: count[num] += 1
result = [] for value, times in enumerate(count): result.extend([value] * times)
return result
print(counting_sort([4, 2, 2, 8, 3, 3, 1]))#include <iostream>#include <vector>#include <algorithm>using namespace std;
vector<int> countingSort(vector<int> arr) { if (arr.empty()) return arr;
int maxVal = *max_element(arr.begin(), arr.end()); vector<int> count(maxVal + 1, 0);
for (int num : arr) count[num]++;
vector<int> result; for (int value = 0; value <= maxVal; value++) { for (int t = 0; t < count[value]; t++) result.push_back(value); } return result;}
int main() { vector<int> arr = {4, 2, 2, 8, 3, 3, 1}; arr = countingSort(arr); for (int x : arr) cout << x << " "; cout << endl; return 0;}import java.util.*;
public class Main { static List<Integer> countingSort(List<Integer> arr) { if (arr.isEmpty()) return arr;
int maxVal = Collections.max(arr); int[] count = new int[maxVal + 1];
for (int num : arr) count[num]++;
List<Integer> result = new ArrayList<>(); for (int value = 0; value <= maxVal; value++) { for (int t = 0; t < count[value]; t++) result.add(value); } return result; }
public static void main(String[] args) { List<Integer> arr = Arrays.asList(4, 2, 2, 8, 3, 3, 1); System.out.println(countingSort(arr)); }}fun countingSort(arr: List<Int>): List<Int> { if (arr.isEmpty()) return arr
val maxVal = arr.max() val count = IntArray(maxVal + 1)
for (num in arr) count[num]++
val result = mutableListOf<Int>() for (value in 0..maxVal) { repeat(count[value]) { result.add(value) } } return result}
fun main() { val arr = listOf(4, 2, 2, 8, 3, 3, 1) println(countingSort(arr))}List<int> countingSort(List<int> arr) { if (arr.isEmpty) return arr;
int maxVal = arr.reduce((a, b) => a > b ? a : b); var count = List<int>.filled(maxVal + 1, 0);
for (var num in arr) count[num]++;
List<int> result = []; for (int value = 0; value <= maxVal; value++) { result.addAll(List.filled(count[value], value)); } return result;}
void main() { var arr = [4, 2, 2, 8, 3, 3, 1]; print(countingSort(arr));}6. Sắp xếp theo nhiều tiêu chí
Cho một list các dictionary học sinh {"ten": ..., "diem": ..., "tuoi": ...}. Sắp xếp giảm dần theo điểm, nếu điểm bằng nhau thì sắp tăng dần theo tuổi.
Xem đáp án
students = [ {"name": "An", "score": 8, "age": 16}, {"name": "Binh", "score": 9, "age": 17}, {"name": "Chi", "score": 8, "age": 15},]
result = sorted(students, key=lambda student: (-student["score"], student["age"]))for student in result: print(student)#include <iostream>#include <vector>#include <algorithm>#include <string>using namespace std;
struct Student { string name; int score; int age;};
int main() { vector<Student> students = { {"An", 8, 16}, {"Binh", 9, 17}, {"Chi", 8, 15}, };
sort(students.begin(), students.end(), [](const Student& a, const Student& b) { if (a.score != b.score) return a.score > b.score; return a.age < b.age; });
for (auto& s : students) { cout << "{name: " << s.name << ", score: " << s.score << ", age: " << s.age << "}" << endl; } return 0;}import java.util.*;
public class Main { record Student(String name, int score, int age) {}
public static void main(String[] args) { List<Student> students = new ArrayList<>(List.of( new Student("An", 8, 16), new Student("Binh", 9, 17), new Student("Chi", 8, 15) ));
students.sort((a, b) -> { if (a.score() != b.score()) return b.score() - a.score(); return a.age() - b.age(); });
for (Student s : students) { System.out.println(s); } }}data class Student(val name: String, val score: Int, val age: Int)
fun main() { val students = listOf( Student("An", 8, 16), Student("Binh", 9, 17), Student("Chi", 8, 15) )
val result = students.sortedWith(compareByDescending<Student> { it.score }.thenBy { it.age }) for (s in result) println(s)}class Student { final String name; final int score; final int age; Student(this.name, this.score, this.age);
@override String toString() => "{name: $name, score: $score, age: $age}";}
void main() { var students = [ Student("An", 8, 16), Student("Binh", 9, 17), Student("Chi", 8, 15), ];
students.sort((a, b) { if (a.score != b.score) return b.score - a.score; return a.age - b.age; });
for (var s in students) { print(s); }}Nhóm 2: Tìm kiếm nâng cao
Phần tiêu đề “Nhóm 2: Tìm kiếm nâng cao”7. Tìm kiếm nhị phân (Binary Search)
Cài đặt tìm kiếm nhị phân trên một list đã sắp xếp tăng dần, trả về index hoặc -1 nếu không tìm thấy.
Ví dụ:
Input: arr=[1, 3, 5, 7, 9, 11], target=7Output: 3Xem đáp án
def binary_search(arr, target): left, right = 0, len(arr) - 1
while left <= right: mid = (left + right) // 2 if arr[mid] == target: return mid elif arr[mid] < target: left = mid + 1 else: right = mid - 1
return -1
print(binary_search([1, 3, 5, 7, 9, 11], 7)) # 3print(binary_search([1, 3, 5, 7, 9, 11], 4)) # -1#include <iostream>#include <vector>using namespace std;
int binarySearch(vector<int>& arr, int target) { int left = 0, right = arr.size() - 1;
while (left <= right) { int mid = (left + right) / 2; if (arr[mid] == target) return mid; else if (arr[mid] < target) left = mid + 1; else right = mid - 1; }
return -1;}
int main() { vector<int> arr = {1, 3, 5, 7, 9, 11}; cout << binarySearch(arr, 7) << endl; // 3 cout << binarySearch(arr, 4) << endl; // -1 return 0;}public class Main { static int binarySearch(int[] arr, int target) { int left = 0, right = arr.length - 1;
while (left <= right) { int mid = (left + right) / 2; if (arr[mid] == target) return mid; else if (arr[mid] < target) left = mid + 1; else right = mid - 1; }
return -1; }
public static void main(String[] args) { int[] arr = {1, 3, 5, 7, 9, 11}; System.out.println(binarySearch(arr, 7)); // 3 System.out.println(binarySearch(arr, 4)); // -1 }}fun binarySearch(arr: List<Int>, target: Int): Int { var left = 0 var right = arr.size - 1
while (left <= right) { val mid = (left + right) / 2 if (arr[mid] == target) return mid else if (arr[mid] < target) left = mid + 1 else right = mid - 1 }
return -1}
fun main() { val arr = listOf(1, 3, 5, 7, 9, 11) println(binarySearch(arr, 7)) // 3 println(binarySearch(arr, 4)) // -1}int binarySearch(List<int> arr, int target) { int left = 0, right = arr.length - 1;
while (left <= right) { int mid = (left + right) ~/ 2; if (arr[mid] == target) return mid; else if (arr[mid] < target) left = mid + 1; else right = mid - 1; }
return -1;}
void main() { var arr = [1, 3, 5, 7, 9, 11]; print(binarySearch(arr, 7)); // 3 print(binarySearch(arr, 4)); // -1}8. Tìm kiếm nhị phân đệ quy
Viết lại bài toán tìm kiếm nhị phân bằng đệ quy thay vì vòng lặp.
Xem đáp án
def binary_search_recursive(arr, target, left=0, right=None): if right is None: right = len(arr) - 1
if left > right: return -1
mid = (left + right) // 2 if arr[mid] == target: return mid elif arr[mid] < target: return binary_search_recursive(arr, target, mid + 1, right) else: return binary_search_recursive(arr, target, left, mid - 1)
print(binary_search_recursive([1, 3, 5, 7, 9, 11], 9)) # 4#include <iostream>#include <vector>using namespace std;
int binarySearchRecursive(vector<int>& arr, int target, int left, int right) { if (left > right) return -1;
int mid = (left + right) / 2; if (arr[mid] == target) return mid; else if (arr[mid] < target) return binarySearchRecursive(arr, target, mid + 1, right); else return binarySearchRecursive(arr, target, left, mid - 1);}
int main() { vector<int> arr = {1, 3, 5, 7, 9, 11}; cout << binarySearchRecursive(arr, 9, 0, arr.size() - 1) << endl; // 4 return 0;}public class Main { static int binarySearchRecursive(int[] arr, int target, int left, int right) { if (left > right) return -1;
int mid = (left + right) / 2; if (arr[mid] == target) return mid; else if (arr[mid] < target) return binarySearchRecursive(arr, target, mid + 1, right); else return binarySearchRecursive(arr, target, left, mid - 1); }
public static void main(String[] args) { int[] arr = {1, 3, 5, 7, 9, 11}; System.out.println(binarySearchRecursive(arr, 9, 0, arr.length - 1)); // 4 }}fun binarySearchRecursive(arr: List<Int>, target: Int, left: Int, right: Int): Int { if (left > right) return -1
val mid = (left + right) / 2 return when { arr[mid] == target -> mid arr[mid] < target -> binarySearchRecursive(arr, target, mid + 1, right) else -> binarySearchRecursive(arr, target, left, mid - 1) }}
fun main() { val arr = listOf(1, 3, 5, 7, 9, 11) println(binarySearchRecursive(arr, 9, 0, arr.size - 1)) // 4}int binarySearchRecursive(List<int> arr, int target, int left, int right) { if (left > right) return -1;
int mid = (left + right) ~/ 2; if (arr[mid] == target) return mid; if (arr[mid] < target) return binarySearchRecursive(arr, target, mid + 1, right); return binarySearchRecursive(arr, target, left, mid - 1);}
void main() { var arr = [1, 3, 5, 7, 9, 11]; print(binarySearchRecursive(arr, 9, 0, arr.length - 1)); // 4}9. Tìm kiếm trong list đã xoay (Rotated Sorted Array)
Cho một list đã sắp xếp tăng dần rồi bị xoay tại một điểm bất kỳ (ví dụ [4,5,6,7,0,1,2]). Tìm vị trí của target với độ phức tạp O(log n) (nghĩa là mỗi bước loại bỏ được một nửa số phần tử còn lại cần xét, giống tìm kiếm nhị phân, thay vì duyệt qua từng phần tử).
Ví dụ:
Input: arr=[4, 5, 6, 7, 0, 1, 2], target=0Output: 4Xem đáp án
def search_rotated(arr, target): left, right = 0, len(arr) - 1
while left <= right: mid = (left + right) // 2 if arr[mid] == target: return mid
# Nửa bên trái đang có thứ tự tăng dần if arr[left] <= arr[mid]: if arr[left] <= target < arr[mid]: right = mid - 1 else: left = mid + 1 else: # Nửa bên phải đang có thứ tự tăng dần if arr[mid] < target <= arr[right]: left = mid + 1 else: right = mid - 1
return -1
print(search_rotated([4, 5, 6, 7, 0, 1, 2], 0)) # 4#include <iostream>#include <vector>using namespace std;
int searchRotated(vector<int>& arr, int target) { int left = 0, right = arr.size() - 1;
while (left <= right) { int mid = (left + right) / 2; if (arr[mid] == target) return mid;
if (arr[left] <= arr[mid]) { if (arr[left] <= target && target < arr[mid]) right = mid - 1; else left = mid + 1; } else { if (arr[mid] < target && target <= arr[right]) left = mid + 1; else right = mid - 1; } }
return -1;}
int main() { vector<int> arr = {4, 5, 6, 7, 0, 1, 2}; cout << searchRotated(arr, 0) << endl; // 4 return 0;}public class Main { static int searchRotated(int[] arr, int target) { int left = 0, right = arr.length - 1;
while (left <= right) { int mid = (left + right) / 2; if (arr[mid] == target) return mid;
if (arr[left] <= arr[mid]) { if (arr[left] <= target && target < arr[mid]) right = mid - 1; else left = mid + 1; } else { if (arr[mid] < target && target <= arr[right]) left = mid + 1; else right = mid - 1; } }
return -1; }
public static void main(String[] args) { int[] arr = {4, 5, 6, 7, 0, 1, 2}; System.out.println(searchRotated(arr, 0)); // 4 }}fun searchRotated(arr: List<Int>, target: Int): Int { var left = 0 var right = arr.size - 1
while (left <= right) { val mid = (left + right) / 2 if (arr[mid] == target) return mid
if (arr[left] <= arr[mid]) { if (arr[left] <= target && target < arr[mid]) right = mid - 1 else left = mid + 1 } else { if (arr[mid] < target && target <= arr[right]) left = mid + 1 else right = mid - 1 } }
return -1}
fun main() { val arr = listOf(4, 5, 6, 7, 0, 1, 2) println(searchRotated(arr, 0)) // 4}int searchRotated(List<int> arr, int target) { int left = 0, right = arr.length - 1;
while (left <= right) { int mid = (left + right) ~/ 2; if (arr[mid] == target) return mid;
if (arr[left] <= arr[mid]) { if (arr[left] <= target && target < arr[mid]) { right = mid - 1; } else { left = mid + 1; } } else { if (arr[mid] < target && target <= arr[right]) { left = mid + 1; } else { right = mid - 1; } } }
return -1;}
void main() { var arr = [4, 5, 6, 7, 0, 1, 2]; print(searchRotated(arr, 0)); // 4}10. Tìm phần tử xuất hiện lẻ số lần (dùng XOR)
Cho một list mà mọi phần tử đều xuất hiện đúng 2 lần, trừ một phần tử xuất hiện đúng 1 lần. Tìm phần tử đó, dùng phép toán XOR (^), không dùng thêm bộ nhớ phụ.
Ví dụ:
Input: [4, 1, 2, 1, 2]Output: 4Xem đáp án
def find_single_number(arr): result = 0 for num in arr: # a ^ a = 0 và a ^ 0 = a, nên các cặp trùng nhau sẽ tự triệt tiêu result ^= num return result
print(find_single_number([4, 1, 2, 1, 2])) # 4#include <iostream>#include <vector>using namespace std;
int findSingleNumber(vector<int>& arr) { int result = 0; for (int num : arr) { // a ^ a = 0 va a ^ 0 = a, nen cac cap trung nhau se tu triet tieu result ^= num; } return result;}
int main() { vector<int> arr = {4, 1, 2, 1, 2}; cout << findSingleNumber(arr) << endl; // 4 return 0;}public class Main { static int findSingleNumber(int[] arr) { int result = 0; for (int num : arr) { result ^= num; } return result; }
public static void main(String[] args) { int[] arr = {4, 1, 2, 1, 2}; System.out.println(findSingleNumber(arr)); // 4 }}fun findSingleNumber(arr: List<Int>): Int { var result = 0 for (num in arr) { result = result xor num } return result}
fun main() { val arr = listOf(4, 1, 2, 1, 2) println(findSingleNumber(arr)) // 4}int findSingleNumber(List<int> arr) { int result = 0; for (var num in arr) { result ^= num; } return result;}
void main() { var arr = [4, 1, 2, 1, 2]; print(findSingleNumber(arr)); // 4}Nhóm 3: Đệ quy & Backtracking
Phần tiêu đề “Nhóm 3: Đệ quy & Backtracking”Backtracking (quay lui) là kỹ thuật thử từng lựa chọn một cách đệ quy; nếu lựa chọn đó dẫn đến ngõ cụt (không thể tạo ra lời giải hợp lệ), quay lại bước trước và thử lựa chọn khác, cho đến khi tìm ra lời giải hoặc thử hết mọi khả năng. Xem thêm lý thuyết: Đệ quy (Recursion).
11. Tháp Hà Nội (Tower of Hanoi)
Viết hàm đệ quy in ra các bước di chuyển để giải bài toán Tháp Hà Nội với n đĩa.
Ví dụ:
Input: n=2, source=A, destination=C, auxiliary=BOutput:Di chuyển đĩa 1 từ A sang BDi chuyển đĩa 2 từ A sang CDi chuyển đĩa 1 từ B sang CXem đáp án
def hanoi(n, source, destination, auxiliary): if n == 1: print(f"Di chuyển đĩa 1 từ {source} sang {destination}") return
hanoi(n - 1, source, auxiliary, destination) print(f"Di chuyển đĩa {n} từ {source} sang {destination}") hanoi(n - 1, auxiliary, destination, source)
hanoi(3, "A", "C", "B")#include <iostream>using namespace std;
void hanoi(int n, char source, char destination, char auxiliary) { if (n == 1) { cout << "Di chuyen dia 1 tu " << source << " sang " << destination << endl; return; }
hanoi(n - 1, source, auxiliary, destination); cout << "Di chuyen dia " << n << " tu " << source << " sang " << destination << endl; hanoi(n - 1, auxiliary, destination, source);}
int main() { hanoi(3, 'A', 'C', 'B'); return 0;}public class Main { static void hanoi(int n, char source, char destination, char auxiliary) { if (n == 1) { System.out.println("Di chuyen dia 1 tu " + source + " sang " + destination); return; }
hanoi(n - 1, source, auxiliary, destination); System.out.println("Di chuyen dia " + n + " tu " + source + " sang " + destination); hanoi(n - 1, auxiliary, destination, source); }
public static void main(String[] args) { hanoi(3, 'A', 'C', 'B'); }}fun hanoi(n: Int, source: Char, destination: Char, auxiliary: Char) { if (n == 1) { println("Di chuyen dia 1 tu $source sang $destination") return }
hanoi(n - 1, source, auxiliary, destination) println("Di chuyen dia $n tu $source sang $destination") hanoi(n - 1, auxiliary, destination, source)}
fun main() { hanoi(3, 'A', 'C', 'B')}void hanoi(int n, String source, String destination, String auxiliary) { if (n == 1) { print("Di chuyen dia 1 tu $source sang $destination"); return; }
hanoi(n - 1, source, auxiliary, destination); print("Di chuyen dia $n tu $source sang $destination"); hanoi(n - 1, auxiliary, destination, source);}
void main() { hanoi(3, "A", "C", "B");}12. Tổ hợp chập k (Combinations)
Viết hàm đệ quy combinations(arr, k) sinh ra tất cả tổ hợp chập k phần tử từ list arr (không dùng itertools).
Ví dụ:
Input: arr=[1, 2, 3, 4], k=2Output: [1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]Xem đáp án
def combinations(arr, k, start=0, current=None): if current is None: current = []
if len(current) == k: print(current) return
for i in range(start, len(arr)): current.append(arr[i]) combinations(arr, k, i + 1, current) current.pop() # Quay lui (backtrack)
combinations([1, 2, 3, 4], 2)#include <iostream>#include <vector>using namespace std;
void combinations(vector<int>& arr, int k, int start, vector<int>& current) { if ((int)current.size() == k) { cout << "["; for (int i = 0; i < (int)current.size(); i++) { cout << current[i]; if (i < (int)current.size() - 1) cout << ", "; } cout << "]" << endl; return; }
for (int i = start; i < (int)arr.size(); i++) { current.push_back(arr[i]); combinations(arr, k, i + 1, current); current.pop_back(); // Quay lui (backtrack) }}
int main() { vector<int> arr = {1, 2, 3, 4}; vector<int> current; combinations(arr, 2, 0, current); return 0;}import java.util.*;
public class Main { static void combinations(int[] arr, int k, int start, List<Integer> current) { if (current.size() == k) { System.out.println(current); return; }
for (int i = start; i < arr.length; i++) { current.add(arr[i]); combinations(arr, k, i + 1, current); current.remove(current.size() - 1); // Quay lui (backtrack) } }
public static void main(String[] args) { int[] arr = {1, 2, 3, 4}; combinations(arr, 2, 0, new ArrayList<>()); }}fun combinations(arr: List<Int>, k: Int, start: Int = 0, current: MutableList<Int> = mutableListOf()) { if (current.size == k) { println(current) return }
for (i in start until arr.size) { current.add(arr[i]) combinations(arr, k, i + 1, current) current.removeAt(current.size - 1) // Quay lui (backtrack) }}
fun main() { combinations(listOf(1, 2, 3, 4), 2)}void combinations(List<int> arr, int k, [int start = 0, List<int>? current]) { current ??= [];
if (current.length == k) { print(current); return; }
for (int i = start; i < arr.length; i++) { current.add(arr[i]); combinations(arr, k, i + 1, current); current.removeLast(); // Quay lui (backtrack) }}
void main() { combinations([1, 2, 3, 4], 2);}13. Hoán vị của list (Permutations)
Viết hàm đệ quy permutations(arr) sinh ra tất cả hoán vị của list arr (không dùng itertools).
Ví dụ:
Input: [1, 2, 3]Output: [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]Xem đáp án
def permutations(arr, current=None): if current is None: current = []
if not arr: print(current) return
for i in range(len(arr)): remaining = arr[:i] + arr[i + 1:] permutations(remaining, current + [arr[i]])
permutations([1, 2, 3])#include <iostream>#include <vector>using namespace std;
void permutations(vector<int> arr, vector<int> current) { if (arr.empty()) { cout << "["; for (int i = 0; i < (int)current.size(); i++) { cout << current[i]; if (i < (int)current.size() - 1) cout << ", "; } cout << "]" << endl; return; }
for (int i = 0; i < (int)arr.size(); i++) { vector<int> remaining; for (int j = 0; j < (int)arr.size(); j++) if (j != i) remaining.push_back(arr[j]);
vector<int> nextCurrent = current; nextCurrent.push_back(arr[i]); permutations(remaining, nextCurrent); }}
int main() { permutations({1, 2, 3}, {}); return 0;}import java.util.*;
public class Main { static void permutations(List<Integer> arr, List<Integer> current) { if (arr.isEmpty()) { System.out.println(current); return; }
for (int i = 0; i < arr.size(); i++) { List<Integer> remaining = new ArrayList<>(arr); remaining.remove(i);
List<Integer> nextCurrent = new ArrayList<>(current); nextCurrent.add(arr.get(i)); permutations(remaining, nextCurrent); } }
public static void main(String[] args) { permutations(new ArrayList<>(List.of(1, 2, 3)), new ArrayList<>()); }}fun permutations(arr: List<Int>, current: List<Int> = listOf()) { if (arr.isEmpty()) { println(current) return }
for (i in arr.indices) { val remaining = arr.filterIndexed { idx, _ -> idx != i } permutations(remaining, current + arr[i]) }}
fun main() { permutations(listOf(1, 2, 3))}void permutations(List<int> arr, [List<int>? current]) { current ??= [];
if (arr.isEmpty) { print(current); return; }
for (int i = 0; i < arr.length; i++) { var remaining = [...arr.sublist(0, i), ...arr.sublist(i + 1)]; permutations(remaining, [...current, arr[i]]); }}
void main() { permutations([1, 2, 3]);}14. Tập con (Subsets / Power Set)
Viết hàm đệ quy sinh ra tất cả tập con (kể cả tập rỗng) của một list.
Ví dụ:
Input: [1, 2, 3]Output: [], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]Xem đáp án
def subsets(arr, index=0, current=None): if current is None: current = []
if index == len(arr): print(current) return
# Không chọn phần tử arr[index] subsets(arr, index + 1, current) # Chọn phần tử arr[index] subsets(arr, index + 1, current + [arr[index]])
subsets([1, 2, 3])#include <iostream>#include <vector>using namespace std;
void printVec(vector<int>& v) { cout << "["; for (int i = 0; i < (int)v.size(); i++) { cout << v[i]; if (i < (int)v.size() - 1) cout << ", "; } cout << "]" << endl;}
void subsets(vector<int>& arr, int index, vector<int> current) { if (index == (int)arr.size()) { printVec(current); return; }
// Khong chon phan tu arr[index] subsets(arr, index + 1, current); // Chon phan tu arr[index] current.push_back(arr[index]); subsets(arr, index + 1, current);}
int main() { vector<int> arr = {1, 2, 3}; subsets(arr, 0, {}); return 0;}import java.util.*;
public class Main { static void subsets(List<Integer> arr, int index, List<Integer> current) { if (index == arr.size()) { System.out.println(current); return; }
// Khong chon phan tu arr[index] subsets(arr, index + 1, current); // Chon phan tu arr[index] List<Integer> withElement = new ArrayList<>(current); withElement.add(arr.get(index)); subsets(arr, index + 1, withElement); }
public static void main(String[] args) { subsets(List.of(1, 2, 3), 0, new ArrayList<>()); }}fun subsets(arr: List<Int>, index: Int = 0, current: List<Int> = listOf()) { if (index == arr.size) { println(current) return }
// Khong chon phan tu arr[index] subsets(arr, index + 1, current) // Chon phan tu arr[index] subsets(arr, index + 1, current + arr[index])}
fun main() { subsets(listOf(1, 2, 3))}void subsets(List<int> arr, [int index = 0, List<int>? current]) { current ??= [];
if (index == arr.length) { print(current); return; }
// Khong chon phan tu arr[index] subsets(arr, index + 1, current); // Chon phan tu arr[index] subsets(arr, index + 1, [...current, arr[index]]);}
void main() { subsets([1, 2, 3]);}15. Bài toán N-Queens
Đếm số cách đặt n quân hậu trên bàn cờ n x n sao cho không có 2 quân nào ăn nhau, dùng backtracking.
Ví dụ:
Input: n=4Output: 2Xem đáp án
def solve_n_queens(n): def is_safe(queen_positions, row, col): for h in range(row): c = queen_positions[h] # Kiểm tra cùng cột hoặc cùng đường chéo if c == col or abs(c - col) == abs(h - row): return False return True
def backtrack(row, queen_positions): if row == n: return 1
ways = 0 for col in range(n): if is_safe(queen_positions, row, col): queen_positions.append(col) ways += backtrack(row + 1, queen_positions) queen_positions.pop() # Quay lui
return ways
return backtrack(0, [])
print(solve_n_queens(4)) # 2print(solve_n_queens(8)) # 92#include <iostream>#include <vector>#include <cmath>using namespace std;
bool isSafe(vector<int>& queenPositions, int row, int col) { for (int h = 0; h < row; h++) { int c = queenPositions[h]; if (c == col || abs(c - col) == abs(h - row)) return false; } return true;}
int backtrack(int n, int row, vector<int>& queenPositions) { if (row == n) return 1;
int ways = 0; for (int col = 0; col < n; col++) { if (isSafe(queenPositions, row, col)) { queenPositions.push_back(col); ways += backtrack(n, row + 1, queenPositions); queenPositions.pop_back(); // Quay lui } } return ways;}
int solveNQueens(int n) { vector<int> queenPositions; return backtrack(n, 0, queenPositions);}
int main() { cout << solveNQueens(4) << endl; // 2 cout << solveNQueens(8) << endl; // 92 return 0;}import java.util.*;
public class Main { static boolean isSafe(List<Integer> queenPositions, int row, int col) { for (int h = 0; h < row; h++) { int c = queenPositions.get(h); if (c == col || Math.abs(c - col) == Math.abs(h - row)) return false; } return true; }
static int backtrack(int n, int row, List<Integer> queenPositions) { if (row == n) return 1;
int ways = 0; for (int col = 0; col < n; col++) { if (isSafe(queenPositions, row, col)) { queenPositions.add(col); ways += backtrack(n, row + 1, queenPositions); queenPositions.remove(queenPositions.size() - 1); // Quay lui } } return ways; }
static int solveNQueens(int n) { return backtrack(n, 0, new ArrayList<>()); }
public static void main(String[] args) { System.out.println(solveNQueens(4)); // 2 System.out.println(solveNQueens(8)); // 92 }}fun isSafe(queenPositions: List<Int>, row: Int, col: Int): Boolean { for (h in 0 until row) { val c = queenPositions[h] if (c == col || Math.abs(c - col) == Math.abs(h - row)) return false } return true}
fun backtrack(n: Int, row: Int, queenPositions: MutableList<Int>): Int { if (row == n) return 1
var ways = 0 for (col in 0 until n) { if (isSafe(queenPositions, row, col)) { queenPositions.add(col) ways += backtrack(n, row + 1, queenPositions) queenPositions.removeAt(queenPositions.size - 1) // Quay lui } } return ways}
fun solveNQueens(n: Int): Int = backtrack(n, 0, mutableListOf())
fun main() { println(solveNQueens(4)) // 2 println(solveNQueens(8)) // 92}bool isSafe(List<int> queenPositions, int row, int col) { for (int h = 0; h < row; h++) { int c = queenPositions[h]; if (c == col || (c - col).abs() == (h - row).abs()) return false; } return true;}
int backtrack(int n, int row, List<int> queenPositions) { if (row == n) return 1;
int ways = 0; for (int col = 0; col < n; col++) { if (isSafe(queenPositions, row, col)) { queenPositions.add(col); ways += backtrack(n, row + 1, queenPositions); queenPositions.removeLast(); // Quay lui } } return ways;}
int solveNQueens(int n) => backtrack(n, 0, []);
void main() { print(solveNQueens(4)); // 2 print(solveNQueens(8)); // 92}16. Đường đi trong lưới (Grid Paths)
Đếm số đường đi từ góc trên-trái đến góc dưới-phải của một lưới m x n, chỉ được di chuyển sang phải hoặc xuống dưới.
Ví dụ:
Input: m=3, n=3Output: 6Xem đáp án
def count_paths(m, n): if m == 1 or n == 1: return 1 return count_paths(m - 1, n) + count_paths(m, n - 1)
print(count_paths(3, 3)) # 6#include <iostream>using namespace std;
int countPaths(int m, int n) { if (m == 1 || n == 1) return 1; return countPaths(m - 1, n) + countPaths(m, n - 1);}
int main() { cout << countPaths(3, 3) << endl; // 6 return 0;}public class Main { static int countPaths(int m, int n) { if (m == 1 || n == 1) return 1; return countPaths(m - 1, n) + countPaths(m, n - 1); }
public static void main(String[] args) { System.out.println(countPaths(3, 3)); // 6 }}fun countPaths(m: Int, n: Int): Int { if (m == 1 || n == 1) return 1 return countPaths(m - 1, n) + countPaths(m, n - 1)}
fun main() { println(countPaths(3, 3)) // 6}int countPaths(int m, int n) { if (m == 1 || n == 1) return 1; return countPaths(m - 1, n) + countPaths(m, n - 1);}
void main() { print(countPaths(3, 3)); // 6}17. Subset Sum
Cho một list số nguyên dương và một tổng đích target. Kiểm tra xem có tồn tại một tập con nào của list có tổng bằng target hay không, dùng đệ quy.
Ví dụ:
Input: arr=[3, 34, 4, 12, 5, 2], target=9Output: TrueXem đáp án
def subset_sum(arr, target, index=0): if target == 0: return True if index == len(arr) or target < 0: return False
# Không chọn arr[index] HOẶC có chọn arr[index] return subset_sum(arr, target, index + 1) or subset_sum(arr, target - arr[index], index + 1)
print(subset_sum([3, 34, 4, 12, 5, 2], 9)) # Trueprint(subset_sum([3, 34, 4, 12, 5, 2], 100)) # False#include <iostream>#include <vector>using namespace std;
bool subsetSum(vector<int>& arr, int target, int index = 0) { if (target == 0) return true; if (index == (int)arr.size() || target < 0) return false;
// Khong chon arr[index] HOAC co chon arr[index] return subsetSum(arr, target, index + 1) || subsetSum(arr, target - arr[index], index + 1);}
int main() { vector<int> arr = {3, 34, 4, 12, 5, 2}; cout << boolalpha << subsetSum(arr, 9) << endl; // true cout << boolalpha << subsetSum(arr, 100) << endl; // false return 0;}public class Main { static boolean subsetSum(int[] arr, int target, int index) { if (target == 0) return true; if (index == arr.length || target < 0) return false;
return subsetSum(arr, target, index + 1) || subsetSum(arr, target - arr[index], index + 1); }
public static void main(String[] args) { int[] arr = {3, 34, 4, 12, 5, 2}; System.out.println(subsetSum(arr, 9, 0)); // true System.out.println(subsetSum(arr, 100, 0)); // false }}fun subsetSum(arr: List<Int>, target: Int, index: Int = 0): Boolean { if (target == 0) return true if (index == arr.size || target < 0) return false
return subsetSum(arr, target, index + 1) || subsetSum(arr, target - arr[index], index + 1)}
fun main() { val arr = listOf(3, 34, 4, 12, 5, 2) println(subsetSum(arr, 9)) // true println(subsetSum(arr, 100)) // false}bool subsetSum(List<int> arr, int target, [int index = 0]) { if (target == 0) return true; if (index == arr.length || target < 0) return false;
return subsetSum(arr, target, index + 1) || subsetSum(arr, target - arr[index], index + 1);}
void main() { var arr = [3, 34, 4, 12, 5, 2]; print(subsetSum(arr, 9)); // true print(subsetSum(arr, 100)); // false}18. Số Catalan bằng đệ quy
Số Catalan thứ n được tính bằng công thức đệ quy: C(0) = 1, C(n) = sum(C(i) * C(n-1-i)) với i từ 0 đến n-1. Viết hàm đệ quy tính số Catalan thứ n.
Ví dụ:
Input: n=4Output: 14Xem đáp án
def catalan(n): if n <= 1: return 1
result = 0 for i in range(n): result += catalan(i) * catalan(n - 1 - i)
return result
for i in range(6): print(catalan(i), end=" ") # 1 1 2 5 14 42#include <iostream>using namespace std;
int catalan(int n) { if (n <= 1) return 1;
int result = 0; for (int i = 0; i < n; i++) { result += catalan(i) * catalan(n - 1 - i); }
return result;}
int main() { for (int i = 0; i < 6; i++) cout << catalan(i) << " "; // 1 1 2 5 14 42 cout << endl; return 0;}public class Main { static int catalan(int n) { if (n <= 1) return 1;
int result = 0; for (int i = 0; i < n; i++) { result += catalan(i) * catalan(n - 1 - i); }
return result; }
public static void main(String[] args) { for (int i = 0; i < 6; i++) System.out.print(catalan(i) + " "); // 1 1 2 5 14 42 }}fun catalan(n: Int): Int { if (n <= 1) return 1
var result = 0 for (i in 0 until n) { result += catalan(i) * catalan(n - 1 - i) }
return result}
fun main() { for (i in 0 until 6) print("${catalan(i)} ") // 1 1 2 5 14 42}import 'dart:io';
int catalan(int n) { if (n <= 1) return 1;
int result = 0; for (int i = 0; i < n; i++) { result += catalan(i) * catalan(n - 1 - i); }
return result;}
void main() { for (int i = 0; i < 6; i++) { stdout.write("${catalan(i)} "); // 1 1 2 5 14 42 }}19. Ghép ngoặc hợp lệ (Generate Parentheses)
Với n cặp ngoặc, sinh ra tất cả các chuỗi ngoặc () hợp lệ có thể tạo được, dùng backtracking.
Ví dụ:
Input: n=3Output: ['((()))', '(()())', '(())()', '()(())', '()()()']Xem đáp án
def generate_parentheses(n): result = []
def backtrack(current, opened, closed): if len(current) == 2 * n: result.append(current) return
if opened < n: backtrack(current + "(", opened + 1, closed) if closed < opened: backtrack(current + ")", opened, closed + 1)
backtrack("", 0, 0) return result
print(generate_parentheses(3))#include <iostream>#include <vector>#include <string>using namespace std;
void backtrack(int n, string current, int opened, int closed, vector<string>& result) { if ((int)current.size() == 2 * n) { result.push_back(current); return; }
if (opened < n) backtrack(n, current + "(", opened + 1, closed, result); if (closed < opened) backtrack(n, current + ")", opened, closed + 1, result);}
vector<string> generateParentheses(int n) { vector<string> result; backtrack(n, "", 0, 0, result); return result;}
int main() { vector<string> result = generateParentheses(3); cout << "["; for (int i = 0; i < (int)result.size(); i++) { cout << "'" << result[i] << "'"; if (i < (int)result.size() - 1) cout << ", "; } cout << "]" << endl; return 0;}import java.util.*;
public class Main { static void backtrack(int n, String current, int opened, int closed, List<String> result) { if (current.length() == 2 * n) { result.add(current); return; }
if (opened < n) backtrack(n, current + "(", opened + 1, closed, result); if (closed < opened) backtrack(n, current + ")", opened, closed + 1, result); }
static List<String> generateParentheses(int n) { List<String> result = new ArrayList<>(); backtrack(n, "", 0, 0, result); return result; }
public static void main(String[] args) { System.out.println(generateParentheses(3)); }}fun backtrack(n: Int, current: String, opened: Int, closed: Int, result: MutableList<String>) { if (current.length == 2 * n) { result.add(current) return }
if (opened < n) backtrack(n, current + "(", opened + 1, closed, result) if (closed < opened) backtrack(n, current + ")", opened, closed + 1, result)}
fun generateParentheses(n: Int): List<String> { val result = mutableListOf<String>() backtrack(n, "", 0, 0, result) return result}
fun main() { println(generateParentheses(3))}void backtrack(int n, String current, int opened, int closed, List<String> result) { if (current.length == 2 * n) { result.add(current); return; }
if (opened < n) backtrack(n, "$current(", opened + 1, closed, result); if (closed < opened) backtrack(n, "$current)", opened, closed + 1, result);}
List<String> generateParentheses(int n) { List<String> result = []; backtrack(n, "", 0, 0, result); return result;}
void main() { print(generateParentheses(3));}20. Chia list thành 2 phần có tổng gần bằng nhau
Dùng đệ quy để tìm cách chia một list số nguyên dương thành 2 phần sao cho hiệu tổng 2 phần là nhỏ nhất có thể.
Ví dụ:
Input: [1, 6, 11, 5]Output: 1Xem đáp án
def optimal_partition(arr): total = sum(arr) min_diff = [total] # dùng list để có thể thay đổi trong hàm lồng
def try_partition(index, sum_part1): if index == len(arr): diff = abs(total - 2 * sum_part1) min_diff[0] = min(min_diff[0], diff) return
try_partition(index + 1, sum_part1 + arr[index]) try_partition(index + 1, sum_part1)
try_partition(0, 0) return min_diff[0]
print(optimal_partition([1, 6, 11, 5])) # 1 (chia thành [1, 5, 6] và [11])#include <iostream>#include <vector>#include <numeric>#include <cmath>#include <climits>using namespace std;
void tryPartition(vector<int>& arr, int index, int sumPart1, int total, int& minDiff) { if (index == (int)arr.size()) { int diff = abs(total - 2 * sumPart1); minDiff = min(minDiff, diff); return; }
tryPartition(arr, index + 1, sumPart1 + arr[index], total, minDiff); tryPartition(arr, index + 1, sumPart1, total, minDiff);}
int optimalPartition(vector<int>& arr) { int total = accumulate(arr.begin(), arr.end(), 0); int minDiff = total; tryPartition(arr, 0, 0, total, minDiff); return minDiff;}
int main() { vector<int> arr = {1, 6, 11, 5}; cout << optimalPartition(arr) << endl; // 1 (chia thanh [1, 5, 6] va [11]) return 0;}public class Main { static int minDiff;
static void tryPartition(int[] arr, int index, int sumPart1, int total) { if (index == arr.length) { int diff = Math.abs(total - 2 * sumPart1); minDiff = Math.min(minDiff, diff); return; }
tryPartition(arr, index + 1, sumPart1 + arr[index], total); tryPartition(arr, index + 1, sumPart1, total); }
static int optimalPartition(int[] arr) { int total = 0; for (int x : arr) total += x; minDiff = total; tryPartition(arr, 0, 0, total); return minDiff; }
public static void main(String[] args) { int[] arr = {1, 6, 11, 5}; System.out.println(optimalPartition(arr)); // 1 (chia thanh [1, 5, 6] va [11]) }}fun tryPartition(arr: List<Int>, index: Int, sumPart1: Int, total: Int, minDiff: IntArray) { if (index == arr.size) { val diff = Math.abs(total - 2 * sumPart1) minDiff[0] = minOf(minDiff[0], diff) return }
tryPartition(arr, index + 1, sumPart1 + arr[index], total, minDiff) tryPartition(arr, index + 1, sumPart1, total, minDiff)}
fun optimalPartition(arr: List<Int>): Int { val total = arr.sum() val minDiff = intArrayOf(total) tryPartition(arr, 0, 0, total, minDiff) return minDiff[0]}
fun main() { val arr = listOf(1, 6, 11, 5) println(optimalPartition(arr)) // 1 (chia thanh [1, 5, 6] va [11])}void tryPartition(List<int> arr, int index, int sumPart1, int total, List<int> minDiff) { if (index == arr.length) { int diff = (total - 2 * sumPart1).abs(); minDiff[0] = diff < minDiff[0] ? diff : minDiff[0]; return; }
tryPartition(arr, index + 1, sumPart1 + arr[index], total, minDiff); tryPartition(arr, index + 1, sumPart1, total, minDiff);}
int optimalPartition(List<int> arr) { int total = arr.fold(0, (a, b) => a + b); var minDiff = [total]; tryPartition(arr, 0, 0, total, minDiff); return minDiff[0];}
void main() { var arr = [1, 6, 11, 5]; print(optimalPartition(arr)); // 1 (chia thanh [1, 5, 6] va [11])}Nhóm 4: Quy hoạch động (Dynamic Programming)
Phần tiêu đề “Nhóm 4: Quy hoạch động (Dynamic Programming)”Quy hoạch động (Dynamic Programming - DP) là kỹ thuật giải bài toán lớn bằng cách chia thành các bài toán con nhỏ hơn có tính chất lặp lại, giải từng bài toán con một lần rồi lưu lại kết quả (thường trong một mảng gọi là dp) để tái sử dụng thay vì tính lại nhiều lần.
21. Fibonacci với Memoization
Tối ưu hàm tính số Fibonacci thứ n bằng kỹ thuật ghi nhớ (memoization) để tránh tính lại nhiều lần.
Ví dụ:
Input: n=50Output: 12586269025Xem đáp án
def fib_memo(n, cache=None): if cache is None: cache = {}
if n <= 1: return n if n in cache: return cache[n]
cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache) return cache[n]
print(fib_memo(50)) # Chạy nhanh nhờ cache, không như đệ quy thường#include <iostream>#include <unordered_map>using namespace std;
long long fibMemo(int n, unordered_map<int, long long>& cache) { if (n <= 1) return n; if (cache.count(n)) return cache[n];
cache[n] = fibMemo(n - 1, cache) + fibMemo(n - 2, cache); return cache[n];}
int main() { unordered_map<int, long long> cache; cout << fibMemo(50, cache) << endl; // Chay nhanh nho cache, khong nhu de quy thuong return 0;}import java.util.*;
public class Main { static long fibMemo(int n, Map<Integer, Long> cache) { if (n <= 1) return n; if (cache.containsKey(n)) return cache.get(n);
long result = fibMemo(n - 1, cache) + fibMemo(n - 2, cache); cache.put(n, result); return result; }
public static void main(String[] args) { System.out.println(fibMemo(50, new HashMap<>())); // Chay nhanh nho cache, khong nhu de quy thuong }}fun fibMemo(n: Int, cache: MutableMap<Int, Long> = mutableMapOf()): Long { if (n <= 1) return n.toLong() cache[n]?.let { return it }
val result = fibMemo(n - 1, cache) + fibMemo(n - 2, cache) cache[n] = result return result}
fun main() { println(fibMemo(50)) // Chay nhanh nho cache, khong nhu de quy thuong}int fibMemo(int n, [Map<int, int>? cache]) { cache ??= {};
if (n <= 1) return n; if (cache.containsKey(n)) return cache[n]!;
cache[n] = fibMemo(n - 1, cache) + fibMemo(n - 2, cache); return cache[n]!;}
void main() { print(fibMemo(50)); // Chay nhanh nho cache, khong nhu de quy thuong}22. Fibonacci Bottom-up
Tính số Fibonacci thứ n bằng quy hoạch động kiểu bottom-up (dùng vòng lặp, không đệ quy).
Ví dụ:
Input: n=30Output: 832040Xem đáp án
def fib_bottom_up(n): if n <= 1: return n
dp = [0] * (n + 1) dp[1] = 1
for i in range(2, n + 1): dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
print(fib_bottom_up(30))#include <iostream>#include <vector>using namespace std;
long long fibBottomUp(int n) { if (n <= 1) return n;
vector<long long> dp(n + 1, 0); dp[1] = 1;
for (int i = 2; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; }
return dp[n];}
int main() { cout << fibBottomUp(30) << endl; return 0;}public class Main { static long fibBottomUp(int n) { if (n <= 1) return n;
long[] dp = new long[n + 1]; dp[1] = 1;
for (int i = 2; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; }
return dp[n]; }
public static void main(String[] args) { System.out.println(fibBottomUp(30)); }}fun fibBottomUp(n: Int): Long { if (n <= 1) return n.toLong()
val dp = LongArray(n + 1) dp[1] = 1
for (i in 2..n) { dp[i] = dp[i - 1] + dp[i - 2] }
return dp[n]}
fun main() { println(fibBottomUp(30))}int fibBottomUp(int n) { if (n <= 1) return n;
var dp = List<int>.filled(n + 1, 0); dp[1] = 1;
for (int i = 2; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; }
return dp[n];}
void main() { print(fibBottomUp(30));}23. Bài toán cái túi 0/1 (0/1 Knapsack)
Cho n món đồ, mỗi món có trọng lượng và giá trị, và một túi có sức chứa capacity. Tìm giá trị lớn nhất có thể mang được (mỗi món chỉ lấy 0 hoặc 1 lần).
Ví dụ:
Input: weights=[1, 3, 4, 5], values=[1, 4, 5, 7], capacity=7Output: 9Xem đáp án
def knapsack(weights, values, capacity): n = len(weights) dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1): for w in range(capacity + 1): if weights[i - 1] <= w: dp[i][w] = max(dp[i - 1][w], values[i - 1] + dp[i - 1][w - weights[i - 1]]) else: dp[i][w] = dp[i - 1][w]
return dp[n][capacity]
weights = [1, 3, 4, 5]values = [1, 4, 5, 7]print(knapsack(weights, values, 7)) # 9#include <iostream>#include <vector>#include <algorithm>using namespace std;
int knapsack(vector<int>& weights, vector<int>& values, int capacity) { int n = weights.size(); vector<vector<int>> dp(n + 1, vector<int>(capacity + 1, 0));
for (int i = 1; i <= n; i++) { for (int w = 0; w <= capacity; w++) { if (weights[i - 1] <= w) { dp[i][w] = max(dp[i - 1][w], values[i - 1] + dp[i - 1][w - weights[i - 1]]); } else { dp[i][w] = dp[i - 1][w]; } } }
return dp[n][capacity];}
int main() { vector<int> weights = {1, 3, 4, 5}; vector<int> values = {1, 4, 5, 7}; cout << knapsack(weights, values, 7) << endl; // 9 return 0;}public class Main { static int knapsack(int[] weights, int[] values, int capacity) { int n = weights.length; int[][] dp = new int[n + 1][capacity + 1];
for (int i = 1; i <= n; i++) { for (int w = 0; w <= capacity; w++) { if (weights[i - 1] <= w) { dp[i][w] = Math.max(dp[i - 1][w], values[i - 1] + dp[i - 1][w - weights[i - 1]]); } else { dp[i][w] = dp[i - 1][w]; } } }
return dp[n][capacity]; }
public static void main(String[] args) { int[] weights = {1, 3, 4, 5}; int[] values = {1, 4, 5, 7}; System.out.println(knapsack(weights, values, 7)); // 9 }}fun knapsack(weights: List<Int>, values: List<Int>, capacity: Int): Int { val n = weights.size val dp = Array(n + 1) { IntArray(capacity + 1) }
for (i in 1..n) { for (w in 0..capacity) { dp[i][w] = if (weights[i - 1] <= w) { maxOf(dp[i - 1][w], values[i - 1] + dp[i - 1][w - weights[i - 1]]) } else { dp[i - 1][w] } } }
return dp[n][capacity]}
fun main() { val weights = listOf(1, 3, 4, 5) val values = listOf(1, 4, 5, 7) println(knapsack(weights, values, 7)) // 9}int knapsack(List<int> weights, List<int> values, int capacity) { int n = weights.length; var dp = List.generate(n + 1, (_) => List<int>.filled(capacity + 1, 0));
for (int i = 1; i <= n; i++) { for (int w = 0; w <= capacity; w++) { if (weights[i - 1] <= w) { dp[i][w] = [dp[i - 1][w], values[i - 1] + dp[i - 1][w - weights[i - 1]]].reduce((a, b) => a > b ? a : b); } else { dp[i][w] = dp[i - 1][w]; } } }
return dp[n][capacity];}
void main() { var weights = [1, 3, 4, 5]; var values = [1, 4, 5, 7]; print(knapsack(weights, values, 7)); // 9}24. Dãy con chung dài nhất (Longest Common Subsequence)
Tìm độ dài dãy con chung dài nhất giữa 2 chuỗi.
Ví dụ:
Input: s1="ABCBDAB", s2="BDCABA"Output: 4Xem đáp án
def lcs(s1, s2): m, n = len(s1), len(s2) dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1): for j in range(1, n + 1): if s1[i - 1] == s2[j - 1]: dp[i][j] = dp[i - 1][j - 1] + 1 else: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n]
print(lcs("ABCBDAB", "BDCABA")) # 4#include <iostream>#include <vector>#include <string>#include <algorithm>using namespace std;
int lcs(const string& s1, const string& s2) { int m = s1.size(), n = s2.size(); vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (s1[i - 1] == s2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1; else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); } }
return dp[m][n];}
int main() { cout << lcs("ABCBDAB", "BDCABA") << endl; // 4 return 0;}public class Main { static int lcs(String s1, String s2) { int m = s1.length(), n = s2.length(); int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (s1.charAt(i - 1) == s2.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1] + 1; else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); } }
return dp[m][n]; }
public static void main(String[] args) { System.out.println(lcs("ABCBDAB", "BDCABA")); // 4 }}fun lcs(s1: String, s2: String): Int { val m = s1.length val n = s2.length val dp = Array(m + 1) { IntArray(n + 1) }
for (i in 1..m) { for (j in 1..n) { dp[i][j] = if (s1[i - 1] == s2[j - 1]) dp[i - 1][j - 1] + 1 else maxOf(dp[i - 1][j], dp[i][j - 1]) } }
return dp[m][n]}
fun main() { println(lcs("ABCBDAB", "BDCABA")) // 4}int lcs(String s1, String s2) { int m = s1.length, n = s2.length; var dp = List.generate(m + 1, (_) => List<int>.filled(n + 1, 0));
for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (s1[i - 1] == s2[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1; } else { dp[i][j] = dp[i - 1][j] > dp[i][j - 1] ? dp[i - 1][j] : dp[i][j - 1]; } } }
return dp[m][n];}
void main() { print(lcs("ABCBDAB", "BDCABA")); // 4}25. Khoảng cách chỉnh sửa (Edit Distance)
Tính số phép biến đổi tối thiểu (thêm, xóa, sửa 1 ký tự) để biến chuỗi s1 thành chuỗi s2.
Ví dụ:
Input: s1="kitten", s2="sitting"Output: 3Xem đáp án
def edit_distance(s1, s2): m, n = len(s1), len(s2) dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1): dp[i][0] = i for j in range(n + 1): dp[0][j] = j
for i in range(1, m + 1): for j in range(1, n + 1): if s1[i - 1] == s2[j - 1]: dp[i][j] = dp[i - 1][j - 1] else: dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
return dp[m][n]
print(edit_distance("kitten", "sitting")) # 3#include <iostream>#include <vector>#include <string>#include <algorithm>using namespace std;
int editDistance(const string& s1, const string& s2) { int m = s1.size(), n = s2.size(); vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
for (int i = 0; i <= m; i++) dp[i][0] = i; for (int j = 0; j <= n; j++) dp[0][j] = j;
for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (s1[i - 1] == s2[j - 1]) dp[i][j] = dp[i - 1][j - 1]; else dp[i][j] = 1 + min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]}); } }
return dp[m][n];}
int main() { cout << editDistance("kitten", "sitting") << endl; // 3 return 0;}public class Main { static int editDistance(String s1, String s2) { int m = s1.length(), n = s2.length(); int[][] dp = new int[m + 1][n + 1];
for (int i = 0; i <= m; i++) dp[i][0] = i; for (int j = 0; j <= n; j++) dp[0][j] = j;
for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (s1.charAt(i - 1) == s2.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1]; else dp[i][j] = 1 + Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1])); } }
return dp[m][n]; }
public static void main(String[] args) { System.out.println(editDistance("kitten", "sitting")); // 3 }}fun editDistance(s1: String, s2: String): Int { val m = s1.length val n = s2.length val dp = Array(m + 1) { IntArray(n + 1) }
for (i in 0..m) dp[i][0] = i for (j in 0..n) dp[0][j] = j
for (i in 1..m) { for (j in 1..n) { dp[i][j] = if (s1[i - 1] == s2[j - 1]) dp[i - 1][j - 1] else 1 + minOf(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) } }
return dp[m][n]}
fun main() { println(editDistance("kitten", "sitting")) // 3}int editDistance(String s1, String s2) { int m = s1.length, n = s2.length; var dp = List.generate(m + 1, (_) => List<int>.filled(n + 1, 0));
for (int i = 0; i <= m; i++) dp[i][0] = i; for (int j = 0; j <= n; j++) dp[0][j] = j;
for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (s1[i - 1] == s2[j - 1]) { dp[i][j] = dp[i - 1][j - 1]; } else { dp[i][j] = 1 + [dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]].reduce((a, b) => a < b ? a : b); } } }
return dp[m][n];}
void main() { print(editDistance("kitten", "sitting")); // 3}26. Đổi tiền tối ưu (Coin Change)
Cho một list mệnh giá tiền xu và một số tiền amount. Tìm số lượng xu tối thiểu để tạo thành amount (trả về -1 nếu không thể).
Ví dụ:
Input: coins=[1, 2, 5], amount=11Output: 3Xem đáp án
def coin_change(coins, amount): dp = [float("inf")] * (amount + 1) dp[0] = 0
for total in range(1, amount + 1): for coin in coins: if coin <= total: dp[total] = min(dp[total], dp[total - coin] + 1)
return dp[amount] if dp[amount] != float("inf") else -1
print(coin_change([1, 2, 5], 11)) # 3 (5 + 5 + 1)#include <iostream>#include <vector>#include <climits>using namespace std;
int coinChange(vector<int>& coins, int amount) { vector<int> dp(amount + 1, INT_MAX); dp[0] = 0;
for (int total = 1; total <= amount; total++) { for (int coin : coins) { if (coin <= total && dp[total - coin] != INT_MAX) { dp[total] = min(dp[total], dp[total - coin] + 1); } } }
return dp[amount] == INT_MAX ? -1 : dp[amount];}
int main() { vector<int> coins = {1, 2, 5}; cout << coinChange(coins, 11) << endl; // 3 return 0;}import java.util.Arrays;
public class Main { static int coinChange(int[] coins, int amount) { int[] dp = new int[amount + 1]; Arrays.fill(dp, Integer.MAX_VALUE); dp[0] = 0;
for (int total = 1; total <= amount; total++) { for (int coin : coins) { if (coin <= total && dp[total - coin] != Integer.MAX_VALUE) { dp[total] = Math.min(dp[total], dp[total - coin] + 1); } } }
return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount]; }
public static void main(String[] args) { int[] coins = {1, 2, 5}; System.out.println(coinChange(coins, 11)); // 3 }}fun coinChange(coins: IntArray, amount: Int): Int { val dp = IntArray(amount + 1) { Int.MAX_VALUE } dp[0] = 0
for (total in 1..amount) { for (coin in coins) { if (coin <= total && dp[total - coin] != Int.MAX_VALUE) { dp[total] = minOf(dp[total], dp[total - coin] + 1) } } }
return if (dp[amount] == Int.MAX_VALUE) -1 else dp[amount]}
fun main() { val coins = intArrayOf(1, 2, 5) println(coinChange(coins, 11)) // 3}int coinChange(List<int> coins, int amount) { final dp = List<int>.filled(amount + 1, 1 << 30); dp[0] = 0;
for (int total = 1; total <= amount; total++) { for (int coin in coins) { if (coin <= total && dp[total - coin] != (1 << 30)) { dp[total] = dp[total] < dp[total - coin] + 1 ? dp[total] : dp[total - coin] + 1; } } }
return dp[amount] == (1 << 30) ? -1 : dp[amount];}
void main() { final coins = [1, 2, 5]; print(coinChange(coins, 11)); // 3}27. Dãy con tăng dài nhất (Longest Increasing Subsequence)
Tìm độ dài dãy con tăng dần dài nhất trong một list số.
Ví dụ:
Input: [10, 9, 2, 5, 3, 7, 101, 18]Output: 4Xem đáp án
def longest_increasing_subsequence(arr): if not arr: return 0
dp = [1] * len(arr)
for i in range(1, len(arr)): for j in range(i): if arr[j] < arr[i]: dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
print(longest_increasing_subsequence([10, 9, 2, 5, 3, 7, 101, 18])) # 4#include <iostream>#include <vector>#include <algorithm>using namespace std;
int longestIncreasingSubsequence(vector<int>& arr) { if (arr.empty()) return 0;
vector<int> dp(arr.size(), 1);
for (size_t i = 1; i < arr.size(); i++) { for (size_t j = 0; j < i; j++) { if (arr[j] < arr[i]) dp[i] = max(dp[i], dp[j] + 1); } }
return *max_element(dp.begin(), dp.end());}
int main() { vector<int> arr = {10, 9, 2, 5, 3, 7, 101, 18}; cout << longestIncreasingSubsequence(arr) << endl; // 4 return 0;}import java.util.Arrays;
public class Main { static int longestIncreasingSubsequence(int[] arr) { if (arr.length == 0) return 0;
int[] dp = new int[arr.length]; Arrays.fill(dp, 1);
for (int i = 1; i < arr.length; i++) { for (int j = 0; j < i; j++) { if (arr[j] < arr[i]) dp[i] = Math.max(dp[i], dp[j] + 1); } }
return Arrays.stream(dp).max().getAsInt(); }
public static void main(String[] args) { int[] arr = {10, 9, 2, 5, 3, 7, 101, 18}; System.out.println(longestIncreasingSubsequence(arr)); // 4 }}fun longestIncreasingSubsequence(arr: IntArray): Int { if (arr.isEmpty()) return 0
val dp = IntArray(arr.size) { 1 }
for (i in 1 until arr.size) { for (j in 0 until i) { if (arr[j] < arr[i]) dp[i] = maxOf(dp[i], dp[j] + 1) } }
return dp.max()}
fun main() { val arr = intArrayOf(10, 9, 2, 5, 3, 7, 101, 18) println(longestIncreasingSubsequence(arr)) // 4}int longestIncreasingSubsequence(List<int> arr) { if (arr.isEmpty) return 0;
final dp = List<int>.filled(arr.length, 1);
for (int i = 1; i < arr.length; i++) { for (int j = 0; j < i; j++) { if (arr[j] < arr[i]) dp[i] = dp[i] > dp[j] + 1 ? dp[i] : dp[j] + 1; } }
return dp.reduce((a, b) => a > b ? a : b);}
void main() { final arr = [10, 9, 2, 5, 3, 7, 101, 18]; print(longestIncreasingSubsequence(arr)); // 4}28. Tổng dãy con lớn nhất (Kadane’s Algorithm)
Tìm tổng lớn nhất của một dãy con liên tiếp trong list số (có thể có số âm).
Ví dụ:
Input: [-2, 1, -3, 4, -1, 2, 1, -5, 4]Output: 6Xem đáp án
def max_subarray_sum(arr): max_sum = arr[0] current_sum = arr[0]
for num in arr[1:]: current_sum = max(num, current_sum + num) max_sum = max(max_sum, current_sum)
return max_sum
print(max_subarray_sum([-2, 1, -3, 4, -1, 2, 1, -5, 4])) # 6#include <iostream>#include <vector>#include <algorithm>using namespace std;
int maxSubarraySum(vector<int>& arr) { int maxSum = arr[0]; int currentSum = arr[0];
for (size_t i = 1; i < arr.size(); i++) { currentSum = max(arr[i], currentSum + arr[i]); maxSum = max(maxSum, currentSum); }
return maxSum;}
int main() { vector<int> arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4}; cout << maxSubarraySum(arr) << endl; // 6 return 0;}public class Main { static int maxSubarraySum(int[] arr) { int maxSum = arr[0]; int currentSum = arr[0];
for (int i = 1; i < arr.length; i++) { currentSum = Math.max(arr[i], currentSum + arr[i]); maxSum = Math.max(maxSum, currentSum); }
return maxSum; }
public static void main(String[] args) { int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4}; System.out.println(maxSubarraySum(arr)); // 6 }}fun maxSubarraySum(arr: IntArray): Int { var maxSum = arr[0] var currentSum = arr[0]
for (i in 1 until arr.size) { currentSum = maxOf(arr[i], currentSum + arr[i]) maxSum = maxOf(maxSum, currentSum) }
return maxSum}
fun main() { val arr = intArrayOf(-2, 1, -3, 4, -1, 2, 1, -5, 4) println(maxSubarraySum(arr)) // 6}int maxSubarraySum(List<int> arr) { int maxSum = arr[0]; int currentSum = arr[0];
for (int i = 1; i < arr.length; i++) { currentSum = arr[i] > currentSum + arr[i] ? arr[i] : currentSum + arr[i]; maxSum = maxSum > currentSum ? maxSum : currentSum; }
return maxSum;}
void main() { final arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]; print(maxSubarraySum(arr)); // 6}29. Leo cầu thang (Climbing Stairs)
Có n bậc cầu thang, mỗi bước bạn có thể leo 1 hoặc 2 bậc. Đếm số cách khác nhau để leo lên đến bậc thứ n.
Ví dụ:
Input: n=5Output: 8Xem đáp án
def climb_stairs(n): if n <= 2: return n
dp = [0] * (n + 1) dp[1], dp[2] = 1, 2
for i in range(3, n + 1): dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
print(climb_stairs(5)) # 8#include <iostream>#include <vector>using namespace std;
int climbStairs(int n) { if (n <= 2) return n;
vector<int> dp(n + 1); dp[1] = 1; dp[2] = 2;
for (int i = 3; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; }
return dp[n];}
int main() { cout << climbStairs(5) << endl; // 8 return 0;}public class Main { static int climbStairs(int n) { if (n <= 2) return n;
int[] dp = new int[n + 1]; dp[1] = 1; dp[2] = 2;
for (int i = 3; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; }
return dp[n]; }
public static void main(String[] args) { System.out.println(climbStairs(5)); // 8 }}fun climbStairs(n: Int): Int { if (n <= 2) return n
val dp = IntArray(n + 1) dp[1] = 1 dp[2] = 2
for (i in 3..n) { dp[i] = dp[i - 1] + dp[i - 2] }
return dp[n]}
fun main() { println(climbStairs(5)) // 8}int climbStairs(int n) { if (n <= 2) return n;
final dp = List<int>.filled(n + 1, 0); dp[1] = 1; dp[2] = 2;
for (int i = 3; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; }
return dp[n];}
void main() { print(climbStairs(5)); // 8}30. Kẻ trộm nhà (House Robber)
Một tên trộm không thể trộm 2 nhà liền kề nhau. Cho list giá trị tiền ở mỗi nhà, tìm số tiền tối đa có thể trộm được.
Ví dụ:
Input: [2, 7, 9, 3, 1]Output: 12Xem đáp án
def house_robber(nums): if not nums: return 0 if len(nums) == 1: return nums[0]
dp = [0] * len(nums) dp[0] = nums[0] dp[1] = max(nums[0], nums[1])
for i in range(2, len(nums)): dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
return dp[-1]
print(house_robber([2, 7, 9, 3, 1])) # 12 (2 + 9 + 1)#include <iostream>#include <vector>using namespace std;
int houseRobber(vector<int>& nums) { if (nums.empty()) return 0; if (nums.size() == 1) return nums[0];
vector<int> dp(nums.size()); dp[0] = nums[0]; dp[1] = max(nums[0], nums[1]);
for (size_t i = 2; i < nums.size(); i++) { dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]); }
return dp.back();}
int main() { vector<int> nums = {2, 7, 9, 3, 1}; cout << houseRobber(nums) << endl; // 12 return 0;}public class Main { static int houseRobber(int[] nums) { if (nums.length == 0) return 0; if (nums.length == 1) return nums[0];
int[] dp = new int[nums.length]; dp[0] = nums[0]; dp[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < nums.length; i++) { dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]); }
return dp[nums.length - 1]; }
public static void main(String[] args) { int[] nums = {2, 7, 9, 3, 1}; System.out.println(houseRobber(nums)); // 12 }}fun houseRobber(nums: IntArray): Int { if (nums.isEmpty()) return 0 if (nums.size == 1) return nums[0]
val dp = IntArray(nums.size) dp[0] = nums[0] dp[1] = maxOf(nums[0], nums[1])
for (i in 2 until nums.size) { dp[i] = maxOf(dp[i - 1], dp[i - 2] + nums[i]) }
return dp.last()}
fun main() { val nums = intArrayOf(2, 7, 9, 3, 1) println(houseRobber(nums)) // 12}int houseRobber(List<int> nums) { if (nums.isEmpty) return 0; if (nums.length == 1) return nums[0];
final dp = List<int>.filled(nums.length, 0); dp[0] = nums[0]; dp[1] = nums[0] > nums[1] ? nums[0] : nums[1];
for (int i = 2; i < nums.length; i++) { dp[i] = dp[i - 1] > dp[i - 2] + nums[i] ? dp[i - 1] : dp[i - 2] + nums[i]; }
return dp.last;}
void main() { final nums = [2, 7, 9, 3, 1]; print(houseRobber(nums)); // 12}Nhóm 5: Cấu trúc dữ liệu
Phần tiêu đề “Nhóm 5: Cấu trúc dữ liệu”31. Stack (Ngăn xếp)
Cài đặt cấu trúc dữ liệu Stack bằng class, hỗ trợ push, pop, peek, is_empty.
Xem đáp án
class Stack: def __init__(self): self._items = []
def push(self, item): self._items.append(item)
def pop(self): return self._items.pop()
def peek(self): return self._items[-1]
def is_empty(self): return len(self._items) == 0
s = Stack()s.push(1)s.push(2)s.push(3)print(s.pop()) # 3print(s.peek()) # 2print(s.is_empty()) # False#include <iostream>#include <vector>using namespace std;
class Stack {private: vector<int> items;public: void push(int item) { items.push_back(item); } int pop() { int top = items.back(); items.pop_back(); return top; } int peek() { return items.back(); } bool isEmpty() { return items.empty(); }};
int main() { Stack s; s.push(1); s.push(2); s.push(3); cout << s.pop() << endl; // 3 cout << s.peek() << endl; // 2 cout << boolalpha << s.isEmpty() << endl; // false return 0;}import java.util.ArrayList;import java.util.List;
public class Main { static class Stack { private List<Integer> items = new ArrayList<>();
void push(int item) { items.add(item); } int pop() { return items.remove(items.size() - 1); } int peek() { return items.get(items.size() - 1); } boolean isEmpty() { return items.isEmpty(); } }
public static void main(String[] args) { Stack s = new Stack(); s.push(1); s.push(2); s.push(3); System.out.println(s.pop()); // 3 System.out.println(s.peek()); // 2 System.out.println(s.isEmpty()); // false }}class Stack { private val items = mutableListOf<Int>()
fun push(item: Int) = items.add(item) fun pop(): Int = items.removeAt(items.size - 1) fun peek(): Int = items.last() fun isEmpty(): Boolean = items.isEmpty()}
fun main() { val s = Stack() s.push(1) s.push(2) s.push(3) println(s.pop()) // 3 println(s.peek()) // 2 println(s.isEmpty()) // false}class Stack { final List<int> _items = [];
void push(int item) => _items.add(item); int pop() => _items.removeLast(); int peek() => _items.last; bool isEmpty() => _items.isEmpty;}
void main() { final s = Stack(); s.push(1); s.push(2); s.push(3); print(s.pop()); // 3 print(s.peek()); // 2 print(s.isEmpty()); // false}32. Kiểm tra ngoặc hợp lệ (dùng Stack)
Dùng Stack để kiểm tra một chuỗi ngoặc (gồm (), [], {}) có hợp lệ (đóng mở đúng thứ tự) hay không.
Ví dụ:
Input: "({[]})"Output: True
Input: "([)]"Output: FalseXem đáp án
def is_valid_parentheses(s): stack = [] bracket_pairs = {")": "(", "]": "[", "}": "{"}
for char in s: if char in "([{": stack.append(char) elif char in ")]}": if not stack or stack.pop() != bracket_pairs[char]: return False
return len(stack) == 0
print(is_valid_parentheses("({[]})")) # Trueprint(is_valid_parentheses("([)]")) # False#include <iostream>#include <stack>#include <unordered_map>#include <string>using namespace std;
bool isValidParentheses(const string& s) { stack<char> st; unordered_map<char, char> pairs = {{')', '('}, {']', '['}, {'}', '{'}};
for (char c : s) { if (c == '(' || c == '[' || c == '{') { st.push(c); } else if (pairs.count(c)) { if (st.empty() || st.top() != pairs[c]) return false; st.pop(); } }
return st.empty();}
int main() { cout << boolalpha << isValidParentheses("({[]})") << endl; // true cout << boolalpha << isValidParentheses("([)]") << endl; // false return 0;}import java.util.Deque;import java.util.ArrayDeque;import java.util.Map;
public class Main { static boolean isValidParentheses(String s) { Deque<Character> stack = new ArrayDeque<>(); Map<Character, Character> pairs = Map.of(')', '(', ']', '[', '}', '{');
for (char c : s.toCharArray()) { if (c == '(' || c == '[' || c == '{') { stack.push(c); } else if (pairs.containsKey(c)) { if (stack.isEmpty() || stack.pop() != pairs.get(c)) return false; } }
return stack.isEmpty(); }
public static void main(String[] args) { System.out.println(isValidParentheses("({[]})")); // true System.out.println(isValidParentheses("([)]")); // false }}fun isValidParentheses(s: String): Boolean { val stack = ArrayDeque<Char>() val pairs = mapOf(')' to '(', ']' to '[', '}' to '{')
for (c in s) { if (c == '(' || c == '[' || c == '{') { stack.addLast(c) } else if (pairs.containsKey(c)) { if (stack.isEmpty() || stack.removeLast() != pairs[c]) return false } }
return stack.isEmpty()}
fun main() { println(isValidParentheses("({[]})")) // true println(isValidParentheses("([)]")) // false}bool isValidParentheses(String s) { final stack = <String>[]; final pairs = {')': '(', ']': '[', '}': '{'};
for (var c in s.split('')) { if (c == '(' || c == '[' || c == '{') { stack.add(c); } else if (pairs.containsKey(c)) { if (stack.isEmpty || stack.removeLast() != pairs[c]) return false; } }
return stack.isEmpty;}
void main() { print(isValidParentheses("({[]})")); // true print(isValidParentheses("([)]")); // false}33. Queue (Hàng đợi) bằng deque
Cài đặt cấu trúc dữ liệu Queue bằng collections.deque, hỗ trợ enqueue, dequeue.
Xem đáp án
from collections import deque
class Queue: def __init__(self): self._items = deque()
def enqueue(self, item): self._items.append(item)
def dequeue(self): return self._items.popleft()
def is_empty(self): return len(self._items) == 0
q = Queue()q.enqueue("A")q.enqueue("B")q.enqueue("C")print(q.dequeue()) # Aprint(q.dequeue()) # B#include <iostream>#include <deque>#include <string>using namespace std;
class Queue {private: deque<string> items;public: void enqueue(const string& item) { items.push_back(item); } string dequeue() { string front = items.front(); items.pop_front(); return front; } bool isEmpty() { return items.empty(); }};
int main() { Queue q; q.enqueue("A"); q.enqueue("B"); q.enqueue("C"); cout << q.dequeue() << endl; // A cout << q.dequeue() << endl; // B return 0;}import java.util.ArrayDeque;import java.util.Deque;
public class Main { static class Queue { private Deque<String> items = new ArrayDeque<>();
void enqueue(String item) { items.addLast(item); } String dequeue() { return items.pollFirst(); } boolean isEmpty() { return items.isEmpty(); } }
public static void main(String[] args) { Queue q = new Queue(); q.enqueue("A"); q.enqueue("B"); q.enqueue("C"); System.out.println(q.dequeue()); // A System.out.println(q.dequeue()); // B }}import java.util.ArrayDeque
class Queue { private val items = ArrayDeque<String>()
fun enqueue(item: String) = items.addLast(item) fun dequeue(): String = items.removeFirst() fun isEmpty(): Boolean = items.isEmpty()}
fun main() { val q = Queue() q.enqueue("A") q.enqueue("B") q.enqueue("C") println(q.dequeue()) // A println(q.dequeue()) // B}import 'dart:collection';
class Queue2 { final _items = ListQueue<String>();
void enqueue(String item) => _items.addLast(item); String dequeue() => _items.removeFirst(); bool isEmpty() => _items.isEmpty;}
void main() { final q = Queue2(); q.enqueue("A"); q.enqueue("B"); q.enqueue("C"); print(q.dequeue()); // A print(q.dequeue()); // B}34. Linked List đơn giản
Cài đặt Linked List (danh sách liên kết đơn) với các thao tác append và print_list.
Xem đáp án
class Node: def __init__(self, value): self.value = value self.next = None
class LinkedList: def __init__(self): self.head = None
def append(self, value): new_node = Node(value) if self.head is None: self.head = new_node return
current = self.head while current.next: current = current.next current.next = new_node
def print_list(self): current = self.head while current: print(current.value, end=" -> ") current = current.next print("None")
ll = LinkedList()ll.append(1)ll.append(2)ll.append(3)ll.print_list() # 1 -> 2 -> 3 -> None#include <iostream>using namespace std;
struct Node { int value; Node* next; Node(int v) : value(v), next(nullptr) {}};
class LinkedList {private: Node* head = nullptr;public: void append(int value) { Node* newNode = new Node(value); if (head == nullptr) { head = newNode; return; } Node* current = head; while (current->next) current = current->next; current->next = newNode; }
void printList() { Node* current = head; while (current) { cout << current->value << " -> "; current = current->next; } cout << "None" << endl; }};
int main() { LinkedList ll; ll.append(1); ll.append(2); ll.append(3); ll.printList(); // 1 -> 2 -> 3 -> None return 0;}public class Main { static class Node { int value; Node next; Node(int value) { this.value = value; } }
static class LinkedList { Node head;
void append(int value) { Node newNode = new Node(value); if (head == null) { head = newNode; return; } Node current = head; while (current.next != null) current = current.next; current.next = newNode; }
void printList() { Node current = head; StringBuilder sb = new StringBuilder(); while (current != null) { sb.append(current.value).append(" -> "); current = current.next; } sb.append("None"); System.out.println(sb); } }
public static void main(String[] args) { LinkedList ll = new LinkedList(); ll.append(1); ll.append(2); ll.append(3); ll.printList(); // 1 -> 2 -> 3 -> None }}class Node(val value: Int) { var next: Node? = null}
class LinkedList { var head: Node? = null
fun append(value: Int) { val newNode = Node(value) if (head == null) { head = newNode return } var current = head while (current?.next != null) current = current.next current?.next = newNode }
fun printList() { var current = head val sb = StringBuilder() while (current != null) { sb.append(current.value).append(" -> ") current = current.next } sb.append("None") println(sb) }}
fun main() { val ll = LinkedList() ll.append(1) ll.append(2) ll.append(3) ll.printList() // 1 -> 2 -> 3 -> None}class Node { int value; Node? next; Node(this.value);}
class LinkedList { Node? head;
void append(int value) { final newNode = Node(value); if (head == null) { head = newNode; return; } var current = head; while (current!.next != null) current = current.next; current.next = newNode; }
void printList() { var current = head; final sb = StringBuffer(); while (current != null) { sb.write("${current.value} -> "); current = current.next; } sb.write("None"); print(sb.toString()); }}
void main() { final ll = LinkedList(); ll.append(1); ll.append(2); ll.append(3); ll.printList(); // 1 -> 2 -> 3 -> None}35. Đảo ngược Linked List
Viết hàm đảo ngược một Linked List (dùng lại class Node/LinkedList ở bài trước).
Xem đáp án
class Node: def __init__(self, value): self.value = value self.next = None
def reverse_linked_list(head): prev = None current = head
while current: next_node = current.next current.next = prev prev = current current = next_node
return prev
def print_list(head): current = head while current: print(current.value, end=" -> ") current = current.next print("None")
# Tạo list 1 -> 2 -> 3a, b, c = Node(1), Node(2), Node(3)a.next, b.next = b, c
new_head = reverse_linked_list(a)print_list(new_head) # 3 -> 2 -> 1 -> None#include <iostream>using namespace std;
struct Node { int value; Node* next; Node(int v) : value(v), next(nullptr) {}};
Node* reverseLinkedList(Node* head) { Node* prev = nullptr; Node* current = head;
while (current) { Node* nextNode = current->next; current->next = prev; prev = current; current = nextNode; }
return prev;}
void printList(Node* head) { Node* current = head; while (current) { cout << current->value << " -> "; current = current->next; } cout << "None" << endl;}
int main() { // Tao list 1 -> 2 -> 3 Node* a = new Node(1); Node* b = new Node(2); Node* c = new Node(3); a->next = b; b->next = c;
Node* newHead = reverseLinkedList(a); printList(newHead); // 3 -> 2 -> 1 -> None return 0;}public class Main { static class Node { int value; Node next; Node(int value) { this.value = value; } }
static Node reverseLinkedList(Node head) { Node prev = null; Node current = head;
while (current != null) { Node nextNode = current.next; current.next = prev; prev = current; current = nextNode; }
return prev; }
static void printList(Node head) { Node current = head; StringBuilder sb = new StringBuilder(); while (current != null) { sb.append(current.value).append(" -> "); current = current.next; } sb.append("None"); System.out.println(sb); }
public static void main(String[] args) { // Tao list 1 -> 2 -> 3 Node a = new Node(1); Node b = new Node(2); Node c = new Node(3); a.next = b; b.next = c;
Node newHead = reverseLinkedList(a); printList(newHead); // 3 -> 2 -> 1 -> None }}class Node(val value: Int) { var next: Node? = null}
fun reverseLinkedList(head: Node?): Node? { var prev: Node? = null var current = head
while (current != null) { val nextNode = current.next current.next = prev prev = current current = nextNode }
return prev}
fun printList(head: Node?) { var current = head val sb = StringBuilder() while (current != null) { sb.append(current.value).append(" -> ") current = current.next } sb.append("None") println(sb)}
fun main() { // Tao list 1 -> 2 -> 3 val a = Node(1) val b = Node(2) val c = Node(3) a.next = b b.next = c
val newHead = reverseLinkedList(a) printList(newHead) // 3 -> 2 -> 1 -> None}class Node { int value; Node? next; Node(this.value);}
Node? reverseLinkedList(Node? head) { Node? prev; var current = head;
while (current != null) { final nextNode = current.next; current.next = prev; prev = current; current = nextNode; }
return prev;}
void printList(Node? head) { var current = head; final sb = StringBuffer(); while (current != null) { sb.write("${current.value} -> "); current = current.next; } sb.write("None"); print(sb.toString());}
void main() { // Tao list 1 -> 2 -> 3 final a = Node(1); final b = Node(2); final c = Node(3); a.next = b; b.next = c;
final newHead = reverseLinkedList(a); printList(newHead); // 3 -> 2 -> 1 -> None}36. Binary Tree - Duyệt cây
Cài đặt cây nhị phân đơn giản và viết 3 hàm duyệt: preorder, inorder, postorder.
Xem đáp án
class TreeNode: def __init__(self, value, left=None, right=None): self.value = value self.left = left self.right = right
def preorder(node): if node: print(node.value, end=" ") preorder(node.left) preorder(node.right)
def inorder(node): if node: inorder(node.left) print(node.value, end=" ") inorder(node.right)
def postorder(node): if node: postorder(node.left) postorder(node.right) print(node.value, end=" ")
# 1# / \# 2 3root = TreeNode(1, TreeNode(2), TreeNode(3))
preorder(root) # 1 2 3print()inorder(root) # 2 1 3print()postorder(root) # 2 3 1#include <iostream>using namespace std;
struct TreeNode { int value; TreeNode* left; TreeNode* right; TreeNode(int v, TreeNode* l = nullptr, TreeNode* r = nullptr) : value(v), left(l), right(r) {}};
void preorder(TreeNode* node) { if (node) { cout << node->value << " "; preorder(node->left); preorder(node->right); }}
void inorder(TreeNode* node) { if (node) { inorder(node->left); cout << node->value << " "; inorder(node->right); }}
void postorder(TreeNode* node) { if (node) { postorder(node->left); postorder(node->right); cout << node->value << " "; }}
int main() { // 1 // / \ // 2 3 TreeNode* root = new TreeNode(1, new TreeNode(2), new TreeNode(3));
preorder(root); // 1 2 3 cout << endl; inorder(root); // 2 1 3 cout << endl; postorder(root); // 2 3 1 cout << endl; return 0;}public class Main { static class TreeNode { int value; TreeNode left, right; TreeNode(int value, TreeNode left, TreeNode right) { this.value = value; this.left = left; this.right = right; } }
static void preorder(TreeNode node) { if (node != null) { System.out.print(node.value + " "); preorder(node.left); preorder(node.right); } }
static void inorder(TreeNode node) { if (node != null) { inorder(node.left); System.out.print(node.value + " "); inorder(node.right); } }
static void postorder(TreeNode node) { if (node != null) { postorder(node.left); postorder(node.right); System.out.print(node.value + " "); } }
public static void main(String[] args) { // 1 // / \ // 2 3 TreeNode root = new TreeNode(1, new TreeNode(2, null, null), new TreeNode(3, null, null));
preorder(root); // 1 2 3 System.out.println(); inorder(root); // 2 1 3 System.out.println(); postorder(root); // 2 3 1 System.out.println(); }}class TreeNode(val value: Int, val left: TreeNode? = null, val right: TreeNode? = null)
fun preorder(node: TreeNode?) { if (node != null) { print("${node.value} ") preorder(node.left) preorder(node.right) }}
fun inorder(node: TreeNode?) { if (node != null) { inorder(node.left) print("${node.value} ") inorder(node.right) }}
fun postorder(node: TreeNode?) { if (node != null) { postorder(node.left) postorder(node.right) print("${node.value} ") }}
fun main() { // 1 // / \ // 2 3 val root = TreeNode(1, TreeNode(2), TreeNode(3))
preorder(root) // 1 2 3 println() inorder(root) // 2 1 3 println() postorder(root) // 2 3 1 println()}import 'dart:io';
class TreeNode { int value; TreeNode? left; TreeNode? right; TreeNode(this.value, [this.left, this.right]);}
void preorder(TreeNode? node) { if (node != null) { stdout.write("${node.value} "); preorder(node.left); preorder(node.right); }}
void inorder(TreeNode? node) { if (node != null) { inorder(node.left); stdout.write("${node.value} "); inorder(node.right); }}
void postorder(TreeNode? node) { if (node != null) { postorder(node.left); postorder(node.right); stdout.write("${node.value} "); }}
void main() { // 1 // / \ // 2 3 final root = TreeNode(1, TreeNode(2), TreeNode(3));
preorder(root); // 1 2 3 print(""); inorder(root); // 2 1 3 print(""); postorder(root); // 2 3 1 print("");}37. Tính chiều cao cây nhị phân
Viết hàm đệ quy tính chiều cao (số tầng) của một cây nhị phân.
Ví dụ: cây 1 có con trái 2 (con trái là 4) và con phải 3.
Output: 3Xem đáp án
class TreeNode: def __init__(self, value, left=None, right=None): self.value = value self.left = left self.right = right
def height(node): if node is None: return 0 return 1 + max(height(node.left), height(node.right))
root = TreeNode(1, TreeNode(2, TreeNode(4)), TreeNode(3))print(height(root)) # 3#include <iostream>#include <algorithm>using namespace std;
struct TreeNode { int value; TreeNode* left; TreeNode* right; TreeNode(int v, TreeNode* l = nullptr, TreeNode* r = nullptr) : value(v), left(l), right(r) {}};
int height(TreeNode* node) { if (node == nullptr) return 0; return 1 + max(height(node->left), height(node->right));}
int main() { TreeNode* root = new TreeNode(1, new TreeNode(2, new TreeNode(4)), new TreeNode(3)); cout << height(root) << endl; // 3 return 0;}public class Main { static class TreeNode { int value; TreeNode left, right; TreeNode(int value, TreeNode left, TreeNode right) { this.value = value; this.left = left; this.right = right; } }
static int height(TreeNode node) { if (node == null) return 0; return 1 + Math.max(height(node.left), height(node.right)); }
public static void main(String[] args) { TreeNode root = new TreeNode(1, new TreeNode(2, new TreeNode(4, null, null), null), new TreeNode(3, null, null)); System.out.println(height(root)); // 3 }}class TreeNode(val value: Int, val left: TreeNode? = null, val right: TreeNode? = null)
fun height(node: TreeNode?): Int { if (node == null) return 0 return 1 + maxOf(height(node.left), height(node.right))}
fun main() { val root = TreeNode(1, TreeNode(2, TreeNode(4)), TreeNode(3)) println(height(root)) // 3}class TreeNode { int value; TreeNode? left; TreeNode? right; TreeNode(this.value, [this.left, this.right]);}
int height(TreeNode? node) { if (node == null) return 0; final leftH = height(node.left); final rightH = height(node.right); return 1 + (leftH > rightH ? leftH : rightH);}
void main() { final root = TreeNode(1, TreeNode(2, TreeNode(4)), TreeNode(3)); print(height(root)); // 3}38. Kiểm tra cây đối xứng (Symmetric Tree)
Kiểm tra một cây nhị phân có đối xứng qua trục dọc hay không.
Ví dụ: cây gốc 1, con trái 2 (con trái 3, con phải 4), con phải 2 (con trái 4, con phải 3).
Output: TrueXem đáp án
class TreeNode: def __init__(self, value, left=None, right=None): self.value = value self.left = left self.right = right
def is_mirror(t1, t2): if t1 is None and t2 is None: return True if t1 is None or t2 is None: return False return (t1.value == t2.value and is_mirror(t1.left, t2.right) and is_mirror(t1.right, t2.left))
def is_symmetric(root): if root is None: return True return is_mirror(root.left, root.right)
root = TreeNode(1, TreeNode(2, TreeNode(3), TreeNode(4)), TreeNode(2, TreeNode(4), TreeNode(3)))print(is_symmetric(root)) # True#include <iostream>using namespace std;
struct TreeNode { int value; TreeNode* left; TreeNode* right; TreeNode(int v, TreeNode* l = nullptr, TreeNode* r = nullptr) : value(v), left(l), right(r) {}};
bool isMirror(TreeNode* t1, TreeNode* t2) { if (t1 == nullptr && t2 == nullptr) return true; if (t1 == nullptr || t2 == nullptr) return false; return t1->value == t2->value && isMirror(t1->left, t2->right) && isMirror(t1->right, t2->left);}
bool isSymmetric(TreeNode* root) { if (root == nullptr) return true; return isMirror(root->left, root->right);}
int main() { TreeNode* root = new TreeNode(1, new TreeNode(2, new TreeNode(3), new TreeNode(4)), new TreeNode(2, new TreeNode(4), new TreeNode(3))); cout << boolalpha << isSymmetric(root) << endl; // true return 0;}public class Main { static class TreeNode { int value; TreeNode left, right; TreeNode(int value, TreeNode left, TreeNode right) { this.value = value; this.left = left; this.right = right; } }
static boolean isMirror(TreeNode t1, TreeNode t2) { if (t1 == null && t2 == null) return true; if (t1 == null || t2 == null) return false; return t1.value == t2.value && isMirror(t1.left, t2.right) && isMirror(t1.right, t2.left); }
static boolean isSymmetric(TreeNode root) { if (root == null) return true; return isMirror(root.left, root.right); }
public static void main(String[] args) { TreeNode root = new TreeNode(1, new TreeNode(2, new TreeNode(3, null, null), new TreeNode(4, null, null)), new TreeNode(2, new TreeNode(4, null, null), new TreeNode(3, null, null))); System.out.println(isSymmetric(root)); // true }}class TreeNode(val value: Int, val left: TreeNode? = null, val right: TreeNode? = null)
fun isMirror(t1: TreeNode?, t2: TreeNode?): Boolean { if (t1 == null && t2 == null) return true if (t1 == null || t2 == null) return false return t1.value == t2.value && isMirror(t1.left, t2.right) && isMirror(t1.right, t2.left)}
fun isSymmetric(root: TreeNode?): Boolean { if (root == null) return true return isMirror(root.left, root.right)}
fun main() { val root = TreeNode(1, TreeNode(2, TreeNode(3), TreeNode(4)), TreeNode(2, TreeNode(4), TreeNode(3))) println(isSymmetric(root)) // true}class TreeNode { int value; TreeNode? left; TreeNode? right; TreeNode(this.value, [this.left, this.right]);}
bool isMirror(TreeNode? t1, TreeNode? t2) { if (t1 == null && t2 == null) return true; if (t1 == null || t2 == null) return false; return t1.value == t2.value && isMirror(t1.left, t2.right) && isMirror(t1.right, t2.left);}
bool isSymmetric(TreeNode? root) { if (root == null) return true; return isMirror(root.left, root.right);}
void main() { final root = TreeNode(1, TreeNode(2, TreeNode(3), TreeNode(4)), TreeNode(2, TreeNode(4), TreeNode(3))); print(isSymmetric(root)); // true}39. Duyệt cây theo tầng (Level Order / BFS)
Duyệt cây nhị phân theo từng tầng, in ra danh sách giá trị của mỗi tầng.
Ví dụ: cây gốc 3, con trái 9, con phải 20 (con trái 15, con phải 7).
Output: [[3], [9, 20], [15, 7]]Xem đáp án
from collections import deque
class TreeNode: def __init__(self, value, left=None, right=None): self.value = value self.left = left self.right = right
def level_order(root): if root is None: return []
result = [] queue = deque([root])
while queue: count_items = len(queue) current_level = []
for _ in range(count_items): node = queue.popleft() current_level.append(node.value)
if node.left: queue.append(node.left) if node.right: queue.append(node.right)
result.append(current_level)
return result
root = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))print(level_order(root)) # [[3], [9, 20], [15, 7]]#include <iostream>#include <vector>#include <deque>using namespace std;
struct TreeNode { int value; TreeNode* left; TreeNode* right; TreeNode(int v, TreeNode* l = nullptr, TreeNode* r = nullptr) : value(v), left(l), right(r) {}};
vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int>> result; if (root == nullptr) return result;
deque<TreeNode*> queue = {root};
while (!queue.empty()) { int countItems = queue.size(); vector<int> currentLevel;
for (int i = 0; i < countItems; i++) { TreeNode* node = queue.front(); queue.pop_front(); currentLevel.push_back(node->value);
if (node->left) queue.push_back(node->left); if (node->right) queue.push_back(node->right); }
result.push_back(currentLevel); }
return result;}
int main() { TreeNode* root = new TreeNode(3, new TreeNode(9), new TreeNode(20, new TreeNode(15), new TreeNode(7))); auto result = levelOrder(root); for (auto& level : result) { cout << "["; for (size_t i = 0; i < level.size(); i++) { cout << level[i]; if (i + 1 < level.size()) cout << ", "; } cout << "] "; } cout << endl; // [3] [9, 20] [15, 7] return 0;}import java.util.*;
public class Main { static class TreeNode { int value; TreeNode left, right; TreeNode(int value, TreeNode left, TreeNode right) { this.value = value; this.left = left; this.right = right; } }
static List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> result = new ArrayList<>(); if (root == null) return result;
Deque<TreeNode> queue = new ArrayDeque<>(); queue.add(root);
while (!queue.isEmpty()) { int countItems = queue.size(); List<Integer> currentLevel = new ArrayList<>();
for (int i = 0; i < countItems; i++) { TreeNode node = queue.poll(); currentLevel.add(node.value);
if (node.left != null) queue.add(node.left); if (node.right != null) queue.add(node.right); }
result.add(currentLevel); }
return result; }
public static void main(String[] args) { TreeNode root = new TreeNode(3, new TreeNode(9, null, null), new TreeNode(20, new TreeNode(15, null, null), new TreeNode(7, null, null))); System.out.println(levelOrder(root)); // [[3], [9, 20], [15, 7]] }}import java.util.ArrayDeque
class TreeNode(val value: Int, val left: TreeNode? = null, val right: TreeNode? = null)
fun levelOrder(root: TreeNode?): List<List<Int>> { val result = mutableListOf<List<Int>>() if (root == null) return result
val queue = ArrayDeque<TreeNode>() queue.add(root)
while (queue.isNotEmpty()) { val countItems = queue.size val currentLevel = mutableListOf<Int>()
repeat(countItems) { val node = queue.poll() currentLevel.add(node.value)
node.left?.let { queue.add(it) } node.right?.let { queue.add(it) } }
result.add(currentLevel) }
return result}
fun main() { val root = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7))) println(levelOrder(root)) // [[3], [9, 20], [15, 7]]}import 'dart:collection';
class TreeNode { int value; TreeNode? left; TreeNode? right; TreeNode(this.value, [this.left, this.right]);}
List<List<int>> levelOrder(TreeNode? root) { final result = <List<int>>[]; if (root == null) return result;
final queue = ListQueue<TreeNode>()..add(root);
while (queue.isNotEmpty) { final countItems = queue.length; final currentLevel = <int>[];
for (int i = 0; i < countItems; i++) { final node = queue.removeFirst(); currentLevel.add(node.value);
if (node.left != null) queue.add(node.left!); if (node.right != null) queue.add(node.right!); }
result.add(currentLevel); }
return result;}
void main() { final root = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7))); print(levelOrder(root)); // [[3], [9, 20], [15, 7]]}40. Binary Search Tree - Thêm và tìm kiếm
Cài đặt cây tìm kiếm nhị phân (BST) với thao tác insert và search.
Ví dụ:
Input: insert [50, 30, 70, 20, 40, 60, 80] rồi search(40)Output: True
Input: search(100)Output: FalseXem đáp án
class BSTNode: def __init__(self, value): self.value = value self.left = None self.right = None
def insert(root, value): if root is None: return BSTNode(value)
if value < root.value: root.left = insert(root.left, value) else: root.right = insert(root.right, value)
return root
def search(root, value): if root is None: return False if root.value == value: return True if value < root.value: return search(root.left, value) return search(root.right, value)
root = Nonefor num in [50, 30, 70, 20, 40, 60, 80]: root = insert(root, num)
print(search(root, 40)) # Trueprint(search(root, 100)) # False#include <iostream>#include <vector>using namespace std;
struct BSTNode { int value; BSTNode* left; BSTNode* right; BSTNode(int v) : value(v), left(nullptr), right(nullptr) {}};
BSTNode* insert(BSTNode* root, int value) { if (root == nullptr) return new BSTNode(value);
if (value < root->value) root->left = insert(root->left, value); else root->right = insert(root->right, value);
return root;}
bool search(BSTNode* root, int value) { if (root == nullptr) return false; if (root->value == value) return true; if (value < root->value) return search(root->left, value); return search(root->right, value);}
int main() { BSTNode* root = nullptr; for (int num : {50, 30, 70, 20, 40, 60, 80}) { root = insert(root, num); }
cout << boolalpha << search(root, 40) << endl; // true cout << boolalpha << search(root, 100) << endl; // false return 0;}public class Main { static class BSTNode { int value; BSTNode left, right; BSTNode(int value) { this.value = value; } }
static BSTNode insert(BSTNode root, int value) { if (root == null) return new BSTNode(value);
if (value < root.value) root.left = insert(root.left, value); else root.right = insert(root.right, value);
return root; }
static boolean search(BSTNode root, int value) { if (root == null) return false; if (root.value == value) return true; if (value < root.value) return search(root.left, value); return search(root.right, value); }
public static void main(String[] args) { BSTNode root = null; for (int num : new int[]{50, 30, 70, 20, 40, 60, 80}) { root = insert(root, num); }
System.out.println(search(root, 40)); // true System.out.println(search(root, 100)); // false }}class BSTNode(val value: Int) { var left: BSTNode? = null var right: BSTNode? = null}
fun insert(root: BSTNode?, value: Int): BSTNode { if (root == null) return BSTNode(value)
if (value < root.value) root.left = insert(root.left, value) else root.right = insert(root.right, value)
return root}
fun search(root: BSTNode?, value: Int): Boolean { if (root == null) return false if (root.value == value) return true return if (value < root.value) search(root.left, value) else search(root.right, value)}
fun main() { var root: BSTNode? = null for (num in intArrayOf(50, 30, 70, 20, 40, 60, 80)) { root = insert(root, num) }
println(search(root, 40)) // true println(search(root, 100)) // false}class BSTNode { int value; BSTNode? left; BSTNode? right; BSTNode(this.value);}
BSTNode insert(BSTNode? root, int value) { if (root == null) return BSTNode(value);
if (value < root.value) { root.left = insert(root.left, value); } else { root.right = insert(root.right, value); }
return root;}
bool search(BSTNode? root, int value) { if (root == null) return false; if (root.value == value) return true; return value < root.value ? search(root.left, value) : search(root.right, value);}
void main() { BSTNode? root; for (var num in [50, 30, 70, 20, 40, 60, 80]) { root = insert(root, num); }
print(search(root, 40)); // true print(search(root, 100)); // false}Nhóm 6: Lập trình hướng đối tượng (OOP) nâng cao
Phần tiêu đề “Nhóm 6: Lập trình hướng đối tượng (OOP) nâng cao”Xem thêm lý thuyết: Classes và Objects, Kế thừa (Inheritance), Đa hình (Polymorphism), Đóng gói (Encapsulation), Special Methods (Magic Methods), Constructor và Methods.
41. Kế thừa (Inheritance)
Viết class Animal với phương thức speak(), sau đó viết class Dog và Cat kế thừa từ Animal và ghi đè (override) phương thức speak().
Xem đáp án
class Animal: def __init__(self, name): self.name = name
def speak(self): return f"{self.name} phát ra âm thanh"
class Dog(Animal): def speak(self): return f"{self.name} sủa: Gâu gâu!"
class Cat(Animal): def speak(self): return f"{self.name} kêu: Meo meo!"
animals = [Dog("Milu"), Cat("Mimi")]for a in animals: print(a.speak())#include <iostream>#include <vector>#include <string>using namespace std;
class Animal {protected: string name;public: Animal(string name) : name(name) {} virtual string speak() { return name + " phat ra am thanh"; } virtual ~Animal() = default;};
class Dog : public Animal {public: Dog(string name) : Animal(name) {} string speak() override { return name + " sua: Gau gau!"; }};
class Cat : public Animal {public: Cat(string name) : Animal(name) {} string speak() override { return name + " keu: Meo meo!"; }};
int main() { vector<Animal*> animals = {new Dog("Milu"), new Cat("Mimi")}; for (auto* a : animals) cout << a->speak() << endl; return 0;}import java.util.List;
public class Main { static class Animal { protected String name; Animal(String name) { this.name = name; } String speak() { return name + " phat ra am thanh"; } }
static class Dog extends Animal { Dog(String name) { super(name); } @Override String speak() { return name + " sua: Gau gau!"; } }
static class Cat extends Animal { Cat(String name) { super(name); } @Override String speak() { return name + " keu: Meo meo!"; } }
public static void main(String[] args) { List<Animal> animals = List.of(new Dog("Milu"), new Cat("Mimi")); for (Animal a : animals) System.out.println(a.speak()); }}open class Animal(val name: String) { open fun speak(): String = "$name phat ra am thanh"}
class Dog(name: String) : Animal(name) { override fun speak(): String = "$name sua: Gau gau!"}
class Cat(name: String) : Animal(name) { override fun speak(): String = "$name keu: Meo meo!"}
fun main() { val animals = listOf(Dog("Milu"), Cat("Mimi")) for (a in animals) println(a.speak())}class Animal { String name; Animal(this.name); String speak() => "$name phat ra am thanh";}
class Dog extends Animal { Dog(super.name); @override String speak() => "$name sua: Gau gau!";}
class Cat extends Animal { Cat(super.name); @override String speak() => "$name keu: Meo meo!";}
void main() { final animals = [Dog("Milu"), Cat("Mimi")]; for (var a in animals) print(a.speak());}42. Đa hình (Polymorphism)
Viết một hàm calculate_area(shape) nhận vào các đối tượng hình học khác nhau (Square, Circle) và gọi đúng phương thức area() tương ứng nhờ đa hình.
Xem đáp án
import math
class Square: def __init__(self, side): self.side = side
def area(self): return self.side ** 2
class Circle: def __init__(self, radius): self.radius = radius
def area(self): return math.pi * self.radius ** 2
def calculate_area(shape): return shape.area()
for shape in [Square(4), Circle(3)]: print(round(calculate_area(shape), 2))#include <iostream>#include <vector>#include <cmath>#include <iomanip>using namespace std;
class Shape {public: virtual double area() = 0; virtual ~Shape() = default;};
class Square : public Shape { double side;public: Square(double side) : side(side) {} double area() override { return side * side; }};
class Circle : public Shape { double radius;public: Circle(double radius) : radius(radius) {} double area() override { return M_PI * radius * radius; }};
double calculateArea(Shape* shape) { return shape->area();}
int main() { vector<Shape*> shapes = {new Square(4), new Circle(3)}; cout << fixed << setprecision(2); for (auto* shape : shapes) cout << calculateArea(shape) << endl; return 0;}import java.util.List;
public class Main { interface Shape { double area(); }
static class Square implements Shape { double side; Square(double side) { this.side = side; } public double area() { return side * side; } }
static class Circle implements Shape { double radius; Circle(double radius) { this.radius = radius; } public double area() { return Math.PI * radius * radius; } }
static double calculateArea(Shape shape) { return shape.area(); }
public static void main(String[] args) { List<Shape> shapes = List.of(new Square(4), new Circle(3)); for (Shape shape : shapes) { System.out.println(Math.round(calculateArea(shape) * 100.0) / 100.0); } }}import kotlin.math.PIimport kotlin.math.round
interface Shape { fun area(): Double}
class Square(val side: Double) : Shape { override fun area(): Double = side * side}
class Circle(val radius: Double) : Shape { override fun area(): Double = PI * radius * radius}
fun calculateArea(shape: Shape): Double = shape.area()
fun main() { val shapes = listOf(Square(4.0), Circle(3.0)) for (shape in shapes) { println(round(calculateArea(shape) * 100) / 100) }}import 'dart:math';
abstract class Shape { double area();}
class Square extends Shape { double side; Square(this.side); @override double area() => side * side;}
class Circle extends Shape { double radius; Circle(this.radius); @override double area() => pi * radius * radius;}
double calculateArea(Shape shape) => shape.area();
void main() { final shapes = [Square(4), Circle(3)]; for (var shape in shapes) { print((calculateArea(shape) * 100).round() / 100); }}43. Encapsulation (property, getter/setter)
Viết class BankAccount với thuộc tính _balance được bảo vệ, dùng @property để đọc và @balance.setter để kiểm tra không cho set số dư âm.
Xem đáp án
class BankAccount: def __init__(self, initial_balance): self._balance = initial_balance
@property def balance(self): return self._balance
@balance.setter def balance(self, value): if value < 0: raise ValueError("Số dư không thể âm") self._balance = value
account = BankAccount(100)print(account.balance) # 100account.balance = 200print(account.balance) # 200
try: account.balance = -50except ValueError as e: print("Lỗi:", e)#include <iostream>#include <stdexcept>using namespace std;
class BankAccount {private: double balance_;public: BankAccount(double initialBalance) : balance_(initialBalance) {}
double getBalance() { return balance_; }
void setBalance(double value) { if (value < 0) throw invalid_argument("So du khong the am"); balance_ = value; }};
int main() { BankAccount account(100); cout << account.getBalance() << endl; // 100 account.setBalance(200); cout << account.getBalance() << endl; // 200
try { account.setBalance(-50); } catch (const invalid_argument& e) { cout << "Loi: " << e.what() << endl; } return 0;}public class Main { static class BankAccount { private double balance;
BankAccount(double initialBalance) { this.balance = initialBalance; }
double getBalance() { return balance; }
void setBalance(double value) { if (value < 0) throw new IllegalArgumentException("So du khong the am"); balance = value; } }
public static void main(String[] args) { BankAccount account = new BankAccount(100); System.out.println(account.getBalance()); // 100 account.setBalance(200); System.out.println(account.getBalance()); // 200
try { account.setBalance(-50); } catch (IllegalArgumentException e) { System.out.println("Loi: " + e.getMessage()); } }}class BankAccount(initialBalance: Double) { var balance: Double = initialBalance set(value) { if (value < 0) throw IllegalArgumentException("So du khong the am") field = value }}
fun main() { val account = BankAccount(100.0) println(account.balance) // 100.0 account.balance = 200.0 println(account.balance) // 200.0
try { account.balance = -50.0 } catch (e: IllegalArgumentException) { println("Loi: ${e.message}") }}class BankAccount { double _balance; BankAccount(this._balance);
double get balance => _balance;
set balance(double value) { if (value < 0) throw ArgumentError("So du khong the am"); _balance = value; }}
void main() { final account = BankAccount(100); print(account.balance); // 100 account.balance = 200; print(account.balance); // 200
try { account.balance = -50; } catch (e) { print("Loi: $e"); }}44. Static Method và Class Method
Viết class MathUtils có 1 @staticmethod tính bình phương và 1 @classmethod tạo đối tượng Point từ chuỗi "x,y".
Xem đáp án
class MathUtils: @staticmethod def square(x): return x ** 2
class Point: def __init__(self, x, y): self.x = x self.y = y
@classmethod def from_string(cls, text): x, y = text.split(",") return cls(int(x), int(y))
def __repr__(self): return f"Point({self.x}, {self.y})"
print(MathUtils.square(5)) # 25
d = Point.from_string("3,4")print(d) # Point(3, 4)#include <iostream>#include <sstream>#include <string>using namespace std;
class MathUtils {public: static int square(int x) { return x * x; }};
class Point {public: int x, y; Point(int x, int y) : x(x), y(y) {}
static Point fromString(const string& text) { stringstream ss(text); string xs, ys; getline(ss, xs, ','); getline(ss, ys, ','); return Point(stoi(xs), stoi(ys)); }
friend ostream& operator<<(ostream& os, const Point& p) { return os << "Point(" << p.x << ", " << p.y << ")"; }};
int main() { cout << MathUtils::square(5) << endl; // 25
Point d = Point::fromString("3,4"); cout << d << endl; // Point(3, 4) return 0;}public class Main { static class MathUtils { static int square(int x) { return x * x; } }
static class Point { int x, y; Point(int x, int y) { this.x = x; this.y = y; }
static Point fromString(String text) { String[] parts = text.split(","); return new Point(Integer.parseInt(parts[0]), Integer.parseInt(parts[1])); }
@Override public String toString() { return "Point(" + x + ", " + y + ")"; } }
public static void main(String[] args) { System.out.println(MathUtils.square(5)); // 25
Point d = Point.fromString("3,4"); System.out.println(d); // Point(3, 4) }}object MathUtils { fun square(x: Int): Int = x * x}
class Point(val x: Int, val y: Int) { companion object { fun fromString(text: String): Point { val (x, y) = text.split(",") return Point(x.toInt(), y.toInt()) } }
override fun toString(): String = "Point($x, $y)"}
fun main() { println(MathUtils.square(5)) // 25
val d = Point.fromString("3,4") println(d) // Point(3, 4)}class MathUtils { static int square(int x) => x * x;}
class Point { int x, y; Point(this.x, this.y);
factory Point.fromString(String text) { final parts = text.split(","); return Point(int.parse(parts[0]), int.parse(parts[1])); }
@override String toString() => "Point($x, $y)";}
void main() { print(MathUtils.square(5)); // 25
final d = Point.fromString("3,4"); print(d); // Point(3, 4)}45. __str__ và __repr__
Viết class Product với __str__ (hiển thị thân thiện cho người dùng) và __repr__ (hiển thị cho lập trình viên/debug).
Xem đáp án
class Product: def __init__(self, name, price): self.name = name self.price = price
def __str__(self): return f"{self.name}: {self.price:,}đ"
def __repr__(self): return f"Product(name={self.name!r}, price={self.price})"
product = Product("Laptop", 15000000)print(str(product)) # Laptop: 15,000,000đprint(repr(product)) # Product(name='Laptop', price=15000000)#include <iostream>#include <string>#include <locale>using namespace std;
class Product {public: string name; long price; Product(string name, long price) : name(name), price(price) {}
string toDisplayString() const { string numStr = to_string(price); string result; int count = 0; for (int i = numStr.size() - 1; i >= 0; i--) { result = numStr[i] + result; count++; if (count % 3 == 0 && i != 0) result = "," + result; } return name + ": " + result + "d"; }
string toDebugString() const { return "Product(name=\"" + name + "\", price=" + to_string(price) + ")"; }};
int main() { Product product("Laptop", 15000000); cout << product.toDisplayString() << endl; // Laptop: 15,000,000d cout << product.toDebugString() << endl; // Product(name="Laptop", price=15000000) return 0;}public class Main { static class Product { String name; long price; Product(String name, long price) { this.name = name; this.price = price; }
@Override public String toString() { return name + ": " + String.format("%,d", price) + "d"; }
String toDebugString() { return "Product(name=" + name + ", price=" + price + ")"; } }
public static void main(String[] args) { Product product = new Product("Laptop", 15000000); System.out.println(product.toString()); // Laptop: 15,000,000d System.out.println(product.toDebugString()); // Product(name=Laptop, price=15000000) }}class Product(val name: String, val price: Long) { override fun toString(): String { return "$name: ${"%,d".format(price)}d" }
fun toDebugString(): String { return "Product(name=$name, price=$price)" }}
fun main() { val product = Product("Laptop", 15000000) println(product.toString()) // Laptop: 15,000,000d println(product.toDebugString()) // Product(name=Laptop, price=15000000)}class Product { String name; int price; Product(this.name, this.price);
@override String toString() { final formatted = price.toString().replaceAllMapped( RegExp(r'\B(?=(\d{3})+(?!\d))'), (m) => ','); return "$name: ${formatted}d"; }
String toDebugString() => "Product(name=$name, price=$price)";}
void main() { final product = Product("Laptop", 15000000); print(product.toString()); // Laptop: 15,000,000d print(product.toDebugString()); // Product(name=Laptop, price=15000000)}46. Nạp chồng toán tử (Operator Overloading)
Viết class Vector2D biểu diễn vector 2 chiều, nạp chồng toán tử +, - và ==.
Xem đáp án
class Vector2D: def __init__(self, x, y): self.x = x self.y = y
def __add__(self, other): return Vector2D(self.x + other.x, self.y + other.y)
def __sub__(self, other): return Vector2D(self.x - other.x, self.y - other.y)
def __eq__(self, other): return self.x == other.x and self.y == other.y
def __repr__(self): return f"Vector2D({self.x}, {self.y})"
v1 = Vector2D(1, 2)v2 = Vector2D(3, 4)print(v1 + v2) # Vector2D(4, 6)print(v1 - v2) # Vector2D(-2, -2)print(v1 == Vector2D(1, 2)) # True#include <iostream>using namespace std;
class Vector2D {public: int x, y; Vector2D(int x, int y) : x(x), y(y) {}
Vector2D operator+(const Vector2D& other) const { return Vector2D(x + other.x, y + other.y); }
Vector2D operator-(const Vector2D& other) const { return Vector2D(x - other.x, y - other.y); }
bool operator==(const Vector2D& other) const { return x == other.x && y == other.y; }
friend ostream& operator<<(ostream& os, const Vector2D& v) { return os << "Vector2D(" << v.x << ", " << v.y << ")"; }};
int main() { Vector2D v1(1, 2); Vector2D v2(3, 4); cout << (v1 + v2) << endl; // Vector2D(4, 6) cout << (v1 - v2) << endl; // Vector2D(-2, -2) cout << boolalpha << (v1 == Vector2D(1, 2)) << endl; // true return 0;}import java.util.Objects;
public class Main { static class Vector2D { int x, y; Vector2D(int x, int y) { this.x = x; this.y = y; }
Vector2D add(Vector2D other) { return new Vector2D(x + other.x, y + other.y); } Vector2D subtract(Vector2D other) { return new Vector2D(x - other.x, y - other.y); }
@Override public boolean equals(Object obj) { if (!(obj instanceof Vector2D)) return false; Vector2D other = (Vector2D) obj; return x == other.x && y == other.y; }
@Override public int hashCode() { return Objects.hash(x, y); }
@Override public String toString() { return "Vector2D(" + x + ", " + y + ")"; } }
public static void main(String[] args) { Vector2D v1 = new Vector2D(1, 2); Vector2D v2 = new Vector2D(3, 4); System.out.println(v1.add(v2)); // Vector2D(4, 6) System.out.println(v1.subtract(v2)); // Vector2D(-2, -2) System.out.println(v1.equals(new Vector2D(1, 2))); // true }}data class Vector2D(val x: Int, val y: Int) { operator fun plus(other: Vector2D) = Vector2D(x + other.x, y + other.y) operator fun minus(other: Vector2D) = Vector2D(x - other.x, y - other.y)}
fun main() { val v1 = Vector2D(1, 2) val v2 = Vector2D(3, 4) println(v1 + v2) // Vector2D(x=4, y=6) println(v1 - v2) // Vector2D(x=-2, y=-2) println(v1 == Vector2D(1, 2)) // true}class Vector2D { int x, y; Vector2D(this.x, this.y);
Vector2D operator +(Vector2D other) => Vector2D(x + other.x, y + other.y); Vector2D operator -(Vector2D other) => Vector2D(x - other.x, y - other.y);
@override bool operator ==(Object other) => other is Vector2D && x == other.x && y == other.y;
@override int get hashCode => Object.hash(x, y);
@override String toString() => "Vector2D($x, $y)";}
void main() { final v1 = Vector2D(1, 2); final v2 = Vector2D(3, 4); print(v1 + v2); // Vector2D(4, 6) print(v1 - v2); // Vector2D(-2, -2) print(v1 == Vector2D(1, 2)); // true}47. Abstract Base Class
Dùng module abc để tạo class trừu tượng Shape với phương thức trừu tượng perimeter(), ép các class con phải cài đặt phương thức này.
Xem đáp án
from abc import ABC, abstractmethod
class Shape(ABC): @abstractmethod def perimeter(self): pass
class Rectangle(Shape): def __init__(self, length, width): self.length = length self.width = width
def perimeter(self): return 2 * (self.length + self.width)
rect = Rectangle(4, 5)print(rect.perimeter()) # 18
try: shape = Shape() # Không thể khởi tạo class trừu tượngexcept TypeError as e: print("Lỗi:", e)#include <iostream>using namespace std;
class Shape {public: virtual double perimeter() = 0; // phuong thuc thuan ao virtual ~Shape() = default;};
class Rectangle : public Shape { double length, width;public: Rectangle(double length, double width) : length(length), width(width) {} double perimeter() override { return 2 * (length + width); }};
int main() { Rectangle rect(4, 5); cout << rect.perimeter() << endl; // 18
// Shape shape; // loi bien dich: khong the khoi tao class truu tuong cout << "Loi: khong the khoi tao class truu tuong Shape" << endl; return 0;}public class Main { static abstract class Shape { abstract double perimeter(); }
static class Rectangle extends Shape { double length, width; Rectangle(double length, double width) { this.length = length; this.width = width; }
@Override double perimeter() { return 2 * (length + width); } }
public static void main(String[] args) { Rectangle rect = new Rectangle(4, 5); System.out.println(rect.perimeter()); // 18
// Shape shape = new Shape() {}; // loi bien dich neu khong cai dat perimeter() System.out.println("Loi: khong the khoi tao class truu tuong Shape"); }}abstract class Shape { abstract fun perimeter(): Double}
class Rectangle(val length: Double, val width: Double) : Shape() { override fun perimeter(): Double = 2 * (length + width)}
fun main() { val rect = Rectangle(4.0, 5.0) println(rect.perimeter()) // 18.0
// val shape = Shape() // loi bien dich: khong the khoi tao class truu tuong println("Loi: khong the khoi tao class truu tuong Shape")}abstract class Shape { double perimeter();}
class Rectangle extends Shape { double length, width; Rectangle(this.length, this.width);
@override double perimeter() => 2 * (length + width);}
void main() { final rect = Rectangle(4, 5); print(rect.perimeter()); // 18.0
// final shape = Shape(); // loi bien dich: khong the khoi tao class truu tuong print("Loi: khong the khoi tao class truu tuong Shape");}48. Dataclass
Dùng @dataclass để viết class Employee gọn hơn, tự động có __init__, __repr__ và __eq__.
Xem đáp án
from dataclasses import dataclass
@dataclassclass Employee: name: str age: int luong: float = 0.0
nv1 = Employee("An", 25, 15000000)nv2 = Employee("An", 25, 15000000)
print(nv1) # Employee(name='An', age=25, luong=15000000)print(nv1 == nv2) # True (dataclass tự sinh __eq__)#include <iostream>#include <string>using namespace std;
struct Employee { string name; int age; double luong = 0.0;
bool operator==(const Employee& other) const { return name == other.name && age == other.age && luong == other.luong; }
friend ostream& operator<<(ostream& os, const Employee& e) { return os << "Employee(name=" << e.name << ", age=" << e.age << ", luong=" << e.luong << ")"; }};
int main() { Employee nv1{"An", 25, 15000000}; Employee nv2{"An", 25, 15000000};
cout << nv1 << endl; // Employee(name=An, age=25, luong=1.5e+07) cout << boolalpha << (nv1 == nv2) << endl; // true return 0;}import java.util.Objects;
public class Main { record Employee(String name, int age, double luong) {}
public static void main(String[] args) { Employee nv1 = new Employee("An", 25, 15000000); Employee nv2 = new Employee("An", 25, 15000000);
System.out.println(nv1); // Employee[name=An, age=25, luong=1.5E7] System.out.println(nv1.equals(nv2)); // true (record tu sinh equals) }}data class Employee(val name: String, val age: Int, val luong: Double = 0.0)
fun main() { val nv1 = Employee("An", 25, 15000000.0) val nv2 = Employee("An", 25, 15000000.0)
println(nv1) // Employee(name=An, age=25, luong=1.5E7) println(nv1 == nv2) // true (data class tu sinh equals)}class Employee { final String name; final int age; final double luong; Employee(this.name, this.age, [this.luong = 0.0]);
@override bool operator ==(Object other) => other is Employee && name == other.name && age == other.age && luong == other.luong;
@override int get hashCode => Object.hash(name, age, luong);
@override String toString() => "Employee(name: $name, age: $age, luong: $luong)";}
void main() { final nv1 = Employee("An", 25, 15000000); final nv2 = Employee("An", 25, 15000000);
print(nv1); // Employee(name: An, age: 25, luong: 15000000.0) print(nv1 == nv2); // true}49. So sánh đối tượng (__eq__, __lt__) để sắp xếp
Viết class Student cài đặt __eq__ và __lt__ để có thể dùng trực tiếp sorted() theo điểm số.
Xem đáp án
class Student: def __init__(self, name, score): self.name = name self.score = score
def __eq__(self, other): return self.score == other.score
def __lt__(self, other): return self.score < other.score
def __repr__(self): return f"{self.name} ({self.score})"
student_list = [Student("An", 8), Student("Binh", 9), Student("Chi", 7)]print(sorted(student_list)) # [Chi (7), An (8), Binh (9)]#include <iostream>#include <vector>#include <algorithm>#include <string>using namespace std;
class Student {public: string name; int score; Student(string name, int score) : name(name), score(score) {}
bool operator<(const Student& other) const { return score < other.score; }
friend ostream& operator<<(ostream& os, const Student& s) { return os << s.name << " (" << s.score << ")"; }};
int main() { vector<Student> studentList = {Student("An", 8), Student("Binh", 9), Student("Chi", 7)}; sort(studentList.begin(), studentList.end());
for (auto& s : studentList) cout << s << " "; cout << endl; // Chi (7) An (8) Binh (9) return 0;}import java.util.*;
public class Main { static class Student implements Comparable<Student> { String name; int score; Student(String name, int score) { this.name = name; this.score = score; }
@Override public int compareTo(Student other) { return Integer.compare(score, other.score); }
@Override public String toString() { return name + " (" + score + ")"; } }
public static void main(String[] args) { List<Student> studentList = new ArrayList<>(List.of( new Student("An", 8), new Student("Binh", 9), new Student("Chi", 7))); Collections.sort(studentList);
System.out.println(studentList); // [Chi (7), An (8), Binh (9)] }}class Student(val name: String, val score: Int) : Comparable<Student> { override fun compareTo(other: Student): Int = score.compareTo(other.score) override fun toString(): String = "$name ($score)"}
fun main() { val studentList = mutableListOf(Student("An", 8), Student("Binh", 9), Student("Chi", 7)) studentList.sort()
println(studentList) // [Chi (7), An (8), Binh (9)]}class Student implements Comparable<Student> { String name; int score; Student(this.name, this.score);
@override int compareTo(Student other) => score.compareTo(other.score);
@override String toString() => "$name ($score)";}
void main() { final studentList = [Student("An", 8), Student("Binh", 9), Student("Chi", 7)]; studentList.sort();
print(studentList); // [Chi (7), An (8), Binh (9)]}50. Singleton Pattern
Cài đặt mẫu thiết kế Singleton đơn giản, đảm bảo một class chỉ có duy nhất 1 đối tượng được tạo ra.
Xem đáp án
class Singleton: _instance = None
def __new__(cls, *args, **kwargs): if cls._instance is None: cls._instance = super().__new__(cls) return cls._instance
def __init__(self): self.value = getattr(self, "value", 0)
a = Singleton()b = Singleton()a.value = 100
print(a is b) # True — cùng 1 đối tượngprint(b.value) # 100#include <iostream>using namespace std;
class Singleton {private: Singleton() {} static Singleton* instance;public: int value = 0;
static Singleton* getInstance() { if (instance == nullptr) instance = new Singleton(); return instance; }};
Singleton* Singleton::instance = nullptr;
int main() { Singleton* a = Singleton::getInstance(); Singleton* b = Singleton::getInstance(); a->value = 100;
cout << boolalpha << (a == b) << endl; // true - cung 1 doi tuong cout << b->value << endl; // 100 return 0;}public class Main { static class Singleton { private static Singleton instance; int value = 0;
private Singleton() {}
static Singleton getInstance() { if (instance == null) instance = new Singleton(); return instance; } }
public static void main(String[] args) { Singleton a = Singleton.getInstance(); Singleton b = Singleton.getInstance(); a.value = 100;
System.out.println(a == b); // true - cung 1 doi tuong System.out.println(b.value); // 100 }}object Singleton { var value: Int = 0}
fun main() { val a = Singleton val b = Singleton a.value = 100
println(a === b) // true - cung 1 doi tuong println(b.value) // 100}class Singleton { static final Singleton _instance = Singleton._internal(); int value = 0;
Singleton._internal();
factory Singleton() => _instance;}
void main() { final a = Singleton(); final b = Singleton(); a.value = 100;
print(identical(a, b)); // true - cung 1 doi tuong print(b.value); // 100}Nhóm 7: Closures, Decorators, Generators
Phần tiêu đề “Nhóm 7: Closures, Decorators, Generators”Closure là khi một hàm con “nhớ” được các biến trong hàm cha bao quanh nó, ngay cả sau khi hàm cha đã chạy xong (xem ví dụ ở bài 51). Xem thêm lý thuyết: Decorators (Hàm trang trí), Generators và Iterators, Context Managers (with statement).
51. Closure - Bộ đếm
Viết một closure make_counter() trả về hàm count() mỗi lần gọi sẽ tăng và trả về một biến đếm được “nhớ” bên trong closure.
Xem đáp án
def make_counter(): count_value = 0
def count(): nonlocal count_value count_value += 1 return count_value
return count
counter = make_counter()print(counter()) # 1print(counter()) # 2print(counter()) # 3#include <iostream>#include <functional>using namespace std;
function<int()> makeCounter() { auto countValue = make_shared<int>(0); return [countValue]() mutable { (*countValue)++; return *countValue; };}
int main() { auto counter = makeCounter(); cout << counter() << endl; // 1 cout << counter() << endl; // 2 cout << counter() << endl; // 3 return 0;}import java.util.function.Supplier;
public class Main { static Supplier<Integer> makeCounter() { int[] countValue = {0}; return () -> ++countValue[0]; }
public static void main(String[] args) { Supplier<Integer> counter = makeCounter(); System.out.println(counter.get()); // 1 System.out.println(counter.get()); // 2 System.out.println(counter.get()); // 3 }}fun makeCounter(): () -> Int { var countValue = 0 return { countValue++ countValue }}
fun main() { val counter = makeCounter() println(counter()) // 1 println(counter()) // 2 println(counter()) // 3}int Function() makeCounter() { int countValue = 0; return () { countValue++; return countValue; };}
void main() { final counter = makeCounter(); print(counter()); // 1 print(counter()); // 2 print(counter()); // 3}52. Decorator đo thời gian chạy hàm
Viết decorator @timer in ra thời gian thực thi của hàm được trang trí.
Xem đáp án
import timefrom functools import wraps
def timer(func): @wraps(func) def wrapper(*args, **kwargs): start_time = time.time() result = func(*args, **kwargs) end_time = time.time() print(f"{func.__name__} chạy trong {end_time - start_time:.4f} giây") return result return wrapper
@timerdef calculate_sum(n): return sum(range(n))
print(calculate_sum(1_000_000))#include <iostream>#include <chrono>#include <functional>using namespace std;using namespace std::chrono;
long long timer(const string& name, function<long long()> func) { auto start = high_resolution_clock::now(); long long result = func(); auto end = high_resolution_clock::now(); double seconds = duration<double>(end - start).count(); cout << name << " chay trong " << seconds << " giay" << endl; return result;}
long long calculateSum(int n) { long long total = 0; for (int i = 0; i < n; i++) total += i; return total;}
int main() { long long result = timer("calculateSum", [] { return calculateSum(1000000); }); cout << result << endl; return 0;}import java.util.function.Supplier;
public class Main { static <T> T timer(String name, Supplier<T> func) { long start = System.nanoTime(); T result = func.get(); long end = System.nanoTime(); System.out.printf("%s chay trong %.4f giay%n", name, (end - start) / 1e9); return result; }
static long calculateSum(int n) { long total = 0; for (int i = 0; i < n; i++) total += i; return total; }
public static void main(String[] args) { long result = timer("calculateSum", () -> calculateSum(1_000_000)); System.out.println(result); }}inline fun <T> timer(name: String, func: () -> T): T { val start = System.nanoTime() val result = func() val end = System.nanoTime() println("$name chay trong ${(end - start) / 1e9} giay") return result}
fun calculateSum(n: Int): Long { var total = 0L for (i in 0 until n) total += i return total}
fun main() { val result = timer("calculateSum") { calculateSum(1_000_000) } println(result)}T timer<T>(String name, T Function() func) { final start = DateTime.now(); final result = func(); final end = DateTime.now(); final seconds = end.difference(start).inMicroseconds / 1e6; print("$name chay trong $seconds giay"); return result;}
int calculateSum(int n) { int total = 0; for (int i = 0; i < n; i++) total += i; return total;}
void main() { final result = timer("calculateSum", () => calculateSum(1000000)); print(result);}53. Decorator ghi log
Viết decorator @log_calls in ra tên hàm cùng tham số truyền vào mỗi khi hàm được gọi.
Xem đáp án
from functools import wraps
def log_calls(func): @wraps(func) def wrapper(*args, **kwargs): print(f"Gọi hàm {func.__name__} với args={args}, kwargs={kwargs}") return func(*args, **kwargs) return wrapper
@log_callsdef add(a, b): return a + b
print(add(3, 5))#include <iostream>#include <functional>using namespace std;
int logCalls(const string& name, int a, int b, function<int(int, int)> func) { cout << "Goi ham " << name << " voi args=(" << a << ", " << b << ")" << endl; return func(a, b);}
int add(int a, int b) { return a + b;}
int main() { cout << logCalls("add", 3, 5, add) << endl; return 0;}import java.util.function.BinaryOperator;
public class Main { static int logCalls(String name, int a, int b, BinaryOperator<Integer> func) { System.out.printf("Goi ham %s voi args=(%d, %d)%n", name, a, b); return func.apply(a, b); }
static int add(int a, int b) { return a + b; }
public static void main(String[] args) { System.out.println(logCalls("add", 3, 5, Main::add)); }}fun logCalls(name: String, a: Int, b: Int, func: (Int, Int) -> Int): Int { println("Goi ham $name voi args=($a, $b)") return func(a, b)}
fun add(a: Int, b: Int): Int = a + b
fun main() { println(logCalls("add", 3, 5, ::add))}int logCalls(String name, int a, int b, int Function(int, int) func) { print("Goi ham $name voi args=($a, $b)"); return func(a, b);}
int add(int a, int b) => a + b;
void main() { print(logCalls("add", 3, 5, add));}54. Decorator tự động thử lại (Retry)
Viết decorator @retry(times) tự động gọi lại hàm tối đa times lần nếu hàm ném ra exception.
Xem đáp án
from functools import wraps
def retry(times=3): def decorator(func): @wraps(func) def wrapper(*args, **kwargs): for attempt in range(1, times + 1): try: return func(*args, **kwargs) except Exception as e: print(f"Lần thử {attempt} thất bại: {e}") raise Exception(f"Đã thử {times} lần nhưng vẫn thất bại") return wrapper return decorator
call_count = [0]
@retry(times=3)def unstable_function(): call_count[0] += 1 if call_count[0] < 3: raise ValueError("Lỗi giả lập") return "Thành công!"
print(unstable_function())#include <iostream>#include <functional>#include <stdexcept>using namespace std;
string retry(int times, function<string()> func) { for (int attempt = 1; attempt <= times; attempt++) { try { return func(); } catch (const exception& e) { cout << "Lan thu " << attempt << " that bai: " << e.what() << endl; } } throw runtime_error("Da thu " + to_string(times) + " lan nhung van that bai");}
int callCount = 0;
string unstableFunction() { callCount++; if (callCount < 3) throw runtime_error("Loi gia lap"); return "Thanh cong!";}
int main() { cout << retry(3, unstableFunction) << endl; return 0;}import java.util.function.Supplier;
public class Main { static int callCount = 0;
static String retry(int times, Supplier<String> func) { for (int attempt = 1; attempt <= times; attempt++) { try { return func.get(); } catch (RuntimeException e) { System.out.println("Lan thu " + attempt + " that bai: " + e.getMessage()); } } throw new RuntimeException("Da thu " + times + " lan nhung van that bai"); }
static String unstableFunction() { callCount++; if (callCount < 3) throw new RuntimeException("Loi gia lap"); return "Thanh cong!"; }
public static void main(String[] args) { System.out.println(retry(3, Main::unstableFunction)); }}fun retry(times: Int, func: () -> String): String { for (attempt in 1..times) { try { return func() } catch (e: Exception) { println("Lan thu $attempt that bai: ${e.message}") } } throw RuntimeException("Da thu $times lan nhung van that bai")}
var callCount = 0
fun unstableFunction(): String { callCount++ if (callCount < 3) throw RuntimeException("Loi gia lap") return "Thanh cong!"}
fun main() { println(retry(3, ::unstableFunction))}String retry(int times, String Function() func) { for (int attempt = 1; attempt <= times; attempt++) { try { return func(); } catch (e) { print("Lan thu $attempt that bai: $e"); } } throw Exception("Da thu $times lan nhung van that bai");}
int callCount = 0;
String unstableFunction() { callCount++; if (callCount < 3) throw Exception("Loi gia lap"); return "Thanh cong!";}
void main() { print(retry(3, unstableFunction));}55. Generator sinh dãy Fibonacci
Viết một generator function fibonacci_gen() sinh vô hạn các số Fibonacci, dùng yield.
Xem đáp án
def fibonacci_gen(): a, b = 0, 1 while True: yield a a, b = b, a + b
gen = fibonacci_gen()for _ in range(10): print(next(gen), end=" ") # 0 1 1 2 3 5 8 13 21 34#include <iostream>using namespace std;
class FibonacciGen { long long a = 0, b = 1;public: long long next() { long long result = a; long long nextB = a + b; a = b; b = nextB; return result; }};
int main() { FibonacciGen gen; for (int i = 0; i < 10; i++) cout << gen.next() << " "; cout << endl; // 0 1 1 2 3 5 8 13 21 34 return 0;}public class Main { static class FibonacciGen { long a = 0, b = 1;
long next() { long result = a; long nextB = a + b; a = b; b = nextB; return result; } }
public static void main(String[] args) { FibonacciGen gen = new FibonacciGen(); StringBuilder sb = new StringBuilder(); for (int i = 0; i < 10; i++) sb.append(gen.next()).append(" "); System.out.println(sb.toString().trim()); // 0 1 1 2 3 5 8 13 21 34 }}fun fibonacciSeq(): Sequence<Long> = sequence { var a = 0L var b = 1L while (true) { yield(a) val next = a + b a = b b = next }}
fun main() { val gen = fibonacciSeq().iterator() repeat(10) { print("${gen.next()} ") } // 0 1 1 2 3 5 8 13 21 34 println()}import 'dart:io';
Iterable<int> fibonacciGen() sync* { int a = 0, b = 1; while (true) { yield a; final next = a + b; a = b; b = next; }}
void main() { final gen = fibonacciGen().iterator; for (int i = 0; i < 10; i++) { gen.moveNext(); stdout.write("${gen.current} "); // 0 1 1 2 3 5 8 13 21 34 } print("");}56. Generator đọc dữ liệu lớn theo từng dòng
Viết generator read_file_lines(file_path) đọc file lớn từng dòng một, tránh load toàn bộ file vào bộ nhớ.
Xem đáp án
def read_file_lines(file_path): with open(file_path, "r", encoding="utf-8") as f: for line in f: yield line.strip()
with open("data.txt", "w", encoding="utf-8") as f: f.write("Dòng 1\nDòng 2\nDòng 3\n")
for line in read_file_lines("data.txt"): print(line)#include <iostream>#include <fstream>#include <string>using namespace std;
class FileLineReader { ifstream file;public: FileLineReader(const string& path) : file(path) {} bool nextLine(string& line) { return static_cast<bool>(getline(file, line)); }};
int main() { ofstream fout("data.txt"); fout << "Dong 1\nDong 2\nDong 3\n"; fout.close();
FileLineReader reader("data.txt"); string line; while (reader.nextLine(line)) cout << line << endl; return 0;}import java.io.*;
public class Main { public static void main(String[] args) throws IOException { try (PrintWriter fout = new PrintWriter(new FileWriter("data.txt"))) { fout.println("Dong 1"); fout.println("Dong 2"); fout.println("Dong 3"); }
try (BufferedReader fin = new BufferedReader(new FileReader("data.txt"))) { String line; while ((line = fin.readLine()) != null) System.out.println(line); } }}import java.io.File
fun readFileLines(filePath: String): Sequence<String> = sequence { File(filePath).bufferedReader().useLines { lines -> lines.forEach { yield(it) } }}
fun main() { File("data.txt").writeText("Dong 1\nDong 2\nDong 3\n")
for (line in readFileLines("data.txt")) println(line)}import 'dart:io';
Iterable<String> readFileLines(String filePath) sync* { final lines = File(filePath).readAsLinesSync(); for (var line in lines) { yield line; }}
void main() { File("data.txt").writeAsStringSync("Dong 1\nDong 2\nDong 3\n");
for (var line in readFileLines("data.txt")) { print(line); }}57. yield from
Viết generator chain_generators(gen1, gen2) dùng yield from để nối 2 generator lại thành 1 chuỗi giá trị liên tục.
Xem đáp án
def even_gen(n): for i in range(0, n, 2): yield i
def odd_gen(n): for i in range(1, n, 2): yield i
def chain_generators(gen1, gen2): yield from gen1 yield from gen2
for num in chain_generators(even_gen(6), odd_gen(6)): print(num, end=" ") # 0 2 4 1 3 5#include <iostream>#include <vector>using namespace std;
vector<int> evenGen(int n) { vector<int> result; for (int i = 0; i < n; i += 2) result.push_back(i); return result;}
vector<int> oddGen(int n) { vector<int> result; for (int i = 1; i < n; i += 2) result.push_back(i); return result;}
vector<int> chainGenerators(vector<int>& gen1, vector<int>& gen2) { vector<int> result(gen1); result.insert(result.end(), gen2.begin(), gen2.end()); return result;}
int main() { auto evens = evenGen(6); auto odds = oddGen(6); for (int num : chainGenerators(evens, odds)) cout << num << " "; cout << endl; // 0 2 4 1 3 5 return 0;}import java.util.*;import java.util.stream.*;
public class Main { static List<Integer> evenGen(int n) { List<Integer> result = new ArrayList<>(); for (int i = 0; i < n; i += 2) result.add(i); return result; }
static List<Integer> oddGen(int n) { List<Integer> result = new ArrayList<>(); for (int i = 1; i < n; i += 2) result.add(i); return result; }
static List<Integer> chainGenerators(List<Integer> gen1, List<Integer> gen2) { return Stream.concat(gen1.stream(), gen2.stream()).collect(Collectors.toList()); }
public static void main(String[] args) { List<Integer> evens = evenGen(6); List<Integer> odds = oddGen(6); for (int num : chainGenerators(evens, odds)) System.out.print(num + " "); System.out.println(); // 0 2 4 1 3 5 }}fun evenGen(n: Int): Sequence<Int> = sequence { for (i in 0 until n step 2) yield(i)}
fun oddGen(n: Int): Sequence<Int> = sequence { for (i in 1 until n step 2) yield(i)}
fun chainGenerators(gen1: Sequence<Int>, gen2: Sequence<Int>): Sequence<Int> = sequence { yieldAll(gen1) yieldAll(gen2)}
fun main() { for (num in chainGenerators(evenGen(6), oddGen(6))) print("$num ") // 0 2 4 1 3 5 println()}import 'dart:io';
Iterable<int> evenGen(int n) sync* { for (int i = 0; i < n; i += 2) yield i;}
Iterable<int> oddGen(int n) sync* { for (int i = 1; i < n; i += 2) yield i;}
Iterable<int> chainGenerators(Iterable<int> gen1, Iterable<int> gen2) sync* { yield* gen1; yield* gen2;}
void main() { for (var num in chainGenerators(evenGen(6), oddGen(6))) { stdout.write("$num "); // 0 2 4 1 3 5 } print("");}58. Generator Expression vs List Comprehension
Viết cùng 1 phép tính bình phương các số từ 1 đến 1 triệu bằng cả list comprehension và generator expression, so sánh kích thước bộ nhớ bằng sys.getsizeof.
Xem đáp án
import sys
list_comp = [x ** 2 for x in range(1_000_000)]gen_exp = (x ** 2 for x in range(1_000_000))
print("List comprehension:", sys.getsizeof(list_comp), "bytes")print("Generator expression:", sys.getsizeof(gen_exp), "bytes")# Generator chỉ lưu "công thức sinh giá trị", không lưu toàn bộ dữ liệu#include <iostream>#include <vector>using namespace std;
int main() { // C++ khong co "generator expression" nhu Python; vector luu toan bo // phan tu trong bo nho, con range-based approach (vi du dung iterator // tu sinh) chi luu "cong thuc" sinh gia tri. vector<long long> listComp; for (int x = 0; x < 1000000; x++) listComp.push_back((long long)x * x);
cout << "Vector (giong list): " << listComp.size() * sizeof(long long) << " bytes" << endl; cout << "Neu dung iterator tu sinh: chi vai chuc bytes (khong luu du lieu)" << endl; return 0;}import java.util.ArrayList;import java.util.List;import java.util.stream.IntStream;
public class Main { public static void main(String[] args) { // Java khong co bo nho tinh truc tiep nhu sys.getsizeof, minh hoa // khai niem bang so luong phan tu duoc luu. List<Long> listComp = new ArrayList<>(); for (int x = 0; x < 1_000_000; x++) listComp.add((long) x * x);
System.out.println("ArrayList (giong list): luu " + listComp.size() + " phan tu trong bo nho");
// IntStream la lazy, khong luu toan bo du lieu truoc var streamExp = IntStream.range(0, 1_000_000).mapToLong(x -> (long) x * x); System.out.println("IntStream (giong generator): chi luu 'cong thuc sinh gia tri'"); }}fun main() { // List luu toan bo phan tu trong bo nho, con Sequence la lazy - chi // luu "cong thuc sinh gia tri" giong generator expression cua Python. val listComp = (0 until 1_000_000).map { it.toLong() * it } val seqExp = (0 until 1_000_000).asSequence().map { it.toLong() * it }
println("List (giong list comprehension): luu ${listComp.size} phan tu trong bo nho") println("Sequence (giong generator): chi luu 'cong thuc sinh gia tri', lazy")}void main() { // List luu toan bo phan tu trong bo nho, con Iterable.generate la lazy - // chi luu "cong thuc sinh gia tri" giong generator expression Python. final listComp = List.generate(1000000, (x) => x * x); final genExp = Iterable.generate(1000000, (x) => x * x);
print("List (giong list comprehension): luu ${listComp.length} phan tu trong bo nho"); print("Iterable.generate (giong generator): chi luu 'cong thuc sinh gia tri', lazy");}59. Decorator cache kết quả (tự viết memoization)
Viết decorator @cache_result tự lưu lại kết quả các lần gọi hàm trước đó, tránh tính toán lại (không dùng functools.lru_cache).
Xem đáp án
from functools import wraps
def cache_result(func): cache = {}
@wraps(func) def wrapper(*args): if args not in cache: cache[args] = func(*args) return cache[args]
return wrapper
@cache_resultdef fib(n): if n <= 1: return n return fib(n - 1) + fib(n - 2)
print(fib(35)) # Chạy nhanh nhờ cache#include <iostream>#include <unordered_map>using namespace std;
unordered_map<int, long long> cache;
long long fib(int n) { if (n <= 1) return n; auto it = cache.find(n); if (it != cache.end()) return it->second; long long result = fib(n - 1) + fib(n - 2); cache[n] = result; return result;}
int main() { cout << fib(35) << endl; // Chay nhanh nho cache return 0;}import java.util.HashMap;import java.util.Map;
public class Main { static Map<Integer, Long> cache = new HashMap<>();
static long fib(int n) { if (n <= 1) return n; if (cache.containsKey(n)) return cache.get(n); long result = fib(n - 1) + fib(n - 2); cache.put(n, result); return result; }
public static void main(String[] args) { System.out.println(fib(35)); // Chay nhanh nho cache }}val cache = HashMap<Int, Long>()
fun fib(n: Int): Long { if (n <= 1) return n.toLong() return cache.getOrPut(n) { fib(n - 1) + fib(n - 2) }}
fun main() { println(fib(35)) // Chay nhanh nho cache}final cache = <int, int>{};
int fib(int n) { if (n <= 1) return n; return cache.putIfAbsent(n, () => fib(n - 1) + fib(n - 2));}
void main() { print(fib(35)); // Chay nhanh nho cache}60. Context Manager tự viết (class)
Viết một class context manager FileOpener (cài đặt __enter__ và __exit__) để dùng với cú pháp with.
Xem đáp án
class FileOpener: def __init__(self, file_path, mode): self.file_path = file_path self.mode = mode
def __enter__(self): self.file = open(self.file_path, self.mode, encoding="utf-8") return self.file
def __exit__(self, exc_type, exc_value, traceback): self.file.close() print("Đã tự động đóng file")
with FileOpener("data.txt", "w") as f: f.write("Xin chào từ context manager tự viết!")#include <iostream>#include <fstream>#include <string>using namespace std;
class FileOpener { ofstream file;public: FileOpener(const string& path) : file(path) {}
ofstream& stream() { return file; }
~FileOpener() { file.close(); cout << "Da tu dong dong file" << endl; }};
int main() { { FileOpener opener("data.txt"); opener.stream() << "Xin chao tu context manager tu viet!"; } // Destructor chay khi ra khoi scope, giong __exit__ return 0;}import java.io.*;
public class Main { static class FileOpener implements AutoCloseable { PrintWriter file;
FileOpener(String path) throws IOException { file = new PrintWriter(new FileWriter(path)); }
@Override public void close() { file.close(); System.out.println("Da tu dong dong file"); } }
public static void main(String[] args) throws IOException { try (FileOpener opener = new FileOpener("data.txt")) { opener.file.write("Xin chao tu context manager tu viet!"); } }}import java.io.Fileimport java.io.PrintWriter
class FileOpener(path: String) : AutoCloseable { val file = PrintWriter(path)
override fun close() { file.close() println("Da tu dong dong file") }}
fun main() { FileOpener("data.txt").use { opener -> opener.file.write("Xin chao tu context manager tu viet!") }}import 'dart:io';
class FileOpener { final IOSink file; FileOpener(String path) : file = File(path).openWrite();
Future<void> close() async { await file.close(); print("Da tu dong dong file"); }}
void main() async { final opener = FileOpener("data.txt"); opener.file.write("Xin chao tu context manager tu viet!"); await opener.close();}Nhóm 8: Lập trình hàm (Functional Programming)
Phần tiêu đề “Nhóm 8: Lập trình hàm (Functional Programming)”61. reduce tính tổng và tích
Dùng functools.reduce để tính tổng và tích các phần tử của một list số.
Xem đáp án
from functools import reduce
numbers = [1, 2, 3, 4, 5]
total = reduce(lambda a, b: a + b, numbers)product_value = reduce(lambda a, b: a * b, numbers)
print("Tổng:", total) # 15print("Tích:", product_value) # 120#include <iostream>#include <vector>#include <numeric>using namespace std;
int main() { vector<int> numbers = {1, 2, 3, 4, 5};
int total = accumulate(numbers.begin(), numbers.end(), 0, [](int a, int b) { return a + b; }); int productValue = accumulate(numbers.begin(), numbers.end(), 1, [](int a, int b) { return a * b; });
cout << "Tong: " << total << endl; // 15 cout << "Tich: " << productValue << endl; // 120 return 0;}import java.util.List;
public class Main { public static void main(String[] args) { List<Integer> numbers = List.of(1, 2, 3, 4, 5);
int total = numbers.stream().reduce(0, (a, b) -> a + b); int productValue = numbers.stream().reduce(1, (a, b) -> a * b);
System.out.println("Tong: " + total); // 15 System.out.println("Tich: " + productValue); // 120 }}fun main() { val numbers = listOf(1, 2, 3, 4, 5)
val total = numbers.reduce { a, b -> a + b } val productValue = numbers.fold(1) { a, b -> a * b }
println("Tong: $total") // 15 println("Tich: $productValue") // 120}void main() { final numbers = [1, 2, 3, 4, 5];
final total = numbers.reduce((a, b) => a + b); final productValue = numbers.fold(1, (a, b) => a * b);
print("Tong: $total"); // 15 print("Tich: $productValue"); // 120}62. Kết hợp map và filter
Cho một list chuỗi số, dùng filter để loại các chuỗi không phải số, dùng map để chuyển các chuỗi còn lại thành int và nhân đôi giá trị.
Xem đáp án
data = ["10", "abc", "20", "xyz", "30"]
valid_numbers = filter(str.isdigit, data)result = list(map(lambda x: int(x) * 2, valid_numbers))
print(result) # [20, 40, 60]#include <iostream>#include <vector>#include <string>#include <algorithm>#include <cctype>using namespace std;
bool isDigits(const string& s) { return !s.empty() && all_of(s.begin(), s.end(), ::isdigit);}
int main() { vector<string> data = {"10", "abc", "20", "xyz", "30"};
vector<int> result; for (auto& s : data) { if (isDigits(s)) result.push_back(stoi(s) * 2); }
cout << "["; for (size_t i = 0; i < result.size(); i++) { cout << result[i]; if (i + 1 < result.size()) cout << ", "; } cout << "]" << endl; // [20, 40, 60] return 0;}import java.util.List;import java.util.stream.Collectors;
public class Main { public static void main(String[] args) { List<String> data = List.of("10", "abc", "20", "xyz", "30");
List<Integer> result = data.stream() .filter(s -> s.chars().allMatch(Character::isDigit)) .map(s -> Integer.parseInt(s) * 2) .collect(Collectors.toList());
System.out.println(result); // [20, 40, 60] }}fun main() { val data = listOf("10", "abc", "20", "xyz", "30")
val result = data.filter { it.all { c -> c.isDigit() } } .map { it.toInt() * 2 }
println(result) // [20, 40, 60]}void main() { final data = ["10", "abc", "20", "xyz", "30"];
final result = data .where((s) => RegExp(r'^\d+$').hasMatch(s)) .map((s) => int.parse(s) * 2) .toList();
print(result); // [20, 40, 60]}63. functools.partial
Dùng functools.partial để tạo ra một hàm mới từ hàm nhan(a, b) với a đã được cố định sẵn.
Xem đáp án
from functools import partial
def multiply(a, b): return a * b
double_value = partial(multiply, 2)triple_value = partial(multiply, 3)
print(double_value(5)) # 10print(triple_value(5)) # 15#include <iostream>#include <functional>using namespace std;
int multiply(int a, int b) { return a * b;}
int main() { auto doubleValue = bind(multiply, 2, placeholders::_1); auto tripleValue = bind(multiply, 3, placeholders::_1);
cout << doubleValue(5) << endl; // 10 cout << tripleValue(5) << endl; // 15 return 0;}import java.util.function.Function;
public class Main { static int multiply(int a, int b) { return a * b; }
public static void main(String[] args) { Function<Integer, Integer> doubleValue = b -> multiply(2, b); Function<Integer, Integer> tripleValue = b -> multiply(3, b);
System.out.println(doubleValue.apply(5)); // 10 System.out.println(tripleValue.apply(5)); // 15 }}fun multiply(a: Int, b: Int): Int = a * b
fun main() { val doubleValue = { b: Int -> multiply(2, b) } val tripleValue = { b: Int -> multiply(3, b) }
println(doubleValue(5)) // 10 println(tripleValue(5)) // 15}int multiply(int a, int b) => a * b;
void main() { int Function(int) doubleValue = (b) => multiply(2, b); int Function(int) tripleValue = (b) => multiply(3, b);
print(doubleValue(5)); // 10 print(tripleValue(5)); // 15}64. itertools.combinations
Dùng itertools.combinations để in ra tất cả tổ hợp chập 2 của một list.
Xem đáp án
from itertools import combinations
items = ["A", "B", "C", "D"]
for combo in combinations(items, 2): print(combo)#include <iostream>#include <vector>#include <string>using namespace std;
void combinations(vector<string>& items, int k) { int n = items.size(); vector<int> indices(k); for (int i = 0; i < k; i++) indices[i] = i;
while (true) { cout << "("; for (int i = 0; i < k; i++) { cout << "'" << items[indices[i]] << "'"; if (i + 1 < k) cout << ", "; } cout << ")" << endl;
int i = k - 1; while (i >= 0 && indices[i] == n - k + i) i--; if (i < 0) break; indices[i]++; for (int j = i + 1; j < k; j++) indices[j] = indices[j - 1] + 1; }}
int main() { vector<string> items = {"A", "B", "C", "D"}; combinations(items, 2); return 0;}import java.util.List;
public class Main { static void combinations(List<String> items, int k) { int n = items.size(); int[] indices = new int[k]; for (int i = 0; i < k; i++) indices[i] = i;
while (true) { StringBuilder sb = new StringBuilder("("); for (int i = 0; i < k; i++) { sb.append(items.get(indices[i])); if (i + 1 < k) sb.append(", "); } sb.append(")"); System.out.println(sb);
int i = k - 1; while (i >= 0 && indices[i] == n - k + i) i--; if (i < 0) break; indices[i]++; for (int j = i + 1; j < k; j++) indices[j] = indices[j - 1] + 1; } }
public static void main(String[] args) { List<String> items = List.of("A", "B", "C", "D"); combinations(items, 2); }}fun combinations(items: List<String>, k: Int) { val n = items.size val indices = IntArray(k) { it }
while (true) { println("(" + (0 until k).joinToString(", ") { items[indices[it]] } + ")")
var i = k - 1 while (i >= 0 && indices[i] == n - k + i) i-- if (i < 0) break indices[i]++ for (j in i + 1 until k) indices[j] = indices[j - 1] + 1 }}
fun main() { val items = listOf("A", "B", "C", "D") combinations(items, 2)}void combinations(List<String> items, int k) { final n = items.length; final indices = List<int>.generate(k, (i) => i);
while (true) { final parts = List.generate(k, (i) => items[indices[i]]); print("(${parts.join(', ')})");
int i = k - 1; while (i >= 0 && indices[i] == n - k + i) i--; if (i < 0) break; indices[i]++; for (int j = i + 1; j < k; j++) indices[j] = indices[j - 1] + 1; }}
void main() { final items = ["A", "B", "C", "D"]; combinations(items, 2);}65. itertools.permutations
Dùng itertools.permutations để in ra tất cả hoán vị của một list 3 phần tử.
Xem đáp án
from itertools import permutations
items = [1, 2, 3]
for current in permutations(items): print(current)#include <iostream>#include <vector>#include <algorithm>using namespace std;
int main() { vector<int> items = {1, 2, 3}; sort(items.begin(), items.end());
do { cout << "("; for (size_t i = 0; i < items.size(); i++) { cout << items[i]; if (i + 1 < items.size()) cout << ", "; } cout << ")" << endl; } while (next_permutation(items.begin(), items.end()));
return 0;}import java.util.*;
public class Main { static void permute(List<Integer> items, List<Integer> current, boolean[] used) { if (current.size() == items.size()) { System.out.println("(" + current.stream().map(String::valueOf) .reduce((a, b) -> a + ", " + b).orElse("") + ")"); return; } for (int i = 0; i < items.size(); i++) { if (used[i]) continue; used[i] = true; current.add(items.get(i)); permute(items, current, used); current.remove(current.size() - 1); used[i] = false; } }
public static void main(String[] args) { List<Integer> items = List.of(1, 2, 3); permute(items, new ArrayList<>(), new boolean[items.size()]); }}fun permute(items: List<Int>, current: MutableList<Int>, used: BooleanArray) { if (current.size == items.size) { println("(" + current.joinToString(", ") + ")") return } for (i in items.indices) { if (used[i]) continue used[i] = true current.add(items[i]) permute(items, current, used) current.removeAt(current.size - 1) used[i] = false }}
fun main() { val items = listOf(1, 2, 3) permute(items, mutableListOf(), BooleanArray(items.size))}void permute(List<int> items, List<int> current, List<bool> used) { if (current.length == items.length) { print("(${current.join(', ')})"); return; } for (int i = 0; i < items.length; i++) { if (used[i]) continue; used[i] = true; current.add(items[i]); permute(items, current, used); current.removeLast(); used[i] = false; }}
void main() { final items = [1, 2, 3]; permute(items, [], List.filled(items.length, false));}66. itertools.groupby
Cho một list số đã sắp xếp, dùng itertools.groupby để nhóm các số theo tính chẵn/lẻ.
Xem đáp án
from itertools import groupby
numbers = [1, 3, 5, 2, 4, 6, 7, 9]numbers_sorted = sorted(numbers, key=lambda x: x % 2)
for key, groups in groupby(numbers_sorted, key=lambda x: "Chẵn" if x % 2 == 0 else "Lẻ"): print(key, ":", list(groups))#include <iostream>#include <vector>#include <algorithm>using namespace std;
int main() { vector<int> numbers = {1, 3, 5, 2, 4, 6, 7, 9}; sort(numbers.begin(), numbers.end(), [](int a, int b) { return (a % 2) < (b % 2); });
size_t i = 0; while (i < numbers.size()) { int parity = numbers[i] % 2; vector<int> group; while (i < numbers.size() && numbers[i] % 2 == parity) { group.push_back(numbers[i]); i++; } cout << (parity == 0 ? "Chan" : "Le") << " : ["; for (size_t j = 0; j < group.size(); j++) { cout << group[j]; if (j + 1 < group.size()) cout << ", "; } cout << "]" << endl; } return 0;}import java.util.*;import java.util.stream.*;
public class Main { public static void main(String[] args) { List<Integer> numbers = new ArrayList<>(List.of(1, 3, 5, 2, 4, 6, 7, 9)); numbers.sort(Comparator.comparingInt(x -> x % 2));
int i = 0; while (i < numbers.size()) { int parity = numbers.get(i) % 2; List<Integer> group = new ArrayList<>(); while (i < numbers.size() && numbers.get(i) % 2 == parity) { group.add(numbers.get(i)); i++; } System.out.println((parity == 0 ? "Chan" : "Le") + " : " + group); } }}fun main() { val numbers = mutableListOf(1, 3, 5, 2, 4, 6, 7, 9) numbers.sortBy { it % 2 }
var i = 0 while (i < numbers.size) { val parity = numbers[i] % 2 val group = mutableListOf<Int>() while (i < numbers.size && numbers[i] % 2 == parity) { group.add(numbers[i]) i++ } println("${if (parity == 0) "Chan" else "Le"} : $group") }}void main() { var numbers = [1, 3, 5, 2, 4, 6, 7, 9]; numbers.sort((a, b) => (a % 2).compareTo(b % 2));
int i = 0; while (i < numbers.length) { int parity = numbers[i] % 2; List<int> group = []; while (i < numbers.length && numbers[i] % 2 == parity) { group.add(numbers[i]); i++; } print("${parity == 0 ? "Chan" : "Le"} : $group"); }}67. sorted với key phức tạp
Cho một list các tuple (ten, tuoi). Sắp xếp theo độ dài tên tăng dần, nếu bằng nhau thì theo tuổi giảm dần.
Xem đáp án
people = [("An", 20), ("Binh", 25), ("Ba", 30), ("Chi", 22)]
result = sorted(people, key=lambda p: (len(p[0]), -p[1]))print(result)#include <iostream>#include <vector>#include <string>#include <algorithm>using namespace std;
int main() { vector<pair<string, int>> people = {{"An", 20}, {"Binh", 25}, {"Ba", 30}, {"Chi", 22}};
sort(people.begin(), people.end(), [](const pair<string, int>& a, const pair<string, int>& b) { if (a.first.size() != b.first.size()) return a.first.size() < b.first.size(); return a.second > b.second; });
cout << "["; for (size_t i = 0; i < people.size(); i++) { cout << "(" << people[i].first << ", " << people[i].second << ")"; if (i + 1 < people.size()) cout << ", "; } cout << "]" << endl; return 0;}import java.util.*;
public class Main { public static void main(String[] args) { List<Object[]> people = new ArrayList<>(List.of( new Object[]{"An", 20}, new Object[]{"Binh", 25}, new Object[]{"Ba", 30}, new Object[]{"Chi", 22} ));
people.sort((a, b) -> { int lenCmp = ((String) a[0]).length() - ((String) b[0]).length(); if (lenCmp != 0) return lenCmp; return (int) b[1] - (int) a[1]; });
StringBuilder sb = new StringBuilder("["); for (int i = 0; i < people.size(); i++) { sb.append("(").append(people.get(i)[0]).append(", ").append(people.get(i)[1]).append(")"); if (i + 1 < people.size()) sb.append(", "); } sb.append("]"); System.out.println(sb); }}fun main() { val people = mutableListOf("An" to 20, "Binh" to 25, "Ba" to 30, "Chi" to 22)
val result = people.sortedWith(compareBy({ it.first.length }, { -it.second })) println(result)}void main() { var people = [("An", 20), ("Binh", 25), ("Ba", 30), ("Chi", 22)];
people.sort((a, b) { if (a.$1.length != b.$1.length) return a.$1.length.compareTo(b.$1.length); return b.$2.compareTo(a.$2); });
print(people);}68. any và all nâng cao
Cho một list các list con điểm số, dùng any/all kết hợp generator expression để kiểm tra: (1) có học sinh nào toàn điểm 10 không, (2) tất cả học sinh có ít nhất 1 điểm trên 8 không.
Xem đáp án
student_scores = [ [8, 9, 7], [10, 10, 10], [6, 9, 5],]
has_student_all_10s = any(all(d == 10 for d in student) for student in student_scores)all_have_score_above_8 = all(any(d > 8 for d in student) for student in student_scores)
print(has_student_all_10s) # Trueprint(all_have_score_above_8) # False#include <iostream>#include <vector>#include <algorithm>using namespace std;
int main() { vector<vector<int>> studentScores = {{8, 9, 7}, {10, 10, 10}, {6, 9, 5}};
bool hasStudentAll10s = any_of(studentScores.begin(), studentScores.end(), [](const vector<int>& s) { return all_of(s.begin(), s.end(), [](int d) { return d == 10; }); }); bool allHaveScoreAbove8 = all_of(studentScores.begin(), studentScores.end(), [](const vector<int>& s) { return any_of(s.begin(), s.end(), [](int d) { return d > 8; }); });
cout << boolalpha << hasStudentAll10s << endl; cout << boolalpha << allHaveScoreAbove8 << endl; return 0;}import java.util.*;
public class Main { public static void main(String[] args) { int[][] studentScores = {{8, 9, 7}, {10, 10, 10}, {6, 9, 5}};
boolean hasStudentAll10s = Arrays.stream(studentScores) .anyMatch(s -> Arrays.stream(s).allMatch(d -> d == 10)); boolean allHaveScoreAbove8 = Arrays.stream(studentScores) .allMatch(s -> Arrays.stream(s).anyMatch(d -> d > 8));
System.out.println(hasStudentAll10s); System.out.println(allHaveScoreAbove8); }}fun main() { val studentScores = listOf(listOf(8, 9, 7), listOf(10, 10, 10), listOf(6, 9, 5))
val hasStudentAll10s = studentScores.any { s -> s.all { it == 10 } } val allHaveScoreAbove8 = studentScores.all { s -> s.any { it > 8 } }
println(hasStudentAll10s) println(allHaveScoreAbove8)}void main() { var studentScores = [ [8, 9, 7], [10, 10, 10], [6, 9, 5], ];
bool hasStudentAll10s = studentScores.any((s) => s.every((d) => d == 10)); bool allHaveScoreAbove8 = studentScores.every((s) => s.any((d) => d > 8));
print(hasStudentAll10s); print(allHaveScoreAbove8);}Nhóm 9: Module chuẩn hữu ích
Phần tiêu đề “Nhóm 9: Module chuẩn hữu ích”Xem thêm lý thuyết: Date and Time (datetime module), Regular Expressions, Làm việc với JSON.
69. collections.Counter - Ký tự phổ biến nhất
Dùng Counter để tìm ra 3 ký tự xuất hiện nhiều nhất trong một chuỗi.
Xem đáp án
from collections import Counter
s = "lap trinh python rat thu vi"count = Counter(s.replace(" ", ""))
print(count.most_common(3))#include <iostream>#include <string>#include <unordered_map>#include <vector>#include <algorithm>using namespace std;
int main() { string s = "lap trinh python rat thu vi"; string noSpace; for (char c : s) if (c != ' ') noSpace += c;
unordered_map<char, int> count; for (char c : noSpace) count[c]++;
vector<pair<char, int>> items(count.begin(), count.end()); sort(items.begin(), items.end(), [](auto& a, auto& b) { return a.second > b.second; });
cout << "["; for (int i = 0; i < 3 && i < (int)items.size(); i++) { cout << "('" << items[i].first << "', " << items[i].second << ")"; if (i < 2 && i + 1 < (int)items.size()) cout << ", "; } cout << "]" << endl; return 0;}import java.util.*;import java.util.stream.*;
public class Main { public static void main(String[] args) { String s = "lap trinh python rat thu vi"; String noSpace = s.replace(" ", "");
Map<Character, Long> count = noSpace.chars() .mapToObj(c -> (char) c) .collect(Collectors.groupingBy(c -> c, Collectors.counting()));
List<Map.Entry<Character, Long>> top3 = count.entrySet().stream() .sorted((a, b) -> Long.compare(b.getValue(), a.getValue())) .limit(3) .collect(Collectors.toList());
System.out.println(top3); }}fun main() { val s = "lap trinh python rat thu vi" val noSpace = s.replace(" ", "")
val count = noSpace.groupingBy { it }.eachCount() val top3 = count.entries.sortedByDescending { it.value }.take(3)
println(top3.map { it.key to it.value })}void main() { String s = "lap trinh python rat thu vi"; String noSpace = s.replaceAll(" ", "");
Map<String, int> count = {}; for (var c in noSpace.split('')) { count[c] = (count[c] ?? 0) + 1; }
var items = count.entries.toList()..sort((a, b) => b.value.compareTo(a.value)); var top3 = items.take(3).map((e) => "(${e.key}, ${e.value})").toList();
print(top3);}70. collections.defaultdict - Nhóm dữ liệu
Cho một list các tuple (name, subject). Dùng defaultdict để nhóm danh sách môn học theo từng người.
Xem đáp án
from collections import defaultdict
data = [("An", "Toán"), ("An", "Lý"), ("Binh", "Hóa"), ("An", "Anh"), ("Binh", "Toán")]
groups = defaultdict(list)for name, subject in data: groups[name].append(subject)
for name, subjects in groups.items(): print(name, ":", subjects)#include <iostream>#include <string>#include <vector>#include <map>using namespace std;
int main() { vector<pair<string, string>> data = { {"An", "Toan"}, {"An", "Ly"}, {"Binh", "Hoa"}, {"An", "Anh"}, {"Binh", "Toan"} };
map<string, vector<string>> groups; for (auto& [name, subject] : data) groups[name].push_back(subject);
for (auto& [name, subjects] : groups) { cout << name << " : ["; for (size_t i = 0; i < subjects.size(); i++) { cout << subjects[i]; if (i + 1 < subjects.size()) cout << ", "; } cout << "]" << endl; } return 0;}import java.util.*;
public class Main { public static void main(String[] args) { List<String[]> data = List.of( new String[]{"An", "Toan"}, new String[]{"An", "Ly"}, new String[]{"Binh", "Hoa"}, new String[]{"An", "Anh"}, new String[]{"Binh", "Toan"} );
Map<String, List<String>> groups = new LinkedHashMap<>(); for (String[] pair : data) { groups.computeIfAbsent(pair[0], k -> new ArrayList<>()).add(pair[1]); }
for (var entry : groups.entrySet()) { System.out.println(entry.getKey() + " : " + entry.getValue()); } }}fun main() { val data = listOf("An" to "Toan", "An" to "Ly", "Binh" to "Hoa", "An" to "Anh", "Binh" to "Toan")
val groups = LinkedHashMap<String, MutableList<String>>() for ((name, subject) in data) { groups.getOrPut(name) { mutableListOf() }.add(subject) }
for ((name, subjects) in groups) { println("$name : $subjects") }}void main() { var data = [ ("An", "Toan"), ("An", "Ly"), ("Binh", "Hoa"), ("An", "Anh"), ("Binh", "Toan") ];
var groups = <String, List<String>>{}; for (var (name, subject) in data) { groups.putIfAbsent(name, () => []).add(subject); }
groups.forEach((name, subjects) { print("$name : $subjects"); });}71. collections.namedtuple
Dùng namedtuple để tạo kiểu dữ liệu Point (có x, y) gọn nhẹ hơn class thông thường.
Xem đáp án
from collections import namedtuple
Point = namedtuple("Point", ["x", "y"])
p1 = Point(1, 2)p2 = Point(x=3, y=4)
print(p1) # Point(x=1, y=2)print(p1.x, p1.y) # 1 2print(p1 == Point(1, 2)) # True#include <iostream>using namespace std;
struct Point { int x, y; bool operator==(const Point& other) const { return x == other.x && y == other.y; }};
ostream& operator<<(ostream& os, const Point& p) { return os << "Point(x=" << p.x << ", y=" << p.y << ")";}
int main() { Point p1{1, 2}; Point p2{3, 4};
cout << p1 << endl; cout << p1.x << " " << p1.y << endl; cout << boolalpha << (p1 == Point{1, 2}) << endl; return 0;}public class Main { record Point(int x, int y) { @Override public String toString() { return "Point(x=" + x + ", y=" + y + ")"; } }
public static void main(String[] args) { Point p1 = new Point(1, 2); Point p2 = new Point(3, 4);
System.out.println(p1); System.out.println(p1.x() + " " + p1.y()); System.out.println(p1.equals(new Point(1, 2))); }}data class Point(val x: Int, val y: Int) { override fun toString() = "Point(x=$x, y=$y)"}
fun main() { val p1 = Point(1, 2) val p2 = Point(x = 3, y = 4)
println(p1) println("${p1.x} ${p1.y}") println(p1 == Point(1, 2))}class Point { final int x, y; Point(this.x, this.y);
@override String toString() => "Point(x=$x, y=$y)";
@override bool operator ==(Object other) => other is Point && x == other.x && y == other.y;
@override int get hashCode => Object.hash(x, y);}
void main() { var p1 = Point(1, 2); var p2 = Point(3, 4);
print(p1); print("${p1.x} ${p1.y}"); print(p1 == Point(1, 2));}72. datetime - Tính số ngày giữa 2 mốc thời gian
Dùng module datetime để tính số ngày giữa 2 ngày cho trước.
Xem đáp án
from datetime import date
date1 = date(2024, 1, 1)date2 = date(2024, 12, 31)
day_count = (date2 - date1).daysprint(f"Số ngày giữa 2 mốc: {day_count}")#include <iostream>#include <ctime>using namespace std;
int main() { tm t1 = {0, 0, 0, 1, 0, 2024 - 1900}; tm t2 = {0, 0, 0, 31, 11, 2024 - 1900};
time_t time1 = mktime(&t1); time_t time2 = mktime(&t2);
int dayCount = (int)(difftime(time2, time1) / (60 * 60 * 24)); cout << "So ngay giua 2 moc: " << dayCount << endl; return 0;}import java.time.LocalDate;import java.time.temporal.ChronoUnit;
public class Main { public static void main(String[] args) { LocalDate date1 = LocalDate.of(2024, 1, 1); LocalDate date2 = LocalDate.of(2024, 12, 31);
long dayCount = ChronoUnit.DAYS.between(date1, date2); System.out.println("So ngay giua 2 moc: " + dayCount); }}import java.time.LocalDateimport java.time.temporal.ChronoUnit
fun main() { val date1 = LocalDate.of(2024, 1, 1) val date2 = LocalDate.of(2024, 12, 31)
val dayCount = ChronoUnit.DAYS.between(date1, date2) println("So ngay giua 2 moc: $dayCount")}void main() { var date1 = DateTime(2024, 1, 1); var date2 = DateTime(2024, 12, 31);
var dayCount = date2.difference(date1).inDays; print("So ngay giua 2 moc: $dayCount");}73. re - Kiểm tra định dạng email
Dùng module re (regular expression) để kiểm tra một chuỗi có đúng định dạng email cơ bản hay không, có cho nhập lại nếu sai định dạng.
Xem đáp án
import re
pattern = r"^[\w.+-]+@[\w-]+\.[a-zA-Z]{2,}$"
while True: email = input("Nhập email: ") if re.match(pattern, email): print("Email hợp lệ!") break print("Email không hợp lệ, vui lòng nhập lại!")#include <iostream>#include <regex>#include <string>using namespace std;
int main() { regex pattern(R"(^[\w.+-]+@[\w-]+\.[a-zA-Z]{2,}$)");
while (true) { cout << "Nhap email: "; string email; cin >> email; if (regex_match(email, pattern)) { cout << "Email hop le!" << endl; break; } cout << "Email khong hop le, vui long nhap lai!" << endl; } return 0;}import java.util.Scanner;import java.util.regex.Pattern;
public class Main { public static void main(String[] args) { Pattern pattern = Pattern.compile("^[\\w.+-]+@[\\w-]+\\.[a-zA-Z]{2,}$"); Scanner sc = new Scanner(System.in);
while (true) { System.out.print("Nhap email: "); String email = sc.nextLine(); if (pattern.matcher(email).matches()) { System.out.println("Email hop le!"); break; } System.out.println("Email khong hop le, vui long nhap lai!"); } }}fun main() { val pattern = Regex("^[\\w.+-]+@[\\w-]+\\.[a-zA-Z]{2,}$")
while (true) { print("Nhap email: ") val email = readLine()!! if (pattern.matches(email)) { println("Email hop le!") break } println("Email khong hop le, vui long nhap lai!") }}import 'dart:io';
void main() { final pattern = RegExp(r"^[\w.+-]+@[\w-]+\.[a-zA-Z]{2,}$");
while (true) { stdout.write("Nhap email: "); final email = stdin.readLineSync()!; if (pattern.hasMatch(email)) { print("Email hop le!"); break; } print("Email khong hop le, vui long nhap lai!"); }}74. re - Trích xuất số điện thoại
Dùng re.findall để trích xuất tất cả số điện thoại (dạng 10 chữ số) xuất hiện trong một đoạn văn bản.
Xem đáp án
import re
text = "Liên hệ An qua 0901234567 hoặc Bình qua 0987654321 để biết thêm chi tiết."
phone_numbers = re.findall(r"\b0\d{9}\b", text)print(phone_numbers) # ['0901234567', '0987654321']#include <iostream>#include <regex>#include <string>using namespace std;
int main() { string text = "Lien he An qua 0901234567 hoac Binh qua 0987654321 de biet them chi tiet.";
regex pattern(R"(\b0\d{9}\b)"); auto begin = sregex_iterator(text.begin(), text.end(), pattern); auto end = sregex_iterator();
cout << "["; bool first = true; for (auto it = begin; it != end; ++it) { if (!first) cout << ", "; cout << "'" << it->str() << "'"; first = false; } cout << "]" << endl; return 0;}import java.util.*;import java.util.regex.*;
public class Main { public static void main(String[] args) { String text = "Lien he An qua 0901234567 hoac Binh qua 0987654321 de biet them chi tiet.";
Pattern pattern = Pattern.compile("\\b0\\d{9}\\b"); Matcher matcher = pattern.matcher(text);
List<String> phoneNumbers = new ArrayList<>(); while (matcher.find()) phoneNumbers.add(matcher.group());
System.out.println(phoneNumbers); }}fun main() { val text = "Lien he An qua 0901234567 hoac Binh qua 0987654321 de biet them chi tiet."
val pattern = Regex("\\b0\\d{9}\\b") val phoneNumbers = pattern.findAll(text).map { it.value }.toList()
println(phoneNumbers)}void main() { final text = "Lien he An qua 0901234567 hoac Binh qua 0987654321 de biet them chi tiet.";
final pattern = RegExp(r"\b0\d{9}\b"); final phoneNumbers = pattern.allMatches(text).map((m) => m.group(0)).toList();
print(phoneNumbers);}75. json - Đọc và ghi dữ liệu JSON
Dùng module json để lưu một dictionary vào file .json, sau đó đọc lại và in ra.
Xem đáp án
import json
data = {"name": "An", "age": 20, "mon_yeu_thich": ["Toán", "Tin"]}
with open("data.json", "w", encoding="utf-8") as f: json.dump(data, f, ensure_ascii=False, indent=2)
with open("data.json", "r", encoding="utf-8") as f: loaded_data = json.load(f)
print(loaded_data)// Yêu cầu thư viện nlohmann/json (header-only): https://github.com/nlohmann/json#include <iostream>#include <fstream>#include <nlohmann/json.hpp>using json = nlohmann::json;
int main() { json data = { {"name", "An"}, {"age", 20}, {"mon_yeu_thich", {"Toan", "Tin"}} };
std::ofstream fout("data.json"); fout << data.dump(2); fout.close();
std::ifstream fin("data.json"); json loadedData; fin >> loadedData;
std::cout << loadedData.dump() << std::endl; return 0;}// Yêu cầu thư viện org.json (org.json:json)import org.json.JSONObject;import java.io.*;import java.nio.file.*;
public class Main { public static void main(String[] args) throws IOException { JSONObject data = new JSONObject(); data.put("name", "An"); data.put("age", 20); data.put("mon_yeu_thich", new String[]{"Toan", "Tin"});
Files.writeString(Paths.get("data.json"), data.toString(2));
String content = Files.readString(Paths.get("data.json")); JSONObject loadedData = new JSONObject(content);
System.out.println(loadedData); }}// Yêu cầu thư viện org.json (org.json:json)import org.json.JSONObjectimport java.io.File
fun main() { val data = JSONObject() data.put("name", "An") data.put("age", 20) data.put("mon_yeu_thich", listOf("Toan", "Tin"))
File("data.json").writeText(data.toString(2))
val loadedData = JSONObject(File("data.json").readText()) println(loadedData)}import 'dart:io';import 'dart:convert';
void main() { var data = { "name": "An", "age": 20, "mon_yeu_thich": ["Toan", "Tin"] };
File("data.json").writeAsStringSync(JsonEncoder.withIndent(" ").convert(data));
var content = File("data.json").readAsStringSync(); var loadedData = jsonDecode(content);
print(loadedData);}76. os / pathlib - Liệt kê file trong thư mục
Dùng pathlib để liệt kê tất cả các file có đuôi .txt trong thư mục hiện tại.
Xem đáp án
from pathlib import Path
directory = Path(".")txt_files = list(directory.glob("*.txt"))
for f in txt_files: print(f.name)#include <iostream>#include <filesystem>namespace fs = std::filesystem;
int main() { for (auto& entry : fs::directory_iterator(".")) { if (entry.path().extension() == ".txt") { std::cout << entry.path().filename().string() << std::endl; } } return 0;}import java.io.File;
public class Main { public static void main(String[] args) { File directory = new File("."); File[] txtFiles = directory.listFiles((dir, name) -> name.endsWith(".txt"));
if (txtFiles != null) { for (File f : txtFiles) System.out.println(f.getName()); } }}import java.io.File
fun main() { val directory = File(".") val txtFiles = directory.listFiles { _, name -> name.endsWith(".txt") }
txtFiles?.forEach { println(it.name) }}import 'dart:io';
void main() { final directory = Directory("."); final txtFiles = directory.listSync().where((f) => f.path.endsWith(".txt"));
for (var f in txtFiles) { print(f.path.split(Platform.pathSeparator).last); }}77. random - Chọn ngẫu nhiên không trùng
Dùng random.sample để chọn ngẫu nhiên 5 số không trùng nhau từ 1 đến 45 (giống quay số trúng thưởng).
Xem đáp án
import random
winning_numbers = random.sample(range(1, 46), 5)print(sorted(winning_numbers))#include <iostream>#include <vector>#include <algorithm>#include <random>using namespace std;
int main() { vector<int> pool; for (int i = 1; i <= 45; i++) pool.push_back(i);
random_device rd; mt19937 g(rd()); shuffle(pool.begin(), pool.end(), g);
vector<int> winningNumbers(pool.begin(), pool.begin() + 5); sort(winningNumbers.begin(), winningNumbers.end());
cout << "["; for (size_t i = 0; i < winningNumbers.size(); i++) { cout << winningNumbers[i]; if (i + 1 < winningNumbers.size()) cout << ", "; } cout << "]" << endl; return 0;}import java.util.*;
public class Main { public static void main(String[] args) { List<Integer> pool = new ArrayList<>(); for (int i = 1; i <= 45; i++) pool.add(i); Collections.shuffle(pool);
List<Integer> winningNumbers = new ArrayList<>(pool.subList(0, 5)); Collections.sort(winningNumbers);
System.out.println(winningNumbers); }}fun main() { val pool = (1..45).toMutableList() pool.shuffle()
val winningNumbers = pool.take(5).sorted() println(winningNumbers)}import 'dart:math';
void main() { var pool = List.generate(45, (i) => i + 1); pool.shuffle(Random());
var winningNumbers = pool.take(5).toList()..sort(); print(winningNumbers);}78. statistics - Thống kê cơ bản
Dùng module statistics để tính trung bình cộng, trung vị (median) và độ lệch chuẩn (standard deviation) của một list điểm số.
Xem đáp án
import statistics
score = [8, 7.5, 9, 6, 10, 8.5, 7]
print("Trung bình:", statistics.mean(score))print("Trung vị:", statistics.median(score))print("Độ lệch chuẩn:", round(statistics.stdev(score), 2))#include <iostream>#include <vector>#include <algorithm>#include <cmath>using namespace std;
double mean(const vector<double>& v) { double sum = 0; for (double x : v) sum += x; return sum / v.size();}
double median(vector<double> v) { sort(v.begin(), v.end()); size_t n = v.size(); if (n % 2 == 0) return (v[n / 2 - 1] + v[n / 2]) / 2.0; return v[n / 2];}
double stdev(const vector<double>& v) { double m = mean(v); double sumSq = 0; for (double x : v) sumSq += (x - m) * (x - m); return sqrt(sumSq / (v.size() - 1));}
int main() { vector<double> score = {8, 7.5, 9, 6, 10, 8.5, 7};
cout << "Trung binh: " << mean(score) << endl; cout << "Trung vi: " << median(score) << endl; cout << "Do lech chuan: " << round(stdev(score) * 100) / 100 << endl; return 0;}import java.util.*;
public class Main { static double mean(List<Double> v) { double sum = 0; for (double x : v) sum += x; return sum / v.size(); }
static double median(List<Double> v) { List<Double> sorted = new ArrayList<>(v); Collections.sort(sorted); int n = sorted.size(); if (n % 2 == 0) return (sorted.get(n / 2 - 1) + sorted.get(n / 2)) / 2.0; return sorted.get(n / 2); }
static double stdev(List<Double> v) { double m = mean(v); double sumSq = 0; for (double x : v) sumSq += (x - m) * (x - m); return Math.sqrt(sumSq / (v.size() - 1)); }
public static void main(String[] args) { List<Double> score = List.of(8.0, 7.5, 9.0, 6.0, 10.0, 8.5, 7.0);
System.out.println("Trung binh: " + mean(score)); System.out.println("Trung vi: " + median(score)); System.out.println("Do lech chuan: " + Math.round(stdev(score) * 100) / 100.0); }}fun main() { val score = listOf(8.0, 7.5, 9.0, 6.0, 10.0, 8.5, 7.0)
val mean = score.average() val sorted = score.sorted() val n = sorted.size val median = if (n % 2 == 0) (sorted[n / 2 - 1] + sorted[n / 2]) / 2.0 else sorted[n / 2] val stdev = Math.sqrt(score.sumOf { (it - mean) * (it - mean) } / (n - 1))
println("Trung binh: $mean") println("Trung vi: $median") println("Do lech chuan: ${Math.round(stdev * 100) / 100.0}")}import 'dart:math';
void main() { var score = [8.0, 7.5, 9.0, 6.0, 10.0, 8.5, 7.0];
var mean = score.reduce((a, b) => a + b) / score.length;
var sorted = [...score]..sort(); int n = sorted.length; var median = n % 2 == 0 ? (sorted[n ~/ 2 - 1] + sorted[n ~/ 2]) / 2.0 : sorted[n ~/ 2];
var sumSq = score.fold(0.0, (sum, x) => sum + (x - mean) * (x - mean)); var stdev = sqrt(sumSq / (n - 1));
print("Trung binh: $mean"); print("Trung vi: $median"); print("Do lech chuan: ${(stdev * 100).round() / 100}");}Nhóm 10: Xử lý ngoại lệ nâng cao
Phần tiêu đề “Nhóm 10: Xử lý ngoại lệ nâng cao”Xem thêm lý thuyết: Exception Handling (Try/Except).
79. Phân cấp Exception tùy chỉnh
Tạo một hệ thống exception phân cấp cho việc rút tiền ngân hàng: AccountError (lớp cha), InsufficientBalanceError và InvalidAmountError (kế thừa từ lớp cha).
Xem đáp án
class AccountError(Exception): pass
class InsufficientBalanceError(AccountError): pass
class InvalidAmountError(AccountError): pass
def withdraw(balance, withdrawal_amount): if withdrawal_amount <= 0: raise InvalidAmountError("Số tiền rút phải lớn hơn 0") if withdrawal_amount > balance: raise InsufficientBalanceError("Số dư không đủ để rút") return balance - withdrawal_amount
for value in [-100, 5000, 100]: try: print(withdraw(1000, value)) except AccountError as e: print(f"Lỗi ({type(e).__name__}): {e}")#include <iostream>#include <stdexcept>#include <string>#include <vector>using namespace std;
class AccountError : public runtime_error {public: AccountError(const string& msg) : runtime_error(msg) {} virtual string name() const { return "AccountError"; }};
class InsufficientBalanceError : public AccountError {public: InsufficientBalanceError(const string& msg) : AccountError(msg) {} string name() const override { return "InsufficientBalanceError"; }};
class InvalidAmountError : public AccountError {public: InvalidAmountError(const string& msg) : AccountError(msg) {} string name() const override { return "InvalidAmountError"; }};
double withdraw(double balance, double amount) { if (amount <= 0) throw InvalidAmountError("So tien rut phai lon hon 0"); if (amount > balance) throw InsufficientBalanceError("So du khong du de rut"); return balance - amount;}
int main() { vector<double> values = {-100, 5000, 100}; for (double value : values) { try { cout << withdraw(1000, value) << endl; } catch (const AccountError& e) { cout << "Loi (" << e.name() << "): " << e.what() << endl; } } return 0;}public class Main { static class AccountError extends RuntimeException { AccountError(String msg) { super(msg); } }
static class InsufficientBalanceError extends AccountError { InsufficientBalanceError(String msg) { super(msg); } }
static class InvalidAmountError extends AccountError { InvalidAmountError(String msg) { super(msg); } }
static double withdraw(double balance, double amount) { if (amount <= 0) throw new InvalidAmountError("So tien rut phai lon hon 0"); if (amount > balance) throw new InsufficientBalanceError("So du khong du de rut"); return balance - amount; }
public static void main(String[] args) { double[] values = {-100, 5000, 100}; for (double value : values) { try { System.out.println(withdraw(1000, value)); } catch (AccountError e) { System.out.println("Loi (" + e.getClass().getSimpleName() + "): " + e.getMessage()); } } }}open class AccountError(message: String) : Exception(message)class InsufficientBalanceError(message: String) : AccountError(message)class InvalidAmountError(message: String) : AccountError(message)
fun withdraw(balance: Double, amount: Double): Double { if (amount <= 0) throw InvalidAmountError("So tien rut phai lon hon 0") if (amount > balance) throw InsufficientBalanceError("So du khong du de rut") return balance - amount}
fun main() { val values = listOf(-100.0, 5000.0, 100.0) for (value in values) { try { println(withdraw(1000.0, value)) } catch (e: AccountError) { println("Loi (${e::class.simpleName}): ${e.message}") } }}class AccountError implements Exception { final String message; AccountError(this.message); String get name => "AccountError"; @override String toString() => message;}
class InsufficientBalanceError extends AccountError { InsufficientBalanceError(super.message); @override String get name => "InsufficientBalanceError";}
class InvalidAmountError extends AccountError { InvalidAmountError(super.message); @override String get name => "InvalidAmountError";}
double withdraw(double balance, double amount) { if (amount <= 0) throw InvalidAmountError("So tien rut phai lon hon 0"); if (amount > balance) throw InsufficientBalanceError("So du khong du de rut"); return balance - amount;}
void main() { var values = [-100.0, 5000.0, 100.0]; for (var value in values) { try { print(withdraw(1000, value)); } on AccountError catch (e) { print("Loi (${e.name}): ${e.message}"); } }}80. Chained Exception (raise ... from ...)
Viết chương trình đọc số từ chuỗi, khi gặp lỗi định dạng thì ném ra một exception mới nhưng vẫn giữ lại nguyên nhân gốc bằng raise ... from ....
Xem đáp án
class InvalidDataError(Exception): pass
def process_data(text): try: return int(text) except ValueError as loi_goc: raise InvalidDataError(f"Không thể xử lý dữ liệu: {text!r}") from loi_goc
try: process_data("abc")except InvalidDataError as e: print("Lỗi:", e) print("Nguyên nhân gốc:", e.__cause__)#include <iostream>#include <stdexcept>#include <string>using namespace std;
class InvalidDataError : public runtime_error {public: exception_ptr cause; InvalidDataError(const string& msg, exception_ptr c) : runtime_error(msg), cause(c) {}};
int processData(const string& text) { try { size_t pos; int result = stoi(text, &pos); if (pos != text.size()) throw invalid_argument("khong hop le"); return result; } catch (...) { throw InvalidDataError("Khong the xu ly du lieu: '" + text + "'", current_exception()); }}
int main() { try { processData("abc"); } catch (const InvalidDataError& e) { cout << "Loi: " << e.what() << endl; try { rethrow_exception(e.cause); } catch (const exception& inner) { cout << "Nguyen nhan goc: " << inner.what() << endl; } } return 0;}public class Main { static class InvalidDataError extends RuntimeException { InvalidDataError(String msg, Throwable cause) { super(msg, cause); } }
static int processData(String text) { try { return Integer.parseInt(text); } catch (NumberFormatException loiGoc) { throw new InvalidDataError("Khong the xu ly du lieu: '" + text + "'", loiGoc); } }
public static void main(String[] args) { try { processData("abc"); } catch (InvalidDataError e) { System.out.println("Loi: " + e.getMessage()); System.out.println("Nguyen nhan goc: " + e.getCause()); } }}class InvalidDataError(message: String, cause: Throwable) : Exception(message, cause)
fun processData(text: String): Int { return try { text.toInt() } catch (loiGoc: NumberFormatException) { throw InvalidDataError("Khong the xu ly du lieu: '$text'", loiGoc) }}
fun main() { try { processData("abc") } catch (e: InvalidDataError) { println("Loi: ${e.message}") println("Nguyen nhan goc: ${e.cause}") }}class InvalidDataError implements Exception { final String message; final Object cause; InvalidDataError(this.message, this.cause); @override String toString() => message;}
int processData(String text) { try { return int.parse(text); } catch (loiGoc) { throw InvalidDataError("Khong the xu ly du lieu: '$text'", loiGoc); }}
void main() { try { processData("abc"); } on InvalidDataError catch (e) { print("Loi: ${e.message}"); print("Nguyen nhan goc: ${e.cause}"); }}81. Context Manager xử lý lỗi (__exit__ trả về True)
Viết context manager SuppressError cho phép bỏ qua một loại exception cụ thể xảy ra bên trong khối with.
Xem đáp án
class SuppressError: def __init__(self, *error_types): self.error_types = error_types
def __enter__(self): return self
def __exit__(self, exc_type, exc_value, traceback): if exc_type in self.error_types: print(f"Đã bỏ qua lỗi: {exc_value}") return True # True nghĩa là exception được "nuốt", chương trình chạy tiếp return False
with SuppressError(ZeroDivisionError): print(10 / 0)
print("Chương trình vẫn chạy tiếp bình thường")// C++ khong co context manager (with) nhu Python; dung RAII + try/catch de mo phong.#include <iostream>#include <stdexcept>using namespace std;
void suppressDivideByZero(int a, int b) { try { if (b == 0) throw runtime_error("division by zero"); cout << a / b << endl; } catch (const exception& e) { cout << "Da bo qua loi: " << e.what() << endl; }}
int main() { suppressDivideByZero(10, 0); cout << "Chuong trinh van chay tiep binh thuong" << endl; return 0;}// Java khong co "with"/context-manager nhu Python; dung try/catch de mo phong hanh vi tuong tu.public class Main { static void suppressArithmeticError(Runnable block) { try { block.run(); } catch (ArithmeticException e) { System.out.println("Da bo qua loi: " + e.getMessage()); } }
public static void main(String[] args) { suppressArithmeticError(() -> System.out.println(10 / 0)); System.out.println("Chuong trinh van chay tiep binh thuong"); }}fun suppressError(block: () -> Unit) { try { block() } catch (e: ArithmeticException) { println("Da bo qua loi: ${e.message}") }}
fun main() { suppressError { println(10 / 0) } println("Chuong trinh van chay tiep binh thuong")}void suppressError(void Function() block) { try { block(); } catch (e) { print("Da bo qua loi: $e"); }}
void main() { suppressError(() => print(10 ~/ 0)); print("Chuong trinh van chay tiep binh thuong");}82. finally luôn được thực thi
Viết chương trình minh họa khối finally luôn chạy dù có exception hay không, hay dù có return sớm trong hàm.
Xem đáp án
def read_data(should_fail): try: if should_fail: raise ValueError("Dữ liệu lỗi") return "Đọc dữ liệu thành công" finally: print("Dọn dẹp tài nguyên (luôn chạy)")
print(read_data(False))
try: read_data(True)except ValueError as e: print("Bắt được lỗi:", e)#include <iostream>#include <stdexcept>#include <string>using namespace std;
// C++ khong co "finally"; dung mot lop RAII de dam bao doan don dep luon chay.struct Cleanup { ~Cleanup() { cout << "Don dep tai nguyen (luon chay)" << endl; }};
string readData(bool shouldFail) { Cleanup cleanup; if (shouldFail) throw runtime_error("Du lieu loi"); return "Doc du lieu thanh cong";}
int main() { cout << readData(false) << endl;
try { readData(true); } catch (const runtime_error& e) { cout << "Bat duoc loi: " << e.what() << endl; } return 0;}public class Main { static String readData(boolean shouldFail) { try { if (shouldFail) throw new IllegalArgumentException("Du lieu loi"); return "Doc du lieu thanh cong"; } finally { System.out.println("Don dep tai nguyen (luon chay)"); } }
public static void main(String[] args) { System.out.println(readData(false));
try { readData(true); } catch (IllegalArgumentException e) { System.out.println("Bat duoc loi: " + e.getMessage()); } }}fun readData(shouldFail: Boolean): String { try { if (shouldFail) throw IllegalArgumentException("Du lieu loi") return "Doc du lieu thanh cong" } finally { println("Don dep tai nguyen (luon chay)") }}
fun main() { println(readData(false))
try { readData(true) } catch (e: IllegalArgumentException) { println("Bat duoc loi: ${e.message}") }}String readData(bool shouldFail) { try { if (shouldFail) throw ArgumentError("Du lieu loi"); return "Doc du lieu thanh cong"; } finally { print("Don dep tai nguyen (luon chay)"); }}
void main() { print(readData(false));
try { readData(true); } on ArgumentError catch (e) { print("Bat duoc loi: ${e.message}"); }}83. Validate dữ liệu nhập với nhiều loại lỗi
Viết hàm input_age() yêu cầu người dùng nhập tuổi, bắt cả lỗi ValueError (không phải số) lẫn lỗi tuổi không hợp lệ (âm hoặc quá lớn), cho nhập lại đến khi hợp lệ.
Xem đáp án
class InvalidAgeError(Exception): pass
def input_age(): while True: try: age = int(input("Nhập tuổi của bạn: ")) if age < 0 or age > 150: raise InvalidAgeError("Tuổi phải trong khoảng 0-150") return age except ValueError: print("Vui lòng nhập một số nguyên hợp lệ!") except InvalidAgeError as e: print(f"Lỗi: {e}, vui lòng nhập lại!")
age = input_age()print("Tuổi hợp lệ:", age)#include <iostream>#include <stdexcept>#include <sstream>using namespace std;
class InvalidAgeError : public runtime_error {public: InvalidAgeError(const string& msg) : runtime_error(msg) {}};
int inputAge() { while (true) { cout << "Nhap tuoi cua ban: "; string input; cin >> input; try { size_t pos; int age = stoi(input, &pos); if (pos != input.size()) throw invalid_argument(""); if (age < 0 || age > 150) throw InvalidAgeError("Tuoi phai trong khoang 0-150"); return age; } catch (const InvalidAgeError& e) { cout << "Loi: " << e.what() << ", vui long nhap lai!" << endl; } catch (...) { cout << "Vui long nhap mot so nguyen hop le!" << endl; } }}
int main() { int age = inputAge(); cout << "Tuoi hop le: " << age << endl; return 0;}import java.util.Scanner;
public class Main { static class InvalidAgeError extends RuntimeException { InvalidAgeError(String msg) { super(msg); } }
static int inputAge(Scanner sc) { while (true) { System.out.print("Nhap tuoi cua ban: "); try { int age = Integer.parseInt(sc.nextLine().trim()); if (age < 0 || age > 150) throw new InvalidAgeError("Tuoi phai trong khoang 0-150"); return age; } catch (NumberFormatException e) { System.out.println("Vui long nhap mot so nguyen hop le!"); } catch (InvalidAgeError e) { System.out.println("Loi: " + e.getMessage() + ", vui long nhap lai!"); } } }
public static void main(String[] args) { Scanner sc = new Scanner(System.in); int age = inputAge(sc); System.out.println("Tuoi hop le: " + age); }}class InvalidAgeError(message: String) : Exception(message)
fun inputAge(): Int { while (true) { print("Nhap tuoi cua ban: ") val input = readLine()!!.trim() try { val age = input.toInt() if (age < 0 || age > 150) throw InvalidAgeError("Tuoi phai trong khoang 0-150") return age } catch (e: NumberFormatException) { println("Vui long nhap mot so nguyen hop le!") } catch (e: InvalidAgeError) { println("Loi: ${e.message}, vui long nhap lai!") } }}
fun main() { val age = inputAge() println("Tuoi hop le: $age")}import 'dart:io';
class InvalidAgeError implements Exception { final String message; InvalidAgeError(this.message);}
int inputAge() { while (true) { stdout.write("Nhap tuoi cua ban: "); final input = stdin.readLineSync()!.trim(); final age = int.tryParse(input); if (age == null) { print("Vui long nhap mot so nguyen hop le!"); continue; } try { if (age < 0 || age > 150) throw InvalidAgeError("Tuoi phai trong khoang 0-150"); return age; } on InvalidAgeError catch (e) { print("Loi: ${e.message}, vui long nhap lai!"); } }}
void main() { final age = inputAge(); print("Tuoi hop le: $age");}Nhóm 11: Thuật toán số học & ma trận nâng cao
Phần tiêu đề “Nhóm 11: Thuật toán số học & ma trận nâng cao”84. Sàng Eratosthenes
Cài đặt thuật toán Sàng Eratosthenes để tìm tất cả số nguyên tố nhỏ hơn n, hiệu quả hơn nhiều so với kiểm tra từng số.
Ví dụ:
Input: n=20Output: [2, 3, 5, 7, 11, 13, 17, 19]Xem đáp án
def sieve_of_eratosthenes(n): is_prime = [True] * n is_prime[0:2] = [False, False] # 0 và 1 không phải số nguyên tố
for i in range(2, int(n ** 0.5) + 1): if is_prime[i]: for j in range(i * i, n, i): is_prime[j] = False
return [num for num, ok in enumerate(is_prime) if ok]
print(sieve_of_eratosthenes(50))#include <iostream>#include <vector>using namespace std;
vector<int> sieveOfEratosthenes(int n) { vector<bool> isPrime(n, true); if (n > 0) isPrime[0] = false; if (n > 1) isPrime[1] = false;
for (int i = 2; i * i < n; i++) { if (isPrime[i]) { for (int j = i * i; j < n; j += i) isPrime[j] = false; } }
vector<int> result; for (int num = 0; num < n; num++) if (isPrime[num]) result.push_back(num); return result;}
int main() { vector<int> primes = sieveOfEratosthenes(50); cout << "["; for (size_t i = 0; i < primes.size(); i++) { cout << primes[i]; if (i + 1 < primes.size()) cout << ", "; } cout << "]" << endl; return 0;}import java.util.*;
public class Main { static List<Integer> sieveOfEratosthenes(int n) { boolean[] isPrime = new boolean[n]; Arrays.fill(isPrime, true); if (n > 0) isPrime[0] = false; if (n > 1) isPrime[1] = false;
for (int i = 2; (long) i * i < n; i++) { if (isPrime[i]) { for (int j = i * i; j < n; j += i) isPrime[j] = false; } }
List<Integer> result = new ArrayList<>(); for (int num = 0; num < n; num++) if (isPrime[num]) result.add(num); return result; }
public static void main(String[] args) { System.out.println(sieveOfEratosthenes(50)); }}fun sieveOfEratosthenes(n: Int): List<Int> { val isPrime = BooleanArray(n) { true } if (n > 0) isPrime[0] = false if (n > 1) isPrime[1] = false
var i = 2 while (i * i < n) { if (isPrime[i]) { var j = i * i while (j < n) { isPrime[j] = false j += i } } i++ }
return (0 until n).filter { isPrime[it] }}
fun main() { println(sieveOfEratosthenes(50))}List<int> sieveOfEratosthenes(int n) { var isPrime = List.filled(n, true); if (n > 0) isPrime[0] = false; if (n > 1) isPrime[1] = false;
for (int i = 2; i * i < n; i++) { if (isPrime[i]) { for (int j = i * i; j < n; j += i) { isPrime[j] = false; } } }
return [for (int num = 0; num < n; num++) if (isPrime[num]) num];}
void main() { print(sieveOfEratosthenes(50));}85. Nhân 2 ma trận
Viết hàm nhân 2 ma trận (list 2 chiều) với nhau, không dùng thư viện ngoài.
Ví dụ:
Input: a=[[1,2],[3,4]], b=[[5,6],[7,8]]Output: [[19, 22], [43, 50]]Xem đáp án
def matrix_multiply(a, b): rows_a, cols_a = len(a), len(a[0]) cols_b = len(b[0])
result = [[0] * cols_b for _ in range(rows_a)]
for i in range(rows_a): for j in range(cols_b): for k in range(cols_a): result[i][j] += a[i][k] * b[k][j]
return result
a = [[1, 2], [3, 4]]b = [[5, 6], [7, 8]]print(matrix_multiply(a, b)) # [[19, 22], [43, 50]]#include <iostream>#include <vector>using namespace std;
vector<vector<int>> matrixMultiply(vector<vector<int>>& a, vector<vector<int>>& b) { int rowsA = a.size(), colsA = a[0].size(), colsB = b[0].size(); vector<vector<int>> result(rowsA, vector<int>(colsB, 0));
for (int i = 0; i < rowsA; i++) for (int j = 0; j < colsB; j++) for (int k = 0; k < colsA; k++) result[i][j] += a[i][k] * b[k][j];
return result;}
int main() { vector<vector<int>> a = {{1, 2}, {3, 4}}; vector<vector<int>> b = {{5, 6}, {7, 8}}; auto result = matrixMultiply(a, b);
cout << "["; for (size_t i = 0; i < result.size(); i++) { cout << "["; for (size_t j = 0; j < result[i].size(); j++) { cout << result[i][j]; if (j + 1 < result[i].size()) cout << ", "; } cout << "]"; if (i + 1 < result.size()) cout << ", "; } cout << "]" << endl; return 0;}import java.util.Arrays;
public class Main { static int[][] matrixMultiply(int[][] a, int[][] b) { int rowsA = a.length, colsA = a[0].length, colsB = b[0].length; int[][] result = new int[rowsA][colsB];
for (int i = 0; i < rowsA; i++) for (int j = 0; j < colsB; j++) for (int k = 0; k < colsA; k++) result[i][j] += a[i][k] * b[k][j];
return result; }
public static void main(String[] args) { int[][] a = {{1, 2}, {3, 4}}; int[][] b = {{5, 6}, {7, 8}}; int[][] result = matrixMultiply(a, b);
System.out.println(Arrays.deepToString(result)); }}fun matrixMultiply(a: Array<IntArray>, b: Array<IntArray>): Array<IntArray> { val rowsA = a.size val colsA = a[0].size val colsB = b[0].size val result = Array(rowsA) { IntArray(colsB) }
for (i in 0 until rowsA) for (j in 0 until colsB) for (k in 0 until colsA) result[i][j] += a[i][k] * b[k][j]
return result}
fun main() { val a = arrayOf(intArrayOf(1, 2), intArrayOf(3, 4)) val b = arrayOf(intArrayOf(5, 6), intArrayOf(7, 8)) val result = matrixMultiply(a, b)
println(result.map { it.toList() })}List<List<int>> matrixMultiply(List<List<int>> a, List<List<int>> b) { int rowsA = a.length, colsA = a[0].length, colsB = b[0].length; var result = List.generate(rowsA, (_) => List.filled(colsB, 0));
for (int i = 0; i < rowsA; i++) { for (int j = 0; j < colsB; j++) { for (int k = 0; k < colsA; k++) { result[i][j] += a[i][k] * b[k][j]; } } }
return result;}
void main() { var a = [[1, 2], [3, 4]]; var b = [[5, 6], [7, 8]]; print(matrixMultiply(a, b));}86. Chuyển vị ma trận (Transpose)
Viết hàm chuyển vị một ma trận (đổi hàng thành cột), không dùng thư viện ngoài.
Ví dụ:
Input: [[1, 2, 3], [4, 5, 6]]Output: [[1, 4], [2, 5], [3, 6]]Xem đáp án
def transpose(matrix): rows = len(matrix) cols = len(matrix[0])
result = [[0] * rows for _ in range(cols)]
for i in range(rows): for j in range(cols): result[j][i] = matrix[i][j]
return result
matrix = [[1, 2, 3], [4, 5, 6]]print(transpose(matrix)) # [[1, 4], [2, 5], [3, 6]]#include <iostream>#include <vector>using namespace std;
vector<vector<int>> transpose(vector<vector<int>>& matrix) { int rows = matrix.size(), cols = matrix[0].size(); vector<vector<int>> result(cols, vector<int>(rows, 0));
for (int i = 0; i < rows; i++) for (int j = 0; j < cols; j++) result[j][i] = matrix[i][j];
return result;}
int main() { vector<vector<int>> matrix = {{1, 2, 3}, {4, 5, 6}}; auto result = transpose(matrix);
cout << "["; for (size_t i = 0; i < result.size(); i++) { cout << "["; for (size_t j = 0; j < result[i].size(); j++) { cout << result[i][j]; if (j + 1 < result[i].size()) cout << ", "; } cout << "]"; if (i + 1 < result.size()) cout << ", "; } cout << "]" << endl; return 0;}import java.util.Arrays;
public class Main { static int[][] transpose(int[][] matrix) { int rows = matrix.length, cols = matrix[0].length; int[][] result = new int[cols][rows];
for (int i = 0; i < rows; i++) for (int j = 0; j < cols; j++) result[j][i] = matrix[i][j];
return result; }
public static void main(String[] args) { int[][] matrix = {{1, 2, 3}, {4, 5, 6}}; System.out.println(Arrays.deepToString(transpose(matrix))); }}fun transpose(matrix: Array<IntArray>): Array<IntArray> { val rows = matrix.size val cols = matrix[0].size val result = Array(cols) { IntArray(rows) }
for (i in 0 until rows) for (j in 0 until cols) result[j][i] = matrix[i][j]
return result}
fun main() { val matrix = arrayOf(intArrayOf(1, 2, 3), intArrayOf(4, 5, 6)) println(transpose(matrix).map { it.toList() })}List<List<int>> transpose(List<List<int>> matrix) { int rows = matrix.length, cols = matrix[0].length; var result = List.generate(cols, (_) => List.filled(rows, 0));
for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { result[j][i] = matrix[i][j]; } }
return result;}
void main() { var matrix = [[1, 2, 3], [4, 5, 6]]; print(transpose(matrix));}87. Xoay ma trận vuông 90 độ
Viết hàm xoay một ma trận vuông 90 độ theo chiều kim đồng hồ, không dùng bộ nhớ phụ (in-place).
Ví dụ:
Input: [[1, 2, 3], [4, 5, 6], [7, 8, 9]]Output: [[7, 4, 1], [8, 5, 2], [9, 6, 3]]Xem đáp án
def rotate_90(matrix): n = len(matrix)
# Bước 1: chuyển vị ma trận for i in range(n): for j in range(i + 1, n): matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
# Bước 2: đảo ngược từng hàng for row in matrix: row.reverse()
return matrix
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]print(rotate_90(matrix)) # [[7, 4, 1], [8, 5, 2], [9, 6, 3]]#include <iostream>#include <vector>#include <algorithm>using namespace std;
vector<vector<int>>& rotate90(vector<vector<int>>& matrix) { int n = matrix.size();
// Buoc 1: chuyen vi ma tran for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) swap(matrix[i][j], matrix[j][i]);
// Buoc 2: dao nguoc tung hang for (auto& row : matrix) reverse(row.begin(), row.end());
return matrix;}
int main() { vector<vector<int>> matrix = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}; rotate90(matrix);
cout << "["; for (size_t i = 0; i < matrix.size(); i++) { cout << "["; for (size_t j = 0; j < matrix[i].size(); j++) { cout << matrix[i][j]; if (j + 1 < matrix[i].size()) cout << ", "; } cout << "]"; if (i + 1 < matrix.size()) cout << ", "; } cout << "]" << endl; return 0;}import java.util.Arrays;import java.util.Collections;
public class Main { static int[][] rotate90(int[][] matrix) { int n = matrix.length;
for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { int tmp = matrix[i][j]; matrix[i][j] = matrix[j][i]; matrix[j][i] = tmp; } }
for (int[] row : matrix) { for (int l = 0, r = row.length - 1; l < r; l++, r--) { int tmp = row[l]; row[l] = row[r]; row[r] = tmp; } }
return matrix; }
public static void main(String[] args) { int[][] matrix = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}; System.out.println(Arrays.deepToString(rotate90(matrix))); }}fun rotate90(matrix: Array<IntArray>): Array<IntArray> { val n = matrix.size
for (i in 0 until n) { for (j in i + 1 until n) { val tmp = matrix[i][j] matrix[i][j] = matrix[j][i] matrix[j][i] = tmp } }
for (row in matrix) row.reverse()
return matrix}
fun main() { val matrix = arrayOf(intArrayOf(1, 2, 3), intArrayOf(4, 5, 6), intArrayOf(7, 8, 9)) println(rotate90(matrix).map { it.toList() })}List<List<int>> rotate90(List<List<int>> matrix) { int n = matrix.length;
for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { int tmp = matrix[i][j]; matrix[i][j] = matrix[j][i]; matrix[j][i] = tmp; } }
for (var row in matrix) { var reversed = row.reversed.toList(); row.setAll(0, reversed); }
return matrix;}
void main() { var matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]; print(rotate90(matrix));}88. Kiểm tra số chính phương không dùng sqrt
Kiểm tra một số nguyên dương có phải là số chính phương hay không, dùng thuật toán tìm kiếm nhị phân thay vì math.sqrt.
Ví dụ:
Input: 16Output: True
Input: 18Output: FalseXem đáp án
def is_perfect_square(n): if n < 0: return False
left, right = 0, n while left <= right: mid = (left + right) // 2 square = mid * mid
if square == n: return True elif square < n: left = mid + 1 else: right = mid - 1
return False
print(is_perfect_square(16)) # Trueprint(is_perfect_square(18)) # False#include <iostream>using namespace std;
bool isPerfectSquare(long long n) { if (n < 0) return false;
long long left = 0, right = n; while (left <= right) { long long mid = (left + right) / 2; long long square = mid * mid;
if (square == n) return true; else if (square < n) left = mid + 1; else right = mid - 1; }
return false;}
int main() { cout << boolalpha << isPerfectSquare(16) << endl; cout << boolalpha << isPerfectSquare(18) << endl; return 0;}public class Main { static boolean isPerfectSquare(long n) { if (n < 0) return false;
long left = 0, right = n; while (left <= right) { long mid = (left + right) / 2; long square = mid * mid;
if (square == n) return true; else if (square < n) left = mid + 1; else right = mid - 1; }
return false; }
public static void main(String[] args) { System.out.println(isPerfectSquare(16)); System.out.println(isPerfectSquare(18)); }}fun isPerfectSquare(n: Long): Boolean { if (n < 0) return false
var left = 0L var right = n while (left <= right) { val mid = (left + right) / 2 val square = mid * mid
when { square == n -> return true square < n -> left = mid + 1 else -> right = mid - 1 } }
return false}
fun main() { println(isPerfectSquare(16)) println(isPerfectSquare(18))}bool isPerfectSquare(int n) { if (n < 0) return false;
int left = 0, right = n; while (left <= right) { int mid = (left + right) ~/ 2; int square = mid * mid;
if (square == n) return true; if (square < n) { left = mid + 1; } else { right = mid - 1; } }
return false;}
void main() { print(isPerfectSquare(16)); print(isPerfectSquare(18));}89. Số nguyên tố Mersenne
Số Mersenne có dạng 2p - 1. Viết chương trình kiểm tra với p là số nguyên tố, số Mersenne tương ứng có phải cũng là số nguyên tố hay không.
Xem đáp án
def is_prime(n): if n < 2: return False for i in range(2, int(n ** 0.5) + 1): if n % i == 0: return False return True
def check_mersenne(p): if not is_prime(p): return None # p phải là số nguyên tố
mersenne_number = 2 ** p - 1 return mersenne_number, is_prime(mersenne_number)
for p in [2, 3, 5, 7, 11]: print(f"p={p}: {check_mersenne(p)}")#include <iostream>#include <string>using namespace std;
bool isPrime(long long n) { if (n < 2) return false; for (long long i = 2; i * i <= n; i++) { if (n % i == 0) return false; } return true;}
string checkMersenne(int p) { if (!isPrime(p)) return "None";
long long mersenneNumber = (1LL << p) - 1; return "(" + to_string(mersenneNumber) + ", " + (isPrime(mersenneNumber) ? "true" : "false") + ")";}
int main() { int ps[] = {2, 3, 5, 7, 11}; for (int p : ps) { cout << "p=" << p << ": " << checkMersenne(p) << endl; } return 0;}public class Main { static boolean isPrime(long n) { if (n < 2) return false; for (long i = 2; i * i <= n; i++) { if (n % i == 0) return false; } return true; }
static String checkMersenne(int p) { if (!isPrime(p)) return "None";
long mersenneNumber = (1L << p) - 1; return "(" + mersenneNumber + ", " + isPrime(mersenneNumber) + ")"; }
public static void main(String[] args) { int[] ps = {2, 3, 5, 7, 11}; for (int p : ps) { System.out.println("p=" + p + ": " + checkMersenne(p)); } }}fun isPrime(n: Long): Boolean { if (n < 2) return false var i = 2L while (i * i <= n) { if (n % i == 0L) return false i++ } return true}
fun checkMersenne(p: Int): String { if (!isPrime(p.toLong())) return "None"
val mersenneNumber = (1L shl p) - 1 return "($mersenneNumber, ${isPrime(mersenneNumber)})"}
fun main() { val ps = listOf(2, 3, 5, 7, 11) for (p in ps) { println("p=$p: ${checkMersenne(p)}") }}bool isPrime(int n) { if (n < 2) return false; for (int i = 2; i * i <= n; i++) { if (n % i == 0) return false; } return true;}
String checkMersenne(int p) { if (!isPrime(p)) return "None";
int mersenneNumber = (1 << p) - 1; return "($mersenneNumber, ${isPrime(mersenneNumber)})";}
void main() { var ps = [2, 3, 5, 7, 11]; for (var p in ps) { print("p=$p: ${checkMersenne(p)}"); }}Nhóm 12: Đồ thị cơ bản (Graph)
Phần tiêu đề “Nhóm 12: Đồ thị cơ bản (Graph)”BFS (Breadth-First Search - duyệt theo chiều rộng) thăm hết các đỉnh gần nhất trước, giống lan ra từng vòng tròn đồng tâm. DFS (Depth-First Search - duyệt theo chiều sâu) đi sâu theo một nhánh đến hết mức có thể rồi mới quay lại thử nhánh khác. Đồ thị trong nhóm bài này được biểu diễn bằng adjacency list (danh sách kề): một dictionary mà mỗi key là 1 đỉnh, value là list các đỉnh kề với nó.
90. Duyệt đồ thị theo chiều rộng (BFS)
Cho một đồ thị biểu diễn bằng dictionary (adjacency list), duyệt đồ thị theo chiều rộng (BFS) bắt đầu từ 1 đỉnh.
Ví dụ:
Input: graph={"A":["B","C"],"B":["A","D","E"],"C":["A","F"],"D":["B"],"E":["B","F"],"F":["C","E"]}, start="A"Output: ['A', 'B', 'C', 'D', 'E', 'F']Xem đáp án
from collections import deque
def bfs(graph, start): visited = {start} queue = deque([start]) visit_order = []
while queue: vertex = queue.popleft() visit_order.append(vertex)
for neighbor in graph[vertex]: if neighbor not in visited: visited.add(neighbor) queue.append(neighbor)
return visit_order
graph = { "A": ["B", "C"], "B": ["A", "D", "E"], "C": ["A", "F"], "D": ["B"], "E": ["B", "F"], "F": ["C", "E"],}
print(bfs(graph, "A"))#include <iostream>#include <vector>#include <queue>#include <set>#include <map>#include <string>using namespace std;
vector<string> bfs(map<string, vector<string>>& graph, string start) { set<string> visited = {start}; queue<string> q; q.push(start); vector<string> visitOrder;
while (!q.empty()) { string vertex = q.front(); q.pop(); visitOrder.push_back(vertex);
for (const string& neighbor : graph[vertex]) { if (visited.find(neighbor) == visited.end()) { visited.insert(neighbor); q.push(neighbor); } } }
return visitOrder;}
int main() { map<string, vector<string>> graph = { {"A", {"B", "C"}}, {"B", {"A", "D", "E"}}, {"C", {"A", "F"}}, {"D", {"B"}}, {"E", {"B", "F"}}, {"F", {"C", "E"}}, };
auto result = bfs(graph, "A"); cout << "["; for (size_t i = 0; i < result.size(); i++) { cout << "'" << result[i] << "'"; if (i + 1 < result.size()) cout << ", "; } cout << "]" << endl; return 0;}import java.util.*;
public class Main { static List<String> bfs(Map<String, List<String>> graph, String start) { Set<String> visited = new HashSet<>(List.of(start)); Queue<String> queue = new LinkedList<>(List.of(start)); List<String> visitOrder = new ArrayList<>();
while (!queue.isEmpty()) { String vertex = queue.poll(); visitOrder.add(vertex);
for (String neighbor : graph.get(vertex)) { if (!visited.contains(neighbor)) { visited.add(neighbor); queue.add(neighbor); } } }
return visitOrder; }
public static void main(String[] args) { Map<String, List<String>> graph = new LinkedHashMap<>(); graph.put("A", List.of("B", "C")); graph.put("B", List.of("A", "D", "E")); graph.put("C", List.of("A", "F")); graph.put("D", List.of("B")); graph.put("E", List.of("B", "F")); graph.put("F", List.of("C", "E"));
System.out.println(bfs(graph, "A")); }}import java.util.LinkedList
fun bfs(graph: Map<String, List<String>>, start: String): List<String> { val visited = mutableSetOf(start) val queue = LinkedList(listOf(start)) val visitOrder = mutableListOf<String>()
while (queue.isNotEmpty()) { val vertex = queue.poll() visitOrder.add(vertex)
for (neighbor in graph[vertex] ?: emptyList()) { if (neighbor !in visited) { visited.add(neighbor) queue.add(neighbor) } } }
return visitOrder}
fun main() { val graph = mapOf( "A" to listOf("B", "C"), "B" to listOf("A", "D", "E"), "C" to listOf("A", "F"), "D" to listOf("B"), "E" to listOf("B", "F"), "F" to listOf("C", "E"), )
println(bfs(graph, "A"))}import 'dart:collection';
List<String> bfs(Map<String, List<String>> graph, String start) { var visited = {start}; var queue = Queue<String>()..add(start); var visitOrder = <String>[];
while (queue.isNotEmpty) { var vertex = queue.removeFirst(); visitOrder.add(vertex);
for (var neighbor in graph[vertex] ?? []) { if (!visited.contains(neighbor)) { visited.add(neighbor); queue.add(neighbor); } } }
return visitOrder;}
void main() { var graph = { "A": ["B", "C"], "B": ["A", "D", "E"], "C": ["A", "F"], "D": ["B"], "E": ["B", "F"], "F": ["C", "E"], };
print(bfs(graph, "A"));}91. Duyệt đồ thị theo chiều sâu (DFS) đệ quy
Với đồ thị ở bài trước, viết hàm duyệt theo chiều sâu (DFS) bằng đệ quy.
Ví dụ:
Input: graph (như bài 90), start="A"Output: ['A', 'B', 'D', 'E', 'F', 'C']Xem đáp án
def dfs(graph, vertex, visited=None): if visited is None: visited = set()
visited.add(vertex) visit_order = [vertex]
for neighbor in graph[vertex]: if neighbor not in visited: visit_order.extend(dfs(graph, neighbor, visited))
return visit_order
graph = { "A": ["B", "C"], "B": ["A", "D", "E"], "C": ["A", "F"], "D": ["B"], "E": ["B", "F"], "F": ["C", "E"],}
print(dfs(graph, "A"))#include <iostream>#include <vector>#include <set>#include <map>#include <string>using namespace std;
void dfs(map<string, vector<string>>& graph, string vertex, set<string>& visited, vector<string>& visitOrder) { visited.insert(vertex); visitOrder.push_back(vertex);
for (const string& neighbor : graph[vertex]) { if (visited.find(neighbor) == visited.end()) { dfs(graph, neighbor, visited, visitOrder); } }}
int main() { map<string, vector<string>> graph = { {"A", {"B", "C"}}, {"B", {"A", "D", "E"}}, {"C", {"A", "F"}}, {"D", {"B"}}, {"E", {"B", "F"}}, {"F", {"C", "E"}}, };
set<string> visited; vector<string> visitOrder; dfs(graph, "A", visited, visitOrder);
cout << "["; for (size_t i = 0; i < visitOrder.size(); i++) { cout << "'" << visitOrder[i] << "'"; if (i + 1 < visitOrder.size()) cout << ", "; } cout << "]" << endl; return 0;}import java.util.*;
public class Main { static void dfs(Map<String, List<String>> graph, String vertex, Set<String> visited, List<String> visitOrder) { visited.add(vertex); visitOrder.add(vertex);
for (String neighbor : graph.get(vertex)) { if (!visited.contains(neighbor)) { dfs(graph, neighbor, visited, visitOrder); } } }
public static void main(String[] args) { Map<String, List<String>> graph = new LinkedHashMap<>(); graph.put("A", List.of("B", "C")); graph.put("B", List.of("A", "D", "E")); graph.put("C", List.of("A", "F")); graph.put("D", List.of("B")); graph.put("E", List.of("B", "F")); graph.put("F", List.of("C", "E"));
Set<String> visited = new HashSet<>(); List<String> visitOrder = new ArrayList<>(); dfs(graph, "A", visited, visitOrder);
System.out.println(visitOrder); }}fun dfs(graph: Map<String, List<String>>, vertex: String, visited: MutableSet<String>, visitOrder: MutableList<String>) { visited.add(vertex) visitOrder.add(vertex)
for (neighbor in graph[vertex] ?: emptyList()) { if (neighbor !in visited) { dfs(graph, neighbor, visited, visitOrder) } }}
fun main() { val graph = mapOf( "A" to listOf("B", "C"), "B" to listOf("A", "D", "E"), "C" to listOf("A", "F"), "D" to listOf("B"), "E" to listOf("B", "F"), "F" to listOf("C", "E"), )
val visited = mutableSetOf<String>() val visitOrder = mutableListOf<String>() dfs(graph, "A", visited, visitOrder)
println(visitOrder)}void dfs(Map<String, List<String>> graph, String vertex, Set<String> visited, List<String> visitOrder) { visited.add(vertex); visitOrder.add(vertex);
for (var neighbor in graph[vertex] ?? []) { if (!visited.contains(neighbor)) { dfs(graph, neighbor, visited, visitOrder); } }}
void main() { var graph = { "A": ["B", "C"], "B": ["A", "D", "E"], "C": ["A", "F"], "D": ["B"], "E": ["B", "F"], "F": ["C", "E"], };
var visited = <String>{}; var visitOrder = <String>[]; dfs(graph, "A", visited, visitOrder);
print(visitOrder);}92. Kiểm tra đồ thị vô hướng có chu trình
Kiểm tra một đồ thị vô hướng (dạng adjacency list) có tồn tại chu trình (cycle) hay không, dùng DFS.
Ví dụ:
Input: {"A": ["B"], "B": ["A", "C"], "C": ["B", "A"]}Output: True
Input: {"A": ["B"], "B": ["A", "C"], "C": ["B"]}Output: FalseXem đáp án
def has_cycle(graph): visited = set()
def dfs(vertex, parent_vertex): visited.add(vertex) for neighbor in graph[vertex]: if neighbor not in visited: if dfs(neighbor, vertex): return True elif neighbor != parent_vertex: return True # Gặp lại đỉnh đã thăm mà không phải đỉnh cha -> có chu trình return False
for vertex in graph: if vertex not in visited: if dfs(vertex, None): return True
return False
graph_with_cycle = {"A": ["B"], "B": ["A", "C"], "C": ["B", "A"]}graph_without_cycle = {"A": ["B"], "B": ["A", "C"], "C": ["B"]}
print(has_cycle(graph_with_cycle)) # Trueprint(has_cycle(graph_without_cycle)) # False#include <iostream>#include <vector>#include <set>#include <map>#include <string>using namespace std;
bool dfs(map<string, vector<string>>& graph, string vertex, string parentVertex, set<string>& visited) { visited.insert(vertex); for (const string& neighbor : graph[vertex]) { if (visited.find(neighbor) == visited.end()) { if (dfs(graph, neighbor, vertex, visited)) return true; } else if (neighbor != parentVertex) { return true; } } return false;}
bool hasCycle(map<string, vector<string>>& graph) { set<string> visited; for (auto& [vertex, _] : graph) { if (visited.find(vertex) == visited.end()) { if (dfs(graph, vertex, "", visited)) return true; } } return false;}
int main() { map<string, vector<string>> graphWithCycle = {{"A", {"B"}}, {"B", {"A", "C"}}, {"C", {"B", "A"}}}; map<string, vector<string>> graphWithoutCycle = {{"A", {"B"}}, {"B", {"A", "C"}}, {"C", {"B"}}};
cout << boolalpha << hasCycle(graphWithCycle) << endl; cout << boolalpha << hasCycle(graphWithoutCycle) << endl; return 0;}import java.util.*;
public class Main { static boolean dfs(Map<String, List<String>> graph, String vertex, String parentVertex, Set<String> visited) { visited.add(vertex); for (String neighbor : graph.get(vertex)) { if (!visited.contains(neighbor)) { if (dfs(graph, neighbor, vertex, visited)) return true; } else if (!neighbor.equals(parentVertex)) { return true; } } return false; }
static boolean hasCycle(Map<String, List<String>> graph) { Set<String> visited = new HashSet<>(); for (String vertex : graph.keySet()) { if (!visited.contains(vertex)) { if (dfs(graph, vertex, null, visited)) return true; } } return false; }
public static void main(String[] args) { Map<String, List<String>> graphWithCycle = new LinkedHashMap<>(); graphWithCycle.put("A", List.of("B")); graphWithCycle.put("B", List.of("A", "C")); graphWithCycle.put("C", List.of("B", "A"));
Map<String, List<String>> graphWithoutCycle = new LinkedHashMap<>(); graphWithoutCycle.put("A", List.of("B")); graphWithoutCycle.put("B", List.of("A", "C")); graphWithoutCycle.put("C", List.of("B"));
System.out.println(hasCycle(graphWithCycle)); System.out.println(hasCycle(graphWithoutCycle)); }}fun dfs(graph: Map<String, List<String>>, vertex: String, parentVertex: String?, visited: MutableSet<String>): Boolean { visited.add(vertex) for (neighbor in graph[vertex] ?: emptyList()) { if (neighbor !in visited) { if (dfs(graph, neighbor, vertex, visited)) return true } else if (neighbor != parentVertex) { return true } } return false}
fun hasCycle(graph: Map<String, List<String>>): Boolean { val visited = mutableSetOf<String>() for (vertex in graph.keys) { if (vertex !in visited) { if (dfs(graph, vertex, null, visited)) return true } } return false}
fun main() { val graphWithCycle = mapOf("A" to listOf("B"), "B" to listOf("A", "C"), "C" to listOf("B", "A")) val graphWithoutCycle = mapOf("A" to listOf("B"), "B" to listOf("A", "C"), "C" to listOf("B"))
println(hasCycle(graphWithCycle)) println(hasCycle(graphWithoutCycle))}bool dfs(Map<String, List<String>> graph, String vertex, String? parentVertex, Set<String> visited) { visited.add(vertex); for (var neighbor in graph[vertex] ?? []) { if (!visited.contains(neighbor)) { if (dfs(graph, neighbor, vertex, visited)) return true; } else if (neighbor != parentVertex) { return true; } } return false;}
bool hasCycle(Map<String, List<String>> graph) { var visited = <String>{}; for (var vertex in graph.keys) { if (!visited.contains(vertex)) { if (dfs(graph, vertex, null, visited)) return true; } } return false;}
void main() { var graphWithCycle = {"A": ["B"], "B": ["A", "C"], "C": ["B", "A"]}; var graphWithoutCycle = {"A": ["B"], "B": ["A", "C"], "C": ["B"]};
print(hasCycle(graphWithCycle)); print(hasCycle(graphWithoutCycle));}93. Đường đi ngắn nhất không trọng số (BFS)
Tìm đường đi ngắn nhất (số bước ít nhất) giữa 2 đỉnh trong đồ thị không trọng số, dùng BFS.
Ví dụ:
Input: graph={"A":["B","C"],"B":["A","D"],"C":["A","D"],"D":["B","C","E"],"E":["D"]}, start="A", end="E"Output: ['A', 'B', 'D', 'E']Xem đáp án
from collections import deque
def shortest_path(graph, start, end): queue = deque([[start]]) visited = {start}
while queue: path = queue.popleft() current_vertex = path[-1]
if current_vertex == end: return path
for neighbor in graph[current_vertex]: if neighbor not in visited: visited.add(neighbor) queue.append(path + [neighbor])
return None # Không có đường đi
graph = { "A": ["B", "C"], "B": ["A", "D"], "C": ["A", "D"], "D": ["B", "C", "E"], "E": ["D"],}
print(shortest_path(graph, "A", "E")) # ['A', 'B', 'D', 'E'] hoặc ['A', 'C', 'D', 'E']#include <iostream>#include <vector>#include <queue>#include <set>#include <map>#include <string>using namespace std;
vector<string> shortestPath(map<string, vector<string>>& graph, string start, string end) { queue<vector<string>> q; q.push({start}); set<string> visited = {start};
while (!q.empty()) { vector<string> path = q.front(); q.pop(); string currentVertex = path.back();
if (currentVertex == end) return path;
for (const string& neighbor : graph[currentVertex]) { if (visited.find(neighbor) == visited.end()) { visited.insert(neighbor); vector<string> newPath = path; newPath.push_back(neighbor); q.push(newPath); } } }
return {};}
int main() { map<string, vector<string>> graph = { {"A", {"B", "C"}}, {"B", {"A", "D"}}, {"C", {"A", "D"}}, {"D", {"B", "C", "E"}}, {"E", {"D"}}, };
auto result = shortestPath(graph, "A", "E"); cout << "["; for (size_t i = 0; i < result.size(); i++) { cout << "'" << result[i] << "'"; if (i + 1 < result.size()) cout << ", "; } cout << "]" << endl; return 0;}import java.util.*;
public class Main { static List<String> shortestPath(Map<String, List<String>> graph, String start, String end) { Queue<List<String>> queue = new LinkedList<>(); queue.add(new ArrayList<>(List.of(start))); Set<String> visited = new HashSet<>(List.of(start));
while (!queue.isEmpty()) { List<String> path = queue.poll(); String currentVertex = path.get(path.size() - 1);
if (currentVertex.equals(end)) return path;
for (String neighbor : graph.get(currentVertex)) { if (!visited.contains(neighbor)) { visited.add(neighbor); List<String> newPath = new ArrayList<>(path); newPath.add(neighbor); queue.add(newPath); } } }
return null; }
public static void main(String[] args) { Map<String, List<String>> graph = new LinkedHashMap<>(); graph.put("A", List.of("B", "C")); graph.put("B", List.of("A", "D")); graph.put("C", List.of("A", "D")); graph.put("D", List.of("B", "C", "E")); graph.put("E", List.of("D"));
System.out.println(shortestPath(graph, "A", "E")); }}import java.util.LinkedList
fun shortestPath(graph: Map<String, List<String>>, start: String, end: String): List<String>? { val queue = LinkedList<List<String>>() queue.add(listOf(start)) val visited = mutableSetOf(start)
while (queue.isNotEmpty()) { val path = queue.poll() val currentVertex = path.last()
if (currentVertex == end) return path
for (neighbor in graph[currentVertex] ?: emptyList()) { if (neighbor !in visited) { visited.add(neighbor) queue.add(path + neighbor) } } }
return null}
fun main() { val graph = mapOf( "A" to listOf("B", "C"), "B" to listOf("A", "D"), "C" to listOf("A", "D"), "D" to listOf("B", "C", "E"), "E" to listOf("D"), )
println(shortestPath(graph, "A", "E"))}import 'dart:collection';
List<String>? shortestPath(Map<String, List<String>> graph, String start, String end) { var queue = Queue<List<String>>()..add([start]); var visited = {start};
while (queue.isNotEmpty) { var path = queue.removeFirst(); var currentVertex = path.last;
if (currentVertex == end) return path;
for (var neighbor in graph[currentVertex] ?? []) { if (!visited.contains(neighbor)) { visited.add(neighbor); queue.add([...path, neighbor]); } } }
return null;}
void main() { var graph = { "A": ["B", "C"], "B": ["A", "D"], "C": ["A", "D"], "D": ["B", "C", "E"], "E": ["D"], };
print(shortestPath(graph, "A", "E"));}94. Đếm số thành phần liên thông (Connected Components)
Đếm số thành phần liên thông trong một đồ thị vô hướng có thể không liên thông hoàn toàn.
Ví dụ:
Input: {"A": ["B"], "B": ["A"], "C": ["D"], "D": ["C"], "E": []}Output: 3Xem đáp án
def count_connected_components(graph): visited = set()
def dfs(vertex): visited.add(vertex) for neighbor in graph[vertex]: if neighbor not in visited: dfs(neighbor)
component_count = 0 for vertex in graph: if vertex not in visited: dfs(vertex) component_count += 1
return component_count
graph = { "A": ["B"], "B": ["A"], "C": ["D"], "D": ["C"], "E": [],}
print(count_connected_components(graph)) # 3#include <iostream>#include <vector>#include <set>#include <map>#include <string>using namespace std;
void dfs(map<string, vector<string>>& graph, string vertex, set<string>& visited) { visited.insert(vertex); for (const string& neighbor : graph[vertex]) { if (visited.find(neighbor) == visited.end()) dfs(graph, neighbor, visited); }}
int countConnectedComponents(map<string, vector<string>>& graph) { set<string> visited; int componentCount = 0;
for (auto& [vertex, _] : graph) { if (visited.find(vertex) == visited.end()) { dfs(graph, vertex, visited); componentCount++; } }
return componentCount;}
int main() { map<string, vector<string>> graph = { {"A", {"B"}}, {"B", {"A"}}, {"C", {"D"}}, {"D", {"C"}}, {"E", {}}, };
cout << countConnectedComponents(graph) << endl; return 0;}import java.util.*;
public class Main { static void dfs(Map<String, List<String>> graph, String vertex, Set<String> visited) { visited.add(vertex); for (String neighbor : graph.get(vertex)) { if (!visited.contains(neighbor)) dfs(graph, neighbor, visited); } }
static int countConnectedComponents(Map<String, List<String>> graph) { Set<String> visited = new HashSet<>(); int componentCount = 0;
for (String vertex : graph.keySet()) { if (!visited.contains(vertex)) { dfs(graph, vertex, visited); componentCount++; } }
return componentCount; }
public static void main(String[] args) { Map<String, List<String>> graph = new LinkedHashMap<>(); graph.put("A", List.of("B")); graph.put("B", List.of("A")); graph.put("C", List.of("D")); graph.put("D", List.of("C")); graph.put("E", List.of());
System.out.println(countConnectedComponents(graph)); }}fun dfs(graph: Map<String, List<String>>, vertex: String, visited: MutableSet<String>) { visited.add(vertex) for (neighbor in graph[vertex] ?: emptyList()) { if (neighbor !in visited) dfs(graph, neighbor, visited) }}
fun countConnectedComponents(graph: Map<String, List<String>>): Int { val visited = mutableSetOf<String>() var componentCount = 0
for (vertex in graph.keys) { if (vertex !in visited) { dfs(graph, vertex, visited) componentCount++ } }
return componentCount}
fun main() { val graph = mapOf( "A" to listOf("B"), "B" to listOf("A"), "C" to listOf("D"), "D" to listOf("C"), "E" to listOf(), )
println(countConnectedComponents(graph))}void dfs(Map<String, List<String>> graph, String vertex, Set<String> visited) { visited.add(vertex); for (var neighbor in graph[vertex] ?? []) { if (!visited.contains(neighbor)) dfs(graph, neighbor, visited); }}
int countConnectedComponents(Map<String, List<String>> graph) { var visited = <String>{}; int componentCount = 0;
for (var vertex in graph.keys) { if (!visited.contains(vertex)) { dfs(graph, vertex, visited); componentCount++; } }
return componentCount;}
void main() { var graph = { "A": ["B"], "B": ["A"], "C": ["D"], "D": ["C"], "E": <String>[], };
print(countConnectedComponents(graph));}95. Sắp xếp Topo (Topological Sort)
Với một đồ thị có hướng không có chu trình (DAG), sắp xếp các đỉnh theo thứ tự topo bằng thuật toán Kahn (dùng bậc vào - in-degree).
Ví dụ:
Input: {"ao": ["quan"], "quan": ["giay"], "vo": ["quan"], "giay": []}Output: ['ao', 'vo', 'quan', 'giay']Xem đáp án
from collections import deque
def topological_sort(graph): in_degree = {vertex: 0 for vertex in graph} for vertex in graph: for neighbor in graph[vertex]: in_degree[neighbor] += 1
queue = deque([vertex for vertex in graph if in_degree[vertex] == 0]) result = []
while queue: vertex = queue.popleft() result.append(vertex)
for neighbor in graph[vertex]: in_degree[neighbor] -= 1 if in_degree[neighbor] == 0: queue.append(neighbor)
return result
graph = { "ao": ["quan"], "quan": ["giay"], "vo": ["quan"], "giay": [],}
print(topological_sort(graph))#include <iostream>#include <vector>#include <queue>#include <map>#include <string>using namespace std;
vector<string> topologicalSort(map<string, vector<string>>& graph) { map<string, int> inDegree; for (auto& [vertex, _] : graph) inDegree[vertex] = 0; for (auto& [vertex, neighbors] : graph) { for (const string& neighbor : neighbors) inDegree[neighbor]++; }
queue<string> q; for (auto& [vertex, _] : graph) { if (inDegree[vertex] == 0) q.push(vertex); }
vector<string> result; while (!q.empty()) { string vertex = q.front(); q.pop(); result.push_back(vertex);
for (const string& neighbor : graph[vertex]) { inDegree[neighbor]--; if (inDegree[neighbor] == 0) q.push(neighbor); } }
return result;}
int main() { map<string, vector<string>> graph = { {"ao", {"quan"}}, {"quan", {"giay"}}, {"vo", {"quan"}}, {"giay", {}}, };
auto result = topologicalSort(graph); cout << "["; for (size_t i = 0; i < result.size(); i++) { cout << "'" << result[i] << "'"; if (i + 1 < result.size()) cout << ", "; } cout << "]" << endl; return 0;}import java.util.*;
public class Main { static List<String> topologicalSort(Map<String, List<String>> graph) { Map<String, Integer> inDegree = new LinkedHashMap<>(); for (String vertex : graph.keySet()) inDegree.put(vertex, 0); for (List<String> neighbors : graph.values()) { for (String neighbor : neighbors) inDegree.merge(neighbor, 1, Integer::sum); }
Queue<String> queue = new LinkedList<>(); for (String vertex : graph.keySet()) { if (inDegree.get(vertex) == 0) queue.add(vertex); }
List<String> result = new ArrayList<>(); while (!queue.isEmpty()) { String vertex = queue.poll(); result.add(vertex);
for (String neighbor : graph.get(vertex)) { inDegree.merge(neighbor, -1, Integer::sum); if (inDegree.get(neighbor) == 0) queue.add(neighbor); } }
return result; }
public static void main(String[] args) { Map<String, List<String>> graph = new LinkedHashMap<>(); graph.put("ao", List.of("quan")); graph.put("quan", List.of("giay")); graph.put("vo", List.of("quan")); graph.put("giay", List.of());
System.out.println(topologicalSort(graph)); }}import java.util.LinkedList
fun topologicalSort(graph: Map<String, List<String>>): List<String> { val inDegree = graph.keys.associateWith { 0 }.toMutableMap() for (neighbors in graph.values) { for (neighbor in neighbors) inDegree[neighbor] = (inDegree[neighbor] ?: 0) + 1 }
val queue = LinkedList(graph.keys.filter { inDegree[it] == 0 }) val result = mutableListOf<String>()
while (queue.isNotEmpty()) { val vertex = queue.poll() result.add(vertex)
for (neighbor in graph[vertex] ?: emptyList()) { inDegree[neighbor] = inDegree[neighbor]!! - 1 if (inDegree[neighbor] == 0) queue.add(neighbor) } }
return result}
fun main() { val graph = linkedMapOf( "ao" to listOf("quan"), "quan" to listOf("giay"), "vo" to listOf("quan"), "giay" to listOf(), )
println(topologicalSort(graph))}import 'dart:collection';
List<String> topologicalSort(Map<String, List<String>> graph) { var inDegree = {for (var v in graph.keys) v: 0}; for (var neighbors in graph.values) { for (var neighbor in neighbors) { inDegree[neighbor] = (inDegree[neighbor] ?? 0) + 1; } }
var queue = Queue<String>()..addAll(graph.keys.where((v) => inDegree[v] == 0)); var result = <String>[];
while (queue.isNotEmpty) { var vertex = queue.removeFirst(); result.add(vertex);
for (var neighbor in graph[vertex] ?? []) { inDegree[neighbor] = inDegree[neighbor]! - 1; if (inDegree[neighbor] == 0) queue.add(neighbor); } }
return result;}
void main() { var graph = { "ao": ["quan"], "quan": ["giay"], "vo": ["quan"], "giay": <String>[], };
print(topologicalSort(graph));}Nhóm 13: Kiểm thử (Testing)
Phần tiêu đề “Nhóm 13: Kiểm thử (Testing)”96. Unit Test với unittest
Viết hàm cong(a, b) và một bộ test dùng module unittest để kiểm tra hàm hoạt động đúng.
Xem đáp án
import unittest
def add(a, b): return a + b
class TestAdd(unittest.TestCase): def test_positive(self): self.assertEqual(add(2, 3), 5)
def test_negative(self): self.assertEqual(add(-1, -1), -2)
def test_zero(self): self.assertEqual(add(0, 5), 5)
# Chạy test (trong file thực tế thường dùng: python -m unittest ten_file.py)runner = unittest.TextTestRunner()runner.run(unittest.TestLoader().loadTestsFromTestCase(TestAdd))// Vi du don gian mo phong unit test, khong dung thu vien ngoai (thuc te co the dung Google Test).#include <iostream>#include <cassert>using namespace std;
int add(int a, int b) { return a + b;}
void testPositive() { assert(add(2, 3) == 5); }void testNegative() { assert(add(-1, -1) == -2); }void testZero() { assert(add(0, 5) == 5); }
int main() { testPositive(); testNegative(); testZero(); cout << "Tat ca test deu pass!" << endl; return 0;}// Vi du don gian mo phong unit test (thuc te co the dung JUnit).public class Main { static int add(int a, int b) { return a + b; }
static void assertEqual(int actual, int expected, String testName) { if (actual != expected) { System.out.println(testName + " FAILED: expected " + expected + " but got " + actual); } else { System.out.println(testName + " passed"); } }
public static void main(String[] args) { assertEqual(add(2, 3), 5, "testPositive"); assertEqual(add(-1, -1), -2, "testNegative"); assertEqual(add(0, 5), 5, "testZero"); }}// Vi du don gian mo phong unit test (thuc te co the dung kotlin.test / JUnit).fun add(a: Int, b: Int): Int = a + b
fun assertEqual(actual: Int, expected: Int, testName: String) { if (actual != expected) { println("$testName FAILED: expected $expected but got $actual") } else { println("$testName passed") }}
fun main() { assertEqual(add(2, 3), 5, "testPositive") assertEqual(add(-1, -1), -2, "testNegative") assertEqual(add(0, 5), 5, "testZero")}// Vi du don gian mo phong unit test (thuc te nen dung package:test).int add(int a, int b) => a + b;
void assertEqual(int actual, int expected, String testName) { if (actual != expected) { print("$testName FAILED: expected $expected but got $actual"); } else { print("$testName passed"); }}
void main() { assertEqual(add(2, 3), 5, "testPositive"); assertEqual(add(-1, -1), -2, "testNegative"); assertEqual(add(0, 5), 5, "testZero");}97. Kiểm tra hàm bằng assert
Viết hàm is_palindrome(s) và dùng các câu lệnh assert để tự kiểm tra nhanh các trường hợp cơ bản.
Xem đáp án
def is_palindrome(s): s = s.lower().replace(" ", "") return s == s[::-1]
assert is_palindrome("level") == Trueassert is_palindrome("hello") == Falseassert is_palindrome("A man a plan a canal Panama") == Trueassert is_palindrome("") == True
print("Tất cả các assert đều đúng!")#include <iostream>#include <string>#include <algorithm>#include <cassert>using namespace std;
bool isPalindrome(string s) { string cleaned; for (char c : s) { if (c != ' ') cleaned += tolower(c); } string reversed = cleaned; reverse(reversed.begin(), reversed.end()); return cleaned == reversed;}
int main() { assert(isPalindrome("level") == true); assert(isPalindrome("hello") == false); assert(isPalindrome("A man a plan a canal Panama") == true); assert(isPalindrome("") == true);
cout << "Tat ca cac assert deu dung!" << endl; return 0;}public class Main { static boolean isPalindrome(String s) { String cleaned = s.toLowerCase().replace(" ", ""); String reversed = new StringBuilder(cleaned).reverse().toString(); return cleaned.equals(reversed); }
public static void main(String[] args) { assert isPalindrome("level") == true; assert isPalindrome("hello") == false; assert isPalindrome("A man a plan a canal Panama") == true; assert isPalindrome("") == true;
System.out.println("Tat ca cac assert deu dung!"); }}fun isPalindrome(s: String): Boolean { val cleaned = s.lowercase().replace(" ", "") return cleaned == cleaned.reversed()}
fun main() { assert(isPalindrome("level") == true) assert(isPalindrome("hello") == false) assert(isPalindrome("A man a plan a canal Panama") == true) assert(isPalindrome("") == true)
println("Tat ca cac assert deu dung!")}bool isPalindrome(String s) { final cleaned = s.toLowerCase().replaceAll(" ", ""); final reversed = cleaned.split('').reversed.join(''); return cleaned == reversed;}
void main() { assert(isPalindrome("level") == true); assert(isPalindrome("hello") == false); assert(isPalindrome("A man a plan a canal Panama") == true); assert(isPalindrome("") == true);
print("Tat ca cac assert deu dung!");}Nhóm 14: Lập trình đồng thời (Concurrency) cơ bản
Phần tiêu đề “Nhóm 14: Lập trình đồng thời (Concurrency) cơ bản”98. threading - Chạy song song đơn giản
GIL (Global Interpreter Lock) là cơ chế trong CPython chỉ cho phép 1 luồng (thread) thực thi code Python tại một thời điểm, nên nhiều thread không thực sự chạy song song mà chỉ xen kẽ nhau rất nhanh. Dùng module threading để chạy 2 tác vụ “song song” theo kiểu này, so sánh với chạy tuần tự.
Xem đáp án
import threadingimport time
def task(name, seconds): print(f"Bắt đầu {name}") time.sleep(seconds) print(f"Hoàn thành {name}")
start_time = time.time()
t1 = threading.Thread(target=task, args=("Task 1", 1))t2 = threading.Thread(target=task, args=("Task 2", 1))
t1.start()t2.start()
t1.join()t2.join()
print(f"Tổng thời gian: {time.time() - start_time:.2f} giây") # ~1 giây thay vì 2#include <iostream>#include <thread>#include <chrono>using namespace std;
void task(string name, int seconds) { cout << "Bat dau " << name << endl; this_thread::sleep_for(chrono::seconds(seconds)); cout << "Hoan thanh " << name << endl;}
int main() { auto start = chrono::steady_clock::now();
thread t1(task, "Task 1", 1); thread t2(task, "Task 2", 1);
t1.join(); t2.join();
chrono::duration<double> elapsed = chrono::steady_clock::now() - start; cout << "Tong thoi gian: " << elapsed.count() << " giay" << endl; return 0;}public class Main { static void task(String name, int seconds) throws InterruptedException { System.out.println("Bat dau " + name); Thread.sleep(seconds * 1000L); System.out.println("Hoan thanh " + name); }
public static void main(String[] args) throws InterruptedException { long startTime = System.currentTimeMillis();
Thread t1 = new Thread(() -> { try { task("Task 1", 1); } catch (InterruptedException ignored) {} }); Thread t2 = new Thread(() -> { try { task("Task 2", 1); } catch (InterruptedException ignored) {} });
t1.start(); t2.start();
t1.join(); t2.join();
System.out.printf("Tong thoi gian: %.2f giay%n", (System.currentTimeMillis() - startTime) / 1000.0); }}fun task(name: String, seconds: Long) { println("Bat dau $name") Thread.sleep(seconds * 1000) println("Hoan thanh $name")}
fun main() { val startTime = System.currentTimeMillis()
val t1 = Thread { task("Task 1", 1) } val t2 = Thread { task("Task 2", 1) }
t1.start() t2.start()
t1.join() t2.join()
println("Tong thoi gian: ${(System.currentTimeMillis() - startTime) / 1000.0} giay")}// Dart chay don luong (event loop); dung Future.wait de mo phong "song song" I/O bound.Future<void> task(String name, int seconds) async { print("Bat dau $name"); await Future.delayed(Duration(seconds: seconds)); print("Hoan thanh $name");}
void main() async { final start = DateTime.now();
await Future.wait([ task("Task 1", 1), task("Task 2", 1), ]);
final elapsed = DateTime.now().difference(start).inMilliseconds / 1000; print("Tong thoi gian: $elapsed giay");}99. multiprocessing - Tính tổng song song
Dùng module multiprocessing để chia một list số lớn thành nhiều phần, tính tổng từng phần song song trên nhiều tiến trình (process), rồi cộng kết quả lại.
Xem đáp án
from multiprocessing import Pool
def calculate_sum(sub_list): return sum(sub_list)
if __name__ == "__main__": numbers = list(range(1, 1_000_001)) num_parts = 4 chunk_size = len(numbers) // num_parts
parts = [ numbers[i:i + chunk_size] for i in range(0, len(numbers), chunk_size) ]
with Pool(processes=num_parts) as pool: part_results = pool.map(calculate_sum, parts)
print("Tổng cuối cùng:", sum(part_results))#include <iostream>#include <vector>#include <thread>#include <numeric>using namespace std;
long long calculateSum(const vector<int>& subList) { return accumulate(subList.begin(), subList.end(), 0LL);}
int main() { vector<int> numbers(1000000); for (int i = 0; i < 1000000; i++) numbers[i] = i + 1;
int numParts = 4; int chunkSize = numbers.size() / numParts;
vector<long long> partResults(numParts); vector<thread> threads;
for (int i = 0; i < numParts; i++) { int startIdx = i * chunkSize; int endIdx = (i == numParts - 1) ? numbers.size() : startIdx + chunkSize; threads.emplace_back([&, i, startIdx, endIdx]() { vector<int> chunk(numbers.begin() + startIdx, numbers.begin() + endIdx); partResults[i] = calculateSum(chunk); }); }
for (auto& t : threads) t.join();
long long total = accumulate(partResults.begin(), partResults.end(), 0LL); cout << "Tong cuoi cung: " << total << endl; return 0;}import java.util.concurrent.*;import java.util.*;
public class Main { public static void main(String[] args) throws Exception { int[] numbers = new int[1_000_000]; for (int i = 0; i < numbers.length; i++) numbers[i] = i + 1;
int numParts = 4; int chunkSize = numbers.length / numParts;
ExecutorService executor = Executors.newFixedThreadPool(numParts); List<Future<Long>> futures = new ArrayList<>();
for (int i = 0; i < numParts; i++) { int start = i * chunkSize; int end = (i == numParts - 1) ? numbers.length : start + chunkSize; futures.add(executor.submit(() -> { long sum = 0; for (int j = start; j < end; j++) sum += numbers[j]; return sum; })); }
long total = 0; for (Future<Long> f : futures) total += f.get(); executor.shutdown();
System.out.println("Tong cuoi cung: " + total); }}import kotlinx.coroutines.*
suspend fun calculateSum(subList: List<Int>): Long = subList.sumOf { it.toLong() }
fun main() = runBlocking { val numbers = (1..1_000_000).toList() val numParts = 4 val chunkSize = numbers.size / numParts
val parts = numbers.chunked(chunkSize)
val partResults = parts.map { part -> async(Dispatchers.Default) { calculateSum(part) } }.awaitAll()
println("Tong cuoi cung: ${partResults.sum()}")}import 'dart:isolate';
Future<int> calculateSum(List<int> subList) async { return subList.fold(0, (sum, x) => sum + x);}
void main() async { final numbers = List.generate(1000000, (i) => i + 1); const numParts = 4; final chunkSize = numbers.length ~/ numParts;
final parts = <List<int>>[]; for (int i = 0; i < numbers.length; i += chunkSize) { parts.add(numbers.sublist(i, i + chunkSize > numbers.length ? numbers.length : i + chunkSize)); }
final partResults = await Future.wait(parts.map((p) => Isolate.run(() => p.fold(0, (sum, x) => sum + x))));
print("Tong cuoi cung: ${partResults.reduce((a, b) => a + b)}");}100. Mô phỏng nhiều tác vụ chờ với concurrent.futures
Dùng concurrent.futures.ThreadPoolExecutor để tải “giả lập” 5 trang web cùng lúc (mỗi trang mất 1 giây), thay vì tải tuần tự mất 5 giây.
Xem đáp án
import timefrom concurrent.futures import ThreadPoolExecutor
def download_page(page_name): time.sleep(1) # Giả lập thời gian chờ mạng return f"Đã tải xong {page_name}"
websites = [f"trang-{i}.com" for i in range(1, 6)]
start_time = time.time()
with ThreadPoolExecutor(max_workers=5) as executor: result = list(executor.map(download_page, websites))
for r in result: print(r)
print(f"Tổng thời gian: {time.time() - start_time:.2f} giây") # ~1 giây thay vì 5#include <iostream>#include <thread>#include <vector>#include <chrono>using namespace std;
string downloadPage(string pageName) { this_thread::sleep_for(chrono::seconds(1)); return "Da tai xong " + pageName;}
int main() { vector<string> websites; for (int i = 1; i <= 5; i++) websites.push_back("trang-" + to_string(i) + ".com");
auto start = chrono::steady_clock::now();
vector<string> results(websites.size()); vector<thread> threads; for (size_t i = 0; i < websites.size(); i++) { threads.emplace_back([&, i]() { results[i] = downloadPage(websites[i]); }); } for (auto& t : threads) t.join();
for (auto& r : results) cout << r << endl;
chrono::duration<double> elapsed = chrono::steady_clock::now() - start; cout << "Tong thoi gian: " << elapsed.count() << " giay" << endl; return 0;}import java.util.concurrent.*;import java.util.*;
public class Main { static String downloadPage(String pageName) throws InterruptedException { Thread.sleep(1000); return "Da tai xong " + pageName; }
public static void main(String[] args) throws Exception { List<String> websites = new ArrayList<>(); for (int i = 1; i <= 5; i++) websites.add("trang-" + i + ".com");
long startTime = System.currentTimeMillis();
ExecutorService executor = Executors.newFixedThreadPool(5); List<Future<String>> futures = new ArrayList<>(); for (String site : websites) { futures.add(executor.submit(() -> downloadPage(site))); }
for (Future<String> f : futures) System.out.println(f.get()); executor.shutdown();
System.out.printf("Tong thoi gian: %.2f giay%n", (System.currentTimeMillis() - startTime) / 1000.0); }}import kotlinx.coroutines.*
suspend fun downloadPage(pageName: String): String { delay(1000) return "Da tai xong $pageName"}
fun main() = runBlocking { val websites = (1..5).map { "trang-$it.com" }
val startTime = System.currentTimeMillis()
val results = websites.map { site -> async(Dispatchers.Default) { downloadPage(site) } }.awaitAll()
results.forEach { println(it) }
println("Tong thoi gian: ${(System.currentTimeMillis() - startTime) / 1000.0} giay")}Future<String> downloadPage(String pageName) async { await Future.delayed(Duration(seconds: 1)); return "Da tai xong $pageName";}
void main() async { final websites = List.generate(5, (i) => "trang-${i + 1}.com");
final start = DateTime.now();
final results = await Future.wait(websites.map(downloadPage));
for (var r in results) print(r);
final elapsed = DateTime.now().difference(start).inMilliseconds / 1000; print("Tong thoi gian: $elapsed giay");}Bạn đã hoàn thành cả 100 bài cơ bản và 100 bài nâng cao? Quay lại trang Bài tập lập trình - Cơ bản để ôn lại, hoặc thử sức với các bài tập theo từng chủ đề riêng ở sidebar bên trái.
Muốn thử sức với các bài toán phong cách phỏng vấn/LeetCode? Ghé qua Bài tập lập trình - Luyện thuật toán với 200 bài từ Dễ đến Khó, có ví dụ minh họa và ràng buộc chi tiết cho từng bài.