webdev programming javascript 100daysofcode

Bí Kíp Thuật Toán: Nắm Trọn 8 Kỹ Thuật Vàng Giải Quyết Mọi Bài Toán Lập Trình!

Lê Lân

26/06/2025

🚀 Các Kỹ Thuật Thuật Toán Cần Biết Để Giải Quyết Vấn Đề Hiệu Quả

Mở Đầu

Trong lĩnh vực lập trình và phát triển phần mềm, kỹ năng giải quyết các bài toán thuật toán một cách nhanh chóng và chính xác là vô cùng quan trọng. Việc sử dụng các kỹ thuật thuật toán phù hợp không chỉ giúp tăng tốc độ xử lý mà còn làm giảm độ phức tạp của các bài toán khó khăn. Bài viết này sẽ giới thiệu tới bạn đọc các kỹ thuật thuật toán phổ biến, kèm theo ví dụ minh họa cụ thể và các bài tập luyện tập trên LeetCode để rèn luyện kỹ năng. Bạn sẽ học được cách áp dụng từng kỹ thuật trong nhiều tình huống khác nhau, từ tìm kiếm, xử lý chuỗi, đến thao tác trên đồ thị.

💡 Note: Việc luyện tập thường xuyên với các bài toán thực tế sẽ giúp bạn nắm vững kiến thức và nâng cao khả năng tư duy thuật toán.

1. Two Pointer Technique (Kỹ Thuật Hai Con Trỏ) 🏃‍♂️🏃‍♀️

Khái Niệm

Two Pointer là kỹ thuật sử dụng hai con trỏ di chuyển trong một cấu trúc dữ liệu (thường là mảng đã được sắp xếp) để xử lý các bài toán tìm kiếm hay so sánh một cách hiệu quả.

Ứng Dụng Thông Thường

Tìm kiếm trong mảng đã sắp xếp.

Tìm cặp phần tử thỏa điều kiện.

Xử lý các bài toán liên quan đến chuỗi con và phân đoạn.

Ví Dụ Cụ Thể

Tìm hai số trong mảng đã sắp xếp có tổng bằng một giá trị mục tiêu.

function twoSumSorted(arr, target) {
  let left = 0, right = arr.length - 1;
  while (left < right) {
    let sum = arr[left] + arr[right];
    if (sum === target) return [arr[left], arr[right]];
    sum < target ? left++ : right--;
  }
  return [];
}

Luyện Tập

Two Sum II - Input Array Is Sorted

🔹 Lưu ý: Kỹ thuật này chỉ áp dụng được khi mảng đã được sắp xếp. Nếu chưa sắp xếp, bạn cần sắp xếp trước hoặc sử dụng kỹ thuật khác.

2. Prefix Sum (Tổng Tiền Tố) ➕

Khái Niệm

Prefix Sum là kỹ thuật tính tổng tích luỹ để trả lời nhanh các truy vấn về tổng trong một đoạn dữ liệu liên tiếp.

Ứng Dụng

Tính tổng đoạn con trong mảng.

Phân tích và phát hiện các mẫu trong chuỗi hoặc mảng số.

Ví Dụ Cụ Thể

Tính mảng prefix sum từ một mảng đã cho:

function prefixSum(arr) {
  let prefix = [0];
  for (let i = 0; i < arr.length; i++) {
    prefix[i + 1] = prefix[i] + arr[i];
  }
  return prefix;
}

Luyện Tập

Range Sum Query - Immutable

🔹 Ưu điểm: Trả lời truy vấn tổng một đoạn bằng cách lấy hiệu hai giá trị prefix sum, giúp truy vấn O(1) sau khi tiền xử lý.

3. Top K Elements (Tìm K Phần Tử Lớn Nhất) 🔝

Khái Niệm

Kỹ thuật này dùng sắp xếp hoặc cấu trúc dữ liệu như heap để tìm top k phần tử quan trọng theo một tiêu chí (ví dụ: giá trị lớn nhất, tần suất cao nhất).

Ví Dụ

Tìm k phần tử lớn nhất trong một mảng:

function topKElements(arr, k) {
  return arr.sort((a, b) => b - a).slice(0, k);
}

Luyện Tập

Top K Frequent Elements

🔹 Chú ý: Sử dụng heap có thể nâng cao hiệu quả nếu mảng rất lớn và k nhỏ.

4. Sliding Window (Kỹ Thuật Cửa Sổ Trượt) 🏠

Khái Niệm

Sliding Window sử dụng một cửa sổ với kích thước cố định hoặc thay đổi di chuyển qua dữ liệu để tối ưu các phép tính trên đoạn liên tiếp.

Ví Dụ

Tìm tổng lớn nhất của k phần tử liên tiếp trong mảng:

function maxSumSubarray(arr, k) {
  let sum = 0, maxSum = -Infinity;
  for (let i = 0; i < k; i++) sum += arr[i];
  maxSum = sum;
  for (let i = k; i < arr.length; i++) {
    sum += arr[i] - arr[i - k];
    maxSum = Math.max(maxSum, sum);
  }
  return maxSum;
}

Luyện Tập

Maximum Subarray

🔹 Mẹo: Kỹ thuật này tránh tính lại tổng nhiều lần, giúp giảm độ phức tạp từ O(n*k) xuống O(n).

5. Breadth-First Search (BFS) 🌳

Khái Niệm

BFS là kỹ thuật duyệt hoặc tìm kiếm trên đồ thị bằng cách khám phá tất cả các node theo lớp, đi từ node nguồn ra các node ở các tầng xa dần.

Ví Dụ

Duyệt đồ thị sử dụng BFS:

function bfs(graph, start) {
  let queue = [start], visited = new Set(queue);
  while (queue.length) {
    let node = queue.shift();
    console.log(node);
    for (let neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
}

Luyện Tập

Binary Tree Level Order Traversal

🔹 Ứng dụng: Tính khoảng cách ngắn nhất trên đồ thị không trọng số, duyệt cây theo cấp độ.

6. Depth-First Search (DFS) 🕵️

Khái Niệm

DFS là kỹ thuật tìm kiếm đi sâu vào một nhánh đến tận cùng trước khi quay lui và khám phá những nhánh khác.

Ví Dụ

DFS trên đồ thị:

function dfs(graph, node, visited = new Set()) {
  if (visited.has(node)) return;
  visited.add(node);
  console.log(node);
  for (let neighbor of graph[node]) {
    dfs(graph, neighbor, visited);
  }
}

Luyện Tập

Number of Islands

🔹 Lưu ý: DFS thường dùng trong bài toán đếm thành phần liên thông, chu trình, hoặc phân tích cấu trúc đồ thị.

7. Topological Sort (Sắp Xếp Tuần Tự) 📋

Khái Niệm

Topological Sort là thuật toán sắp xếp các node của đồ thị có hướng sao cho với mỗi cạnh u → v, u đứng trước v trong thứ tự.

Ví Dụ

Sắp xếp topo của đồ thị:

function topologicalSort(graph) {
  let inDegree = {}, queue = [], result = [];
  Object.keys(graph).forEach(node => inDegree[node] = 0);
  Object.values(graph).flat().forEach(node => inDegree[node]++);
  Object.keys(graph).forEach(node => inDegree[node] === 0 && queue.push(node));

  while (queue.length) {
    let node = queue.shift();
    result.push(node);
    graph[node].forEach(neighbor => {
      if (--inDegree[neighbor] === 0) queue.push(neighbor);
    });
  }
  return result;
}

Luyện Tập

Course Schedule II

🔹 Sử dụng: Trong các bài toán liên quan đến lịch trình, thứ tự công việc có phụ thuộc.

8. Divide and Conquer (Chia Để Trị) ✂️

Khái Niệm

Phương pháp chia nhỏ bài toán thành các bài toán con độc lập, giải từng bài toán con và kết hợp kết quả lại thành lời giải cho bài toán lớn.

Ví Dụ

Thuật toán Merge Sort:

function mergeSort(arr) {
  if (arr.length < 2) return arr;
  let mid = Math.floor(arr.length / 2);
  let left = mergeSort(arr.slice(0, mid));
  let right = mergeSort(arr.slice(mid));
  return merge(left, right);
}

function merge(left, right) {
  let result = [];
  while (left.length && right.length) {
    result.push(left[0] < right[0] ? left.shift() : right.shift());
  }
  return [...result, ...left, ...right];
}

Luyện Tập

Sort an Array

🔹 Ưu điểm: Giảm đáng kể độ phức tạp bài toán, phù hợp với nhiều thuật toán sắp xếp và tìm kiếm phức tạp.

Kết Luận

Việc nắm vững và thành thạo các kỹ thuật thuật toán kể trên sẽ tăng tốc đáng kể khả năng giải quyết bài toán của bạn. Từng kỹ thuật đều có ứng dụng thực tế và giúp giảm độ phức tạp không cần thiết trong quá trình lập trình. Hãy không ngừng luyện tập các bài toán thực tế trên các nền tảng như LeetCode để rèn luyện kỹ năng và cải thiện tư duy thuật toán.

🚀 Hãy bắt đầu luyện tập ngay hôm nay! Càng thực hành nhiều, bạn sẽ càng tự tin và sáng tạo hơn trong việc lựa chọn giải pháp thuật toán tối ưu.

Tham Khảo

LeetCode

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. Introduction to Algorithms, MIT Press

Khan Academy - Algorithms

GeeksforGeeks - Algorithm Tutorials

June 1, 2024