100 câu hỏi phỏng vấn kinh điển về giải thuật và cấu trúc dữ liệu có lời giải chi tiết A-Z

Table of Contents

Câu hỏi 1: Kiểm tra chuỗi đối xứng (Palindrome)

Viết hàm kiểm tra xem một chuỗi có phải là chuỗi đối xứng hay không.

Giải pháp

javascriptSao chép mãfunction isPalindrome(str) {
// Bước 1: Chuẩn hóa chuỗi (loại bỏ khoảng trắng và chuyển về chữ thường)
const normalizedStr = str.replace(/[^a-zA-Z0-9]/g, '').toLowerCase();
// Bước 2: So sánh chuỗi đã chuẩn hóa với chuỗi đảo ngược của nó
return normalizedStr === normalizedStr.split('').reverse().join('');
}

Phân tích chi tiết

Chuẩn hóa chuỗi:
- str.replace(/[^a-zA-Z0-9]/g, ''): Loại bỏ các ký tự không phải chữ cái và số.
  - Biểu thức chính quy /[^a-zA-Z0-9]/g tìm tất cả các ký tự không thuộc khoảng a-z, A-Z, hoặc 0-9.
  - '' thay thế các ký tự không mong muốn bằng chuỗi rỗng.
- .toLowerCase(): Chuyển toàn bộ chuỗi về chữ thường để so sánh không phân biệt hoa/thường.
Đảo ngược chuỗi:
- .split(''): Chuyển chuỗi thành mảng các ký tự.
- .reverse(): Đảo ngược mảng.
- .join(''): Ghép các phần tử trong mảng lại thành chuỗi.
So sánh:
- normalizedStr === normalizedStr.split('').reverse().join(''): So sánh chuỗi đã chuẩn hóa với chuỗi đảo ngược.

Ví dụ

javascriptSao chép mãconsole.log(isPalindrome("A man, a plan, a canal: Panama")); // true
console.log(isPalindrome("race a car")); // false

Câu hỏi 2: Tìm phần tử xuất hiện lẻ lần trong mảng

Viết hàm nhận vào một mảng số nguyên, trả về phần tử xuất hiện lẻ số lần.

Giải pháp

javascriptSao chép mãfunction findOdd(arr) {
return arr.reduce((acc, num) => acc ^ num, 0);
}

Phân tích chi tiết

Tìm hiểu toán tử XOR (^):
- Toán tử XOR trả về 1 nếu hai bit khác nhau, 0 nếu hai bit giống nhau.
- Tính chất:
  - a ^ a = 0 (một số XOR với chính nó bằng 0).
  - a ^ 0 = a (một số XOR với 0 vẫn là chính nó).
  - XOR có tính giao hoán và kết hợp.
Ứng dụng XOR:
- Khi XOR tất cả các phần tử trong mảng, các phần tử xuất hiện chẵn lần sẽ bị triệt tiêu (vì a ^ a = 0).
- Chỉ phần tử xuất hiện lẻ lần còn lại.
Sử dụng reduce:
- .reduce((acc, num) => acc ^ num, 0):
  - acc: Giá trị tích lũy (ban đầu là 0).
  - num: Phần tử hiện tại trong mảng.
  - acc ^ num: Thực hiện XOR giữa giá trị tích lũy và phần tử hiện tại.

Ví dụ

javascriptSao chép mãconsole.log(findOdd([1, 2, 3, 2, 3, 1, 1])); // 1
console.log(findOdd([4, 3, 4, 4, 4, 5, 5])); // 3

Câu hỏi 3: Sắp xếp mảng theo tần suất

Sắp xếp mảng theo tần suất xuất hiện, tần suất cao hơn sẽ đứng trước, nếu bằng nhau thì sắp xếp theo giá trị tăng dần.

Giải pháp

javascriptSao chép mãfunction frequencySort(arr) {
const freqMap = {};
// Bước 1: Tính tần suất xuất hiện của từng phần tử
arr.forEach(num => {
freqMap[num] = (freqMap[num] || 0) + 1;
});
// Bước 2: Sắp xếp mảng dựa trên tần suất và giá trị
return arr.sort((a, b) => {
if (freqMap[b] === freqMap[a]) {
return a - b; // Nếu tần suất bằng nhau, sắp xếp theo giá trị
}
return freqMap[b] - freqMap[a]; // Sắp xếp theo tần suất giảm dần
});
}

Phân tích chi tiết

Tạo bảng tần suất (freqMap):
- arr.forEach(num => { freqMap[num] = (freqMap[num] || 0) + 1; }):
  - Duyệt qua từng phần tử trong mảng.
  - Nếu phần tử chưa có trong freqMap, gán giá trị ban đầu là 0.
  - Cộng thêm 1 mỗi lần gặp phần tử.
Sắp xếp mảng:
- arr.sort((a, b) => { ... }):
  - freqMap[b] - freqMap[a]: Sắp xếp giảm dần theo tần suất.
  - a - b: Nếu tần suất bằng nhau, sắp xếp tăng dần theo giá trị.

Ví dụ

javascriptSao chép mãconsole.log(frequencySort([1, 1, 2, 2, 2, 3])); // [2, 2, 2, 1, 1, 3]
console.log(frequencySort([4, 5, 6, 5, 4, 3])); // [4, 4, 5, 5, 3, 6]

Câu hỏi 4: Tìm tổng hai số có trong mảng bằng một số mục tiêu (Two Sum)

Viết một hàm nhận vào mảng số nguyên và một số mục tiêu, trả về chỉ số của hai số trong mảng sao cho tổng của chúng bằng số mục tiêu.

Giải pháp 1: Sử dụng vòng lặp lồng nhau (Brute Force)

function twoSum(nums, target) {
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] === target) {
return [i, j];
}
}
}
return [];
}

Phân tích chi tiết

Duyệt qua các cặp phần tử:
- for (let i = 0; i < nums.length; i++): Vòng lặp ngoài duyệt từng phần tử.
- for (let j = i + 1; j < nums.length; j++): Vòng lặp trong duyệt các phần tử còn lại để tránh kiểm tra lặp lại.
Kiểm tra điều kiện:
- if (nums[i] + nums[j] === target): Nếu tổng hai phần tử bằng target, trả về chỉ số của chúng.
Độ phức tạp:
- Thời gian: O(n2)O(n^2) do có hai vòng lặp lồng nhau.
- Bộ nhớ: O(1)O(1) vì không sử dụng cấu trúc lưu trữ bổ sung.

Giải pháp 2: Sử dụng Hash Map (Hiệu quả hơn)

function twoSum(nums, target) {
const numMap = new Map();
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i];
if (numMap.has(complement)) {
return [numMap.get(complement), i];
}
numMap.set(nums[i], i);
}
return [];
}

Phân tích chi tiết

Hash Map (numMap):
- new Map(): Tạo một cấu trúc lưu trữ giá trị và chỉ số của phần tử.
Tính giá trị cần tìm (complement):
- const complement = target - nums[i]: Tìm giá trị cần để tổng bằng target.
Kiểm tra trong Hash Map:
- if (numMap.has(complement)): Nếu giá trị cần tìm đã tồn tại, trả về chỉ số.
Lưu giá trị vào Hash Map:
- numMap.set(nums[i], i): Lưu giá trị hiện tại và chỉ số của nó.
Độ phức tạp:
- Thời gian: O(n)O(n) do chỉ cần duyệt qua mảng một lần.
- Bộ nhớ: O(n)O(n) để lưu các giá trị vào Hash Map.

Ví dụ

console.log(twoSum([2, 7, 11, 15], 9)); // [0, 1]
console.log(twoSum([3, 2, 4], 6)); // [1, 2]

Câu hỏi 5: Tìm độ dài của chuỗi con dài nhất không chứa ký tự lặp

Giải pháp

function lengthOfLongestSubstring(s) {
let set = new Set();
let maxLength = 0;
let left = 0;
for (let right = 0; right < s.length; right++) {
while (set.has(s[right])) {
set.delete(s[left]);
left++;
}
set.add(s[right]);
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
}

Phân tích chi tiết

Sử dụng cửa sổ trượt (Sliding Window):
- left và right: Hai con trỏ đại diện cho ranh giới của cửa sổ.
- set: Một tập hợp để lưu các ký tự duy nhất trong cửa sổ.
Kiểm tra ký tự lặp:
- while (set.has(s[right])): Nếu ký tự tại right đã xuất hiện trong cửa sổ, xóa các ký tự từ left đến khi ký tự đó không còn.
Thêm ký tự mới:
- set.add(s[right]): Thêm ký tự hiện tại vào cửa sổ.
Cập nhật độ dài lớn nhất:
- maxLength = Math.max(maxLength, right - left + 1): Cập nhật độ dài chuỗi con không lặp dài nhất.
Độ phức tạp:
- Thời gian: O(n)O(n) do mỗi ký tự được duyệt tối đa 2 lần (thêm vào và xóa khỏi tập hợp).
- Bộ nhớ: O(k)O(k) với kk là số lượng ký tự duy nhất trong chuỗi.

Ví dụ

console.log(lengthOfLongestSubstring("abcabcbb")); // 3 ("abc")
console.log(lengthOfLongestSubstring("bbbbb")); // 1 ("b")
console.log(lengthOfLongestSubstring("pwwkew")); // 3 ("wke")

Câu hỏi 6: Tìm giá trị lớn thứ hai trong mảng

Giải pháp

function secondLargest(nums) {
let first = -Infinity, second = -Infinity;
for (let num of nums) {
if (num > first) {
second = first;
first = num;
} else if (num > second && num !== first) {
second = num;
}
}
return second === -Infinity ? null : second;
}

Phân tích chi tiết

Biến theo dõi giá trị lớn nhất và lớn thứ hai:
- first: Giá trị lớn nhất.
- second: Giá trị lớn thứ hai.
Cập nhật giá trị lớn nhất và lớn thứ hai:
- if (num > first): Nếu num lớn hơn giá trị lớn nhất hiện tại, cập nhật first và second.
- else if (num > second && num !== first): Nếu num lớn hơn second và khác first, cập nhật second.
Xử lý trường hợp không có giá trị lớn thứ hai:
- return second === -Infinity ? null : second: Nếu không tồn tại giá trị lớn thứ hai, trả về null.
Độ phức tạp:
- Thời gian: O(n)O(n) do chỉ duyệt qua mảng một lần.
- Bộ nhớ: O(1)O(1) do không sử dụng cấu trúc dữ liệu bổ sung.

Ví dụ

console.log(secondLargest([3, 2, 1])); // 2
console.log(secondLargest([10, 10, 10])); // null
console.log(secondLargest([5])); // null

Câu hỏi 7: Tìm tất cả các dãy con không trùng lặp (Subsets)

Viết hàm nhận vào một mảng số nguyên và trả về tất cả các dãy con (subsets) không trùng lặp.

Giải pháp

function subsets(nums) {
const result = [];
function backtrack(start, current) {
result.push([...current]);
for (let i = start; i < nums.length; i++) {
current.push(nums[i]);       // Thêm phần tử vào dãy con hiện tại
backtrack(i + 1, current);  // Đệ quy với phần tử tiếp theo
current.pop();              // Loại bỏ phần tử vừa thêm để quay lại trạng thái trước
}
}
backtrack(0, []);
return result;
}

Phân tích chi tiết

Hàm backtrack:
- start: Chỉ số bắt đầu để duyệt các phần tử tiếp theo.
- current: Dãy con hiện tại đang xây dựng.
Thêm dãy con vào kết quả:
- result.push([...current]): Sao chép current và thêm vào danh sách kết quả.
Duyệt từng phần tử từ chỉ số start:
- for (let i = start; i < nums.length; i++): Duyệt qua các phần tử từ chỉ số start trở đi.
- current.push(nums[i]): Thêm phần tử hiện tại vào dãy con.
- backtrack(i + 1, current): Đệ quy với chỉ số tiếp theo.
Loại bỏ phần tử khi quay lại:
- current.pop(): Sau khi hoàn thành một nhánh, loại bỏ phần tử cuối để thử các nhánh khác.
Độ phức tạp:
- Thời gian: O(2n)O(2^n) với nn là độ dài của mảng (mỗi phần tử có 2 trạng thái: chọn hoặc không chọn).
- Bộ nhớ: O(n)O(n) cho dãy con hiện tại.

Ví dụ

console.log(subsets([1, 2, 3]));
// [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

Câu hỏi 8: Tìm phần tử lớn nhất trong mảng xoay

Cho một mảng đã được sắp xếp nhưng sau đó bị xoay một số lần. Hãy tìm phần tử lớn nhất trong mảng.

Giải pháp

function findMaxInRotatedArray(nums) {
let left = 0, right = nums.length - 1;
while (left < right) {
let mid = Math.floor((left + right) / 2);
if (nums[mid] > nums[right]) {
left = mid + 1;
} else {
right = mid;
}
}
return nums[right];
}

Phân tích chi tiết

Binary Search:
- Chia mảng thành hai nửa để tìm kiếm.
- mid: Chỉ số giữa của mảng được tính bằng (left + right) / 2.
Điều kiện so sánh:
- if (nums[mid] > nums[right]): Nếu phần tử giữa lớn hơn phần tử cuối, giá trị lớn nhất nằm ở bên phải (left = mid + 1).
- else: Nếu không, giá trị lớn nhất nằm ở bên trái hoặc tại mid (right = mid).
Kết quả:
- Khi vòng lặp dừng (left === right), phần tử tại right là lớn nhất.
Độ phức tạp:
- Thời gian: O(log⁡n)O(\log n) nhờ giảm kích thước tìm kiếm theo cấp số nhân.
- Bộ nhớ: O(1)O(1) không sử dụng bộ nhớ bổ sung.

Ví dụ

console.log(findMaxInRotatedArray([4, 5, 6, 7, 0, 1, 2])); // 7
console.log(findMaxInRotatedArray([2, 3, 4, 5, 1])); // 5

Câu hỏi 9: Sắp xếp các mảng con theo tổng

Cho một mảng chứa các mảng con, sắp xếp các mảng con này theo tổng của chúng.

Giải pháp

function sortSubarraysBySum(arr) {
return arr.sort((a, b) => {
const sumA = a.reduce((acc, num) => acc + num, 0);
const sumB = b.reduce((acc, num) => acc + num, 0);
return sumA - sumB;
});
}

Phân tích chi tiết

Tính tổng các mảng con:
- a.reduce((acc, num) => acc + num, 0): Tính tổng của mảng con a.
Sắp xếp mảng:
- .sort((a, b) => sumA - sumB): So sánh tổng của hai mảng con và sắp xếp tăng dần.
Độ phức tạp:
- Thời gian: O(n⋅m⋅log⁡n)O(n \cdot m \cdot \log n), với nn là số mảng con và mm là độ dài trung bình của mảng con.
- Bộ nhớ: O(1)O(1) không sử dụng bộ nhớ bổ sung.

Ví dụ

console.log(sortSubarraysBySum([[3, 2], [1, 1, 1], [4], [2, 2]]));
// [[1, 1, 1], [4], [2, 2], [3, 2]]

Câu hỏi 10: Sinh chuỗi ngoặc hợp lệ

Cho một số nn, sinh tất cả các chuỗi ngoặc hợp lệ có nn cặp ngoặc.

Giải pháp

function generateParentheses(n) {
const result = [];
function backtrack(current, open, close) {
if (current.length === n * 2) {
result.push(current);
return;
}
if (open < n) {
backtrack(current + '(', open + 1, close);
}
if (close < open) {
backtrack(current + ')', open, close + 1);
}
}
backtrack('', 0, 0);
return result;
}

Phân tích chi tiết

Hàm backtrack:
- current: Chuỗi hiện tại.
- open: Số ngoặc mở đã sử dụng.
- close: Số ngoặc đóng đã sử dụng.
Điều kiện kết thúc:
- if (current.length === n * 2): Khi chuỗi đạt đủ 2n2n ký tự, thêm vào kết quả.
Sinh chuỗi ngoặc:
- if (open < n): Nếu số ngoặc mở chưa đủ nn, thêm ngoặc mở.
- if (close < open): Nếu số ngoặc đóng ít hơn số ngoặc mở, thêm ngoặc đóng.
Độ phức tạp:
- Thời gian: O(4n/n)O(4^n / \sqrt{n}) với nn là số cặp ngoặc.
- Bộ nhớ: O(n)O(n) cho mỗi nhánh đệ quy.

Ví dụ

console.log(generateParentheses(3));
// ["((()))", "(()())", "(())()", "()(())", "()()()"]

Câu hỏi 11: Tìm số nguyên dương nhỏ nhất không xuất hiện trong mảng

Cho một mảng số nguyên numsnums, tìm số nguyên dương nhỏ nhất không xuất hiện trong mảng.

Giải pháp 1: Sử dụng Set

function firstMissingPositive(nums) {
const numSet = new Set(nums);
let smallest = 1;
while (numSet.has(smallest)) {
smallest++;
}
return smallest;
}

Phân tích chi tiết

Tạo Set để lưu các phần tử:
- const numSet = new Set(nums): Sử dụng Set để dễ dàng kiểm tra sự tồn tại của phần tử trong O(1)O(1).
Tìm số nguyên dương nhỏ nhất:
- while (numSet.has(smallest)): Kiểm tra từ số nguyên dương 11 trở đi.
- Nếu smallestsmallest không nằm trong Set, trả về giá trị đó.
Độ phức tạp:
- Thời gian: O(n)O(n) để duyệt qua mảng và kiểm tra Set.
- Bộ nhớ: O(n)O(n) để lưu các phần tử vào Set.

Ví dụ

console.log(firstMissingPositive([1, 2, 0])); // 3
console.log(firstMissingPositive([3, 4, -1, 1])); // 2

Giải pháp 2: Sắp xếp và kiểm tra

function firstMissingPositive(nums) {
nums.sort((a, b) => a - b); // Sắp xếp mảng
let smallest = 1;
for (const num of nums) {
if (num === smallest) {
smallest++;
}
}
return smallest;
}

Phân tích chi tiết

Sắp xếp mảng:
- nums.sort((a, b) => a - b): Sắp xếp tăng dần các phần tử.
Duyệt qua mảng:
- if (num === smallest): Nếu gặp giá trị bằng smallest, tăng giá trị cần tìm.
Độ phức tạp:
- Thời gian: O(nlog⁡n)O(n \log n) do sắp xếp mảng.
- Bộ nhớ: O(1)O(1) nếu không tính bộ nhớ cho sắp xếp.

Ví dụ

console.log(firstMissingPositive([1, 2, 0])); // 3
console.log(firstMissingPositive([3, 4, -1, 1])); // 2

Câu hỏi 12: Số Fibonacci ở vị trí thứ nn

Viết hàm tính số Fibonacci tại vị trí nn.

Giải pháp 1: Đệ quy (Chậm)

function fibonacci(n) {
if (n <= 1) return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}

Phân tích chi tiết

Định nghĩa Fibonacci:
- F(0)=0,F(1)=1F(0) = 0, F(1) = 1.
- F(n)=F(n−1)+F(n−2)F(n) = F(n-1) + F(n-2) với n≥2n \geq 2.
Đệ quy:
- Nếu n≤1n \leq 1, trả về nn.
- Ngược lại, trả về tổng của F(n−1)F(n-1) và F(n−2)F(n-2).
Độ phức tạp:
- Thời gian: O(2n)O(2^n) do tính lặp lại.
- Bộ nhớ: O(n)O(n) cho stack đệ quy.

Giải pháp 2: Lặp (Tối ưu)

function fibonacci(n) {
if (n <= 1) return n;
let prev = 0, curr = 1;
for (let i = 2; i <= n; i++) {
const next = prev + curr;
prev = curr;
curr = next;
}
return curr;
}

Phân tích chi tiết

Biến theo dõi:
- prev: Số Fibonacci thứ n−2n-2.
- curr: Số Fibonacci thứ n−1n-1.
Lặp để tính Fibonacci:
- Từ i=2i = 2 đến nn, tính số Fibonacci tiếp theo bằng prev + curr.
- Cập nhật prev và curr cho vòng lặp tiếp theo.
Độ phức tạp:
- Thời gian: O(n)O(n).
- Bộ nhớ: O(1)O(1).

Ví dụ

console.log(fibonacci(10)); // 55
console.log(fibonacci(20)); // 6765

Câu hỏi 13: Đếm số lượng đảo trong lưới

Cho một lưới 2D chứa các phần tử '1' (đất) và '0' (nước). Đếm số lượng đảo (một nhóm các ô '1' được nối liền nhau theo chiều ngang hoặc dọc).

Giải pháp

function numIslands(grid) {
if (!grid || grid.length === 0) return 0;
const rows = grid.length;
const cols = grid[0].length;
let count = 0;
function dfs(row, col) {
if (row < 0 || col < 0 || row >= rows || col >= cols || grid[row][col] === '0') {
return;
}
grid[row][col] = '0'; // Đánh dấu ô đã thăm
// Duyệt 4 hướng
dfs(row + 1, col);
dfs(row - 1, col);
dfs(row, col + 1);
dfs(row, col - 1);
}
for (let row = 0; row < rows; row++) {
for (let col = 0; col < cols; col++) {
if (grid[row][col] === '1') {
count++;
dfs(row, col);
}
}
}
return count;
}

Phân tích chi tiết

Duyệt qua lưới:
- for (let row = 0; row < rows; row++) và for (let col = 0; col < cols; col++): Duyệt qua từng ô trong lưới.
Tìm đảo mới:
- Nếu gặp '1', tăng biến đếm count và gọi hàm DFS để đánh dấu toàn bộ ô thuộc đảo đó.
DFS (Đệ quy):
- dfs(row, col): Nếu vượt ra ngoài lưới hoặc gặp '0', thoát.
- Nếu gặp '1', đánh dấu ô đó là đã thăm (grid[row][col] = '0') và tiếp tục DFS trên 4 hướng.
Độ phức tạp:
- Thời gian: O(m×n)O(m \times n) với m,nm, n là kích thước lưới.
- Bộ nhớ: O(m×n)O(m \times n) cho stack đệ quy.

Ví dụ

console.log(numIslands([
['1', '1', '0', '0', '0'],
['1', '1', '0', '0', '0'],
['0', '0', '1', '0', '0'],
['0', '0', '0', '1', '1']
])); // 3

Câu hỏi 14: Tìm tổng lớn nhất của chuỗi con liên tục (Maximum Subarray)

Cho một mảng số nguyên, tìm tổng lớn nhất của một chuỗi con liên tục.

Giải pháp: Thuật toán Kadane

function maxSubArray(nums) {
let currentSum = nums[0];
let maxSum = nums[0];
for (let i = 1; i < nums.length; i++) {
currentSum = Math.max(nums[i], currentSum + nums[i]);
maxSum = Math.max(maxSum, currentSum);
}
return maxSum;
}

Phân tích chi tiết

Biến khởi tạo:
- currentSum: Tổng của chuỗi con hiện tại (bắt đầu với phần tử đầu tiên).
- maxSum: Tổng lớn nhất đã gặp (khởi tạo bằng giá trị đầu tiên).
Cập nhật giá trị:
- currentSum = Math.max(nums[i], currentSum + nums[i]): Tại mỗi phần tử, quyết định có nên bắt đầu chuỗi con mới từ nums[i] hoặc tiếp tục chuỗi con hiện tại.
- maxSum = Math.max(maxSum, currentSum): Cập nhật tổng lớn nhất.
Độ phức tạp:
- Thời gian: O(n)O(n) (duyệt qua mảng một lần).
- Bộ nhớ: O(1)O(1).

Ví dụ

console.log(maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4])); // 6 ([4, -1, 2, 1])
console.log(maxSubArray([1])); // 1
console.log(maxSubArray([-1, -2, -3])); // -1

