八、五大基础算法思想
8.1 枚举法（暴力法）
最简单的算法思想：尝试所有可能性。
// 找出所有三位数的水仙花数（153 = 1³+5³+3³）
function findNarcissisticNumbers() {
const results = [];
for (let i = 100; i <= 999; i++) {
const digits = i.toString().split('');
const sum = digits.reduce((acc, d) => acc + Math.pow(parseInt(d), 3), 0);
if (sum === i) {
results.push(i);
}
}
return results;
}
console.log(findNarcissisticNumbers()); // [153, 370, 371, 407]
8.2 贪心算法
每一步都选择当前最优解，希望达到全局最优。
// 找零问题：用最少的硬币找零
function minCoins(amount, coins) {
coins.sort((a, b) => b - a); // 从大到小排序
let remaining = amount;
let count = 0;
for (const coin of coins) {
const num = Math.floor(remaining / coin);
count += num;
remaining -= num * coin;
if (remaining === 0) break;
}
return remaining === 0 ? count : -1;
}
console.log(minCoins(63, [1, 5, 10, 25])); // 25+25+10+1+1+1 = 6枚
// 贪心并不总是最优，但在这个硬币体系中是最优的
// 贪心算法经典案例：活动选择
function maxActivities(activities) {
// 按结束时间排序
activities.sort((a, b) => a.end - b.end);
const selected = [activities[0]];
let lastEnd = activities[0].end;
for (let i = 1; i < activities.length; i++) {
if (activities[i].start >= lastEnd) {
selected.push(activities[i]);
lastEnd = activities[i].end;
}
}
return selected;
}
const activities = [
{ start: 1, end: 4 },
{ start: 3, end: 5 },
{ start: 0, end: 6 },
{ start: 5, end: 7 },
{ start: 3, end: 9 },
{ start: 5, end: 9 },
{ start: 6, end: 10 },
{ start: 8, end: 11 },
{ start: 8, end: 12 },
{ start: 2, end: 14 },
{ start: 12, end: 16 }
];
console.log(maxActivities(activities).length); // 4个活动
8.3 分治算法
将大问题分解为小问题，分别解决后合并结果。
// 归并排序（分治算法经典）
function mergeSort(arr) {
if (arr.length <= 1) return arr;
const mid = Math.floor(arr.length / 2);
const left = mergeSort(arr.slice(0, mid));
const right = mergeSort(arr.slice(mid));
return merge(left, right);
}
function merge(left, right) {
const result = [];
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++]);
}
}
return result.concat(left.slice(i)).concat(right.slice(j));
}
// 最大子数组和（分治法）
function maxSubArray(nums) {
return _maxSubArray(nums, 0, nums.length - 1);
}
function _maxSubArray(nums, left, right) {
if (left === right) return nums[left];
const mid = Math.floor((left + right) / 2);
const leftMax = _maxSubArray(nums, left, mid);
const rightMax = _maxSubArray(nums, mid + 1, right);
const crossMax = maxCrossingSum(nums, left, mid, right);
return Math.max(leftMax, rightMax, crossMax);
}
function maxCrossingSum(nums, left, mid, right) {
let leftSum = -Infinity;
let sum = 0;
for (let i = mid; i >= left; i--) {
sum += nums[i];
leftSum = Math.max(leftSum, sum);
}
let rightSum = -Infinity;
sum = 0;
for (let i = mid + 1; i <= right; i++) {
sum += nums[i];
rightSum = Math.max(rightSum, sum);
}
return leftSum + rightSum;
}
console.log(maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4])); // 6（子数组[4,-1,2,1]）
8.4 动态规划（DP）
将大问题分解为重叠子问题，保存子问题的解避免重复计算。
// 1. 斐波那契数列（DP入门）
function fibDP(n) {
if (n <= 1) return n;
const dp = new Array(n + 1);
dp[0] = 0;
dp[1] = 1;
for (let i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
// 空间优化版本
function fibOptimized(n) {
if (n <= 1) return n;
let prev2 = 0;
let prev1 = 1;
for (let i = 2; i <= n; i++) {
const current = prev1 + prev2;
prev2 = prev1;
prev1 = current;
}
return prev1;
}
console.log(fibOptimized(10)); // 55
// 2. 爬楼梯问题
// 每次可以爬1或2阶，爬到n阶有多少种方法
function climbStairs(n) {
if (n <= 2) return n;
const dp = new Array(n + 1);
dp[1] = 1;
dp[2] = 2;
for (let i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
console.log(climbStairs(5)); // 8
// 3. 背包问题（经典DP）
/**
* 0-1背包问题
* @param {number[]} weights 物品重量
* @param {number[]} values 物品价值
* @param {number} capacity 背包容量
*/
function knapsack(weights, values, capacity) {
const n = weights.length;
// dp[i][w] 表示前i个物品，容量为w时的最大价值
const dp = Array(n + 1).fill().map(() => Array(capacity + 1).fill(0));
for (let i = 1; i <= n; i++) {
for (let w = 1; w <= capacity; w++) {
if (weights[i - 1] <= w) {
// 可以选择放或不放当前物品
dp[i][w] = Math.max(
dp[i - 1][w], // 不放
dp[i - 1][w - weights[i - 1]] + values[i - 1] // 放
);
} else {
dp[i][w] = dp[i - 1][w];
}
}
}
return dp[n][capacity];
}
const weights = [2, 3, 4, 5];
const values = [3, 4, 5, 6];
console.log(knapsack(weights, values, 5)); // 7（放重量2+3，价值3+4）
// 4. 最长公共子序列（LCS）
function longestCommonSubsequence(text1, text2) {
const m = text1.length;
const n = text2.length;
const dp = Array(m + 1).fill().map(() => Array(n + 1).fill(0));
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (text1[i - 1] === text2[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];
}
console.log(longestCommonSubsequence("abcde", "ace")); // 3（"ace"）
8.5 回溯算法
通过尝试所有可能性，遇到不满足条件时回退（剪枝）。解决排列、组合、子集等问题。
// 1. 全排列
function permute(nums) {
const result = [];
const used = new Array(nums.length).fill(false);
function backtrack(path) {
if (path.length === nums.length) {
result.push([...path]);
return;
}
for (let i = 0; i < nums.length; i++) {
if (used[i]) continue;
used[i] = true;
path.push(nums[i]);
backtrack(path);
path.pop(); // 回溯
used[i] = false;
}
}
backtrack([]);
return result;
}
console.log(permute([1, 2, 3]));
// [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
// 2. 组合（从n个数中选k个）
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;
}
console.log(combine(4, 2));
// [[1,2], [1,3], [1,4], [2,3], [2,4], [3,4]]
// 3. N皇后问题
function solveNQueens(n) {
const result = [];
const board = Array(n).fill().map(() => Array(n).fill('.'));
function isValid(row, col) {
// 检查列
for (let i = 0; i < row; i++) {
if (board[i][col] === 'Q') return false;
}
// 检查左上对角线
for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if (board[i][j] === 'Q') return false;
}
// 检查右上对角线
for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
if (board[i][j] === 'Q') return false;
}
return true;
}
function backtrack(row) {
if (row === n) {
result.push(board.map(row => row.join('')));
return;
}
for (let col = 0; col < n; col++) {
if (isValid(row, col)) {
board[row][col] = 'Q';
backtrack(row + 1);
board[row][col] = '.';
}
}
}
backtrack(0);
return result;
}
const solutions = solveNQueens(4);
console.log(`4皇后问题有 ${solutions.length} 个解`);
console.log(solutions[0]);
// [ '.Q..', '...Q', 'Q...', '..Q.' ]
附：
知识点地图
数据结构与算法
├── 复杂度分析 (O(1), O(n), O(n²), O(log n)...)
├── 线性结构
│ ├── 数组 (连续内存，随机访问快)
│ ├── 链表 (动态，插入删除快)
│ ├── 栈 (后进先出，函数调用)
│ └── 队列 (先进先出，任务调度)
├── 哈希表 (键值存储，O(1) 操作)
├── 树形结构
│ ├── 二叉树 (每个节点最多两个子节点)
│ ├── 二叉搜索树 (有序，中序遍历)
│ └── 遍历 (前序、中序、后序、层序)
└── 算法思想
├── 枚举 (暴力求解)
├── 贪心 (局部最优)
├── 分治 (分解合并)
├── 动态规划 (重叠子问题)
└── 回溯 (尝试+剪枝)
