1. 排序算法
1.1. 冒泡排序（Bubble Sort）
冒泡排序是一种简单的排序算法，通过反复遍历数组，将相邻的两个元素进行比较并交换位置，从而将最大的元素逐步移到数组的末尾。
优点：
实现简单：算法逻辑简单，易于理解。
原地排序：不需要额外的内存空间，空间复杂度为 O(1)。
缺点：
效率低下：时间复杂度为 O(n²)，对大规模数据排序效率很差。
适合小规模数据：对于小规模数据或几乎有序的数据有一定效果。
代码示例：
function bubbleSort(arr: number[]): number[] {
const len = arr.length;
for (let i = 0; i < len; i++) {
for (let j = 0; j < len - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; // 交换位置
}
}
}
return arr;
}使用场景：
小规模数据排序：当数据量很小时可以使用，尤其是数据几乎有序时。
1.2. 选择排序（Selection Sort）
选择排序每次从未排序的部分选择最小或最大的元素，放到已排序部分的末尾，逐步缩小未排序部分。
优点：
简单直观：逻辑简单，易于实现。
数据移动次数少：每次交换只涉及一次最小值移动。
缺点：
效率较低：时间复杂度为 O(n²)，大规模数据表现不佳。
不稳定排序：相同元素的相对顺序可能会被改变。
代码示例：
function selectionSort(arr: number[]): number[] {
const len = arr.length;
for (let i = 0; i < len - 1; i++) {
let minIndex = i;
for (let j = i + 1; j < len; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
if (minIndex !== i) {
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]; // 交换最小值到已排序部分
}
}
return arr;
}使用场景：
小规模数据排序：适合数据量较少的情况。
对内存写操作敏感的场景：如硬盘排序或闪存存储。
1.3. 插入排序（Insertion Sort）
插入排序通过将每个元素插入到已排序部分的适当位置，逐步构建有序序列。
优点：
适合小规模数据：表现较好，尤其是数据接近有序时。
稳定排序：相同元素的相对顺序不会改变。
缺点：
效率较低：时间复杂度为 O(n²)，无序数据时性能较差。
代码示例：
function insertionSort(arr: number[]): number[] {
const len = arr.length;
for (let i = 1; i < len; i++) {
let key = arr[i];
let j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j]; // 将比 key 大的元素后移
j--;
}
arr[j + 1] = key;
}
return arr;
}使用场景：
小规模数据排序：适合数据量较少的情况。
几乎有序的数据：当数据接近有序时，插入排序的时间复杂度接近 O(n)。
1.4. 归并排序（Merge Sort）
归并排序是一种基于分治思想的排序算法，将数组分为两个子数组，递归排序后合并成一个有序数组。
优点：
时间复杂度稳定：O(n log n)，适合大规模数据。
稳定排序：相同元素的相对顺序不变。
缺点：
需要额外空间：需要 O(n) 的额外空间存储合并结果。
代码示例：
function mergeSort(arr: number[]): number[] {
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: number[], right: number[]): number[] {
const result: number[] = [];
let i = 0, j = 0;
while (i < left.length && j < right.length) {
if (left[i] < right[j]) {
result.push(left[i]);
i++;
} else {
result.push(right[j]);
j++;
}
}
return result.concat(left.slice(i), right.slice(j));
}使用场景：
大规模数据排序：归并排序适合处理大量数据。
链表排序：归并排序在链表上的效率高于其他排序算法。
1.5. 快速排序（Quick Sort）
快速排序通过选择一个基准元素，将数组分为小于和大于基准的两部分，递归排序。
优点：
平均性能优异：时间复杂度为 O(n log n)，常数因子小，适合大规模数据。
原地排序：不需要额外的存储空间，空间复杂度为 O(log n))。
缺点：
最坏情况退化：在不好的情况下，时间复杂度会退化为 O(n²)。
不稳定排序：相同元素的相对顺序可能改变。
代码示例：
function quickSort(arr: number[]): number[] {
if (arr.length <= 1) return arr;
const pivot = arr[Math.floor(arr.length / 2)];
const left = arr.filter(x => x < pivot);
const right = arr.filter(x => x > pivot);
const middle = arr.filter(x => x === pivot);
return quickSort(left).concat(middle, quickSort(right));
}使用场景：
大规模数据排序：快速排序是实际应用中常用的排序算法之一。
对空间要求敏感的场景：快速排序为原地排序。
1.6. 希尔排序（Shell Sort）
希尔排序是插入排序的改进版，通过将数组按照一定的间隔分为多个子序列，先对每个子序列进行插入排序，然后逐渐减小间隔直到最后对整个序列进行插入排序。
优点：
改进了插入排序：通过间隔分组，减少了大数据量的移动，提升了效率。
适合中等规模数据：在一些特定场景中，希尔排序比 O(n log n) 的算法更快。
缺点：
时间复杂度依赖于间隔序列的选择：通常的复杂度在 O(n log² n) 到 O(n³/2) 之间。
不稳定排序：相同元素的相对顺序可能会改变。
代码示例：
function shellSort(arr: number[]): number[] {
let gap = Math.floor(arr.length / 2);
while (gap > 0) {
for (let i = gap; i < arr.length; i++) {
const temp = arr[i];
let j;
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
arr[j] = arr[j - gap];
}
arr[j] = temp;
}
gap = Math.floor(gap / 2);
}
return arr;
}使用场景：
希尔排序适用于中等规模的数组或列表，尤其是在插入排序表现不佳时使用。
1.7. 堆排序（Heap Sort）
堆排序利用堆这种数据结构来排序，首先将数组构造成一个大顶堆或小顶堆，然后反复取出堆顶元素并将其放在已排好序的部分。
优点：
时间复杂度稳定：最坏、最好、平均情况下时间复杂度均为 O(n log n)。
原地排序：只需要少量的额外存储空间O(1)。
缺点：
不稳定排序：相同元素的相对顺序可能改变。
常数较大：相比于快速排序，堆排序的常数因子较大，速度稍慢。
代码示例：
function heapSort(arr: number[]): number[] {
const heapify = (arr: number[], length: number, i: number) => {
let largest = i;
const left = 2 * i + 1;
const right = 2 * i + 2;
if (left < length && arr[left] > arr[largest]) {
largest = left;
}
if (right < length && arr[right] > arr[largest]) {
largest = right;
}
if (largest !== i) {
[arr[i], arr[largest]] = [arr[largest], arr[i]];
heapify(arr, length, largest);
}
};
const length = arr.length;
for (let i = Math.floor(length / 2) - 1; i >= 0; i--) {
heapify(arr, length, i);
}
for (let i = length - 1; i > 0; i--) {
[arr[0], arr[i]] = [arr[i], arr[0]];
heapify(arr, i, 0);
}
return arr;
}使用场景：
数据量大，且不要求稳定性的排序场景中使用。
1.8. 桶排序（Bucket Sort）
桶排序将数组划分为若干个桶，然后对每个桶内部进行排序，最后合并所有桶中的元素。
优点：
时间复杂度：在最佳情况下，时间复杂度可以达到 O(n + k)，其中 k 是桶的数量。
适合数据分布均匀的场景：能够利用数据的特性提高排序效率。
缺点：
需要额外空间：由于需要存储桶，空间复杂度较高。
不适用于数据分布不均匀的场景：如果数据分布极端，可能退化为 O(n²)。
代码示例：
function bucketSort(arr: number[], bucketsize = 5): number[] {
if (arr.length === 0) return arr;
const min = Math.min(...arr);
const max = Math.max(...arr);
const buckets = Array.from({ length: Math.floor((max - min) / bucketsize) + 1 }, () => []);
arr.forEach((num) => {
const index = Math.floor((num - min) / bucketsize);
buckets[index].push(num);
});
return buckets.reduce((acc, bucket) => acc.concat(bucket.sort((a, b) => a - b)), []);
}使用场景：
适用于已知数据范围且分布较为均匀的场景，如成绩排序。
1.9. 计数排序（Counting Sort）
计数排序适用于整数排序，它通过统计数组中元素的出现次数来实现排序。
优点：
时间复杂度为 O(n + k)：适用于小范围整数的排序。
稳定排序：相同元素的相对顺序保持不变。
缺点：
受数据范围限制：当数据范围很大时，空间复杂度较高。
只能用于整数排序：无法直接对浮点数等进行排序。
代码示例：
function countingSort(arr: number[]): number[] {
const max = Math.max(...arr);
const count = new Array(max + 1).fill(0);
arr.forEach(num => count[num]++);
const result: number[] = [];
count.forEach((num, index) => {
while (num > 0) {
result.push(index);
num--;
}
});
return result;
}使用场景：
适用于数据范围较小、重复数据较多的场景，如考试成绩、年龄等。
1.10. 基数排序（Radix Sort）
基数排序将数据按位（个位、十位等）进行多次排序，通常使用稳定的排序算法，如计数排序作为子过程。
优点：
时间复杂度为 O(d * (n + k))，d 是数字位数，k 是基数，适合大规模数字的排序。
稳定排序：每次子排序都使用稳定排序，保证最终结果的稳定性。
缺点：
受数据类型限制：通常只能用于整数和定长字符串的排序。
空间复杂度较高：需要额外空间存储中间结果。
代码示例：
function radixSort(arr: number[]): number[] {
const getMax = (arr: number[]): number => Math.max(...arr);
const getDigit = (num: number, place: number) => Math.floor(Math.abs(num) / Math.pow(10, place)) % 10;
const countingSortByDigit = (arr: number[], place: number): number[] => {
const count = Array(10).fill(0);
const output = Array(arr.length);
arr.forEach(num => {
const digit = getDigit(num, place);
count[digit]++;
});
for (let i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
for (let i = arr.length - 1; i >= 0; i--) {
const digit = getDigit(arr[i], place);
output[--count[digit]] = arr[i];
}
return output;
};
const max = getMax(arr);
let place = 0;
while (Math.floor(max / Math.pow(10, place)) > 0) {
arr = countingSortByDigit(arr, place);
place++;
}
return arr;
}使用场景：
适用于大规模且定长的数据，如身份证号、电话号码等。
2. 查找算法
2.1. 二分查找（Binary Search）
二分查找是一种高效的查找算法，前提是数组必须有序。每次将查找范围减半，从而快速找到目标元素的位置。
优点：
时间复杂度低：O(log n)，查找速度非常快。
适合大规模数据：对于大规模有序数据，查找效率高。
缺点：
仅适用于有序数据：数组必须是有序的，否则无法使用。
插入与删除复杂：插入或删除元素需要移动大量数据，时间复杂度为 O(n)。
代码示例：
function binarySearch(arr: number[], target: number): number {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] === target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1; // 未找到
}使用场景：
查找有序数据：适用于静态有序数据集的高效查找。
查找频繁的场景：如字典查找、数据库索引等。
2.2. 线性查找（Linear Search）
线性查找是一种最基本的查找算法，从数组的第一个元素开始，依次与目标值进行比较，直到找到目标元素或遍历完整个数组。
优点：
简单易实现：不需要数据有序，任何情况下都能使用。
适用于小规模数据：当数据量较小时，线性查找可以很容易实现。
缺点：
时间复杂度高：最坏情况的时间复杂度为 O(n)。
效率低：特别是对于大规模数据，查找效率较低。
代码示例：
function linearSearch(arr: number[], target: number): number {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) {
return i;
}
}
return -1; // 未找到
}使用场景：
小规模数据查找：适用于数据量较小且无序的数据集。
数据不频繁查找：数据变化频繁的场景中可以直接使用。
2.3. 插值查找（Interpolation Search）
插值查找是二分查找的改进版，基于目标值在数组中的位置比例来计算查找点。适合用于元素值分布较为均匀的有序数组。
优点：
平均性能优于二分查找：当数据分布均匀时，时间复杂度为 O(log log n)。
高效查找：比二分查找更适合数据范围已知、分布均匀的场景。
缺点：
仅适用于有序且均匀分布的数据：数据分布不均时，最坏情况退化为 O(n)。
插入与删除复杂：和二分查找类似，插入或删除的代价较高。
代码示例：
function interpolationSearch(arr: number[], target: number): number {
let low = 0;
let high = arr.length - 1;
while (low <= high && target >= arr[low] && target <= arr[high]) {
if (low === high) {
if (arr[low] === target) return low;
return -1;
}
const pos = low + Math.floor(((target - arr[low]) * (high - low)) / (arr[high] - arr[low]));
if (arr[pos] === target) return pos;
if (arr[pos] < target) low = pos + 1;
else high = pos - 1;
}
return -1; // 未找到
}使用场景：
大规模且均匀分布的数据集：例如价格列表、自然数序列等。
2.4. 跳表查找（Skip List Search）
跳表是一种用于有序链表的查找算法，利用“多级链表”结构加快查找速度，每层链表存储比上一层链表更多的元素，以实现快速定位。
优点：
支持动态增删操作：相比二分查找，跳表可以在 O(log n) 时间内完成插入、删除和查找操作。
高效查找：在保持链表结构的前提下，可以进行较为快速的查找。
缺点：
空间复杂度较高：为了加速查找，需要额外存储多层链表，占用更多空间。
代码示例：
class SkipListNode {
constructor(public value: number, public next: SkipListNode[] = []) {}
}
class SkipList {
private maxLevel = 16; // 跳表最大层数
private head = new SkipListNode(-1, Array(this.maxLevel).fill(null));
search(target: number): SkipListNode | null {
let current = this.head;
for (let level = this.maxLevel - 1; level >= 0; level--) {
while (current.next[level] && current.next[level].value < target) {
current = current.next[level];
}
}
current = current.next[0];
return current && current.value === target ? current : null;
}
}使用场景：
动态数据集：如频繁插入、删除元素的有序链表。
适用于实现动态数据库索引或缓存系统。
2.5. 二叉查找树（Binary Search Tree, BST）
二叉查找树是一种每个节点都有两个子节点的数据结构，左子节点值小于根节点，右子节点值大于根节点。通过递归方式查找目标元素。
优点：
支持动态增删操作：查找、插入、删除操作的平均时间复杂度为 O(log n)。
适用于动态有序数据：可以高效地插入、删除数据，并保持数据有序。
缺点：
最坏情况退化为链表：当树的结构不平衡时，最坏情况时间复杂度为 O(n)。
需要平衡操作：需要结合平衡机制（如 AVL 树或红黑树）以保持性能稳定。
代码示例：
class TreeNode {
constructor(public value: number, public left: TreeNode | null = null, public right: TreeNode | null = null) {}
}
function searchBST(root: TreeNode | null, target: number): TreeNode | null {
if (!root || root.value === target) return root;
if (target < root.value) return searchBST(root.left, target);
return searchBST(root.right, target);
}使用场景：
动态数据集：适合频繁插入、删除的有序数据集，如自平衡二叉树可用于数据库或文件系统索引。
2.6. 哈希查找（Hash Search）
哈希查找通过哈希函数将数据映射到表中的一个位置，以常数时间 O(1) 完成查找操作。
优点：
时间复杂度极低：平均查找时间复杂度为 O(1)。
支持动态增删：哈希表允许快速的插入和删除操作。
缺点：
受哈希函数的影响：如果哈希函数设计不当，会产生大量冲突，最坏情况时间复杂度为 O(n)。
不能保证数据顺序：哈希表无法进行有序查找。
代码示例：
class HashTable {
private table: any[];
constructor(size: number) {
this.table = new Array(size);
}
hash(key: string, size: number): number {
let hash = 0;
for (let i = 0; i < key.length; i++) {
hash += key.charCodeAt(i);
}
return hash % size;
}
search(key: string): any {
const index = this.hash(key, this.table.length);
return this.table[index];
}
insert(key: string, value: any) {
const index = this.hash(key, this.table.length);
this.table[index] = value;
}
}使用场景：
查找频繁的场景：如缓存、数据库索引等需要高效查找的场景。
动态数据集合：适用于对数据增删要求较高的系统。
2.7. B+树查找（B+ Tree Search）
B+树是一种自平衡树结构，适用于数据库和文件系统中的数据查找，每个节点包含多个关键字，叶子节点按顺序排列。
优点：
适合磁盘存储：B+树的扇出较高，减少了树的高度，适合存储大量数据，查找时间复杂度为 O(log n)。
有序查找：叶子节点按顺序排列，便于区间查找。
缺点：
实现复杂：相比二叉树，B+树的实现和维护复杂度更高。
代码示例：
B+树的实现较为复杂，这里省略代码，通常作为数据库的核心数据结构。
使用场景：
数据库和文件系统：B+树广泛应用于数据库索引和大规模文件存储。
3. 递归算法
递归是指函数调用自身来解决问题的编程方式。通常用于分解复杂问题，将其化简为更小的同类问题。
优点：
代码简洁：对于具备递归结构的问题，递归实现通常非常简洁。
易于解决分治问题：递归非常适合解决分治问题。
缺点：
效率问题：递归可能导致重复计算，导致时间复杂度上升。
栈空间有限：过深的递归可能导致栈溢出。
代码示例：
function fibonacci(n: number): number {
if (n <= 1) return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}使用场景：
分治问题：如归并排序、快速排序、汉诺塔问题等。
树形结构：如二叉树遍历、图的深度优先搜索等。
4. 贪心算法（Greedy Algorithm）
贪心算法通过每一步选择当前最优解来期望得到全局最优解，适用于具有贪心选择性质的问题。
优点：
实现简单：每一步选择当前最优解，算法逻辑简单。
局部最优：对某些问题，贪心算法能够快速获得全局最优解。
缺点：
不能保证全局最优解：贪心算法不适用于所有问题，容易得到局部最优而非全局最优。
适用范围有限：只能用于某些特定问题。
代码示例：
function minCoins(coins: number[], amount: number): number {
coins.sort((a, b) => b - a); // 从大到小排序
let count = 0;
for (let coin of coins) {
if (amount === 0) break;
count += Math.floor(amount / coin);
amount %= coin;
}
return amount === 0 ? count : -1; // 如果无法凑齐返回 -1
}使用场景：
活动选择问题：选择不冲突的最大活动数。
最小生成树问题：如 Prim 算法和 Kruskal 算法。
背包问题：在可分割的物品条件下，使用贪心算法解决背包问题。
5. 回溯算法（Backtracking Algorithm）
回溯算法通过在解空间中逐步构建解，遇到不满足条件的部分时回退，尝试其他可能的路径，直到找到所有解或满足条件的最优解。适用于解决组合、排列、子集等问题。
优点：
系统性搜索：回溯算法能够全面探索解空间，保证找到所有解或可能存在的最优解。
解决复杂问题：适合用于解决需要枚举所有可能解的复杂问题，如数独、八皇后等。
缺点：
效率较低：由于需要遍历所有可能的解，回溯算法在大规模问题上可能效率不高，容易出现指数级时间复杂度。
存储消耗：回溯过程通常会用递归来保存中间状态，可能消耗大量内存。
代码示例（八皇后问题）：
在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
const N: number = 8;
let result: string[][] = [];
function solveNQueens(): string[][] {
let board: string[][] = Array.from({ length: N }, () => Array(N).fill('.'));
backtrack(board, 0);
return result;
}
function backtrack(board: string[][], row: number): void {
// 如果已经放置了 N 个皇后，将当前棋盘的状态加入结果集
if (row === N) {
result.push(board.map(r => r.join('')));
return;
}
// 遍历当前行的每一列，尝试放置皇后
for (let col = 0; col < N; col++) {
if (!isValid(board, row, col)) continue; // 如果当前位置不合法，跳过
board[row][col] = 'Q'; // 放置皇后
backtrack(board, row + 1); // 递归处理下一行
board[row][col] = '.'; // 回溯，移除皇后
}
}
// 检查是否可以在 board[row][col] 放置皇后
function isValid(board: string[][], row: number, col: number): boolean {
// 检查同列是否有皇后
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;
}
// 调用函数并输出结果
console.log(solveNQueens());使用场景：
八皇后问题：在 8×8 的棋盘上放置 8 个皇后，使它们互不攻击。
数独问题：在 9×9 的数独棋盘上填入数字，满足行、列和小九宫格的规则。
组合问题：如求解数组的所有子集、排列组合等。
6. 动态规划（Dynamic Programming）
动态规划是一种优化算法，适用于求解具有重叠子问题和最优子结构性质的问题。通过将问题分解为更小的子问题，逐步解决并存储每个子问题的结果，以避免重复计算。
优点：
解决重叠子问题：通过保存子问题的解，减少了重复计算，提升了算法效率。
时间复杂度低：相对于递归算法，动态规划可以将指数时间复杂度降低到多项式时间。
缺点：
空间复杂度较高：由于需要存储子问题的解，可能会消耗较多的存储空间。
不适合所有问题：动态规划只能解决具有最优子结构和重叠子问题性质的问题。
使用场景：
最优子结构和重叠子问题：动态规划适用于具有这两个性质的问题，如最短路径问题、最优序列问题等。
资源分配：常用于解决背包问题、资源调度等与资源分配相关的问题。
字符串处理：编辑距离、最长公共子序列等与字符串匹配相关的问题。
6.1. 斐波那契数列（Fibonacci Sequence）
问题描述：给定一个整数 n，求斐波那契数列的第 n 项。
递推关系： F(n)=F(n−1)+F(n−2)
初始条件：F(0)=0,F(1)=1
代码示例：
function fibonacci(n: number): number {
if (n <= 1) return n;
const dp = [0, 1];
for (let i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}时间复杂度：O(n)
空间复杂度：O(n)
6.2. 最长公共子序列（Longest Common Subsequence, LCS）
问题描述：给定两个字符串 str1 和 str2，求它们的最长公共子序列的长度。
递推关系：
当 str1[i]==str2[j] 时，LCS(i, j) = LCS(i-1, j-1) + 1
否则，LCS(i, j) = max(LCS(i-1, j), LCS(i, j-1))
代码示例：
function longestCommonSubsequence(str1: string, str2: string): number {
const m = str1.length;
const n = str2.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 (str1[i - 1] === str2[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];
}时间复杂度：O(m * n)
空间复杂度：O(m * n)
6.3. 背包问题（Knapsack Problem）
问题描述：给定 n 件物品，每件物品有重量和价值，背包的最大承重为 W，求如何选择物品使得背包内的物品总价值最大。
递推关系：
当物品 i 不放入背包时：dp[i][w]=dp[i−1][w]
当物品 i 放入背包时：dp[i][w]=max(dp[i−1][w],dp[i−1][w−weight[i]]+value[i])
代码示例：
function knapsack(weights: number[], values: number[], W: number): number {
const n = weights.length;
const dp = Array.from({ length: n + 1 }, () => Array(W + 1).fill(0));
for (let i = 1; i <= n; i++) {
for (let w = 1; w <= W; 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][W];
}时间复杂度：O(n * W)
空间复杂度：O(n * W)
6.4. 硬币找零问题（Coin Change Problem）
问题描述：给定硬币面值数组 coins，和一个目标金额 amount，求最少需要多少个硬币凑成该金额。如果无法凑成，返回 -1。
递推关系：dp[i]=min(dp[i],dp[i−coin]+1)，其中 coin 是当前硬币面值。
代码示例：
function coinChange(coins: number[], amount: number): number {
const dp = Array(amount + 1).fill(Infinity);
dp[0] = 0;
for (let i = 1; i <= amount; i++) {
for (const coin of coins) {
if (i - coin >= 0) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
return dp[amount] === Infinity ? -1 : dp[amount];
}时间复杂度：O(amount * coins.length)
空间复杂度：O(amount)
6.5. 编辑距离（Edit Distance）
问题描述：给定两个字符串 str1 和 str2，计算将 str1 转换为 str2 所需的最少编辑操作次数。操作包括插入、删除和替换。
递推关系：
当 str1[i]==str2[j] 时，dp[i][j] = dp[i-1][j-1]
否则，dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
代码示例：
function minDistance(str1: string, str2: string): number {
const m = str1.length;
const n = str2.length;
const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
for (let i = 0; i <= m; i++) dp[i][0] = i;
for (let j = 0; j <= n; j++) dp[0][j] = j;
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (str1[i - 1] === str2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = 1 + Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]);
}
}
}
return dp[m][n];
}时间复杂度：O(m * n)
空间复杂度：O(m * n)
7. 补充资料
LeetCode: https://leetcode.com/
LeetCode: 力扣 (LeetCode) 全球极客挚爱的技术成长平台
力扣加加: https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution
Hello 算法: Hello 算法
LeetCode 算法动画: https://github.com/MisterBooo/LeetCodeAnimation
算法可视化: 通过动画可视化数据结构和算法<br> – VisuAlgo
动画算法: https://www.donghuauanfa.com/portal
暂无评论内容