Câu hỏi 15: Tìm phần tử duy nhất trong mảng

Cho một mảng số nguyên, trong đó tất cả các phần tử xuất hiện hai lần ngoại trừ một phần tử duy nhất. Tìm phần tử đó.

Giải pháp: XOR

function singleNumber(nums) {
return nums.reduce((acc, num) => acc ^ num, 0);
}

Phân tích chi tiết

Toán tử XOR (^):
- Tính chất:
  - a ^ a = 0: Một số XOR với chính nó bằng 0.
  - a ^ 0 = a: Một số XOR với 0 vẫn là chính nó.
- XOR có tính giao hoán và kết hợp, cho phép loại bỏ tất cả các số xuất hiện hai lần.
Sử dụng reduce:
- .reduce((acc, num) => acc ^ num, 0): XOR tất cả các phần tử trong mảng. Kết quả là phần tử duy nhất.
Độ phức tạp:
- Thời gian: O(n)O(n).
- Bộ nhớ: O(1)O(1).

Ví dụ

console.log(singleNumber([4, 1, 2, 1, 2])); // 4
console.log(singleNumber([2, 2, 3])); // 3

Câu hỏi 16: Đếm số bước để giảm một số xuống 0

Viết hàm đếm số bước cần thiết để giảm một số nn về 0. Nếu nn là số chẵn, chia nó cho 2. Nếu nn là số lẻ, trừ 1.

Giải pháp

function numberOfSteps(n) {
let steps = 0;
while (n > 0) {
if (n % 2 === 0) {
n /= 2;
} else {
n -= 1;
}
steps++;
}
return steps;
}

Phân tích chi tiết

Kiểm tra số chẵn/lẻ:
- if (n % 2 === 0): Nếu nn chia hết cho 2, chia nó cho 2.
- else: Nếu không, giảm nn đi 1.
Đếm số bước:
- steps++: Tăng số bước sau mỗi lần thay đổi nn.
Độ phức tạp:
- Thời gian: O(log⁡n)O(\log n), mỗi bước giảm nn theo cấp số nhân.
- Bộ nhớ: O(1)O(1).

Ví dụ

console.log(numberOfSteps(14)); // 6
console.log(numberOfSteps(8)); // 4
console.log(numberOfSteps(123)); // 12

Câu hỏi 17: Kiểm tra hai chuỗi là hoán vị (Anagrams)

Viết hàm kiểm tra hai chuỗi có phải là hoán vị của nhau không. Chuỗi là hoán vị nếu chúng chứa các ký tự giống nhau với số lần xuất hiện giống nhau.

Giải pháp

function isAnagram(s, t) {
if (s.length !== t.length) return false;
const count = {};
for (let char of s) {
count[char] = (count[char] || 0) + 1;
}
for (let char of t) {
if (!count[char]) return false;
count[char]--;
}
return true;
}

Phân tích chi tiết

Tạo bảng đếm ký tự:
- count[char] = (count[char] || 0) + 1: Đếm số lần xuất hiện của mỗi ký tự trong chuỗi s.
Kiểm tra chuỗi t:
- if (!count[char]) return false: Nếu ký tự trong t không tồn tại hoặc số lượng không khớp, trả về false.
- count[char]--: Giảm số lượng ký tự khi thấy ký tự trong t.
Độ phức tạp:
- Thời gian: O(n)O(n), với nn là độ dài của chuỗi.
- Bộ nhớ: O(1)O(1) cho bảng đếm.

Ví dụ

console.log(isAnagram("anagram", "nagaram")); // true
console.log(isAnagram("rat", "car")); // false

Câu hỏi 18: Đếm số nguyên tố nhỏ hơn nn

Viết hàm đếm số nguyên tố nhỏ hơn nn.

Giải pháp: Sàng Eratosthenes

function countPrimes(n) {
if (n <= 2) return 0;
const isPrime = new Array(n).fill(true);
isPrime[0] = isPrime[1] = false;
for (let i = 2; i * i < n; i++) {
if (isPrime[i]) {
for (let j = i * i; j < n; j += i) {
isPrime[j] = false;
}
}
}
return isPrime.filter(val => val).length;
}

Phân tích chi tiết

Khởi tạo mảng:
- new Array(n).fill(true): Mảng isPrime biểu thị số nguyên nào là số nguyên tố.
- isPrime[0] = isPrime[1] = false: 0 và 1 không phải là số nguyên tố.
Loại bỏ bội số:
- for (let j = i * i; j < n; j += i): Đánh dấu tất cả bội số của ii là không phải số nguyên tố.
Đếm số nguyên tố:
- isPrime.filter(val => val).length: Đếm các giá trị true.
Độ phức tạp:
- Thời gian: O(nlog⁡log⁡n)O(n \log \log n).
- Bộ nhớ: O(n)O(n).

Ví dụ

console.log(countPrimes(10)); // 4 (2, 3, 5, 7)
console.log(countPrimes(0)); // 0
console.log(countPrimes(1)); // 0

Câu hỏi 19: Tìm chỉ số điểm cân bằng (Pivot Index)

Viết hàm nhận vào một mảng số nguyên và trả về chỉ số “điểm cân bằng” nơi tổng các phần tử bên trái bằng tổng các phần tử bên phải. Nếu không có điểm cân bằng, trả về −1-1.

Giải pháp

function pivotIndex(nums) {
const totalSum = nums.reduce((acc, num) => acc + num, 0);
let leftSum = 0;
for (let i = 0; i < nums.length; i++) {
if (leftSum === totalSum - leftSum - nums[i]) {
return i;
}
leftSum += nums[i];
}
return -1;
}

Phân tích chi tiết

Tính tổng toàn bộ mảng:
- const totalSum = nums.reduce((acc, num) => acc + num, 0): Tính tổng tất cả các phần tử trong mảng.
Duyệt qua mảng:
- if (leftSum === totalSum - leftSum - nums[i]): Nếu tổng bên trái == tổng bên phải, trả về chỉ số hiện tại.
- leftSum += nums[i]: Cập nhật tổng bên trái.
Độ phức tạp:
- Thời gian: O(n)O(n), với nn là độ dài mảng.
- Bộ nhớ: O(1)O(1).

Ví dụ

console.log(pivotIndex([1, 7, 3, 6, 5, 6])); // 3
console.log(pivotIndex([1, 2, 3])); // -1
console.log(pivotIndex([2, 1, -1])); // 0

Câu hỏi 20: Tìm sản phẩm của mảng ngoại trừ chính nó (Product of Array Except Self)

Viết hàm nhận vào một mảng số nguyên và trả về một mảng mà mỗi phần tử là tích của tất cả các phần tử khác ngoại trừ chính nó.

Giải pháp

function productExceptSelf(nums) {
const n = nums.length;
const result = new Array(n).fill(1);
let prefix = 1;
for (let i = 0; i < n; i++) {
result[i] *= prefix;
prefix *= nums[i];
}
let suffix = 1;
for (let i = n - 1; i >= 0; i--) {
result[i] *= suffix;
suffix *= nums[i];
}
return result;
}

Phân tích chi tiết

Mảng kết quả (result):
- new Array(n).fill(1): Tạo mảng kết quả với giá trị ban đầu là 11.
Duyệt từ trái sang phải (prefix):
- prefix *= nums[i]: Tích các phần tử từ đầu đến trước ii.
- result[i] *= prefix: Gán tích này vào phần tử kết quả.
Duyệt từ phải sang trái (suffix):
- suffix *= nums[i]: Tích các phần tử từ cuối đến sau ii.
- result[i] *= suffix: Nhân thêm tích này vào phần tử kết quả.
Độ phức tạp:
- Thời gian: O(n)O(n).
- Bộ nhớ: O(1)O(1) nếu không tính mảng kết quả.

Ví dụ

console.log(productExceptSelf([1, 2, 3, 4])); // [24, 12, 8, 6]
console.log(productExceptSelf([0, 1, 2, 3])); // [6, 0, 0, 0]

Câu hỏi 21: Đếm số đảo ngược trong mảng (Inversion Count)

Số đảo ngược là các cặp phần tử trong mảng mà phần tử đứng trước lớn hơn phần tử đứng sau.

Giải pháp 1: Brute Force

function countInversions(nums) {
let count = 0;
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (nums[i] > nums[j]) count++;
}
}
return count;
}

Phân tích chi tiết

Duyệt qua tất cả các cặp phần tử:
- for (let i = 0; i < nums.length; i++) và for (let j = i + 1; j < nums.length; j++): Kiểm tra mọi cặp phần tử.
Kiểm tra điều kiện đảo ngược:
- if (nums[i] > nums[j]): Nếu phần tử đứng trước lớn hơn phần tử đứng sau, tăng biến đếm.
Độ phức tạp:
- Thời gian: O(n2)O(n^2), với nn là độ dài mảng.

Ví dụ

console.log(countInversions([8, 4, 2, 1])); // 6
console.log(countInversions([3, 1, 2])); // 2

Giải pháp 2: Merge Sort (Tối ưu)

function countInversions(nums) {
function mergeSort(arr) {
if (arr.length < 2) return [arr, 0];
const mid = Math.floor(arr.length / 2);
const [left, leftCount] = mergeSort(arr.slice(0, mid));
const [right, rightCount] = mergeSort(arr.slice(mid));
const [merged, splitCount] = merge(left, right);
return [merged, leftCount + rightCount + splitCount];
}
function merge(left, right) {
let result = [];
let count = 0;
let i = 0, j = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
result.push(left[i++]);
} else {
result.push(right[j++]);
count += left.length - i; // Các phần tử còn lại trong `left` đều lớn hơn `right[j]`.
}
}
return [result.concat(left.slice(i)).concat(right.slice(j)), count];
}
const [, inversionCount] = mergeSort(nums);
return inversionCount;
}

Phân tích chi tiết

Merge Sort:
- Chia nhỏ mảng đến khi mỗi mảng chỉ chứa một phần tử.
- Gọi đệ quy hàm mergeSort trên từng nửa mảng.
Merge và đếm đảo ngược:
- So sánh các phần tử trong hai nửa:
  - Nếu left[i] > right[j], các phần tử còn lại trong left đều lớn hơn right[j].
Độ phức tạp:
- Thời gian: O(nlog⁡n)O(n \log n).
- Bộ nhớ: O(n)O(n) cho mảng tạm.

Ví dụ

console.log(countInversions([8, 4, 2, 1])); // 6
console.log(countInversions([3, 1, 2])); // 2

Câu hỏi 22: Tìm chiều dài dãy con tăng dần dài nhất (Longest Increasing Subsequence – LIS)

Viết hàm nhận vào một mảng số nguyên và trả về chiều dài dãy con tăng dần dài nhất.

Giải pháp 1: Dynamic Programming (DP)

function lengthOfLIS(nums) {
if (nums.length === 0) return 0;
const dp = new Array(nums.length).fill(1);
for (let i = 1; i < nums.length; i++) {
for (let j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
return Math.max(...dp);
}

Phân tích chi tiết

Khởi tạo mảng DP:
- dp[i]: Chiều dài dãy con tăng dần dài nhất kết thúc tại chỉ số ii.
- Ban đầu, tất cả các phần tử đều có giá trị 11, vì mỗi phần tử tự nó là một dãy con tăng dần.
Duyệt qua các cặp phần tử:
- Với mỗi phần tử nums[i]nums[i], kiểm tra tất cả các phần tử trước đó nums[j]nums[j]:
  - Nếu nums[i]>nums[j]nums[i] > nums[j]: Cập nhật dp[i] để lấy chiều dài tối đa của dãy con tăng dần.
Kết quả:
- Tìm giá trị lớn nhất trong mảng dp bằng Math.max(...dp).
Độ phức tạp:
- Thời gian: O(n2)O(n^2) do hai vòng lặp lồng nhau.
- Bộ nhớ: O(n)O(n) để lưu mảng dp.

Ví dụ

console.log(lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18])); // 4 ([2, 3, 7, 101])
console.log(lengthOfLIS([0, 1, 0, 3, 2, 3])); // 4 ([0, 1, 2, 3])

Giải pháp 2: Tối ưu bằng Binary Search

function lengthOfLIS(nums) {
const subsequence = [];
for (let num of nums) {
let left = 0, right = subsequence.length;
while (left < right) {
let mid = Math.floor((left + right) / 2);
if (subsequence[mid] < num) {
left = mid + 1;
} else {
right = mid;
}
}
if (left < subsequence.length) {
subsequence[left] = num;
} else {
subsequence.push(num);
}
}
return subsequence.length;
}

Phân tích chi tiết

Mảng subsequence:
- Lưu các phần tử đại diện cho dãy con tăng dần hiện tại.
Binary Search:
- Với mỗi phần tử numnum, tìm vị trí trong subsequence mà numnum nên được chèn vào (hoặc thay thế).
- Nếu numnum lớn hơn tất cả, thêm nó vào cuối subsequence.
Kết quả:
- Chiều dài của subsequence là chiều dài của dãy con tăng dần dài nhất.
Độ phức tạp:
- Thời gian: O(nlog⁡n)O(n \log n), nhờ sử dụng Binary Search.
- Bộ nhớ: O(n)O(n) cho mảng subsequence.

Ví dụ

console.log(lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18])); // 4 ([2, 3, 7, 101])
console.log(lengthOfLIS([0, 1, 0, 3, 2, 3])); // 4 ([0, 1, 2, 3])

Câu hỏi 23: Tìm chuỗi con chung dài nhất (Longest Common Subsequence – LCS)

Viết hàm nhận vào hai chuỗi s1s1 và s2s2 và trả về độ dài của chuỗi con chung dài nhất.

Giải pháp: Dynamic Programming

function longestCommonSubsequence(s1, s2) {
const m = s1.length, n = s2.length;
const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
for (let i = 1; i <= m; i++) {
for (let 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] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}

Phân tích chi tiết

Khởi tạo mảng DP:
- dp[i][j]: Độ dài của LCS giữa s1[0…i−1]s1[0 \ldots i-1] và s2[0…j−1]s2[0 \ldots j-1].
- Ban đầu, dp[0][j]=0dp[0][j] = 0 và dp[i][0]=0dp[i][0] = 0, vì không có chuỗi nào để so sánh.
So sánh từng ký tự:
- Nếu s1[i−1]===s2[j−1]s1[i-1] === s2[j-1]: Tăng độ dài LCS lên 1.
- Nếu không, lấy giá trị lớn nhất giữa dp[i-1][j] và dp[i][j-1].
Kết quả:
- dp[m][n]dp[m][n] là độ dài của LCS.
Độ phức tạp:
- Thời gian: O(m×n)O(m \times n), với m,nm, n là độ dài của hai chuỗi.
- Bộ nhớ: O(m×n)O(m \times n).

Ví dụ

console.log(longestCommonSubsequence("abcde", "ace")); // 3 ("ace")
console.log(longestCommonSubsequence("abc", "def")); // 0

Câu hỏi 24: Đếm số đường đi trong lưới (Unique Paths)

Cho một lưới m×nm \times n, tìm số cách để đi từ góc trên trái đến góc dưới phải, chỉ di chuyển xuống hoặc sang phải.

Giải pháp: Dynamic Programming

function uniquePaths(m, n) {
const dp = Array.from({ length: m }, () => Array(n).fill(1));
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}

Phân tích chi tiết

Khởi tạo mảng DP:
- dp[i][j]: Số cách để đi đến ô (i,j)(i, j).
- Ô đầu tiên dp[0][0]=1dp[0][0] = 1, vì chỉ có một cách để bắt đầu.
Cập nhật số cách:
- Mỗi ô dp[i][j]dp[i][j] là tổng số cách từ ô trên dp[i−1][j]dp[i-1][j] và ô bên trái dp[i][j−1]dp[i][j-1].
Kết quả:
- dp[m−1][n−1]dp[m-1][n-1] là số đường đi đến góc dưới phải.
Độ phức tạp:
- Thời gian: O(m×n)O(m \times n).
- Bộ nhớ: O(m×n)O(m \times n).

Ví dụ

console.log(uniquePaths(3, 7)); // 28
console.log(uniquePaths(3, 2)); // 3

Câu hỏi 25: Tìm các tổ hợp có tổng bằng mục tiêu (Combination Sum)

Viết hàm nhận vào một mảng số nguyên không âm và một số mục tiêu targettarget. Trả về tất cả các tổ hợp của các số trong mảng sao cho tổng bằng targettarget. Một số có thể được sử dụng nhiều lần.

Giải pháp: Backtracking

function combinationSum(candidates, target) {
const result = [];
function backtrack(start, combination, total) {
if (total === target) {
result.push([...combination]);
return;
}
if (total > target) return;
for (let i = start; i < candidates.length; i++) {
combination.push(candidates[i]);
backtrack(i, combination, total + candidates[i]); // Cho phép sử dụng lại `candidates[i]`
combination.pop();
}
}
backtrack(0, [], 0);
return result;
}

Phân tích chi tiết

Backtracking:
- combination: Dãy hiện tại đang xét.
- total: Tổng của dãy hiện tại.
Điều kiện dừng:
- if (total === target): Nếu tổng bằng targettarget, thêm tổ hợp vào kết quả.
- if (total > target): Nếu tổng vượt targettarget, kết thúc nhánh.
Duyệt qua các phần tử:
- for (let i = start; i < candidates.length; i++): Bắt đầu từ chỉ số hiện tại để tránh lặp lại tổ hợp.
Độ phức tạp:
- Thời gian: O(2n)O(2^n) trong trường hợp xấu nhất.
- Bộ nhớ: O(target/min(candidates))O(target / min(candidates)), với min(candidates)min(candidates) là số nhỏ nhất.

Ví dụ

console.log(combinationSum([2, 3, 6, 7], 7)); // [[7], [2, 2, 3]]
console.log(combinationSum([2, 3, 5], 8)); // [[2, 2, 2, 2], [2, 3, 3], [3, 5]]

Câu hỏi 26: Tìm khoảng thời gian không trùng nhau

Cho một danh sách các khoảng thời gian [start,end][start, end]. Viết hàm hợp nhất các khoảng thời gian trùng nhau.

Giải pháp: Sắp xếp và duyệt

function mergeIntervals(intervals) {
if (!intervals.length) return [];
intervals.sort((a, b) => a[0] - b[0]); // Sắp xếp theo thời gian bắt đầu
const result = [intervals[0]];
for (let i = 1; i < intervals.length; i++) {
const prev = result[result.length - 1];
const current = intervals[i];
if (current[0] <= prev[1]) {
prev[1] = Math.max(prev[1], current[1]); // Gộp khoảng thời gian
} else {
result.push(current);
}
}
return result;
}

Phân tích chi tiết

Sắp xếp khoảng thời gian:
- Sắp xếp theo thời gian bắt đầu để dễ dàng xử lý các khoảng thời gian trùng nhau.
Hợp nhất khoảng thời gian:
- if (current[0] <= prev[1]): Nếu khoảng hiện tại chồng lên khoảng trước, gộp chúng lại.
- else: Thêm khoảng hiện tại vào kết quả.
Độ phức tạp:
- Thời gian: O(nlog⁡n)O(n \log n) để sắp xếp và O(n)O(n) để duyệt.
- Bộ nhớ: O(n)O(n) cho mảng kết quả.

Ví dụ

console.log(mergeIntervals([[1, 3], [2, 6], [8, 10], [15, 18]])); // [[1, 6], [8, 10], [15, 18]]
console.log(mergeIntervals([[1, 4], [4, 5]])); // [[1, 5]]

Câu hỏi 27: Đảo ngược từ trong chuỗi

Cho một chuỗi, đảo ngược thứ tự các từ trong chuỗi nhưng giữ nguyên thứ tự các ký tự trong mỗi từ.

Giải pháp

function reverseWords(s) {
return s.trim().split(/\s+/).reverse().join(' ');
}

Phân tích chi tiết

Loại bỏ khoảng trắng thừa:
- trim(): Loại bỏ khoảng trắng ở đầu và cuối chuỗi.
- split(/\s+/): Chia chuỗi thành mảng các từ dựa trên khoảng trắng (bao gồm nhiều khoảng trắng liên tiếp).
Đảo ngược và ghép lại:
- reverse(): Đảo ngược thứ tự các từ trong mảng.
- join(' '): Ghép các từ lại thành chuỗi với khoảng trắng giữa chúng.
Độ phức tạp:
- Thời gian: O(n)O(n), với nn là độ dài chuỗi.
- Bộ nhớ: O(n)O(n) cho mảng từ.

Ví dụ

console.log(reverseWords("  the sky   is blue  ")); // "blue is sky the"
console.log(reverseWords("hello world!")); // "world! hello"

Câu hỏi 28: Tìm chuỗi con dài nhất chứa tối đa kk ký tự khác nhau

Viết hàm nhận vào một chuỗi ss và một số kk, trả về độ dài của chuỗi con dài nhất chứa tối đa kk ký tự khác nhau.

Giải pháp: Sliding Window

function lengthOfLongestSubstringKDistinct(s, k) {
const charMap = new Map();
let left = 0, maxLength = 0;
for (let right = 0; right < s.length; right++) {
charMap.set(s[right], (charMap.get(s[right]) || 0) + 1);
while (charMap.size > k) {
charMap.set(s[left], charMap.get(s[left]) - 1);
if (charMap.get(s[left]) === 0) {
charMap.delete(s[left]);
}
left++;
}
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
}

Phân tích chi tiết

Cửa sổ trượt (Sliding Window):
- left và right: Đại diện cho hai đầu của cửa sổ.
Quản lý số lượng ký tự:
- charMap: Lưu số lần xuất hiện của mỗi ký tự trong cửa sổ.
- Nếu charMap.size > k, di chuyển left để giảm số lượng ký tự khác nhau trong cửa sổ.
Cập nhật độ dài lớn nhất:
- maxLength = Math.max(maxLength, right - left + 1).
Độ phức tạp:
- Thời gian: O(n)O(n), với nn là độ dài chuỗi.
- Bộ nhớ: O(k)O(k), với kk là số ký tự khác nhau tối đa.

Ví dụ

console.log(lengthOfLongestSubstringKDistinct("eceba", 2)); // 3 ("ece")
console.log(lengthOfLongestSubstringKDistinct("aa", 1)); // 2 ("aa")

Câu hỏi 29: Tìm số nguyên tố lớn nhất nhỏ hơn nn

Viết hàm tìm số nguyên tố lớn nhất nhỏ hơn một số nguyên nn.

Giải pháp: Sàng Eratosthenes

function largestPrimeLessThan(n) {
if (n <= 2) return -1;
const isPrime = new Array(n).fill(true);
isPrime[0] = isPrime[1] = false;
for (let i = 2; i * i < n; i++) {
if (isPrime[i]) {
for (let j = i * i; j < n; j += i) {
isPrime[j] = false;
}
}
}
for (let i = n - 1; i >= 2; i--) {
if (isPrime[i]) return i;
}
return -1;
}

Phân tích chi tiết

Sàng Eratosthenes:
- Tạo mảng isPrime với tất cả giá trị ban đầu là true.
- Đánh dấu các số không phải nguyên tố (bội số của các số nguyên tố).
Tìm số nguyên tố lớn nhất nhỏ hơn nn:
- Duyệt ngược từ n−1n-1 đến 22 và trả về số nguyên tố đầu tiên.
Độ phức tạp:
- Thời gian: O(nlog⁡log⁡n)O(n \log \log n).
- Bộ nhớ: O(n)O(n).

Ví dụ

console.log(largestPrimeLessThan(10)); // 7
console.log(largestPrimeLessThan(20)); // 19
console.log(largestPrimeLessThan(2)); // -1

Câu hỏi 30: Xóa phần tử trùng lặp trong mảng đã sắp xếp

Cho một mảng đã được sắp xếp tăng dần, xóa các phần tử trùng lặp sao cho mỗi phần tử chỉ xuất hiện một lần.

Giải pháp

function removeDuplicates(nums) {
if (nums.length === 0) return 0;
let index = 1;
for (let i = 1; i < nums.length; i++) {
if (nums[i] !== nums[i - 1]) {
nums[index] = nums[i];
index++;
}
}
return index;
}

Phân tích chi tiết

Biến index:
- Dùng để đánh dấu vị trí tiếp theo để ghi phần tử không trùng lặp.
Duyệt qua mảng:
- Nếu phần tử hiện tại khác phần tử trước đó, ghi nó vào vị trí index.
Trả về kết quả:
- Giá trị trả về là số lượng phần tử không trùng lặp trong mảng.
Độ phức tạp:
- Thời gian: O(n)O(n), duyệt qua mảng một lần.
- Bộ nhớ: O(1)O(1), không sử dụng cấu trúc dữ liệu bổ sung.

Ví dụ

const nums = [1, 1, 2];
console.log(removeDuplicates(nums)); // 2
console.log(nums.slice(0, 2)); // [1, 2]
const nums2 = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4];
console.log(removeDuplicates(nums2)); // 5
console.log(nums2.slice(0, 5)); // [0, 1, 2, 3, 4]

Câu hỏi 31: Tìm nước trong cột (Trapping Rain Water)

Cho một mảng số nguyên đại diện cho chiều cao các cột, tính lượng nước có thể giữ lại giữa các cột.

Giải pháp: Hai con trỏ

function trap(height) {
if (height.length === 0) return 0;
let left = 0, right = height.length - 1;
let leftMax = 0, rightMax = 0, water = 0;
while (left < right) {
if (height[left] < height[right]) {
if (height[left] >= leftMax) {
leftMax = height[left];
} else {
water += leftMax - height[left];
}
left++;
} else {
if (height[right] >= rightMax) {
rightMax = height[right];
} else {
water += rightMax - height[right];
}
right--;
}
}
return water;
}

Phân tích chi tiết

Hai con trỏ:
- left và right: Đầu và cuối mảng.
- leftMax và rightMax: Chiều cao cột lớn nhất bên trái và bên phải.
Tính nước tích lũy:
- Nếu chiều cao cột nhỏ hơn max bên trái hoặc bên phải, nước có thể được giữ lại bằng hiệu số giữa max và chiều cao cột hiện tại.
Độ phức tạp:
- Thời gian: O(n)O(n), chỉ duyệt qua mảng một lần.
- Bộ nhớ: O(1)O(1), không sử dụng cấu trúc dữ liệu bổ sung.

Ví dụ

console.log(trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1])); // 6
console.log(trap([4, 2, 0, 3, 2, 5])); // 9

Câu hỏi 32: Sắp xếp mảng 0, 1, 2 (Dutch National Flag Problem)

Sắp xếp mảng chứa các số 00, 11, và 22 sao cho các số 00 nằm trước, 11 ở giữa và 22 ở cuối.

Giải pháp: Ba con trỏ

function sortColors(nums) {
let low = 0, mid = 0, high = nums.length - 1;
while (mid <= high) {
if (nums[mid] === 0) {
[nums[low], nums[mid]] = [nums[mid], nums[low]];
low++;
mid++;
} else if (nums[mid] === 1) {
mid++;
} else {
[nums[mid], nums[high]] = [nums[high], nums[mid]];
high--;
}
}
}

Phân tích chi tiết

Ba con trỏ:
- low: Chỉ số cho các phần tử 00.
- mid: Chỉ số hiện tại đang xử lý.
- high: Chỉ số cho các phần tử 22.
Hoán đổi giá trị:
- Nếu phần tử là 00, hoán đổi với low và tăng cả low và mid.
- Nếu phần tử là 22, hoán đổi với high và giảm high.
Độ phức tạp:
- Thời gian: O(n)O(n), mỗi phần tử được xử lý một lần.
- Bộ nhớ: O(1)O(1), không sử dụng cấu trúc dữ liệu bổ sung.

Ví dụ

const nums = [2, 0, 2, 1, 1, 0];
sortColors(nums);
console.log(nums); // [0, 0, 1, 1, 2, 2]
const nums2 = [2, 0, 1];
sortColors(nums2);
console.log(nums2); // [0, 1, 2]

Câu hỏi 33: Tìm số lần đảo ngược để mảng tăng dần (Minimum Swaps to Sort)

Viết hàm nhận vào một mảng số nguyên và trả về số lần hoán đổi tối thiểu để sắp xếp mảng tăng dần.

Giải pháp

function minSwapsToSort(arr) {
const n = arr.length;
const arrWithIndex = arr.map((value, index) => ({ value, index }));
arrWithIndex.sort((a, b) => a.value - b.value);
const visited = new Array(n).fill(false);
let swaps = 0;
for (let i = 0; i < n; i++) {
if (visited[i] || arrWithIndex[i].index === i) {
continue;
}
let cycleSize = 0;
let j = i;
while (!visited[j]) {
visited[j] = true;
j = arrWithIndex[j].index;
cycleSize++;
}
if (cycleSize > 1) {
swaps += cycleSize - 1;
}
}
return swaps;
}

Phân tích chi tiết

Tạo mảng với chỉ số ban đầu:
- arr.map((value, index) => ({ value, index })): Tạo mảng chứa giá trị và chỉ số gốc.
- sort((a, b) => a.value - b.value): Sắp xếp mảng theo giá trị.
Tìm chu trình hoán đổi:
- Nếu một phần tử đã được sắp xếp đúng vị trí hoặc đã thăm, bỏ qua (visited[i]).
- Duyệt qua chu trình để tính kích thước chu trình (cycleSize).
Tính số lần hoán đổi:
- Với chu trình kích thước kk, cần k−1k – 1 lần hoán đổi để sắp xếp.
Độ phức tạp:
- Thời gian: O(nlog⁡n)O(n \log n) cho sắp xếp và O(n)O(n) cho duyệt chu trình.
- Bộ nhớ: O(n)O(n).

Ví dụ

console.log(minSwapsToSort([4, 3, 2, 1])); // 2
console.log(minSwapsToSort([1, 5, 4, 3, 2])); // 2

Câu hỏi 34: Tìm tổng dãy con liên tục chia hết cho kk (Subarray Sum Divisible by kk)

Viết hàm nhận vào một mảng số nguyên và một số kk, trả về số lượng dãy con liên tục có tổng chia hết cho kk.

Giải pháp

function subarraysDivByK(nums, k) {
const remainderMap = new Map();
remainderMap.set(0, 1);
let sum = 0, count = 0;
for (let num of nums) {
sum += num;
let remainder = ((sum % k) + k) % k;
if (remainderMap.has(remainder)) {
count += remainderMap.get(remainder);
}
remainderMap.set(remainder, (remainderMap.get(remainder) || 0) + 1);
}
return count;
}

Phân tích chi tiết

Tính tổng và dư:
- sum += num: Tính tổng dãy con hiện tại.
- remainder = ((sum % k) + k) % k: Đảm bảo dư không âm.
Đếm số dãy con:
- Nếu dư đã tồn tại trong remainderMap, số dãy con có tổng chia hết cho kk tăng thêm giá trị lưu trong remainderMap.
Cập nhật bản đồ dư:
- Tăng số lần xuất hiện của dư hiện tại trong remainderMap.
Độ phức tạp:
- Thời gian: O(n)O(n), duyệt qua mảng một lần.
- Bộ nhớ: O(k)O(k), với kk là số dư tối đa.

Ví dụ

console.log(subarraysDivByK([4, 5, 0, -2, -3, 1], 5)); // 7
console.log(subarraysDivByK([5, 10, 11], 5)); // 5

Câu hỏi 35: Kiểm tra mảng con với tổng kk (Subarray Sum Equals kk)

Viết hàm nhận vào một mảng số nguyên và một số kk, kiểm tra xem có tồn tại dãy con liên tục với tổng bằng kk.

Giải pháp

function subarraySum(nums, k) {
const sumMap = new Map();
sumMap.set(0, 1);
let sum = 0, count = 0;
for (let num of nums) {
sum += num;
if (sumMap.has(sum - k)) {
count += sumMap.get(sum - k);
}
sumMap.set(sum, (sumMap.get(sum) || 0) + 1);
}
return count;
}

Phân tích chi tiết

Tính tổng dãy con:
- sum += num: Cộng giá trị phần tử hiện tại vào tổng.
Kiểm tra tổng kk:
- if (sumMap.has(sum - k)): Nếu tổng hiện tại trừ kk tồn tại trong sumMap, tăng biến đếm.
Cập nhật bản đồ tổng:
- Tăng số lần xuất hiện của tổng hiện tại trong sumMap.
Độ phức tạp:
- Thời gian: O(n)O(n).
- Bộ nhớ: O(n)O(n).

Ví dụ

console.log(subarraySum([1, 1, 1], 2)); // 2
console.log(subarraySum([1, 2, 3], 3)); // 2

Câu hỏi 36: Kiểm tra chuỗi có thể được sắp xếp thành Palindrome

Viết hàm kiểm tra xem một chuỗi có thể được sắp xếp thành một Palindrome không.

Giải pháp

function canPermutePalindrome(s) {
const charCount = new Map();
for (let char of s) {
charCount.set(char, (charCount.get(char) || 0) + 1);
}
let oddCount = 0;
for (let count of charCount.values()) {
if (count % 2 !== 0) oddCount++;
if (oddCount > 1) return false;
}
return true;
}

Phân tích chi tiết

Đếm ký tự:
- charCount: Lưu số lần xuất hiện của mỗi ký tự.
Kiểm tra số ký tự lẻ:
- Một chuỗi có thể sắp xếp thành Palindrome nếu tối đa chỉ có một ký tự xuất hiện lẻ.
Độ phức tạp:
- Thời gian: O(n)O(n), với nn là độ dài chuỗi.
- Bộ nhớ: O(k)O(k), với kk là số ký tự khác nhau.

Ví dụ

console.log(canPermutePalindrome("civic")); // true
console.log(canPermutePalindrome("ivicc")); // true
console.log(canPermutePalindrome("hello")); // false

Câu hỏi 37: Đếm số hình chữ nhật chứa toàn số 1 trong ma trận

Viết hàm nhận vào một ma trận nhị phân (chỉ chứa 00 và 11) và trả về số lượng hình chữ nhật chứa toàn số 11.

Giải pháp

function countSubmatricesWithAllOnes(matrix) {
const m = matrix.length;
const n = matrix[0].length;
const heights = new Array(n).fill(0);
let count = 0;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
heights[j] = matrix[i][j] === 0 ? 0 : heights[j] + 1;
}
count += countSubmatricesWithHeights(heights);
}
return count;
}
function countSubmatricesWithHeights(heights) {
const stack = [];
const n = heights.length;
const count = new Array(n).fill(0);
let result = 0;
for (let i = 0; i < n; i++) {
while (stack.length && heights[stack[stack.length - 1]] >= heights[i]) {
stack.pop();
}
const prevIndex = stack.length === 0 ? -1 : stack[stack.length - 1];
count[i] = (i - prevIndex) * heights[i] + (prevIndex === -1 ? 0 : count[prevIndex]);
result += count[i];
stack.push(i);
}
return result;
}

Phân tích chi tiết

Tính chiều cao của các cột:
- Với mỗi hàng, tính heights[j], là chiều cao của cột tính đến hàng hiện tại.
Đếm số hình chữ nhật chứa toàn 11:
- Sử dụng countSubmatricesWithHeights để đếm số hình chữ nhật trong hàng hiện tại dựa trên chiều cao.
Xử lý stack để tìm chiều cao tối ưu:
- Với mỗi cột, xác định số hình chữ nhật có thể tạo dựa trên chiều cao liên tiếp.
Độ phức tạp:
- Thời gian: O(m×n)O(m \times n), với m,nm, n là số hàng và cột của ma trận.
- Bộ nhớ: O(n)O(n) cho chiều cao và stack.

Ví dụ

console.log(countSubmatricesWithAllOnes([
[1, 0, 1],
[1, 1, 0],
[1, 1, 0]
])); // 5
console.log(countSubmatricesWithAllOnes([
[0, 1, 1],
[1, 1, 1],
[1, 1, 1]
])); // 15

Câu hỏi 38: Tìm số lượng đảo đơn lẻ trong ma trận

Cho một ma trận nhị phân (chỉ chứa 00 và 11), tìm số lượng các đảo (khu vực chứa 11 liền kề nhau theo chiều ngang, dọc).

Giải pháp: DFS

function numIslands(grid) {
if (!grid || grid.length === 0) return 0;
const m = grid.length;
const n = grid[0].length;
let count = 0;
function dfs(x, y) {
if (x < 0 || y < 0 || x >= m || y >= n || grid[x][y] === '0') return;
grid[x][y] = '0'; // Đánh dấu đã thăm
dfs(x + 1, y); // Xuống
dfs(x - 1, y); // Lên
dfs(x, y + 1); // Phải
dfs(x, y - 1); // Trái
}
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === '1') {
count++;
dfs(i, j);
}
}
}
return count;
}

Phân tích chi tiết

Duyệt qua ma trận:
- Với mỗi ô chứa 11, gọi hàm DFS để đánh dấu tất cả các ô trong cùng một đảo.
DFS để đánh dấu:
- Đánh dấu ô hiện tại là đã thăm bằng cách đổi giá trị 11 thành 00.
- Đệ quy tìm tất cả các ô liên kề theo 4 hướng.
Độ phức tạp:
- Thời gian: O(m×n)O(m \times n), với m,nm, n là kích thước ma trận.
- Bộ nhớ: O(m×n)O(m \times n) cho stack đệ quy.

Ví dụ

console.log(numIslands([
['1', '1', '0', '0', '0'],
['1', '1', '0', '0', '0'],
['0', '0', '1', '0', '0'],
['0', '0', '0', '1', '1']
])); // 3
console.log(numIslands([
['1', '0', '1', '0', '1']
])); // 3

Câu hỏi 39: Tìm từ trong bảng (Word Search)

Viết hàm kiểm tra xem một từ có thể được tạo ra từ các ký tự liên tiếp trong bảng (theo chiều ngang hoặc dọc).

Giải pháp: Backtracking

function exist(board, word) {
const m = board.length;
const n = board[0].length;
function backtrack(x, y, index) {
if (index === word.length) return true;
if (x < 0 || y < 0 || x >= m || y >= n || board[x][y] !== word[index]) return false;
const temp = board[x][y];
board[x][y] = '#'; // Đánh dấu đã thăm
const found = backtrack(x + 1, y, index + 1) ||
backtrack(x - 1, y, index + 1) ||
backtrack(x, y + 1, index + 1) ||
backtrack(x, y - 1, index + 1);
board[x][y] = temp; // Hoàn nguyên
return found;
}
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (backtrack(i, j, 0)) return true;
}
}
return false;
}

Phân tích chi tiết

Backtracking:
- Với mỗi ô, kiểm tra xem ký tự tại ô đó có khớp với ký tự hiện tại trong từ không.
- Di chuyển đến các ô lân cận nếu ký tự khớp.
Đánh dấu và hoàn nguyên:
- Đánh dấu ô hiện tại là đã thăm bằng cách gán giá trị đặc biệt '#'.
- Sau khi hoàn thành nhánh, hoàn nguyên lại giá trị ban đầu.
Độ phức tạp:
- Thời gian: O(m×n×4l)O(m \times n \times 4^l), với m,nm, n là kích thước bảng và ll là độ dài từ.
- Bộ nhớ: O(l)O(l) cho stack đệ quy.

Ví dụ

console.log(exist([
['A', 'B', 'C', 'E'],
['S', 'F', 'C', 'S'],
['A', 'D', 'E', 'E']
], 'ABCCED')); // true
console.log(exist([
['A', 'B', 'C', 'E'],
['S', 'F', 'C', 'S'],
['A', 'D', 'E', 'E']
], 'SEE')); // true
console.log(exist([
['A', 'B', 'C', 'E'],
['S', 'F', 'C', 'S'],
['A', 'D', 'E', 'E']
], 'ABCB')); // false

Câu hỏi 40: Kiểm tra đường tròn con trong danh sách liên kết (Linked List Cycle)

Viết hàm kiểm tra xem danh sách liên kết có chứa đường tròn (vòng lặp) hay không.

Giải pháp: Floyd’s Cycle Detection Algorithm

function hasCycle(head) {
if (!head || !head.next) return false;
let slow = head;
let fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) return true;
}
return false;
}

Phân tích chi tiết

Hai con trỏ:
- slow: Di chuyển một bước mỗi lần.
- fast: Di chuyển hai bước mỗi lần.
Kiểm tra vòng lặp:
- Nếu slow và fast gặp nhau, danh sách liên kết có vòng lặp.
- Nếu fast hoặc fast.next là null, không có vòng lặp.
Độ phức tạp:
- Thời gian: O(n)O(n), với nn là số lượng node trong danh sách liên kết.
- Bộ nhớ: O(1)O(1), không sử dụng cấu trúc dữ liệu bổ sung.

Ví dụ

class ListNode {
constructor(value) {
this.value = value;
this.next = null;
}
}
const head = new ListNode(3);
head.next = new ListNode(2);
head.next.next = new ListNode(0);
head.next.next.next = new ListNode(-4);
head.next.next.next.next = head.next;
console.log(hasCycle(head)); // true
const noCycleHead = new ListNode(1);
noCycleHead.next = new ListNode(2);
console.log(hasCycle(noCycleHead)); // false

Câu hỏi 41: Tìm điểm bắt đầu của đường tròn trong danh sách liên kết

Viết hàm trả về node bắt đầu của đường tròn trong danh sách liên kết. Nếu không có vòng lặp, trả về null.

Giải pháp

function detectCycle(head) {
if (!head || !head.next) return null;
let slow = head;
let fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) {
let entry = head;
while (entry !== slow) {
entry = entry.next;
slow = slow.next;
}
return entry;
}
}
return null;
}

Phân tích chi tiết

Phát hiện vòng lặp:
- Sử dụng hai con trỏ (slow và fast) để tìm điểm gặp nhau nếu có vòng lặp.
Tìm điểm bắt đầu:
- Đặt một con trỏ từ head và con trỏ khác từ điểm gặp nhau.
- Di chuyển cả hai con trỏ một bước mỗi lần, chúng sẽ gặp nhau tại điểm bắt đầu vòng lặp.
Độ phức tạp:
- Thời gian: O(n)O(n).
- Bộ nhớ: O(1)O(1).

Ví dụ

const head = new ListNode(3);
head.next = new ListNode(2);
head.next.next = new ListNode(0);
head.next.next.next = new ListNode(-4);
head.next.next.next.next = head.next;
console.log(detectCycle(head)); // ListNode { value: 2, next: ListNode { ... } }
const noCycleHead = new ListNode(1);
noCycleHead.next = new ListNode(2);
console.log(detectCycle(noCycleHead)); // null

Câu hỏi 42: Tìm phần tử giao nhau của hai danh sách liên kết

Viết hàm nhận vào hai danh sách liên kết đơn và trả về node đầu tiên nơi hai danh sách giao nhau. Nếu không có giao điểm, trả về null.

Giải pháp

function getIntersectionNode(headA, headB) {
if (!headA || !headB) return null;
let pointerA = headA;
let pointerB = headB;
while (pointerA !== pointerB) {
pointerA = pointerA ? pointerA.next : headB;
pointerB = pointerB ? pointerB.next : headA;
}
return pointerA;
}

Phân tích chi tiết

Chuyển đổi danh sách:
- Khi một con trỏ đến cuối danh sách của nó, chuyển nó sang đầu danh sách kia.
- Điều này đảm bảo hai con trỏ sẽ gặp nhau tại node giao nhau hoặc nullnull nếu không có giao điểm.
Độ phức tạp:
- Thời gian: O(m+n)O(m + n), với m,nm, n là độ dài hai danh sách.
- Bộ nhớ: O(1)O(1).

Ví dụ

const intersectNode = new ListNode(8);
intersectNode.next = new ListNode(4);
intersectNode.next.next = new ListNode(5);
const headA = new ListNode(4);
headA.next = new ListNode(1);
headA.next.next = intersectNode;
const headB = new ListNode(5);
headB.next = new ListNode(0);
headB.next.next = new ListNode(1);
headB.next.next.next = intersectNode;
console.log(getIntersectionNode(headA, headB)); // ListNode { value: 8, next: ListNode { ... } }
const noIntersectionA = new ListNode(1);
const noIntersectionB = new ListNode(2);
console.log(getIntersectionNode(noIntersectionA, noIntersectionB)); // null

Câu hỏi 43: Xóa node giữa trong danh sách liên kết

Viết hàm nhận vào một node trong danh sách liên kết, xóa node đó mà không cần truy cập vào đầu danh sách.

Giải pháp

function deleteNode(node) {
if (!node || !node.next) return;
node.value = node.next.value;
node.next = node.next.next;
}

Phân tích chi tiết

Xóa node:
- Thay thế giá trị của node hiện tại bằng giá trị của node tiếp theo.
- Kết nối node hiện tại tới node sau của node tiếp theo.
Độ phức tạp:
- Thời gian: O(1)O(1).
- Bộ nhớ: O(1)O(1).

Ví dụ

const head = new ListNode(4);
head.next = new ListNode(5);
head.next.next = new ListNode(1);
head.next.next.next = new ListNode(9);
deleteNode(head.next);
console.log(head); // ListNode { value: 4, next: ListNode { value: 1, next: ListNode { value: 9, next: null } } }

Câu hỏi 44: Đảo ngược một danh sách liên kết

Viết hàm đảo ngược một danh sách liên kết đơn.

Giải pháp

function reverseList(head) {
let prev = null;
let current = head;
while (current) {
let nextNode = current.next;
current.next = prev;
prev = current;
current = nextNode;
}
return prev;
}

Phân tích chi tiết

Biến khởi tạo:
- prev: Node trước đó, bắt đầu là null.
- current: Node hiện tại, bắt đầu từ head.
Duyệt qua danh sách:
- Lưu current.next vào nextNode để không mất liên kết.
- Gán current.next trỏ về prev.
- Cập nhật prev và current để chuyển sang node tiếp theo.
**Trả về node cuối cùng (bây giờ là prev) làm đầu danh sách đảo ngược.
Độ phức tạp:
- Thời gian: O(n)O(n), với nn là số node trong danh sách.
- Bộ nhớ: O(1)O(1), không sử dụng cấu trúc dữ liệu bổ sung.

Ví dụ

const head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(4);
const reversedHead = reverseList(head);
// ListNode { value: 4, next: ListNode { value: 3, next: ListNode { value: 2, next: ListNode { value: 1, next: null } } } }

Câu hỏi 45: Kiểm tra danh sách liên kết có đối xứng không (Palindrome)

Viết hàm kiểm tra xem danh sách liên kết có phải là một Palindrome không.

Giải pháp

function isPalindrome(head) {
if (!head || !head.next) return true;
let slow = head, fast = head;
// Tìm điểm giữa của danh sách
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
}
// Đảo ngược nửa sau của danh sách
let prev = null;
while (slow) {
let nextNode = slow.next;
slow.next = prev;
prev = slow;
slow = nextNode;
}
// So sánh hai nửa danh sách
let left = head, right = prev;
while (right) {
if (left.value !== right.value) return false;
left = left.next;
right = right.next;
}
return true;
}

Phân tích chi tiết

Tìm điểm giữa:
- Sử dụng hai con trỏ slow và fast để tìm điểm giữa danh sách.
Đảo ngược nửa sau:
- Đảo ngược danh sách bắt đầu từ điểm giữa.
So sánh hai nửa:
- So sánh từng node của hai nửa danh sách.
Độ phức tạp:
- Thời gian: O(n)O(n), với nn là số node trong danh sách.
- Bộ nhớ: O(1)O(1).

Ví dụ

const head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(2);
head.next.next.next = new ListNode(1);
console.log(isPalindrome(head)); // true
const nonPalindromeHead = new ListNode(1);
nonPalindromeHead.next = new ListNode(2);
nonPalindromeHead.next.next = new ListNode(3);
console.log(isPalindrome(nonPalindromeHead)); // false

Câu hỏi 46: Xóa node thứ nn từ cuối danh sách

Viết hàm xóa node thứ nn từ cuối danh sách liên kết.

Giải pháp

function removeNthFromEnd(head, n) {
const dummy = new ListNode(0);
dummy.next = head;
let first = dummy;
let second = dummy;
// Di chuyển `first` cách `n + 1` bước
for (let i = 0; i <= n; i++) {
first = first.next;
}
// Di chuyển cả `first` và `second` cho đến khi `first` đến cuối
while (first) {
first = first.next;
second = second.next;
}
// Xóa node thứ n
second.next = second.next.next;
return dummy.next;
}

Phân tích chi tiết

Dummy Node:
- Thêm một node giả ở đầu danh sách để xử lý trường hợp đặc biệt (xóa node đầu).
Di chuyển con trỏ:
- first di chuyển cách n + 1 bước để tạo khoảng cách với second.
- Di chuyển cả hai con trỏ cho đến khi first đạt cuối danh sách.
Xóa node:
- second.next = second.next.next: Bỏ qua node thứ nn.
Độ phức tạp:
- Thời gian: O(n)O(n).
- Bộ nhớ: O(1)O(1).

Ví dụ

const head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(4);
head.next.next.next.next = new ListNode(5);
const updatedHead = removeNthFromEnd(head, 2);
// ListNode { value: 1, next: ListNode { value: 2, next: ListNode { value: 3, next: ListNode { value: 5, next: null } } } }

Câu hỏi 47: Thêm hai số dưới dạng danh sách liên kết

Viết hàm nhận vào hai danh sách liên kết biểu diễn hai số nguyên, trả về danh sách liên kết biểu diễn tổng của hai số đó.

Giải pháp

function addTwoNumbers(l1, l2) {
const dummy = new ListNode(0);
let current = dummy;
let carry = 0;
while (l1 || l2 || carry) {
const sum = (l1 ? l1.value : 0) + (l2 ? l2.value : 0) + carry;
carry = Math.floor(sum / 10);
current.next = new ListNode(sum % 10);
current = current.next;
if (l1) l1 = l1.next;
if (l2) l2 = l2.next;
}
return dummy.next;
}

Phân tích chi tiết

Tính tổng node hiện tại:
- Tổng bao gồm giá trị của node hiện tại từ hai danh sách và số dư carry.
Tính số dư và phần còn lại:
- carry = Math.floor(sum / 10): Số dư cho bước tiếp theo.
- sum % 10: Phần còn lại để thêm vào danh sách.
Duyệt qua danh sách:
- Di chuyển đến node tiếp theo trong cả hai danh sách.
Độ phức tạp:
- Thời gian: O(max⁡(m,n))O(\max(m, n)), với m,nm, n là số node của hai danh sách.
- Bộ nhớ: O(max⁡(m,n))O(\max(m, n)).

Ví dụ

const l1 = new ListNode(2);
l1.next = new ListNode(4);
l1.next.next = new ListNode(3);
const l2 = new ListNode(5);
l2.next = new ListNode(6);
l2.next.next = new ListNode(4);
const result = addTwoNumbers(l1, l2);
// ListNode { value: 7, next: ListNode { value: 0, next: ListNode { value: 8, next: null } } }

Câu hỏi 48: Hợp nhất kk danh sách liên kết đã sắp xếp

Viết hàm hợp nhất kk danh sách liên kết đã sắp xếp thành một danh sách liên kết duy nhất cũng được sắp xếp.

Giải pháp: Sử dụng Min-Heap

class MinHeap {
constructor() {
this.heap = [];
}
insert(node) {
this.heap.push(node);
this.bubbleUp(this.heap.length - 1);
}
bubbleUp(index) {
while (index > 0) {
const parentIndex = Math.floor((index - 1) / 2);
if (this.heap[parentIndex].value > this.heap[index].value) {
[this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]];
index = parentIndex;
} else break;
}
}
remove() {
if (this.heap.length === 0) return null;
if (this.heap.length === 1) return this.heap.pop();
const top = this.heap[0];
this.heap[0] = this.heap.pop();
this.bubbleDown(0);
return top;
}
bubbleDown(index) {
const length = this.heap.length;
while (true) {
let smallest = index;
const left = 2 * index + 1;
const right = 2 * index + 2;
if (left < length && this.heap[left].value < this.heap[smallest].value) {
smallest = left;
}
if (right < length && this.heap[right].value < this.heap[smallest].value) {
smallest = right;
}
if (smallest === index) break;
[this.heap[smallest], this.heap[index]] = [this.heap[index], this.heap[smallest]];
index = smallest;
}
}
size() {
return this.heap.length;
}
}
function mergeKLists(lists) {
const heap = new MinHeap();
const dummy = new ListNode(0);
let current = dummy;
for (const list of lists) {
if (list) heap.insert(list);
}
while (heap.size() > 0) {
const smallest = heap.remove();
current.next = smallest;
current = current.next;
if (smallest.next) {
heap.insert(smallest.next);
}
}
return dummy.next;
}

Phân tích chi tiết

Min-Heap:
- Min-Heap được sử dụng để luôn lấy node nhỏ nhất trong số các danh sách liên kết.
Thêm vào Heap:
- Ban đầu, thêm node đầu tiên của mỗi danh sách vào heap.
Hợp nhất danh sách:
- Lấy node nhỏ nhất từ heap, thêm vào danh sách kết quả.
- Nếu node này có next, thêm next vào heap.
Độ phức tạp:
- Thời gian: O(Nlog⁡k)O(N \log k), với NN là tổng số node và kk là số danh sách.
- Bộ nhớ: O(k)O(k) cho heap.

Ví dụ

const l1 = new ListNode(1);
l1.next = new ListNode(4);
l1.next.next = new ListNode(5);
const l2 = new ListNode(1);
l2.next = new ListNode(3);
l2.next.next = new ListNode(4);
const l3 = new ListNode(2);
l3.next = new ListNode(6);
const merged = mergeKLists([l1, l2, l3]);
// ListNode { value: 1, next: ListNode { value: 1, next: ListNode { value: 2, next: ListNode { value: 3, next: ... } } } }

Câu hỏi 49: Tìm node giữa trong danh sách liên kết

Viết hàm trả về node giữa của danh sách liên kết. Nếu danh sách có số lượng node chẵn, trả về node thứ hai trong hai node giữa.

Giải pháp: Hai con trỏ

function middleNode(head) {
let slow = head;
let fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}

Phân tích chi tiết

Hai con trỏ:
- slow: Di chuyển một bước mỗi lần.
- fast: Di chuyển hai bước mỗi lần.
Tìm node giữa:
- Khi fast đạt cuối danh sách, slow sẽ ở node giữa.
Độ phức tạp:
- Thời gian: O(n)O(n), với nn là số node.
- Bộ nhớ: O(1)O(1).

Ví dụ

const head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(4);
head.next.next.next.next = new ListNode(5);
console.log(middleNode(head)); // ListNode { value: 3, next: ListNode { value: 4, next: ListNode { value: 5, next: null } } }

Câu hỏi 50: Chia danh sách liên kết thành hai phần theo giá trị xx

Viết hàm chia danh sách liên kết thành hai phần: các node nhỏ hơn xx ở trước và các node lớn hơn hoặc bằng xx ở sau.

Giải pháp

function partition(head, x) {
const beforeDummy = new ListNode(0);
const afterDummy = new ListNode(0);
let before = beforeDummy;
let after = afterDummy;
while (head) {
if (head.value < x) {
before.next = head;
before = before.next;
} else {
after.next = head;
after = after.next;
}
head = head.next;
}
after.next = null; // Kết thúc danh sách sau
before.next = afterDummy.next; // Nối danh sách trước và sau
return beforeDummy.next;
}

Phân tích chi tiết

Hai danh sách:
- beforeDummy: Lưu các node nhỏ hơn xx.
- afterDummy: Lưu các node lớn hơn hoặc bằng xx.
Duyệt danh sách:
- Thêm node vào danh sách before hoặc after dựa trên giá trị.
Nối hai danh sách:
- Kết nối danh sách before với after.
Độ phức tạp:
- Thời gian: O(n)O(n).
- Bộ nhớ: O(1)O(1).

Ví dụ

const head = new ListNode(1);
head.next = new ListNode(4);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(2);
head.next.next.next.next = new ListNode(5);
head.next.next.next.next.next = new ListNode(2);
const partitioned = partition(head, 3);
// ListNode { value: 1, next: ListNode { value: 2, next: ListNode { value: 2, next: ListNode { value: 4, next: ... } } } }

Câu hỏi 51: Hợp nhất hai danh sách liên kết đã sắp xếp

Viết hàm hợp nhất hai danh sách liên kết đã sắp xếp thành một danh sách liên kết duy nhất cũng được sắp xếp.

Giải pháp

function mergeTwoLists(l1, l2) {
const dummy = new ListNode(0);
let current = dummy;
while (l1 && l2) {
if (l1.value <= l2.value) {
current.next = l1;
l1 = l1.next;
} else {
current.next = l2;
l2 = l2.next;
}
current = current.next;
}
current.next = l1 || l2;
return dummy.next;
}

Phân tích chi tiết

Dummy Node:
- Sử dụng một node giả dummy để dễ dàng xây dựng danh sách kết quả.
So sánh các phần tử:
- So sánh giá trị node hiện tại của l1 và l2, thêm node có giá trị nhỏ hơn vào danh sách kết quả.
Xử lý phần còn lại:
- Nếu một trong hai danh sách còn node chưa được xử lý, gán toàn bộ phần còn lại vào danh sách kết quả.
Độ phức tạp:
- Thời gian: O(m+n)O(m + n), với m,nm, n là số node trong hai danh sách.
- Bộ nhớ: O(1)O(1), không sử dụng thêm bộ nhớ ngoài.

Ví dụ

const l1 = new ListNode(1);
l1.next = new ListNode(2);
l1.next.next = new ListNode(4);
const l2 = new ListNode(1);
l2.next = new ListNode(3);
l2.next.next = new ListNode(4);
const merged = mergeTwoLists(l1, l2);
// ListNode { value: 1, next: ListNode { value: 1, next: ListNode { value: 2, next: ListNode { value: 3, next: ... } } } }

Câu hỏi 52: Xoay danh sách liên kết sang phải

Viết hàm xoay danh sách liên kết sang phải kk lần.

Giải pháp

function rotateRight(head, k) {
if (!head || !head.next || k === 0) return head;
let length = 1;
let tail = head;
// Tính độ dài danh sách và tìm node cuối
while (tail.next) {
tail = tail.next;
length++;
}
k = k % length;
if (k === 0) return head;
// Nối đuôi danh sách với đầu danh sách
tail.next = head;
// Tìm node mới để cắt
let stepsToNewHead = length - k;
let newTail = tail;
while (stepsToNewHead--) {
newTail = newTail.next;
}
const newHead = newTail.next;
newTail.next = null;
return newHead;
}

Phân tích chi tiết

Tính độ dài danh sách:
- Xác định số node trong danh sách và node cuối cùng.
Điều chỉnh kk:
- k=k%lengthk = k \% length: Đảm bảo số lần xoay không vượt quá độ dài danh sách.
Xoay danh sách:
- Nối đuôi danh sách với đầu danh sách.
- Duyệt đến vị trí cần cắt, xác định newHead và ngắt liên kết tại newTail.
Độ phức tạp:
- Thời gian: O(n)O(n), với nn là số node.
- Bộ nhớ: O(1)O(1).

Ví dụ

const head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(4);
head.next.next.next.next = new ListNode(5);
const rotated = rotateRight(head, 2);
// ListNode { value: 4, next: ListNode { value: 5, next: ListNode { value: 1, next: ListNode { value: 2, next: ... } } } }

Câu hỏi 53: Tách danh sách liên kết thành kk phần

Viết hàm tách danh sách liên kết thành kk phần gần bằng nhau.

Giải pháp

function splitListToParts(head, k) {
let length = 0;
let current = head;
// Tính độ dài danh sách
while (current) {
length++;
current = current.next;
}
const partSize = Math.floor(length / k);
let extra = length % k;
const result = [];
current = head;
for (let i = 0; i < k; i++) {
const dummy = new ListNode(0);
let partTail = dummy;
for (let j = 0; j < partSize + (extra > 0 ? 1 : 0); j++) {
partTail.next = current;
partTail = partTail.next;
if (current) current = current.next;
}
if (partTail) partTail.next = null;
result.push(dummy.next);
if (extra > 0) extra--;
}
return result;
}

Phân tích chi tiết

Tính kích thước mỗi phần:
- partSize = Math.floor(length / k): Kích thước cơ bản mỗi phần.
- extra = length % k: Số phần cần được thêm 1 node.
Tạo các phần:
- Mỗi phần có partSize node, thêm 1 node cho đến khi extra bằng 0.
Độ phức tạp:
- Thời gian: O(n)O(n), với nn là số node.
- Bộ nhớ: O(k)O(k), cho mảng kết quả.

Ví dụ

const head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(4);
head.next.next.next.next = new ListNode(5);
head.next.next.next.next.next = new ListNode(6);
const parts = splitListToParts(head, 3);
// [
//   ListNode { value: 1, next: ListNode { value: 2, next: null } },
//   ListNode { value: 3, next: ListNode { value: 4, next: null } },
//   ListNode { value: 5, next: ListNode { value: 6, next: null } }
// ]

Câu hỏi 54: Xóa các phần tử trùng lặp trong danh sách liên kết đã sắp xếp

Viết hàm xóa tất cả các phần tử trùng lặp trong danh sách liên kết đã sắp xếp.

Giải pháp

function deleteDuplicates(head) {
let current = head;
while (current && current.next) {
if (current.value === current.next.value) {
current.next = current.next.next;
} else {
current = current.next;
}
}
return head;
}

Phân tích chi tiết

Duyệt qua danh sách:
- Nếu giá trị của current và current.next giống nhau, bỏ qua current.next.
Độ phức tạp:
- Thời gian: O(n)O(n).
- Bộ nhớ: O(1)O(1).

Ví dụ

const head = new ListNode(1);
head.next = new ListNode(1);
head.next.next = new ListNode(2);
head.next.next.next = new ListNode(3);
head.next.next.next.next = new ListNode(3);
const updatedHead = deleteDuplicates(head);
// ListNode { value: 1, next: ListNode { value: 2, next: ListNode { value: 3, next: null } } }

Câu hỏi 55: Nhân hai số nguyên lớn được biểu diễn dưới dạng chuỗi

Viết hàm nhận vào hai chuỗi biểu diễn các số nguyên lớn và trả về tích của chúng dưới dạng chuỗi.

Giải pháp

function multiplyStrings(num1, num2) {
if (num1 === "0" || num2 === "0") return "0";
const result = new Array(num1.length + num2.length).fill(0);
for (let i = num1.length - 1; i >= 0; i--) {
for (let j = num2.length - 1; j >= 0; j--) {
const mul = (num1[i] - '0') * (num2[j] - '0');
const sum = mul + result[i + j + 1];
result[i + j + 1] = sum % 10;
result[i + j] += Math.floor(sum / 10);
}
}
while (result[0] === 0) {
result.shift();
}
return result.join('');
}

Phân tích chi tiết

Khởi tạo mảng kết quả:
- Mảng result có độ dài bằng tổng độ dài của hai chuỗi đầu vào để đảm bảo lưu đủ giá trị.
Nhân từng chữ số:
- Nhân các chữ số từ cuối đến đầu của cả hai chuỗi.
- Cộng kết quả vào vị trí tương ứng trong mảng result, bao gồm cả phần dư.
Loại bỏ số 00 thừa:
- Xóa các số 00 ở đầu mảng kết quả (nếu có).
Chuyển đổi mảng kết quả thành chuỗi:
- Dùng join('') để nối các phần tử của mảng thành chuỗi kết quả.
Độ phức tạp:
- Thời gian: O(m×n)O(m \times n), với m,nm, n là độ dài của hai chuỗi.
- Bộ nhớ: O(m+n)O(m + n).

Ví dụ

console.log(multiplyStrings("123", "456")); // "56088"
console.log(multiplyStrings("0", "123")); // "0"
console.log(multiplyStrings("999", "999")); // "998001"

Câu hỏi 56: Tìm chuỗi con lặp lại dài nhất (Longest Repeating Substring)

Viết hàm nhận vào một chuỗi và trả về chuỗi con lặp lại dài nhất.

Giải pháp: Sử dụng Binary Search + Hashing

function longestRepeatingSubstring(s) {
const n = s.length;
function search(length) {
const seen = new Set();
for (let i = 0; i <= n - length; i++) {
const substring = s.substring(i, i + length);
if (seen.has(substring)) return substring;
seen.add(substring);
}
return null;
}
let left = 1, right = n;
let result = "";
while (left <= right) {
const mid = Math.floor((left + right) / 2);
const found = search(mid);
if (found) {
result = found;
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
}

Phân tích chi tiết

Binary Search trên độ dài:
- Tìm kiếm chuỗi con lặp lại dài nhất bằng cách thử các độ dài từ nhỏ đến lớn.
Kiểm tra lặp lại:
- Hàm search(length) kiểm tra xem có chuỗi con nào có độ dài length lặp lại hay không.
Cập nhật kết quả:
- Nếu tìm thấy chuỗi con lặp lại, tăng giá trị left để thử độ dài lớn hơn.
- Nếu không, giảm giá trị right.
Độ phức tạp:
- Thời gian: O(n2log⁡n)O(n^2 \log n), với nn là độ dài chuỗi.
- Bộ nhớ: O(n)O(n) cho tập hợp các chuỗi con.

Ví dụ

console.log(longestRepeatingSubstring("banana")); // "ana"
console.log(longestRepeatingSubstring("abcdef")); // ""
console.log(longestRepeatingSubstring("aabcaabdaab")); // "aab"

Câu hỏi 57: Tìm chuỗi con chung dài nhất (Longest Common Substring)

Viết hàm nhận vào hai chuỗi và trả về chuỗi con chung dài nhất.

Giải pháp: Dynamic Programming

function longestCommonSubstring(s1, s2) {
const m = s1.length;
const n = s2.length;
const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
let maxLength = 0;
let endIndex = 0;
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (s1[i - 1] === s2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
if (dp[i][j] > maxLength) {
maxLength = dp[i][j];
endIndex = i - 1;
}
}
}
}
return s1.substring(endIndex - maxLength + 1, endIndex + 1);
}

Phân tích chi tiết

Mảng DP:
- dp[i][j]: Độ dài chuỗi con chung kết thúc tại s1[i−1]s1[i-1] và s2[j−1]s2[j-1].
Cập nhật giá trị:
- Nếu ký tự s1[i−1]s1[i-1] và s2[j−1]s2[j-1] khớp nhau, tăng giá trị của dp[i][j] bằng dp[i-1][j-1] + 1.
Theo dõi chuỗi con dài nhất:
- Lưu độ dài tối đa và chỉ số kết thúc để trích xuất chuỗi con.
Độ phức tạp:
- Thời gian: O(m×n)O(m \times n), với m,nm, n là độ dài hai chuỗi.
- Bộ nhớ: O(m×n)O(m \times n).

Ví dụ

console.log(longestCommonSubstring("abcdef", "zcdemf")); // "cde"
console.log(longestCommonSubstring("xyz", "abcd")); // ""
console.log(longestCommonSubstring("abcde", "cdeab")); // "cde"

Câu hỏi 58: Sắp xếp chuỗi theo tần suất xuất hiện

Viết hàm nhận vào một chuỗi và trả về chuỗi đã được sắp xếp theo tần suất xuất hiện của các ký tự (tần suất giảm dần).

Giải pháp

function frequencySort(s) {
const freqMap = new Map();
for (let char of s) {
freqMap.set(char, (freqMap.get(char) || 0) + 1);
}
return Array.from(freqMap)
.sort((a, b) => b[1] - a[1])
.map(([char, freq]) => char.repeat(freq))
.join('');
}

Phân tích chi tiết

Đếm tần suất:
- Sử dụng Map để lưu số lần xuất hiện của mỗi ký tự.
Sắp xếp:
- Chuyển Map thành mảng và sắp xếp theo tần suất giảm dần.
Tạo chuỗi mới:
- Lặp qua mảng đã sắp xếp, nhân ký tự với tần suất và ghép chúng lại.
Độ phức tạp:
- Thời gian: O(n+klog⁡k)O(n + k \log k), với nn là độ dài chuỗi và kk là số lượng ký tự khác nhau.
- Bộ nhớ: O(k)O(k).

Ví dụ

console.log(frequencySort("tree")); // "eert"
console.log(frequencySort("cccaaa")); // "cccaaa"
console.log(frequencySort("Aabb")); // "bbAa"

Câu hỏi 59: Sinh tất cả các chuỗi ngoặc hợp lệ (Generate Parentheses)

Viết hàm nhận vào một số nguyên nn, trả về tất cả các chuỗi ngoặc hợp lệ có nn cặp ngoặc.

Giải pháp: Backtracking

function generateParentheses(n) {
const result = [];
function backtrack(current, open, close) {
if (current.length === 2 * n) {
result.push(current);
return;
}
if (open < n) {
backtrack(current + "(", open + 1, close);
}
if (close < open) {
backtrack(current + ")", open, close + 1);
}
}
backtrack("", 0, 0);
return result;
}

Phân tích chi tiết

Hàm backtrack:
- current: Chuỗi ngoặc hiện tại.
- open: Số lượng ngoặc mở đã sử dụng.
- close: Số lượng ngoặc đóng đã sử dụng.
Điều kiện dừng:
- Nếu độ dài chuỗi bằng 2n2n, thêm chuỗi vào danh sách kết quả.
Ràng buộc:
- open<nopen < n: Chỉ thêm ngoặc mở nếu số ngoặc mở chưa đạt nn.
- close<openclose < open: Chỉ thêm ngoặc đóng nếu số ngoặc đóng ít hơn số ngoặc mở.
Độ phức tạp:
- Thời gian: O(4n/n)O(4^n / \sqrt{n}), do số lượng chuỗi hợp lệ là số Catalan.
- Bộ nhớ: O(n)O(n) cho stack đệ quy.

Ví dụ

console.log(generateParentheses(3));
// ["((()))", "(()())", "(())()", "()(())", "()()()"]
console.log(generateParentheses(1));
// ["()"]

Câu hỏi 60: Tìm phần tử xuất hiện nhiều hơn một nửa (Majority Element)

Viết hàm nhận vào một mảng số nguyên và trả về phần tử xuất hiện nhiều hơn một nửa độ dài mảng.

Giải pháp: Boyer-Moore Voting Algorithm

function majorityElement(nums) {
let candidate = null;
let count = 0;
for (let num of nums) {
if (count === 0) {
candidate = num;
}
count += (num === candidate) ? 1 : -1;
}
return candidate;
}

Phân tích chi tiết

Thuật toán Boyer-Moore:
- Sử dụng một biến candidate để lưu trữ phần tử có khả năng là kết quả.
- Biến count được sử dụng để theo dõi số lần xuất hiện của candidate.
Cách hoạt động:
- Nếu count === 0, chọn candidate mới.
- Nếu phần tử hiện tại khớp với candidate, tăng count. Ngược lại, giảm count.
Độ phức tạp:
- Thời gian: O(n)O(n), với nn là số phần tử trong mảng.
- Bộ nhớ: O(1)O(1).

Ví dụ

console.log(majorityElement([3, 2, 3])); // 3
console.log(majorityElement([2, 2, 1, 1, 1, 2, 2])); // 2

Câu hỏi 61: Sắp xếp mảng theo một thứ tự đã cho

Viết hàm sắp xếp mảng arr theo thứ tự của mảng order.

Giải pháp

function sortArrayByOrder(arr, order) {
const orderMap = new Map();
for (let i = 0; i < order.length; i++) {
orderMap.set(order[i], i);
}
return arr.sort((a, b) => {
const indexA = orderMap.has(a) ? orderMap.get(a) : Infinity;
const indexB = orderMap.has(b) ? orderMap.get(b) : Infinity;
return indexA - indexB;
});
}

Phân tích chi tiết

Tạo bản đồ thứ tự:
- orderMap lưu vị trí của từng phần tử trong order để so sánh.
Sắp xếp:
- Dùng sort để sắp xếp arr.
- Nếu phần tử không có trong order, đặt ở cuối (dùng giá trị Infinity).
Độ phức tạp:
- Thời gian: O(nlog⁡n)O(n \log n), với nn là số phần tử trong arr.
- Bộ nhớ: O(m)O(m), với mm là số phần tử trong order.

Ví dụ

console.log(sortArrayByOrder([2, 3, 1, 4], [3, 1, 4])); // [3, 1, 4, 2]
console.log(sortArrayByOrder([5, 6, 7, 8], [8, 7])); // [8, 7, 5, 6]

Câu hỏi 62: Tìm kk số lớn nhất trong mảng

Viết hàm nhận vào một mảng số nguyên và một số kk, trả về kk số lớn nhất trong mảng.

Giải pháp: Heap (Min-Heap)

function findKLargest(nums, k) {
const minHeap = [];
for (let num of nums) {
minHeap.push(num);
minHeap.sort((a, b) => a - b); // Sắp xếp heap
if (minHeap.length > k) {
minHeap.shift(); // Loại bỏ phần tử nhỏ nhất
}
}
return minHeap;
}

Phân tích chi tiết

Min-Heap:
- Duy trì một heap có kích thước tối đa kk.
- Chỉ giữ lại kk phần tử lớn nhất.
Loại bỏ phần tử nhỏ nhất:
- Nếu kích thước heap vượt quá kk, loại bỏ phần tử nhỏ nhất (shift).
Độ phức tạp:
- Thời gian: O(nlog⁡k)O(n \log k), với nn là số phần tử trong mảng.
- Bộ nhớ: O(k)O(k).

Ví dụ

console.log(findKLargest([3, 2, 1, 5, 6, 4], 2)); // [5, 6]
console.log(findKLargest([1, 9, 8, 7, 2, 3], 3)); // [7, 8, 9]

Câu hỏi 63: Tìm kk phần tử gần nhất với một giá trị xx trong mảng

Viết hàm nhận vào một mảng số nguyên arr, một số nguyên kk, và một giá trị xx. Trả về kk phần tử gần nhất với xx, được sắp xếp theo thứ tự tăng dần.

Giải pháp

function findClosestElements(arr, k, x) {
return arr
.sort((a, b) => Math.abs(a - x) - Math.abs(b - x) || a - b)
.slice(0, k)
.sort((a, b) => a - b);
}

Phân tích chi tiết

Sắp xếp theo độ gần:
- Math.abs(a - x) - Math.abs(b - x): Sắp xếp mảng theo khoảng cách của mỗi phần tử đến xx.
- a - b: Trong trường hợp hai phần tử có khoảng cách bằng nhau, sắp xếp theo giá trị.
Chọn kk phần tử đầu tiên:
- Sử dụng slice(0, k) để lấy kk phần tử gần nhất.
Sắp xếp kết quả theo thứ tự tăng dần:
- Sắp xếp kk phần tử đã chọn theo giá trị thực.
Độ phức tạp:
- Thời gian: O(nlog⁡n)O(n \log n), với nn là số phần tử trong arr.
- Bộ nhớ: O(k)O(k), với kk là số phần tử gần nhất.

Ví dụ

console.log(findClosestElements([1, 2, 3, 4, 5], 4, 3)); // [1, 2, 3, 4]
console.log(findClosestElements([1, 3, 5, 7], 2, 6)); // [5, 7]

Câu hỏi 64: Tìm độ dài chuỗi con liên tục với tổng bằng kk

Viết hàm nhận vào một mảng số nguyên và một số nguyên kk, trả về độ dài chuỗi con liên tục dài nhất có tổng bằng kk.

Giải pháp: Hash Map

function maxSubArrayLen(nums, k) {
const sumMap = new Map();
let sum = 0;
let maxLength = 0;
sumMap.set(0, -1);
for (let i = 0; i < nums.length; i++) {
sum += nums[i];
if (sumMap.has(sum - k)) {
maxLength = Math.max(maxLength, i - sumMap.get(sum - k));
}
if (!sumMap.has(sum)) {
sumMap.set(sum, i);
}
}
return maxLength;
}

Phân tích chi tiết

Duyệt qua mảng:
- Tính tổng hiện tại sum khi duyệt qua từng phần tử.
Kiểm tra tổng trừ kk:
- Nếu sum−ksum – k tồn tại trong sumMap, xác định độ dài chuỗi con.
Cập nhật bản đồ:
- Lưu sum cùng với chỉ số của nó nếu chưa tồn tại.
Độ phức tạp:
- Thời gian: O(n)O(n), với nn là số phần tử trong mảng.
- Bộ nhớ: O(n)O(n), cho sumMap.

Ví dụ

console.log(maxSubArrayLen([1, -1, 5, -2, 3], 3)); // 4
console.log(maxSubArrayLen([-2, -1, 2, 1], 1)); // 2

Câu hỏi 65: Tìm tổng nhỏ nhất của chuỗi con có độ dài ít nhất kk

Viết hàm nhận vào một mảng số nguyên và một số nguyên kk, trả về tổng nhỏ nhất của chuỗi con liên tục có độ dài ít nhất kk.

Giải pháp: Sliding Window

function minSubArrayLen(target, nums) {
let left = 0;
let sum = 0;
let minLength = Infinity;
for (let right = 0; right < nums.length; right++) {
sum += nums[right];
while (sum >= target) {
minLength = Math.min(minLength, right - left + 1);
sum -= nums[left];
left++;
}
}
return minLength === Infinity ? 0 : minLength;
}

Phân tích chi tiết

Cửa sổ trượt:
- left và right đại diện cho hai đầu của cửa sổ.
Thu hẹp cửa sổ:
- Khi tổng sum≥targetsum \geq target, tính độ dài cửa sổ và thu hẹp cửa sổ từ trái.
Độ phức tạp:
- Thời gian: O(n)O(n), với nn là số phần tử trong mảng.
- Bộ nhớ: O(1)O(1).

Ví dụ

console.log(minSubArrayLen(7, [2, 3, 1, 2, 4, 3])); // 2
console.log(minSubArrayLen(4, [1, 4, 4])); // 1
console.log(minSubArrayLen(11, [1, 1, 1, 1, 1, 1, 1, 1])); // 0

Câu hỏi 66: Kiểm tra chuỗi con của chuỗi khác

Viết hàm kiểm tra xem một chuỗi có phải là chuỗi con của chuỗi khác hay không.

Giải pháp: Hai con trỏ

function isSubsequence(s, t) {
let i = 0;
let j = 0;
while (i < s.length && j < t.length) {
if (s[i] === t[j]) {
i++;
}
j++;
}
return i === s.length;
}

Phân tích chi tiết

Hai con trỏ:
- i duyệt qua chuỗi s, j duyệt qua chuỗi t.
Kiểm tra ký tự:
- Nếu ký tự tại s[i] và t[j] khớp nhau, tăng i.
- Duyệt tiếp t[j] bất kể khớp hay không.
Độ phức tạp:
- Thời gian: O(n+m)O(n + m), với n,mn, m là độ dài của s và t.
- Bộ nhớ: O(1)O(1).

Ví dụ

console.log(isSubsequence("abc", "ahbgdc")); // true
console.log(isSubsequence("axc", "ahbgdc")); // false
console.log(isSubsequence("", "ahbgdc")); // true

Câu hỏi 67: Tìm hoán vị của chuỗi (Permutations)

Viết hàm trả về tất cả các hoán vị của một chuỗi hoặc một mảng.

Giải pháp: Backtracking

function permute(nums) {
const result = [];
function backtrack(path, remaining) {
if (remaining.length === 0) {
result.push([...path]);
return;
}
for (let i = 0; i < remaining.length; i++) {
path.push(remaining[i]);
backtrack(path, remaining.slice(0, i).concat(remaining.slice(i + 1)));
path.pop();
}
}
backtrack([], nums);
return result;
}

Phân tích chi tiết

Hàm backtrack:
- path: Dãy hiện tại đang xây dựng.
- remaining: Các phần tử chưa được sử dụng.
Điều kiện dừng:
- Khi remaining rỗng, thêm path vào danh sách kết quả.
Lặp qua các phần tử:
- Thêm phần tử vào path.
- Đệ quy để tạo hoán vị từ các phần tử còn lại.
- Loại bỏ phần tử đã thêm sau khi quay lại.
Độ phức tạp:
- Thời gian: O(n!)O(n!), với nn là độ dài của mảng.
- Bộ nhớ: O(n!)O(n!) để lưu kết quả.

Ví dụ

console.log(permute([1, 2, 3]));
// [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

Câu hỏi 68: Tìm tổ hợp của các phần tử (Combinations)

Viết hàm trả về tất cả các tổ hợp của kk phần tử từ nn phần tử.

Giải pháp: Backtracking

function combine(n, k) {
const result = [];
function backtrack(start, path) {
if (path.length === k) {
result.push([...path]);
return;
}
for (let i = start; i <= n; i++) {
path.push(i);
backtrack(i + 1, path);
path.pop();
}
}
backtrack(1, []);
return result;
}

Phân tích chi tiết

Hàm backtrack:
- start: Điểm bắt đầu để duyệt qua các phần tử.
- path: Dãy hiện tại đang xây dựng.
Điều kiện dừng:
- Khi path.length === k, thêm tổ hợp vào danh sách kết quả.
Lặp qua các phần tử:
- Thêm phần tử vào path.
- Đệ quy để tìm tổ hợp tiếp theo.
- Loại bỏ phần tử đã thêm sau khi quay lại.
Độ phức tạp:
- Thời gian: O(C(n,k))O(C(n, k)), với C(n,k)C(n, k) là số tổ hợp.
- Bộ nhớ: O(C(n,k))O(C(n, k)) để lưu kết quả.

Ví dụ

console.log(combine(4, 2));
// [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]

Câu hỏi 69: Tìm tập hợp con (Subsets)

Viết hàm trả về tất cả các tập hợp con của một mảng.

Giải pháp: Backtracking

function subsets(nums) {
const result = [];
function backtrack(start, path) {
result.push([...path]);
for (let i = start; i < nums.length; i++) {
path.push(nums[i]);
backtrack(i + 1, path);
path.pop();
}
}
backtrack(0, []);
return result;
}

Phân tích chi tiết

Hàm backtrack:
- start: Điểm bắt đầu để duyệt qua các phần tử.
- path: Dãy hiện tại đang xây dựng.
Thêm vào kết quả:
- Mỗi lần gọi backtrack, thêm path hiện tại vào danh sách kết quả.
Lặp qua các phần tử:
- Thêm phần tử vào path.
- Đệ quy để tạo tập hợp con từ các phần tử còn lại.
- Loại bỏ phần tử đã thêm sau khi quay lại.
Độ phức tạp:
- Thời gian: O(2n)O(2^n), với nn là số phần tử trong mảng.
- Bộ nhớ: O(2n)O(2^n) để lưu kết quả.

Ví dụ

console.log(subsets([1, 2, 3]));
// [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

Câu hỏi 70: Tìm hoán vị có chứa phần tử trùng lặp

Viết hàm trả về tất cả các hoán vị của một mảng có thể chứa các phần tử trùng lặp.

Giải pháp: Backtracking với kiểm tra trùng lặp

function permuteUnique(nums) {
const result = [];
nums.sort((a, b) => a - b);
function backtrack(path, used) {
if (path.length === nums.length) {
result.push([...path]);
return;
}
for (let i = 0; i < nums.length; i++) {
if (used[i]) continue;
if (i > 0 && nums[i] === nums[i - 1] && !used[i - 1]) continue;
path.push(nums[i]);
used[i] = true;
backtrack(path, used);
used[i] = false;
path.pop();
}
}
backtrack([], Array(nums.length).fill(false));
return result;
}

Phân tích chi tiết

Sắp xếp mảng:
- Sắp xếp mảng ban đầu để dễ dàng loại bỏ hoán vị trùng lặp.
Kiểm tra trùng lặp:
- Bỏ qua phần tử trùng lặp nếu phần tử trước đó đã bị bỏ qua.
Quản lý trạng thái:
- Mảng used lưu trạng thái đã sử dụng của từng phần tử.
Độ phức tạp:
- Thời gian: O(n×n!)O(n \times n!), với nn là độ dài của mảng.
- Bộ nhớ: O(n!)O(n!) để lưu kết quả.

Ví dụ

console.log(permuteUnique([1, 1, 2]));
// [[1, 1, 2], [1, 2, 1], [2, 1, 1]]

Câu hỏi 71: Tìm chuỗi con Palindrome dài nhất (Longest Palindromic Substring)

Viết hàm nhận vào một chuỗi và trả về chuỗi con Palindrome dài nhất.

Giải pháp: Expand Around Center

function longestPalindrome(s) {
if (s.length < 1) return "";
let start = 0, end = 0;
function expandAroundCenter(left, right) {
while (left >= 0 && right < s.length && s[left] === s[right]) {
left--;
right++;
}
return right - left - 1;
}
for (let i = 0; i < s.length; i++) {
const len1 = expandAroundCenter(i, i); // Palindrome lẻ
const len2 = expandAroundCenter(i, i + 1); // Palindrome chẵn
const len = Math.max(len1, len2);
if (len > end - start) {
start = i - Math.floor((len - 1) / 2);
end = i + Math.floor(len / 2);
}
}
return s.substring(start, end + 1);
}

Phân tích chi tiết

Hàm mở rộng từ trung tâm:
- Kiểm tra chuỗi con là Palindrome bằng cách mở rộng từ trung tâm.
Kiểm tra Palindrome chẵn và lẻ:
- Xét cả hai trường hợp: chuỗi có độ dài chẵn và lẻ.
Cập nhật chuỗi con dài nhất:
- Nếu độ dài chuỗi Palindrome hiện tại lớn hơn chuỗi đã lưu, cập nhật vị trí bắt đầu và kết thúc.
Độ phức tạp:
- Thời gian: O(n2)O(n^2), với nn là độ dài chuỗi.
- Bộ nhớ: O(1)O(1).

Ví dụ

console.log(longestPalindrome("babad")); // "bab" hoặc "aba"
console.log(longestPalindrome("cbbd")); // "bb"

Câu hỏi 72: Kiểm tra chuỗi là Palindrome sau khi xóa tối đa một ký tự

Viết hàm kiểm tra xem một chuỗi có thể trở thành Palindrome sau khi xóa tối đa một ký tự.

Giải pháp: Hai con trỏ

function validPalindrome(s) {
function isPalindrome(left, right) {
while (left < right) {
if (s[left] !== s[right]) return false;
left++;
right--;
}
return true;
}
let left = 0, right = s.length - 1;
while (left < right) {
if (s[left] !== s[right]) {
return isPalindrome(left + 1, right) || isPalindrome(left, right - 1);
}
left++;
right--;
}
return true;
}

Phân tích chi tiết

Hàm kiểm tra Palindrome:
- Kiểm tra xem chuỗi từ chỉ số left đến right có phải là Palindrome hay không.
Hai con trỏ:
- Duyệt từ đầu và cuối chuỗi. Khi phát hiện ký tự không khớp, kiểm tra bằng cách bỏ một trong hai ký tự.
Độ phức tạp:
- Thời gian: O(n)O(n).
- Bộ nhớ: O(1)O(1).

Ví dụ

console.log(validPalindrome("abca")); // true (bỏ 'c')
console.log(validPalindrome("racecar")); // true
console.log(validPalindrome("hello")); // false

Câu hỏi 73: Tìm chuỗi con có tổng độ dài kk lớn nhất

Viết hàm nhận vào một chuỗi và một số kk, trả về chuỗi con có tổng các ký tự lớn nhất với độ dài kk.

Giải pháp: Sliding Window

function maxSubstringSum(s, k) {
let maxSum = 0, currentSum = 0, start = 0, result = "";
for (let end = 0; end < s.length; end++) {
currentSum += s.charCodeAt(end);
if (end - start + 1 === k) {
if (currentSum > maxSum) {
maxSum = currentSum;
result = s.substring(start, end + 1);
}
currentSum -= s.charCodeAt(start);
start++;
}
}
return result;
}

Phân tích chi tiết

Cửa sổ trượt:
- Duyệt chuỗi bằng một cửa sổ có kích thước kk.
Cập nhật tổng lớn nhất:
- Tính tổng ASCII của các ký tự trong cửa sổ hiện tại.
- Nếu tổng lớn hơn maxSum, cập nhật chuỗi con.
Duyệt và trượt cửa sổ:
- Trượt cửa sổ bằng cách loại bỏ ký tự đầu và thêm ký tự cuối.
Độ phức tạp:
- Thời gian: O(n)O(n), với nn là độ dài chuỗi.
- Bộ nhớ: O(1)O(1).

Ví dụ

console.log(maxSubstringSum("abcde", 2)); // "de" (tổng ASCII lớn nhất: 201)
console.log(maxSubstringSum("xyz", 2)); // "yz"

Câu hỏi 74: Tìm chuỗi con duy nhất dài nhất

Viết hàm trả về chuỗi con duy nhất dài nhất từ một chuỗi.

Giải pháp: Sliding Window + HashMap

function lengthOfLongestSubstring(s) {
const charMap = new Map();
let maxLength = 0, start = 0;
for (let end = 0; end < s.length; end++) {
if (charMap.has(s[end])) {
start = Math.max(start, charMap.get(s[end]) + 1);
}
charMap.set(s[end], end);
maxLength = Math.max(maxLength, end - start + 1);
}
return maxLength;
}

Phân tích chi tiết

HashMap:
- Lưu vị trí xuất hiện cuối cùng của mỗi ký tự.
Cửa sổ trượt:
- Nếu ký tự trùng lặp được tìm thấy, cập nhật start đến vị trí sau ký tự trùng lặp.
Cập nhật độ dài lớn nhất:
- Cập nhật maxLength bằng khoảng cách giữa start và end.
Độ phức tạp:
- Thời gian: O(n)O(n), với nn là độ dài chuỗi.
- Bộ nhớ: O(k)O(k), với kk là số ký tự khác nhau.

Ví dụ

console.log(lengthOfLongestSubstring("abcabcbb")); // 3 ("abc")
console.log(lengthOfLongestSubstring("bbbbb")); // 1 ("b")
console.log(lengthOfLongestSubstring("pwwkew")); // 3 ("wke")

Câu hỏi 75: Tìm từ khóa xuất hiện nhiều nhất trong chuỗi

Viết hàm nhận vào một chuỗi và trả về từ khóa xuất hiện nhiều nhất trong chuỗi.

Giải pháp

function mostFrequentWord(s) {
const words = s.toLowerCase().match(/\b[a-z]+\b/g); // Tách từ
const freqMap = new Map();
for (let word of words) {
freqMap.set(word, (freqMap.get(word) || 0) + 1);
}
let maxFreq = 0;
let result = "";
for (let [word, freq] of freqMap.entries()) {
if (freq > maxFreq || (freq === maxFreq && word < result)) {
maxFreq = freq;
result = word;
}
}
return result;
}

Phân tích chi tiết

Tách từ:
- Sử dụng biểu thức chính quy \b[a-z]+\b để tách từ.
Đếm tần suất:
- Lưu tần suất xuất hiện của mỗi từ vào Map.
Tìm từ xuất hiện nhiều nhất:
- So sánh tần suất và cập nhật từ có tần suất cao nhất.
- Nếu tần suất bằng nhau, chọn từ nhỏ hơn về mặt từ điển.
Độ phức tạp:
- Thời gian: O(n)O(n), với nn là số từ trong chuỗi.
- Bộ nhớ: O(k)O(k), với kk là số từ khác nhau.

Ví dụ

console.log(mostFrequentWord("The cat and the hat.")); // "the"
console.log(mostFrequentWord("hello world hello")); // "hello"
console.log(mostFrequentWord("a b c a b a")); // "a"

Câu hỏi 76: Đếm số lần xuất hiện của một mẫu trong chuỗi

Viết hàm đếm số lần xuất hiện của một chuỗi con patternpattern trong chuỗi ss.

Giải pháp

function countOccurrences(s, pattern) {
let count = 0;
let index = s.indexOf(pattern);
while (index !== -1) {
count++;
index = s.indexOf(pattern, index + 1);
}
return count;
}

Phân tích chi tiết

Tìm vị trí xuất hiện:
- Sử dụng indexOf để tìm vị trí của chuỗi con.
Lặp lại tìm kiếm:
- Sau khi tìm thấy, tiếp tục tìm kiếm từ vị trí tiếp theo.
Độ phức tạp:
- Thời gian: O(n×m)O(n \times m), với nn là độ dài chuỗi và mm là độ dài mẫu.
- Bộ nhớ: O(1)O(1).

Ví dụ

console.log(countOccurrences("ababab", "ab")); // 3
console.log(countOccurrences("aaaaa", "aa")); // 4
console.log(countOccurrences("hello world", "world")); // 1

Câu hỏi 77: Tìm ký tự đầu tiên không lặp lại

Viết hàm nhận vào một chuỗi và trả về ký tự đầu tiên không lặp lại. Nếu không có, trả về null.

Giải pháp

function firstNonRepeatingCharacter(s) {
const freqMap = new Map();
for (let char of s) {
freqMap.set(char, (freqMap.get(char) || 0) + 1);
}
for (let char of s) {
if (freqMap.get(char) === 1) {
return char;
}
}
return null;
}

Phân tích chi tiết

Đếm tần suất:
- Sử dụng Map để đếm số lần xuất hiện của mỗi ký tự.
Tìm ký tự không lặp lại:
- Duyệt qua chuỗi ban đầu, trả về ký tự có tần suất bằng 11.
Độ phức tạp:
- Thời gian: O(n)O(n), với nn là độ dài chuỗi.
- Bộ nhớ: O(k)O(k), với kk là số ký tự khác nhau.

Ví dụ

console.log(firstNonRepeatingCharacter("leetcode")); // "l"
console.log(firstNonRepeatingCharacter("aabbcc")); // null
console.log(firstNonRepeatingCharacter("swiss")); // "w"

Câu hỏi 78: Tìm chuỗi con có tần suất xuất hiện lớn nhất

Viết hàm nhận vào một chuỗi và trả về chuỗi con có tần suất xuất hiện lớn nhất với độ dài cố định kk.

Giải pháp

function mostFrequentSubstring(s, k) {
const freqMap = new Map();
for (let i = 0; i <= s.length - k; i++) {
const substring = s.substring(i, i + k);
freqMap.set(substring, (freqMap.get(substring) || 0) + 1);
}
let maxFreq = 0;
let result = "";
for (let [substring, freq] of freqMap.entries()) {
if (freq > maxFreq || (freq === maxFreq && substring < result)) {
maxFreq = freq;
result = substring;
}
}
return result;
}

Phân tích chi tiết

Tạo chuỗi con:
- Lấy tất cả chuỗi con có độ dài kk từ chuỗi đầu vào.
Đếm tần suất:
- Sử dụng Map để lưu số lần xuất hiện của mỗi chuỗi con.
Tìm chuỗi con có tần suất lớn nhất:
- So sánh tần suất và chọn chuỗi con có tần suất lớn nhất.
- Nếu tần suất bằng nhau, chọn chuỗi con nhỏ hơn về mặt từ điển.
Độ phức tạp:
- Thời gian: O(n×k)O(n \times k), với nn là độ dài chuỗi và kk là độ dài chuỗi con.
- Bộ nhớ: O(n)O(n).

Ví dụ

console.log(mostFrequentSubstring("ababab", 2)); // "ab"
console.log(mostFrequentSubstring("abcabc", 3)); // "abc"
console.log(mostFrequentSubstring("aaaa", 2)); // "aa"

Câu hỏi 79: Kiểm tra chuỗi có chứa tất cả các ký tự từ aa đến zz (Pangram)

Viết hàm kiểm tra xem một chuỗi có phải là Pangram không (chứa tất cả các ký tự từ aa đến zz).

Giải pháp

function isPangram(s) {
const set = new Set();
for (let char of s.toLowerCase()) {
if (char >= 'a' && char <= 'z') {
set.add(char);
}
}
return set.size === 26;
}

Phân tích chi tiết

Lưu ký tự duy nhất:
- Sử dụng Set để lưu các ký tự trong khoảng aa đến zz.
Kiểm tra Pangram:
- Nếu Set có đủ 26 ký tự, chuỗi là Pangram.
Độ phức tạp:
- Thời gian: O(n)O(n), với nn là độ dài chuỗi.
- Bộ nhớ: O(1)O(1), vì Set có tối đa 26 ký tự.

Ví dụ

console.log(isPangram("The quick brown fox jumps over the lazy dog")); // true
console.log(isPangram("Hello World")); // false
console.log(isPangram("Pack my box with five dozen liquor jugs")); // true

Câu hỏi 80: Kiểm tra xem hai chuỗi có phải là hoán vị của nhau (Anagram)

Viết hàm kiểm tra xem hai chuỗi có phải là hoán vị của nhau hay không.

Giải pháp: Sử dụng HashMap

function isAnagram(s, t) {
if (s.length !== t.length) return false;
const charCount = new Map();
for (let char of s) {
charCount.set(char, (charCount.get(char) || 0) + 1);
}
for (let char of t) {
if (!charCount.has(char)) return false;
charCount.set(char, charCount.get(char) - 1);
if (charCount.get(char) === 0) charCount.delete(char);
}
return charCount.size === 0;
}

Phân tích chi tiết

Đếm tần suất ký tự trong chuỗi ss:
- Sử dụng Map để lưu số lần xuất hiện của mỗi ký tự.
Kiểm tra chuỗi tt:
- Nếu ký tự trong tt không tồn tại trong Map hoặc tần suất không khớp, trả về false.
Kiểm tra kết quả:
- Nếu Map rỗng, hai chuỗi là hoán vị của nhau.
Độ phức tạp:
- Thời gian: O(n)O(n), với nn là độ dài chuỗi.
- Bộ nhớ: O(k)O(k), với kk là số ký tự khác nhau.

Ví dụ

console.log(isAnagram("anagram", "nagaram")); // true
console.log(isAnagram("rat", "car")); // false
console.log(isAnagram("aacc", "ccac")); // false

Câu hỏi 81: Tìm từ có độ dài lớn nhất có thể hình thành từ chuỗi ký tự cho trước

Viết hàm nhận vào một danh sách từ và một chuỗi ký tự, trả về từ dài nhất có thể hình thành bằng cách sử dụng các ký tự trong chuỗi.

Giải pháp

function longestWord(words, chars) {
const charCount = new Map();
for (let char of chars) {
charCount.set(char, (charCount.get(char) || 0) + 1);
}
let maxLength = 0;
for (let word of words) {
const wordCount = new Map();
for (let char of word) {
wordCount.set(char, (wordCount.get(char) || 0) + 1);
}
let canForm = true;
for (let [char, count] of wordCount) {
if (!charCount.has(char) || charCount.get(char) < count) {
canForm = false;
break;
}
}
if (canForm) {
maxLength = Math.max(maxLength, word.length);
}
}
return maxLength;
}

Phân tích chi tiết

Đếm ký tự khả dụng:
- Sử dụng Map để đếm số lần xuất hiện của mỗi ký tự trong charschars.
Kiểm tra từng từ:
- Đếm số lần xuất hiện của mỗi ký tự trong từ.
- So sánh với các ký tự khả dụng, nếu từ không thể hình thành, bỏ qua.
Cập nhật độ dài lớn nhất:
- Nếu từ có thể hình thành, so sánh độ dài của từ với độ dài lớn nhất hiện tại.
Độ phức tạp:
- Thời gian: O(n×m)O(n \times m), với nn là số từ và mm là độ dài từ trung bình.
- Bộ nhớ: O(k)O(k), với kk là số ký tự khác nhau.

Ví dụ

console.log(longestWord(["cat", "bt", "hat", "tree"], "atach")); // 3 ("cat" hoặc "hat")
console.log(longestWord(["hello", "world", "leetcode"], "welldonehoneyr")); // 5 ("world")

Câu hỏi 82: Đảo ngược các từ trong một chuỗi

Viết hàm đảo ngược thứ tự các từ trong một chuỗi, loại bỏ khoảng trắng thừa.

Giải pháp

function reverseWords(s) {
return s.trim().split(/\s+/).reverse().join(" ");
}

Phân tích chi tiết

Loại bỏ khoảng trắng:
- trim() loại bỏ khoảng trắng ở đầu và cuối chuỗi.
- split(/\s+/) tách chuỗi thành các từ, bỏ qua khoảng trắng thừa.
Đảo ngược và ghép lại:
- reverse() đảo ngược thứ tự các từ.
- join(" ") ghép các từ lại với khoảng trắng giữa chúng.
Độ phức tạp:
- Thời gian: O(n)O(n), với nn là độ dài chuỗi.
- Bộ nhớ: O(n)O(n) cho mảng từ.

Ví dụ

console.log(reverseWords("  the sky is   blue  ")); // "blue is sky the"
console.log(reverseWords("hello world!")); // "world! hello"

Câu hỏi 83: Tìm từ dài nhất trong chuỗi con của một chuỗi khác

Viết hàm nhận vào một danh sách từ và một chuỗi ss, trả về từ dài nhất có thể hình thành bằng cách sắp xếp chuỗi con của ss.

Giải pháp

function findLongestWord(s, dictionary) {
dictionary.sort((a, b) => b.length - a.length || a.localeCompare(b));
function isSubsequence(word) {
let i = 0, j = 0;
while (i < word.length && j < s.length) {
if (word[i] === s[j]) i++;
j++;
}
return i === word.length;
}
for (let word of dictionary) {
if (isSubsequence(word)) {
return word;
}
}
return "";
}

Phân tích chi tiết

Sắp xếp danh sách từ:
- Sắp xếp từ dài nhất đến ngắn nhất, nếu bằng nhau thì theo thứ tự từ điển.
Kiểm tra chuỗi con:
- Sử dụng hai con trỏ để kiểm tra xem từ có phải là chuỗi con của ss.
Trả về kết quả:
- Trả về từ đầu tiên thỏa mãn điều kiện.
Độ phức tạp:
- Thời gian: O(n×m)O(n \times m), với nn là số từ và mm là độ dài trung bình của từ.
- Bộ nhớ: O(1)O(1).

Ví dụ

console.log(findLongestWord("abpcplea", ["ale", "apple", "monkey", "plea"])); // "apple"
console.log(findLongestWord("abpcplea", ["a", "b", "c"])); // "a"

Câu hỏi 84: Tìm số lượng từ trong một chuỗi

Viết hàm đếm số lượng từ trong một chuỗi. Một từ được định nghĩa là chuỗi các ký tự không phải khoảng trắng.

Giải pháp

function countWords(s) {
const words = s.trim().split(/\s+/);
return words.length === 1 && words[0] === "" ? 0 : words.length;
}

Phân tích chi tiết

Loại bỏ khoảng trắng thừa:
- trim() loại bỏ khoảng trắng ở đầu và cuối chuỗi.
- split(/\s+/) tách chuỗi thành các từ dựa trên khoảng trắng.
Xử lý trường hợp đặc biệt:
- Nếu chuỗi rỗng hoặc chỉ chứa khoảng trắng, trả về 0.
Đếm số từ:
- Số phần tử trong mảng words là số từ.
Độ phức tạp:
- Thời gian: O(n)O(n), với nn là độ dài chuỗi.
- Bộ nhớ: O(k)O(k), với kk là số từ trong chuỗi.

Ví dụ

console.log(countWords("Hello World")); // 2
console.log(countWords("  Leading and trailing spaces   ")); // 4
console.log(countWords("")); // 0

Câu hỏi 85: Tìm độ dài từ cuối cùng trong chuỗi

Viết hàm trả về độ dài của từ cuối cùng trong chuỗi. Nếu không có từ, trả về 0.

Giải pháp

function lengthOfLastWord(s) {
const words = s.trim().split(/\s+/);
return words.length === 0 ? 0 : words[words.length - 1].length;
}

Phân tích chi tiết

Loại bỏ khoảng trắng thừa:
- trim() loại bỏ khoảng trắng ở đầu và cuối chuỗi.
- split(/\s+/) tách chuỗi thành các từ dựa trên khoảng trắng.
Lấy từ cuối cùng:
- Lấy phần tử cuối cùng trong mảng words và trả về độ dài của nó.
Xử lý trường hợp đặc biệt:
- Nếu mảng không có phần tử, trả về 0.
Độ phức tạp:
- Thời gian: O(n)O(n), với nn là độ dài chuỗi.
- Bộ nhớ: O(k)O(k), với kk là số từ trong chuỗi.

Ví dụ

console.log(lengthOfLastWord("Hello World")); // 5
console.log(lengthOfLastWord("  fly me   to   the moon  ")); // 4
console.log(lengthOfLastWord("   ")); // 0

Câu hỏi 86: Kiểm tra chuỗi là Palindrome, không phân biệt khoảng trắng và ký tự đặc biệt

Viết hàm kiểm tra xem một chuỗi có phải là Palindrome không, bỏ qua khoảng trắng, ký tự đặc biệt và không phân biệt chữ hoa, chữ thường.

Giải pháp

function isPalindromeIgnoreCase(s) {
const cleaned = s.toLowerCase().replace(/[^a-z0-9]/g, "");
let left = 0, right = cleaned.length - 1;
while (left < right) {
if (cleaned[left] !== cleaned[right]) return false;
left++;
right--;
}
return true;
}

Phân tích chi tiết

Làm sạch chuỗi:
- toLowerCase(): Chuyển toàn bộ ký tự về chữ thường.
- replace(/[^a-z0-9]/g, ""): Loại bỏ tất cả ký tự không phải chữ cái và số.
Kiểm tra Palindrome:
- Sử dụng hai con trỏ để so sánh ký tự đầu và cuối, di chuyển vào giữa.
Độ phức tạp:
- Thời gian: O(n)O(n), với nn là độ dài chuỗi sau khi làm sạch.
- Bộ nhớ: O(n)O(n), cho chuỗi làm sạch.

Ví dụ

console.log(isPalindromeIgnoreCase("A man, a plan, a canal: Panama")); // true
console.log(isPalindromeIgnoreCase("race a car")); // false
console.log(isPalindromeIgnoreCase(" ")); // true

Câu hỏi 87: Loại bỏ các ký tự trùng lặp liền kề trong chuỗi

Viết hàm loại bỏ tất cả các ký tự trùng lặp liền kề trong chuỗi.

Giải pháp

function removeDuplicates(s) {
const stack = [];
for (let char of s) {
if (stack.length > 0 && stack[stack.length - 1] === char) {
stack.pop();
} else {
stack.push(char);
}
}
return stack.join('');
}

Phân tích chi tiết

Sử dụng Stack:
- Nếu ký tự hiện tại bằng với ký tự ở đỉnh stack, loại bỏ ký tự ở đỉnh stack.
- Ngược lại, thêm ký tự vào stack.
Ghép kết quả:
- Sau khi duyệt qua toàn bộ chuỗi, các ký tự trong stack là kết quả cuối cùng.
Độ phức tạp:
- Thời gian: O(n)O(n), với nn là độ dài chuỗi.
- Bộ nhớ: O(n)O(n), cho stack.

Ví dụ

console.log(removeDuplicates("abbaca")); // "ca"
console.log(removeDuplicates("azxxzy")); // "ay"
console.log(removeDuplicates("aaaa")); // ""

Câu hỏi 88: Xóa chuỗi con Palindrome dài nhất

Viết hàm trả về số lần xóa tối thiểu để chuỗi trở thành chuỗi rỗng bằng cách xóa các chuỗi con Palindrome.

Giải pháp

function removePalindromeSub(s) {
if (s === "") return 0;
return s === s.split('').reverse().join('') ? 1 : 2;
}

Phân tích chi tiết

Trường hợp đặc biệt:
- Nếu chuỗi rỗng, không cần xóa, trả về 0.
Kiểm tra Palindrome:
- Nếu chuỗi là Palindrome, chỉ cần xóa một lần.
- Nếu không, cần tối đa 2 lần:
  - Xóa tất cả chữ cái ‘a’.
  - Xóa tất cả chữ cái ‘b’.
Độ phức tạp:
- Thời gian: O(n)O(n), với nn là độ dài chuỗi.
- Bộ nhớ: O(n)O(n), cho thao tác đảo chuỗi.

Ví dụ

console.log(removePalindromeSub("ababa")); // 1
console.log(removePalindromeSub("abb")); // 2
console.log(removePalindromeSub("")); // 0

Câu hỏi 89: Sắp xếp chuỗi theo tần suất ký tự giảm dần

Viết hàm nhận vào một chuỗi và trả về chuỗi đã được sắp xếp theo tần suất xuất hiện của các ký tự, giảm dần.

Giải pháp

function frequencySort(s) {
const freqMap = new Map();
for (let char of s) {
freqMap.set(char, (freqMap.get(char) || 0) + 1);
}
return Array.from(freqMap)
.sort((a, b) => b[1] - a[1])
.map(([char, freq]) => char.repeat(freq))
.join('');
}

Phân tích chi tiết

Đếm tần suất ký tự:
- Sử dụng Map để lưu tần suất của mỗi ký tự trong chuỗi.
Sắp xếp theo tần suất:
- Chuyển Map thành mảng và sắp xếp các phần tử theo tần suất giảm dần.
Tạo chuỗi kết quả:
- Nhân ký tự với tần suất của nó và ghép các phần tử lại thành chuỗi.
Độ phức tạp:
- Thời gian: O(n+klog⁡k)O(n + k \log k), với nn là độ dài chuỗi và kk là số ký tự khác nhau.
- Bộ nhớ: O(k)O(k).

Ví dụ

console.log(frequencySort("tree")); // "eert" hoặc "eetr"
console.log(frequencySort("cccaaa")); // "cccaaa" hoặc "aaaccc"
console.log(frequencySort("Aabb")); // "bbAa" hoặc "bbaA"

Câu hỏi 90: Tìm từ dài nhất trong danh sách là chuỗi con của chuỗi ss

Viết hàm nhận vào một chuỗi ss và một danh sách từ, trả về từ dài nhất trong danh sách có thể là chuỗi con của ss. Nếu có nhiều từ cùng độ dài, trả về từ nhỏ nhất theo thứ tự từ điển.

Giải pháp

function findLongestWord(s, dictionary) {
dictionary.sort((a, b) => b.length - a.length || a.localeCompare(b));
function isSubsequence(word) {
let i = 0, j = 0;
while (i < word.length && j < s.length) {
if (word[i] === s[j]) i++;
j++;
}
return i === word.length;
}
for (let word of dictionary) {
if (isSubsequence(word)) {
return word;
}
}
return "";
}

Phân tích chi tiết

Sắp xếp danh sách từ:
- Sắp xếp từ dài nhất đến ngắn nhất, nếu cùng độ dài thì theo thứ tự từ điển.
Kiểm tra chuỗi con:
- Sử dụng hai con trỏ để kiểm tra xem từ có phải là chuỗi con của ss.
Trả về kết quả:
- Trả về từ đầu tiên thỏa mãn điều kiện là chuỗi con.
Độ phức tạp:
- Thời gian: O(n×m)O(n \times m), với nn là số từ và mm là độ dài trung bình của từ.
- Bộ nhớ: O(1)O(1).

Ví dụ

console.log(findLongestWord("abpcplea", ["ale", "apple", "monkey", "plea"])); // "apple"
console.log(findLongestWord("abpcplea", ["a", "b", "c"])); // "a"

Câu hỏi 91: Tìm chuỗi con lặp lại nhiều nhất trong chuỗi

Viết hàm nhận vào một chuỗi và độ dài kk, trả về chuỗi con có tần suất lặp lại nhiều nhất với độ dài kk.

Giải pháp

function mostFrequentSubstring(s, k) {
const freqMap = new Map();
for (let i = 0; i <= s.length - k; i++) {
const substring = s.substring(i, i + k);
freqMap.set(substring, (freqMap.get(substring) || 0) + 1);
}
let maxFreq = 0;
let result = "";
for (let [substring, freq] of freqMap.entries()) {
if (freq > maxFreq || (freq === maxFreq && substring < result)) {
maxFreq = freq;
result = substring;
}
}
return result;
}

Phân tích chi tiết

Tạo chuỗi con:
- Lấy tất cả chuỗi con có độ dài kk từ chuỗi đầu vào.
Đếm tần suất:
- Sử dụng Map để lưu số lần xuất hiện của mỗi chuỗi con.
Tìm chuỗi con có tần suất lớn nhất:
- So sánh tần suất và chọn chuỗi con có tần suất lớn nhất.
- Nếu tần suất bằng nhau, chọn chuỗi con nhỏ hơn về mặt từ điển.
Độ phức tạp:
- Thời gian: O(n×k)O(n \times k), với nn là độ dài chuỗi và kk là độ dài chuỗi con.
- Bộ nhớ: O(n)O(n).

Ví dụ

console.log(mostFrequentSubstring("ababab", 2)); // "ab"
console.log(mostFrequentSubstring("abcabc", 3)); // "abc"
console.log(mostFrequentSubstring("aaaa", 2)); // "aa"

Câu hỏi 92: Tìm chuỗi con liên tục có tổng ASCII lớn nhất

Viết hàm nhận vào một chuỗi và trả về chuỗi con liên tục có tổng giá trị ASCII lớn nhất.

Giải pháp: Kadane’s Algorithm

function maxSubstringASCII(s) {
let maxSum = -Infinity, currentSum = 0;
let start = 0, tempStart = 0, end = 0;
for (let i = 0; i < s.length; i++) {
currentSum += s.charCodeAt(i);
if (currentSum > maxSum) {
maxSum = currentSum;
start = tempStart;
end = i;
}
if (currentSum < 0) {
currentSum = 0;
tempStart = i + 1;
}
}
return s.substring(start, end + 1);
}

Phân tích chi tiết

Duyệt qua chuỗi:
- Tính tổng giá trị ASCII của chuỗi con liên tục.
Cập nhật chuỗi con tối ưu:
- Nếu tổng hiện tại lớn hơn tổng lớn nhất, cập nhật chỉ số bắt đầu và kết thúc của chuỗi con.
Khởi động lại tổng:
- Nếu tổng hiện tại âm, bắt đầu lại từ vị trí kế tiếp.
Độ phức tạp:
- Thời gian: O(n)O(n), với nn là độ dài chuỗi.
- Bộ nhớ: O(1)O(1).

Ví dụ

console.log(maxSubstringASCII("abcde")); // "abcde" (tổng ASCII: 495)
console.log(maxSubstringASCII("abcxyz")); // "xyz" (tổng ASCII: 378)
console.log(maxSubstringASCII("a")); // "a"

Câu hỏi 93: Tìm độ dài chuỗi con liên tục duy nhất dài nhất (Longest Substring Without Repeating Characters)

Viết hàm nhận vào một chuỗi và trả về độ dài của chuỗi con liên tục mà không chứa ký tự lặp lại.

Giải pháp: Sliding Window + HashMap

function lengthOfLongestSubstring(s) {
const charMap = new Map();
let maxLength = 0, start = 0;
for (let end = 0; end < s.length; end++) {
if (charMap.has(s[end])) {
start = Math.max(start, charMap.get(s[end]) + 1);
}
charMap.set(s[end], end);
maxLength = Math.max(maxLength, end - start + 1);
}
return maxLength;
}

Phân tích chi tiết

HashMap:
- Lưu trữ vị trí xuất hiện cuối cùng của mỗi ký tự.
Cửa sổ trượt:
- Khi phát hiện ký tự lặp lại, cập nhật start để loại bỏ ký tự trùng.
Cập nhật độ dài lớn nhất:
- Tính độ dài của cửa sổ hiện tại và cập nhật maxLength.
Độ phức tạp:
- Thời gian: O(n)O(n), với nn là độ dài chuỗi.
- Bộ nhớ: O(k)O(k), với kk là số lượng ký tự khác nhau trong chuỗi.

Ví dụ

console.log(lengthOfLongestSubstring("abcabcbb")); // 3 ("abc")
console.log(lengthOfLongestSubstring("bbbbb")); // 1 ("b")
console.log(lengthOfLongestSubstring("pwwkew")); // 3 ("wke")

Câu hỏi 94: Tìm chuỗi con Palindrome nhiều lần lặp lại nhất

Viết hàm trả về chuỗi con Palindrome có tần suất xuất hiện nhiều nhất trong chuỗi.

Giải pháp

function mostFrequentPalindrome(s) {
const freqMap = new Map();
function isPalindrome(str) {
let left = 0, right = str.length - 1;
while (left < right) {
if (str[left] !== str[right]) return false;
left++;
right--;
}
return true;
}
for (let i = 0; i < s.length; i++) {
for (let j = i + 1; j <= s.length; j++) {
const substring = s.substring(i, j);
if (isPalindrome(substring)) {
freqMap.set(substring, (freqMap.get(substring) || 0) + 1);
}
}
}
let maxFreq = 0;
let result = "";
for (let [substring, freq] of freqMap.entries()) {
if (freq > maxFreq || (freq === maxFreq && substring.length > result.length)) {
maxFreq = freq;
result = substring;
}
}
return result;
}

Phân tích chi tiết

Kiểm tra Palindrome:
- Sử dụng hai con trỏ để kiểm tra nếu một chuỗi là Palindrome.
Tạo các chuỗi con:
- Duyệt qua tất cả các chuỗi con từ ii đến jj và kiểm tra nếu chúng là Palindrome.
Đếm tần suất:
- Lưu số lần xuất hiện của mỗi Palindrome vào Map.
Tìm chuỗi con tối ưu:
- Trả về chuỗi Palindrome có tần suất xuất hiện lớn nhất. Nếu tần suất bằng nhau, chọn chuỗi dài nhất.
Độ phức tạp:
- Thời gian: O(n3)O(n^3), với nn là độ dài chuỗi (bao gồm cả kiểm tra Palindrome).
- Bộ nhớ: O(k)O(k), với kk là số chuỗi con khác nhau.

Ví dụ

console.log(mostFrequentPalindrome("ababa")); // "aba"
console.log(mostFrequentPalindrome("racecaracecar")); // "racecar"
console.log(mostFrequentPalindrome("abcd")); // "a"

Câu hỏi 95: Tìm chuỗi con với độ dài kk chứa nhiều ký tự duy nhất nhất

Viết hàm nhận vào một chuỗi và một số kk, trả về chuỗi con có độ dài kk chứa nhiều ký tự duy nhất nhất.

Giải pháp: Sliding Window

function uniqueSubstringWithK(s, k) {
const charMap = new Map();
let maxUnique = 0, start = 0, result = "";
for (let end = 0; end < s.length; end++) {
charMap.set(s[end], (charMap.get(s[end]) || 0) + 1);
if (end - start + 1 > k) {
const leftChar = s[start];
charMap.set(leftChar, charMap.get(leftChar) - 1);
if (charMap.get(leftChar) === 0) {
charMap.delete(leftChar);
}
start++;
}
if (end - start + 1 === k) {
if (charMap.size > maxUnique) {
maxUnique = charMap.size;
result = s.substring(start, end + 1);
}
}
}
return result;
}

Phân tích chi tiết

Cửa sổ trượt:
- Duyệt qua chuỗi với một cửa sổ có kích thước kk.
Theo dõi tần suất ký tự:
- Sử dụng Map để lưu tần suất ký tự trong cửa sổ.
Tìm chuỗi con tối ưu:
- Nếu cửa sổ có kk ký tự và số lượng ký tự duy nhất lớn hơn, cập nhật chuỗi con tối ưu.
Độ phức tạp:
- Thời gian: O(n)O(n), với nn là độ dài chuỗi.
- Bộ nhớ: O(k)O(k), với kk là kích thước cửa sổ.

Ví dụ

console.log(uniqueSubstringWithK("abcabcbb", 3)); // "abc"
console.log(uniqueSubstringWithK("aaaaa", 2)); // "aa"
console.log(uniqueSubstringWithK("abcdefg", 4)); // "abcd"

Câu hỏi 96: Xác định chuỗi có phải là chuỗi con sắp xếp của chuỗi khác

Viết hàm kiểm tra xem chuỗi s1s1 có phải là một chuỗi con sắp xếp của chuỗi s2s2 không.

Giải pháp: Sliding Window + HashMap

function checkInclusion(s1, s2) {
const charCount = new Map();
for (let char of s1) {
charCount.set(char, (charCount.get(char) || 0) + 1);
}
let start = 0, matched = 0;
for (let end = 0; end < s2.length; end++) {
const char = s2[end];
if (charCount.has(char)) {
charCount.set(char, charCount.get(char) - 1);
if (charCount.get(char) === 0) matched++;
}
if (matched === charCount.size) return true;
if (end >= s1.length - 1) {
const leftChar = s2[start];
if (charCount.has(leftChar)) {
if (charCount.get(leftChar) === 0) matched--;
charCount.set(leftChar, charCount.get(leftChar) + 1);
}
start++;
}
}
return false;
}

Phân tích chi tiết

Tạo bản đồ tần suất:
- Lưu tần suất ký tự của s1s1 vào Map.
Cửa sổ trượt:
- Duyệt qua s2s2 với một cửa sổ có kích thước bằng s1s1.
Kiểm tra hoán vị:
- Nếu tất cả ký tự trong cửa sổ khớp với s1s1, trả về true.
Độ phức tạp:
- Thời gian: O(n)O(n), với nn là độ dài của s2s2.
- Bộ nhớ: O(k)O(k), với kk là số ký tự trong s1s1.

Ví dụ

console.log(checkInclusion("ab", "eidbaooo")); // true ("ba" là hoán vị của "ab")
console.log(checkInclusion("ab", "eidboaoo")); // false

Câu hỏi 97: Tìm chuỗi con ngắn nhất chứa tất cả các ký tự của một chuỗi

Viết hàm nhận vào hai chuỗi ss và tt, trả về chuỗi con ngắn nhất trong ss chứa tất cả các ký tự của tt. Nếu không tồn tại, trả về chuỗi rỗng.

Giải pháp: Sliding Window + HashMap

function minWindow(s, t) {
const tMap = new Map();
for (let char of t) {
tMap.set(char, (tMap.get(char) || 0) + 1);
}
let start = 0, matched = 0, minLen = Infinity, subStart = 0;
const sMap = new Map();
for (let end = 0; end < s.length; end++) {
const endChar = s[end];
if (tMap.has(endChar)) {
sMap.set(endChar, (sMap.get(endChar) || 0) + 1);
if (sMap.get(endChar) === tMap.get(endChar)) {
matched++;
}
}
while (matched === tMap.size) {
if (end - start + 1 < minLen) {
minLen = end - start + 1;
subStart = start;
}
const startChar = s[start];
if (tMap.has(startChar)) {
if (sMap.get(startChar) === tMap.get(startChar)) {
matched--;
}
sMap.set(startChar, sMap.get(startChar) - 1);
}
start++;
}
}
return minLen === Infinity ? "" : s.substring(subStart, subStart + minLen);
}

Phân tích chi tiết

Tạo bản đồ tần suất:
- Lưu tần suất của các ký tự trong tt vào Map.
Cửa sổ trượt:
- Sử dụng một cửa sổ để theo dõi các ký tự trong ss.
Thu hẹp cửa sổ:
- Khi cửa sổ chứa đủ tất cả các ký tự của tt, cố gắng thu hẹp để tìm chuỗi ngắn nhất.
Độ phức tạp:
- Thời gian: O(n+m)O(n + m), với nn là độ dài ss và mm là độ dài tt.
- Bộ nhớ: O(k)O(k), với kk là số ký tự khác nhau trong tt.

Ví dụ

console.log(minWindow("ADOBECODEBANC", "ABC")); // "BANC"
console.log(minWindow("a", "a")); // "a"
console.log(minWindow("a", "aa")); // ""

Câu hỏi 98: Tìm chuỗi con lớn nhất là chuỗi con chung của hai chuỗi

Viết hàm nhận vào hai chuỗi s1s1 và s2s2, trả về chuỗi con lớn nhất là chuỗi con chung của cả hai.

Giải pháp: Dynamic Programming

function longestCommonSubstring(s1, s2) {
const m = s1.length, n = s2.length;
const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
let maxLength = 0;
let endIndex = 0;
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (s1[i - 1] === s2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
if (dp[i][j] > maxLength) {
maxLength = dp[i][j];
endIndex = i - 1;
}
}
}
}
return s1.substring(endIndex - maxLength + 1, endIndex + 1);
}

Phân tích chi tiết

Mảng DP:
- dp[i][j]: Độ dài chuỗi con chung kết thúc tại s1[i−1]s1[i-1] và s2[j−1]s2[j-1].
Cập nhật DP:
- Nếu s1[i−1]===s2[j−1]s1[i-1] === s2[j-1], tăng giá trị DP từ phần tử trước.
Theo dõi chuỗi con dài nhất:
- Lưu độ dài lớn nhất và vị trí kết thúc của chuỗi con.
Độ phức tạp:
- Thời gian: O(m×n)O(m \times n), với m,nm, n là độ dài của s1s1 và s2s2.
- Bộ nhớ: O(m×n)O(m \times n).

Ví dụ

console.log(longestCommonSubstring("abcdef", "zcdemf")); // "cde"
console.log(longestCommonSubstring("abc", "def")); // ""
console.log(longestCommonSubstring("xyzabcd", "abcdxyz")); // "abcd"

Câu hỏi 99: Tìm chuỗi con có tổng ASCII lớn nhất

Viết hàm nhận vào một chuỗi và trả về chuỗi con liên tục có tổng giá trị ASCII lớn nhất.

Giải pháp: Kadane’s Algorithm

function maxASCIISubstring(s) {
let maxSum = -Infinity, currentSum = 0;
let start = 0, tempStart = 0, end = 0;
for (let i = 0; i < s.length; i++) {
currentSum += s.charCodeAt(i);
if (currentSum > maxSum) {
maxSum = currentSum;
start = tempStart;
end = i;
}
if (currentSum < 0) {
currentSum = 0;
tempStart = i + 1;
}
}
return s.substring(start, end + 1);
}

Phân tích chi tiết

Duyệt qua chuỗi:
- Tính tổng giá trị ASCII của chuỗi con liên tục.
Cập nhật chuỗi con tối ưu:
- Nếu tổng hiện tại lớn hơn tổng lớn nhất, cập nhật chỉ số bắt đầu và kết thúc của chuỗi con.
Khởi động lại tổng:
- Nếu tổng hiện tại âm, bắt đầu lại từ vị trí kế tiếp.
Độ phức tạp:
- Thời gian: O(n)O(n), với nn là độ dài chuỗi.
- Bộ nhớ: O(1)O(1).

Ví dụ

console.log(maxASCIISubstring("abcde")); // "abcde" (tổng ASCII: 495)
console.log(maxASCIISubstring("abcxyz")); // "abcxyz" (tổng ASCII: 726)
console.log(maxASCIISubstring("a")); // "a"

Câu hỏi 100: Xoay chuỗi để kiểm tra tính đồng dạng

Viết hàm kiểm tra xem chuỗi s2s2 có thể là chuỗi s1s1 xoay một số lần không.

Giải pháp

function isRotation(s1, s2) {
if (s1.length !== s2.length) return false;
return (s1 + s1).includes(s2);
}

Phân tích chi tiết

Kiểm tra độ dài:
- Nếu s1s1 và s2s2 không cùng độ dài, trả về false.
Tạo chuỗi mở rộng:
- Nối s1s1 với chính nó để kiểm tra mọi trường hợp xoay.
Kiểm tra sự tồn tại:
- Sử dụng includes để kiểm tra xem s2s2 có nằm trong chuỗi mở rộng không.
Độ phức tạp:
- Thời gian: O(n)O(n), với nn là độ dài chuỗi.
- Bộ nhớ: O(n)O(n), cho chuỗi mở rộng.

Ví dụ

console.log(isRotation("waterbottle", "erbottlewat")); // true
console.log(isRotation("abc", "cab")); // true
console.log(isRotation("abc", "bac")); // false