算法分类笔记

排序算法

冒泡排序、选择排序、插入排序、归并排序、快速排序、堆排序等

排序算法有很多种，根据它们的特性和适用场景可以分为几大类。

比较排序算法

1. 冒泡排序 (Bubble Sort)

   • 描述：重复地遍历列表，比较相邻的元素并交换它们，如果它们的顺序错误。遍历列表直到没有需要交换的元素为止。
   • 时间复杂度：O(n^2)
   • 空间复杂度：O(1)

2. 选择排序 (Selection Sort)

   • 描述：每次从未排序部分中选出最小（或最大）的元素，将其放在已排序部分的末尾。
   • 时间复杂度：O(n^2)
   • 空间复杂度：O(1)

3. 插入排序 (Insertion Sort)

   • 描述：构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
   • 时间复杂度：O(n^2)
   • 空间复杂度：O(1)

4. 归并排序 (Merge Sort)

   • 描述：使用分治法将数组分成两个子数组，分别排序，然后合并这两个子数组以得到最终的排序结果。
   • 时间复杂度：O(n log n)
   • 空间复杂度：O(n)

5. 快速排序 (Quick Sort)

   • 描述：选择一个基准元素，将数组分为小于基准和大于基准的两部分，递归地对这两部分进行排序。
   • 时间复杂度：O(n log n) 平均，O(n^2) 最坏
   • 空间复杂度：O(log n) 平均，O(n) 最坏

6. 堆排序 (Heap Sort)

   • 描述：利用堆这种数据结构来进行排序，首先构建一个最大堆，然后逐一取出堆顶元素并调整堆结构。
   • 时间复杂度：O(n log n)
   • 空间复杂度：O(1)

非比较排序算法

1. 计数排序 (Counting Sort)

   • 描述：适用于整数排序，通过计数数组记录每个数出现的次数，然后按照计数结果将元素依次放入原数组。
   • 时间复杂度：O(n + k) 其中 k 是数组中最大值减最小值的范围
   • 空间复杂度：O(k)

2. 桶排序 (Bucket Sort)

   • 描述：将数组元素分到有限数量的桶中，对每个桶内的元素进行排序，然后依次合并桶中的元素。
   • 时间复杂度：O(n + k) 其中 k 是桶的数量
   • 空间复杂度：O(n + k)

3. 基数排序 (Radix Sort)

   • 描述：按位排序，首先根据最低有效位对数组进行排序，然后依次对每一个有效位进行排序。
   • 时间复杂度：O(n * k) 其中 k 是数字的位数
   • 空间复杂度：O(n + k)

稳定性和适用场景

1. 稳定排序算法（保持相同元素的相对顺序不变）：

   • 冒泡排序
   • 插入排序
   • 归并排序
   • 计数排序
   • 桶排序
   • 基数排序

2. 不稳定排序算法（不保证相同元素的相对顺序）：

   • 选择排序
   • 快速排序
   • 堆排序

示例代码

**冒泡排序 (Bubble Sort)**：

function bubbleSort(arr) {
    let n = arr.length;
    for (let i = 0; i < n - 1; i++) {
        for (let j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; // 交换元素
            }
        }
    }
    return arr;
}

**选择排序 (Selection Sort)**：

function selectionSort(arr) {
    let n = arr.length;
    for (let i = 0; i < n - 1; i++) {
        let minIndex = i;
        for (let j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]; // 交换元素
    }
    return arr;
}

**插入排序 (Insertion Sort)**：

function insertionSort(arr) {
    let n = arr.length;
    for (let i = 1; i < n; i++) {
        let key = arr[i];
        let j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
    return arr;
}

**归并排序 (Merge Sort)**：

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]);
            i++;
        } else {
            result.push(right[j]);
            j++;
        }
    }
    return result.concat(left.slice(i)).concat(right.slice(j));
}

**快速排序 (Quick Sort)**：

function quickSort(arr) {
    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);
    return [...quickSort(left), pivot, ...quickSort(right)];
}

**堆排序 (Heap Sort)**：

function heapSort(arr) {
    let n = arr.length;

    // 建堆
    for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }

    // 一个个取出元素
    for (let i = n - 1; i > 0; i--) {
        [arr[0], arr[i]] = [arr[i], arr[0]]; // 交换
        heapify(arr, i, 0);
    }
    return arr;
}

function heapify(arr, n, i) {
    let largest = i; // 初始化最大值为根节点
    let left = 2 * i + 1; // 左子节点
    let right = 2 * i + 2; // 右子节点

    // 如果左子节点大于根节点
    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }

    // 如果右子节点大于最大值
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }

    // 如果最大值不是根节点
    if (largest !== i) {
        [arr[i], arr[largest]] = [arr[largest], arr[i]]; // 交换
        heapify(arr, n, largest); // 递归堆化子树
    }
}

总结

通过以上分类和示例代码，你可以了解各种排序算法的特点、时间复杂度、空间复杂度以及适用场景。在学习和使用这些排序算法时，根据具体需求选择合适的算法是非常重要的。

搜索算法

二分搜索、广度优先搜索（BFS）、深度优先搜索（DFS）等。

搜索算法用于在数据结构中查找特定元素或满足特定条件的元素。根据其特性和适用场景，可以将搜索算法分类如下：

基本搜索算法

1. 线性搜索 (Linear Search)

   • 描述：逐一检查每个元素，直到找到目标元素或遍历完整个数据结构。
   • 时间复杂度：O(n)
   • 空间复杂度：O(1)
   • 应用场景：适用于小规模数据或无序数据。

2. 二分搜索 (Binary Search)

   • 描述：在有序数组中查找目标元素，通过每次将查找范围减半来缩小搜索范围。
   • 时间复杂度：O(log n)
   • 空间复杂度：O(1)
   • 应用场景：适用于大规模有序数组。

深度优先搜索 (DFS) 和广度优先搜索 (BFS)

1. 深度优先搜索 (Depth-First Search, DFS)

   • 描述：从起始节点出发，沿着一个分支深入到不能继续为止，然后回溯并继续搜索其他分支。
   • 时间复杂度：O(V + E) 其中 V 是顶点数，E 是边数
   • 空间复杂度：O(V)
   • 应用场景：用于遍历或搜索图、树结构，解决连通性问题、拓扑排序、路径搜索等。

2. 广度优先搜索 (Breadth-First Search, BFS)

   • 描述：从起始节点出发，逐层遍历邻接节点，直到找到目标节点或遍历完整个图。
   • 时间复杂度：O(V + E)
   • 空间复杂度：O(V)
   • 应用场景：用于最短路径搜索（无权图）、层次遍历、连通性问题等。

最短路径算法

1. Dijkstra算法

   • 描述：用于带权图中找到从起点到其他所有节点的最短路径。
   • 时间复杂度：O(V^2) 使用邻接矩阵，O((V + E) log V) 使用优先队列
   • 空间复杂度：O(V)
   • 应用场景：适用于非负权重图的最短路径搜索。

2. Bellman-Ford算法

   • 描述：用于带权图中找到从起点到其他所有节点的最短路径，允许负权重。
   • 时间复杂度：O(VE)
   • 空间复杂度：O(V)
   • 应用场景：适用于含负权重的图，检测负权重环。

3. Floyd-Warshall算法

   • 描述：用于找到所有节点对之间的最短路径。
   • 时间复杂度：O(V^3)
   • 空间复杂度：O(V^2)
   • 应用场景：适用于密集图，求解所有节点对之间的最短路径。

A* 算法

• 描述：启发式搜索算法，通过估计函数（通常是到目标节点的直线距离）来优先搜索最有希望的路径。
• 时间复杂度：O(b^d) 最坏情况，其中 b 是分支因子，d 是深度
• 空间复杂度：O(b^d)
• 应用场景：用于路径规划、游戏AI等需要找到最优路径的问题。

示例代码

以下是一些常见搜索算法的示例代码：

**线性搜索 (Linear Search)**：

function linearSearch(arr, target) {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) {
            return i; // 找到目标元素，返回其索引
        }
    }
    return -1; // 未找到目标元素
}

**二分搜索 (Binary Search)**：

function binarySearch(arr, target) {
    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; // 未找到目标元素
}

**深度优先搜索 (DFS)**：

function dfs(graph, start) {
    const stack = [start];
    const visited = new Set();
    while (stack.length > 0) {
        const node = stack.pop();
        if (!visited.has(node)) {
            visited.add(node);
            console.log(node); // 处理节点
            const neighbors = graph[node];
            for (const neighbor of neighbors) {
                stack.push(neighbor);
            }
        }
    }
}

**广度优先搜索 (BFS)**：

function bfs(graph, start) {
    const queue = [start];
    const visited = new Set();
    while (queue.length > 0) {
        const node = queue.shift();
        if (!visited.has(node)) {
            visited.add(node);
            console.log(node); // 处理节点
            const neighbors = graph[node];
            for (const neighbor of neighbors) {
                queue.push(neighbor);
            }
        }
    }
}

Dijkstra算法：

function dijkstra(graph, start) {
    const distances = {};
    const visited = new Set();
    const pq = new PriorityQueue();

    // 初始化距离
    for (const vertex in graph) {
        distances[vertex] = Infinity;
    }
    distances[start] = 0;
    pq.enqueue(start, 0);

    while (!pq.isEmpty()) {
        const { element: current } = pq.dequeue();
        visited.add(current);

        for (const neighbor in graph[current]) {
            if (!visited.has(neighbor)) {
                const newDistance = distances[current] + graph[current][neighbor];
                if (newDistance < distances[neighbor]) {
                    distances[neighbor] = newDistance;
                    pq.enqueue(neighbor, newDistance);
                }
            }
        }
    }

    return distances;
}

结合以上分类和示例代码

通过以上分类和示例代码，你可以了解各种搜索算法的特点、时间复杂度、空间复杂度及其适用场景。在学习和使用这些搜索算法时，根据具体需求选择合适的算法是非常重要的。

动态规划

斐波那契数列、最长公共子序列、矩阵相关距离、背包问题等。

动态规划（Dynamic Programming, DP）是一种用于解决最优化问题的算法设计方法，它通过将问题分解成更小的子问题，并将这些子问题的解保存下来，避免重复计算。动态规划适用于那些可以被分解成重叠子问题的问题，通常这些问题具有以下两个性质：

1. 最优子结构（Optimal Substructure）：一个问题的最优解包含其子问题的最优解。
2. 重叠子问题（Overlapping Subproblems）：问题可以被分解成多个重复的子问题，这些子问题会被多次解决。

动态规划的步骤

1. 定义状态：明确状态表示什么，通常是子问题的解。
2. 定义状态转移方程：确定如何通过已解决的子问题来求解当前子问题。
3. 初始化状态：设置边界条件，通常是最小的子问题的解。
4. 计算状态：根据状态转移方程逐步计算出每个状态的值。
5. 返回结果：从计算结果中提取出最终的解。

动态规划常见问题

1. 背包问题 (Knapsack Problem)

   • 描述：给定一组物品，每个物品有重量和价值，给定一个背包容量，求能够装入背包的最大总价值。
   • 时间复杂度：O(n * W) 其中 n 是物品数，W 是背包容量
   • 空间复杂度：O(n * W)

2. 最长公共子序列 (Longest Common Subsequence, LCS)

   • 描述：给定两个字符串，找出它们的最长公共子序列。
   • 时间复杂度：O(m * n) 其中 m 和 n 是两个字符串的长度
   • 空间复杂度：O(m * n)

3. 最长递增子序列 (Longest Increasing Subsequence, LIS)

   • 描述：给定一个整数数组，找出其中的最长递增子序列。
   • 时间复杂度：O(n^2) 或 O(n log n)（使用二分查找优化）
   • 空间复杂度：O(n)

4. 编辑距离 (Edit Distance)

   • 描述：计算将一个字符串转换为另一个字符串所需的最少操作数（插入、删除、替换）。
   • 时间复杂度：O(m * n) 其中 m 和 n 是两个字符串的长度
   • 空间复杂度：O(m * n)

5. 0-1 背包问题 (0-1 Knapsack Problem)

   • 描述：与背包问题类似，但每个物品只能选择一次。
   • 时间复杂度：O(n * W)
   • 空间复杂度：O(n * W)

示例代码

**背包问题 (Knapsack Problem)**：

function knapsack(weights, values, W) {
    let n = weights.length;
    let dp = Array(W + 1).fill(0);

    for (let i = 0; i < n; i++) {
        for (let w = W; w >= weights[i]; w--) {
            dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
        }
    }

    return dp[W];
}

**最长公共子序列 (Longest Common Subsequence, LCS)**：

function longestCommonSubsequence(s1, s2) {
    let m = s1.length, n = s2.length;
    let 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];
}

**最长递增子序列 (Longest Increasing Subsequence, LIS)**：

function lengthOfLIS(nums) {
    if (nums.length === 0) return 0;
    let dp = 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);
}

**编辑距离 (Edit Distance)**：

function minDistance(word1, word2) {
    let m = word1.length, n = word2.length;
    let 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 (word1[i - 1] === word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1;
            }
        }
    }

    return dp[m][n];
}

**0-1 背包问题 (0-1 Knapsack Problem)**：

function knapsack01(weights, values, W) {
    let n = weights.length;
    let 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];
}

总结

动态规划通过将复杂问题分解为更小的子问题，并将子问题的解存储起来，从而避免重复计算，优化了时间复杂度。掌握动态规划的核心思想和常见问题可以帮助解决许多实际问题。在学习动态规划时，理解问题的最优子结构和重叠子问题是关键。

Leetcode题目

LeetCode 53. 最大子数组和

var maxSubArray = function (nums) {
    if (nums.length === 0) return 0;
    
    let dp = new Array(nums.length);
    dp[0] = nums[0];
    let maxSum = nums[0]; // 初始化最大子数组和

    for (let i = 1; i < nums.length; i++) {
        dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]); // 当前最大子数组和
        maxSum = Math.max(maxSum, dp[i]); // 更新最大子数组和
    }

    return maxSum;
};

时间复杂度是 O(n)，空间复杂度是 O(n)，可以进一步优化空间复杂度到 O(1)。

不使用额外的数组，使用变量记录：

var maxSubArray = function (nums) {
    if (nums.length === 0) return 0;
    
    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;
};

时间复杂度是 O(n)，空间复杂度是 O(n)。

LeetCode 70. 爬楼梯

var climbStairs = function (n) {
    if (n === 1) return 1;
    let dp = new Array(n + 1);
    dp[0] = 1;
    dp[1] = 1;
    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
};

LeetCode 120. 三角形最小路径和

求解三角形最小路径和的问题，可以使用动态规划方法。我们从三角形的底部开始，逐层向上进行计算，每一步都选择最小的路径和，最后到达顶点时即为所求。

假设三角形的数据结构如下：

[
     [2],
    [3, 4],
   [6, 5, 7],
  [4, 1, 8, 3]
]

每一层的每个位置的最小路径和可以通过选择其下一层中相邻位置的最小路径和来进行计算。

动态规划实现

我们可以直接在原三角形数组中进行更新，这样可以节省空间复杂度。具体实现如下：

/**
 * @param {number[][]} triangle
 * @return {number}
 */
var minimumTotal = function(triangle) {
    // 从倒数第二层开始向上计算
    for (let row = triangle.length - 2; row >= 0; row--) {
        for (let col = 0; col < triangle[row].length; col++) {
            // 更新当前节点的值为当前节点值加上其下一层相邻节点中的较小值
            triangle[row][col] += Math.min(triangle[row + 1][col], triangle[row + 1][col + 1]);
        }
    }
    // 顶点的值就是最小路径和
    return triangle[0][0];
};

详细解释：

1. 初始化：

   • 无需额外初始化，直接使用传入的 triangle 数组。

2. 从倒数第二层开始向上计算：

   for (let row = triangle.length - 2; row >= 0; row--) {
       for (let col = 0; col < triangle[row].length; col++) {
           triangle[row][col] += Math.min(triangle[row + 1][col], triangle[row + 1][col + 1]);
       }
   }

   • 从倒数第二层开始，逐层向上计算，每个元素更新为其值加上下一层相邻两个元素中的较小值。
   • 这样确保每次更新后的值是从当前元素到最底层的最小路径和。

3. 返回结果：

   return triangle[0][0];

   • 最终，顶点 triangle[0][0] 的值即为从顶到底的最小路径和。

示例：

对于以下三角形：

[
     [2],
    [3, 4],
   [6, 5, 7],
  [4, 1, 8, 3]
]

计算过程如下：

1. 从倒数第二层开始计算：
   • 第三层更新为 [6 + min(4, 1), 5 + min(1, 8), 7 + min(8, 3)] 即 [7, 6, 10]。
2. 第二层更新为 [3 + min(7, 6), 4 + min(6, 10)] 即 [9, 10]。
3. 第一层更新为 [2 + min(9, 10)] 即 [11]。

最终结果是 11，即从顶到底的最小路径和为 11。

LeetCode 198. 打家劫舍

方法一：

var rob = function (nums) {
    if (nums.length == 1) return nums[0];
    
    if (nums.length == 2) return Math.max(nums[0], nums[1]);

    let dp = new Array(nums.length);
    dp[0] = nums[0];
    dp[1] = Math.max(nums[0], nums[1])
    for (let i = 2; i < nums.length; i++) {
        dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
    }
    return dp[nums.length - 1]
};

方法二：

var rob = function(nums) {
    if (nums.length === 0) return 0;
    if (nums.length === 1) return nums[0];
    
    let prev1 = 0;
    let prev2 = 0;
    
    for (let i = 0; i < nums.length; i++) {
        let temp = Math.max(prev1, prev2 + nums[i]);
        prev2 = prev1;
        prev1 = temp;
    }
    
    return prev1;
};

LeetCode 300. 最长递增子序列

LeetCode 322. 零钱兑换

LeetCode 1143. 最长公共子序列

var longestCommonSubsequence = function (text1, text2) {
    let m = text1.length;
    let n = text2.length;

    // 创建二维数组 dp，注意这里要初始化 m+1 行和 n+1 列
    let dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));

    // 注意循环从 1 开始，因为 dp 数组多出来的一行一列是用来处理空字符串的情况的
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            // 注意这里要比较的是 text1[i-1] 和 text2[j-1]
            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]);
            }
        }
    }
    // 返回 dp 数组的右下角元素，即最长公共子序列的长度
    return dp[m][n];
};

贪心算法

活动选择问题、哈夫曼编码、最小生成树等。

贪心算法（Greedy Algorithm）是一种用于解决最优化问题的算法设计方法，它通过逐步选择当前最优的解（即在每一步选择中选择局部最优解），期望通过局部最优解的组合得到全局最优解。贪心算法适用于那些局部最优解可以保证全局最优解的问题。

贪心算法的特点

1. 局部最优选择：在每一步选择中，贪心算法选择当前看起来最优的选项。
2. 全局最优解：通过局部最优选择的集合希望能得到全局最优解。
3. 无回溯：贪心算法在选择时不会回溯，即不会重新考虑之前的选择。

贪心算法的步骤

1. 确定贪心选择性质：找出每一步做出的选择如何影响最终解。
2. 构造贪心策略：确定贪心选择的标准和策略。
3. 证明贪心策略的正确性：验证通过贪心选择得到的解是否最优。
4. 实现算法：根据贪心策略实现算法，处理具体问题。

常见的贪心算法问题

1. 活动选择问题 (Activity Selection Problem)

   • 描述：给定一组活动，每个活动都有一个开始时间和结束时间，选择尽可能多的互不重叠的活动。
   • 贪心策略：每次选择结束时间最早的活动。
   • 时间复杂度：O(n log n)（排序） + O(n)（选择）

2. 最小生成树 (Minimum Spanning Tree, MST)

   • 描述：给定一个加权无向图，找到一个生成树，使得其权重之和最小。
   • 贪心策略：
     • Kruskal算法：每次选择权重最小的边，使用并查集检测是否形成回路。
     • Prim算法：每次选择一个连接到树中节点的权重最小的边。
   • 时间复杂度：
     • Kruskal：O(E log E)（排序边）+ O(E α(V))（并查集操作）
     • Prim：O(E log V)（使用优先队列）

3. 单源最短路径 (Single Source Shortest Path)

   • 描述：在带权图中找到从源节点到所有其他节点的最短路径。
   • 贪心策略：使用Dijkstra算法，通过选择当前最短路径的节点进行扩展。
   • 时间复杂度：O((V + E) log V)（使用优先队列）

4. 霍夫曼编码 (Huffman Coding)

   • 描述：给定字符及其频率，构建一种最优的前缀编码方案。
   • 贪心策略：每次选择两个频率最小的字符合并成一个新字符。
   • 时间复杂度：O(n log n)（使用优先队列）

5. 零钱兑换问题 (Coin Change Problem)

   • 描述：给定不同面额的硬币和一个总金额，找出所需的最少硬币数量。
   • 贪心策略：每次选择面额最大的硬币，直到总金额达到或超过目标。
   • 时间复杂度：O(n)（如果硬币面额是有序的）

示例代码

以下是一些经典贪心算法问题的示例代码：

**活动选择问题 (Activity Selection Problem)**：

function activitySelection(activities) {
    activities.sort((a, b) => a.end - b.end); // 按结束时间排序
    let result = [];
    let lastEndTime = 0;

    for (let activity of activities) {
        if (activity.start >= lastEndTime) {
            result.push(activity);
            lastEndTime = activity.end;
        }
    }

    return result;
}

**Kruskal算法 (最小生成树)**：

function kruskal(vertices, edges) {
    edges.sort((a, b) => a.weight - b.weight); // 按边权重排序
    const parent = Array(vertices).fill(null).map((_, i) => i);
    const find = (x) => {
        if (parent[x] !== x) parent[x] = find(parent[x]);
        return parent[x];
    };
    const union = (x, y) => parent[find(x)] = find(y);

    const mst = [];
    for (const edge of edges) {
        if (find(edge.from) !== find(edge.to)) {
            union(edge.from, edge.to);
            mst.push(edge);
        }
    }

    return mst;
}

**Prim算法 (最小生成树)**：

function prim(vertices, edges) {
    const adj = Array.from({ length: vertices }, () => []);
    for (const { from, to, weight } of edges) {
        adj[from].push({ to, weight });
        adj[to].push({ from, weight });
    }

    const inMST = Array(vertices).fill(false);
    const minEdge = Array(vertices).fill(Infinity);
    minEdge[0] = 0;

    let result = 0;
    let pq = [[0, 0]]; // [weight, vertex]

    while (pq.length > 0) {
        const [weight, u] = pq.shift();
        if (inMST[u]) continue;
        inMST[u] = true;
        result += weight;

        for (const { to, weight } of adj[u]) {
            if (!inMST[to] && weight < minEdge[to]) {
                minEdge[to] = weight;
                pq.push([weight, to]);
            }
        }
    }

    return result;
}

**霍夫曼编码 (Huffman Coding)**：

function huffmanCoding(freq) {
    const pq = Object.entries(freq).map(([char, freq]) => ({ char, freq }));
    pq.sort((a, b) => a.freq - b.freq);

    while (pq.length > 1) {
        const left = pq.shift();
        const right = pq.shift();
        const newNode = {
            char: left.char + right.char,
            freq: left.freq + right.freq,
            left,
            right
        };
        pq.push(newNode);
        pq.sort((a, b) => a.freq - b.freq);
    }

    const root = pq[0];
    const code = {};
    function dfs(node, path) {
        if (!node.left && !node.right) {
            code[node.char] = path;
        } else {
            if (node.left) dfs(node.left, path + '0');
            if (node.right) dfs(node.right, path + '1');
        }
    }
    dfs(root, '');

    return code;
}

**零钱兑换问题 (Coin Change Problem)**：

function coinChange(coins, amount) {
    let dp = Array(amount + 1).fill(Infinity);
    dp[0] = 0;

    for (let i = 1; i <= amount; i++) {
        for (let coin of coins) {
            if (i >= coin) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }

    return dp[amount] === Infinity ? -1 : dp[amount];
}

总结

贪心算法通过局部最优选择来尝试构造全局最优解，适用于那些能够通过贪心策略得到最优解的问题。在使用贪心算法时，需要仔细证明贪心策略的正确性，以确保其能够得到最优解。

分治算法

归并排序、快速排序、Karatsuba乘法等。

分治算法（Divide and Conquer）是一种解决问题的算法设计策略，它通过将一个大问题分解成多个较小的子问题，递归地解决这些子问题，然后将它们的解合并起来以得到原问题的解。分治算法适用于那些可以被分解成更小、相似子问题的问题。

分治算法的步骤

1. 分解：将原问题分解为若干个规模较小的子问题，子问题的形式与原问题相似。
2. 解决：递归地解决这些子问题。如果子问题的规模足够小，则直接求解。
3. 合并：将子问题的解合并成原问题的解。

常见的分治算法问题

1. 归并排序 (Merge Sort)

   • 描述：将一个数组分解成若干个子数组，分别排序后再合并成一个有序数组。
   • 时间复杂度：O(n log n)
   • 空间复杂度：O(n)
   • 合并：将两个已排序的数组合并成一个排序数组。

2. 快速排序 (Quick Sort)

   • 描述：通过选择一个”基准”元素，将数组划分成两个部分，其中一部分元素小于基准，另一部分大于基准，然后递归地排序两个部分。
   • 时间复杂度：O(n log n) 平均情况，O(n^2) 最坏情况
   • 空间复杂度：O(log n) 平均情况，O(n) 最坏情况
   • 划分：将数组分成两个子数组，使得一个子数组中的元素都不大于基准，另一个子数组中的元素都不小于基准。

3. 二分查找 (Binary Search)

   • 描述：在一个有序数组中查找一个特定元素，通过每次将搜索范围缩小一半。
   • 时间复杂度：O(log n)
   • 空间复杂度：O(1)
   • 分解：每次将数组分成两个部分，查找目标元素是否在其中一个部分。

4. 最大子数组和 (Maximum Subarray Sum)

   • 描述：给定一个整数数组，找到具有最大和的连续子数组。
   • 时间复杂度：O(n)
   • 空间复杂度：O(1)
   • 分解：将数组分成左右两部分，分别求解最大子数组和，然后合并两部分的结果。

5. 最近点对问题 (Closest Pair of Points)

   • 描述：给定一组点，找到距离最近的一对点。
   • 时间复杂度：O(n log n)
   • 空间复杂度：O(n)
   • 分解：将点集按照坐标排序，分成左右两部分，递归求解，并合并两部分的解。

6. 矩阵乘法 (Matrix Multiplication)

   • 描述：计算两个矩阵的乘积。
   • 时间复杂度：O(n^3)（普通算法），O(n^log2(7)) 斯特拉森算法
   • 空间复杂度：O(n^2)
   • 分解：将矩阵分解成更小的矩阵块，递归计算并合并结果。

示例代码

以下是一些经典分治算法问题的示例代码：

**归并排序 (Merge Sort)**：

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) {
    let result = [], 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));
}

**快速排序 (Quick Sort)**：

function quickSort(arr, low = 0, high = arr.length - 1) {
    if (low < high) {
        const pivotIndex = partition(arr, low, high);
        quickSort(arr, low, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, high);
    }
}

function partition(arr, low, high) {
    const pivot = arr[high];
    let i = low;
    for (let j = low; j < high; j++) {
        if (arr[j] < pivot) {
            [arr[i], arr[j]] = [arr[j], arr[i]];
            i++;
        }
    }
    [arr[i], arr[high]] = [arr[high], arr[i]];
    return i;
}

**二分查找 (Binary Search)**：

function binarySearch(arr, target) {
    let low = 0, high = arr.length - 1;

    while (low <= high) {
        const mid = Math.floor((low + high) / 2);
        if (arr[mid] === target) {
            return mid;
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    return -1; // 未找到
}

**最大子数组和 (Maximum Subarray Sum)**：

function maxSubArraySum(arr) {
    function maxCrossingSum(arr, low, mid, high) {
        let leftSum = -Infinity, rightSum = -Infinity;
        let sum = 0;

        for (let i = mid; i >= low; i--) {
            sum += arr[i];
            if (sum > leftSum) leftSum = sum;
        }

        sum = 0;
        for (let i = mid + 1; i <= high; i++) {
            sum += arr[i];
            if (sum > rightSum) rightSum = sum;
        }

        return leftSum + rightSum;
    }

    function divideAndConquer(arr, low, high) {
        if (low === high) return arr[low];

        const mid = Math.floor((low + high) / 2);
        return Math.max(
            divideAndConquer(arr, low, mid),
            divideAndConquer(arr, mid + 1, high),
            maxCrossingSum(arr, low, mid, high)
        );
    }

    return divideAndConquer(arr, 0, arr.length - 1);
}

**最近点对问题 (Closest Pair of Points)**：

function closestPair(points) {
    points.sort((a, b) => a[0] - b[0]);

    function distance(p1, p2) {
        return Math.sqrt(Math.pow(p1[0] - p2[0], 2) + Math.pow(p1[1] - p2[1], 2));
    }

    function closestPairRec(points) {
        if (points.length <= 3) {
            return points.reduce((minDist, p1, i) => {
                return points.slice(i + 1).reduce((minDist, p2) => Math.min(minDist, distance(p1, p2)), minDist);
            }, Infinity);
        }

        const mid = Math.floor(points.length / 2);
        const left = points.slice(0, mid);
        const right = points.slice(mid);

        const minLeft = closestPairRec(left);
        const minRight = closestPairRec(right);
        const minDist = Math.min(minLeft, minRight);

        const strip = points.filter(p => Math.abs(p[0] - points[mid][0]) < minDist);
        strip.sort((a, b) => a[1] - b[1]);

        let minStripDist = minDist;
        for (let i = 0; i < strip.length; i++) {
            for (let j = i + 1; j < strip.length && (strip[j][1] - strip[i][1]) < minDist; j++) {
                minStripDist = Math.min(minStripDist, distance(strip[i], strip[j]));
            }
        }

        return minStripDist;
    }

    return closestPairRec(points);
}

总结

分治算法通过将问题分解成更小的子问题，递归解决这些子问题并合并它们的解，来解决复杂问题。它的关键在于能够有效地分解问题、递归解决和合并结果。在学习和使用分治算法时，理解如何有效地分解问题和合并结果是非常重要的。

图算法

Dijkstra算法、Bellman-Ford算法、Floyd-Warshall算法等。

图算法是处理图结构数据的算法。图是由顶点（节点）和边（连接顶点的线）组成的，图算法用于解决各种与图有关的问题，如最短路径、最小生成树、网络流等。下面是一些常见的图算法及其说明：

常见图算法

1. 深度优先搜索 (Depth-First Search, DFS)

   • 描述：一种遍历图的算法，通过尽可能深地访问图的分支。
   • 应用：
     • 发现连通分量
     • 检测图中的环
     • 拓扑排序
   • 时间复杂度：O(V + E) 其中 V 是顶点数，E 是边数
   • 代码示例：

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

2. 广度优先搜索 (Breadth-First Search, BFS)

   • 描述：一种遍历图的算法，通过逐层访问图的节点。
   • 应用：
     • 最短路径（无权图）
     • 连通分量
     • 计算最短路径的层次
   • 时间复杂度：O(V + E)
   • 代码示例：

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

3. 最短路径算法

   • Dijkstra 算法

     • 描述：用于计算带权图中从一个源点到所有其他顶点的最短路径。
     • 时间复杂度：O((V + E) log V)（使用优先队列）
     • 空间复杂度：O(V)
     • 代码示例：

       function dijkstra(graph, start) {
           const dist = {};
           const pq = new PriorityQueue((a, b) => dist[a] < dist[b]);
           for (const node in graph) {
               dist[node] = Infinity;
           }
           dist[start] = 0;
           pq.enqueue(start);
        
           while (!pq.isEmpty()) {
               const u = pq.dequeue();
               for (const [v, weight] of graph[u]) {
                   const alt = dist[u] + weight;
                   if (alt < dist[v]) {
                       dist[v] = alt;
                       pq.enqueue(v);
                   }
               }
           }
           return dist;
       }

   • Bellman-Ford 算法

     • 描述：可以处理带负权边的图，检测负权回路。
     • 时间复杂度：O(V * E)
     • 空间复杂度：O(V)
     • 代码示例：

       function bellmanFord(graph, start) {
           const dist = {};
           const edges = [];
           for (const u in graph) {
               for (const [v, weight] of graph[u]) {
                   edges.push([u, v, weight]);
               }
           }
        
           for (const node in graph) {
               dist[node] = Infinity;
           }
           dist[start] = 0;
        
           for (let i = 1; i < Object.keys(graph).length; i++) {
               for (const [u, v, weight] of edges) {
                   if (dist[u] + weight < dist[v]) {
                       dist[v] = dist[u] + weight;
                   }
               }
           }
        
           // Check for negative-weight cycles
           for (const [u, v, weight] of edges) {
               if (dist[u] + weight < dist[v]) {
                   throw new Error("Graph contains a negative-weight cycle");
               }
           }
        
           return dist;
       }

4. 最小生成树算法

   • Kruskal 算法

     • 描述：用于计算无向图的最小生成树，通过逐步选择最小权重边来构建生成树。
     • 时间复杂度：O(E log E)（排序边） + O(E α(V))（并查集操作）
     • 代码示例：

       function kruskal(vertices, edges) {
           edges.sort((a, b) => a.weight - b.weight);
           const parent = Array(vertices).fill(null).map((_, i) => i);
           const find = (x) => {
               if (parent[x] !== x) parent[x] = find(parent[x]);
               return parent[x];
           };
           const union = (x, y) => parent[find(x)] = find(y);
        
           const mst = [];
           for (const edge of edges) {
               if (find(edge.from) !== find(edge.to)) {
                   union(edge.from, edge.to);
                   mst.push(edge);
               }
           }
        
           return mst;
       }

   • Prim 算法

     • 描述：通过逐步选择最小权重的边，扩展生成树。
     • 时间复杂度：O(E log V)（使用优先队列）
     • 代码示例：

       function prim(vertices, edges) {
           const adj = Array.from({ length: vertices }, () => []);
           for (const { from, to, weight } of edges) {
               adj[from].push({ to, weight });
               adj[to].push({ from, weight });
           }
        
           const inMST = Array(vertices).fill(false);
           const minEdge = Array(vertices).fill(Infinity);
           minEdge[0] = 0;
        
           let result = 0;
           let pq = new PriorityQueue((a, b) => minEdge[a] < minEdge[b]);
        
           while (!pq.isEmpty()) {
               const u = pq.dequeue();
               inMST[u] = true;
               result += minEdge[u];
        
               for (const { to, weight } of adj[u]) {
                   if (!inMST[to] && weight < minEdge[to]) {
                       minEdge[to] = weight;
                       pq.enqueue(to);
                   }
               }
           }
        
           return result;
       }

5. 网络流算法

   • Ford-Fulkerson 算法

     • 描述：用于计算网络流中的最大流量。
     • 时间复杂度：O(max_flow * E)
     • 代码示例：

       function fordFulkerson(graph, source, sink) {
           const residualGraph = createResidualGraph(graph);
           let maxFlow = 0;
       
           while (true) {
               const parent = bfs(residualGraph, source, sink);
               if (!parent) break;
       
               let pathFlow = Infinity;
               for (let v = sink; v !== source; v = parent[v]) {
                   const u = parent[v];
                   pathFlow = Math.min(pathFlow, residualGraph[u][v]);
               }
       
               for (let v = sink; v !== source; v = parent[v]) {
                   const u = parent[v];
                   residualGraph[u][v] -= pathFlow;
                   residualGraph[v][u] += pathFlow;
               }
       
               maxFlow += pathFlow;
           }
       
           return maxFlow;
       }

   • Edmonds-Karp 算法

     • 描述：Ford-Fulkerson 算法的一种实现，使用 BFS 寻找增广路径。
     • 时间复杂度：O(V * E^2)
     • 代码示例：

       function edmondsKarp(graph, source, sink) {
           let maxFlow = 0;
           const residualGraph = createResidualGraph(graph);
       
           while (true) {
               const parent = bfs(residualGraph, source, sink);
               if (!parent) break;
       
               let pathFlow = Infinity;
               for (let v = sink; v !== source; v = parent[v]) {
                   const u = parent[v];
                   pathFlow = Math.min(pathFlow, residualGraph[u][v]);
               }
       
               for (let v = sink; v !== source; v = parent[v]) {
                   const u = parent[v];
                   residualGraph[u][v] -= pathFlow;
                   residualGraph[v][u] += pathFlow;
               }
       
               maxFlow += pathFlow;
           }
       
           return maxFlow;
       }

总结

图算法涵盖了多种处理图结构数据的技术，从遍历到最短路径，再到最小生成树和网络流等问题。理解这些算法的核心思想、应用场景和时间复杂度可以帮助你解决许多实际的图相关问题。在实现这些算法时，选择合适的数据结构（如优先队列、并查集）和算法策略是关键。

回溯算法

N皇后问题、数独、全排列等。

回溯算法（Backtracking）是一种通过递归来解决问题的算法设计策略，它通过尝试所有可能的解，并在发现某个解不符合要求时，回退到上一个状态以寻找其他可能的解。这种方法特别适合解决组合、排列、子集等问题。

回溯算法的步骤

1. 选择：在当前状态下选择一个可能的选项。
2. 约束：判断当前选择是否满足问题的约束条件。
3. 目标：检查是否达到问题的目标（即是否找到了一个有效解）。
4. 回退：如果当前选择不满足条件或无法找到有效解，则回退到上一步，尝试其他选项。

常见回溯算法问题

1. N 皇后问题 (N-Queens Problem)

   • 描述：在一个 N x N 的棋盘上放置 N 个皇后，使得任何两个皇后不在同一行、同一列或同一对角线。
   • 代码示例：

     function solveNQueens(n) {
         const results = [];
         const board = Array.from({ length: n }, () => Array(n).fill('.'));
     
         function isValid(board, row, col) {
             for (let i = 0; i < row; i++) {
                 if (board[i][col] === 'Q') return false;
                 if (col - (row - i) >= 0 && board[i][col - (row - i)] === 'Q') return false;
                 if (col + (row - i) < n && board[i][col + (row - i)] === 'Q') return false;
             }
             return true;
         }
     
         function backtrack(row) {
             if (row === n) {
                 results.push(board.map(r => r.join('')));
                 return;
             }
             for (let col = 0; col < n; col++) {
                 if (isValid(board, row, col)) {
                     board[row][col] = 'Q';
                     backtrack(row + 1);
                     board[row][col] = '.';
                 }
             }
         }
     
         backtrack(0);
         return results;
     }

2. 组合总和 (Combination Sum)

   • 描述：给定一个候选数字列表和一个目标数字，找出所有可以使目标数字的组合，其中每个候选数字可以被重复使用。
   • 代码示例：

     function combinationSum(candidates, target) {
         const results = [];
     
         function backtrack(start, target, path) {
             if (target === 0) {
                 results.push([...path]);
                 return;
             }
             if (target < 0) return;
     
             for (let i = start; i < candidates.length; i++) {
                 path.push(candidates[i]);
                 backtrack(i, target - candidates[i], path);
                 path.pop();
             }
         }
     
         backtrack(0, target, []);
         return results;
     }

3. 子集生成 (Subsets)

   • 描述：给定一个整数数组，找出所有可能的子集（幂集）。子集中的元素可以是原始数组中的任意顺序的子集。
   • 代码示例：

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

4. 排列 (Permutations)

   • 描述：给定一个不含重复数字的数组，返回其所有可能的排列。
   • 代码示例：

     function permute(nums) {
         const results = [];
     
         function backtrack(path) {
             if (path.length === nums.length) {
                 results.push([...path]);
                 return;
             }
             for (let i = 0; i < nums.length; i++) {
                 if (path.includes(nums[i])) continue;
                 path.push(nums[i]);
                 backtrack(path);
                 path.pop();
             }
         }
     
         backtrack([]);
         return results;
     }

5. 解数独 (Sudoku Solver)

   • 描述：填充一个 9x9 的数独板，使得每行、每列和每个 3x3 的小方块中都包含数字 1 到 9。
   • 代码示例：

     function solveSudoku(board) {
         function isValid(board, row, col, num) {
             for (let i = 0; i < 9; i++) {
                 if (board[row][i] === num || board[i][col] === num || 
                     board[3 * Math.floor(row / 3) + Math.floor(i / 3)][3 * Math.floor(col / 3) + i % 3] === num) {
                     return false;
                 }
             }
             return true;
         }
     
         function backtrack() {
             for (let row = 0; row < 9; row++) {
                 for (let col = 0; col < 9; col++) {
                     if (board[row][col] === '.') {
                         for (let num = 1; num <= 9; num++) {
                             if (isValid(board, row, col, num.toString())) {
                                 board[row][col] = num.toString();
                                 if (backtrack()) return true;
                                 board[row][col] = '.';
                             }
                         }
                         return false;
                     }
                 }
             }
             return true;
         }
     
         backtrack();
     }

回溯算法的特点

1. 递归和撤销：通过递归探索解空间树，并在回溯时撤销之前的选择。
2. 剪枝：通过判断当前选择是否满足约束，来剪去不必要的分支，提高效率。
3. 解空间树：将问题表示为一棵解空间树，每个节点代表一个状态，每条边代表一次选择。

总结

回溯算法是一种适用于需要穷举所有可能解的问题的算法设计策略。通过递归和撤销策略，它能够有效地解决组合、排列、子集等问题。理解如何构建递归树、进行有效的剪枝，以及处理回溯的状态恢复，是使用回溯算法的关键。

字符串算法

KMP算法、Boyer-Moore算法、Rabin-Karp算法等。

字符串算法是处理和操作字符串的算法，涉及到查找、匹配、转换等各种操作。以下是一些常见的字符串算法及其说明：

1. 字符串查找和匹配

• 暴力匹配 (Brute Force)

  • 描述：逐字符比较模式字符串和目标字符串，从目标字符串的每个位置开始进行比较。
  • 时间复杂度：O((N-M+1) * M) 其中 N 是目标字符串长度，M 是模式字符串长度
  • 代码示例：

    function bruteForceSearch(text, pattern) {
        const n = text.length;
        const m = pattern.length;
        for (let i = 0; i <= n - m; i++) {
            let j = 0;
            while (j < m && text[i + j] === pattern[j]) {
                j++;
            }
            if (j === m) {
                return i; // 找到匹配
            }
        }
        return -1; // 未找到匹配
    }

• KMP 算法 (Knuth-Morris-Pratt)

  • 描述：通过预处理模式字符串，使用部分匹配表来避免重复比较。
  • 时间复杂度：O(N + M)
  • 空间复杂度：O(M)
  • 代码示例：

    function kmpSearch(text, pattern) {
        function buildPartialMatchTable(pattern) {
            const table = Array(pattern.length).fill(0);
            let j = 0;
            for (let i = 1; i < pattern.length; i++) {
                while (j > 0 && pattern[i] !== pattern[j]) {
                    j = table[j - 1];
                }
                if (pattern[i] === pattern[j]) {
                    j++;
                }
                table[i] = j;
            }
            return table;
        }
    
        const table = buildPartialMatchTable(pattern);
        let j = 0;
        for (let i = 0; i < text.length; i++) {
            while (j > 0 && text[i] !== pattern[j]) {
                j = table[j - 1];
            }
            if (text[i] === pattern[j]) {
                j++;
            }
            if (j === pattern.length) {
                return i - j + 1; // 找到匹配
            }
        }
        return -1; // 未找到匹配
    }

• Boyer-Moore 算法

  • 描述：通过预处理模式字符串的坏字符规则和好后缀规则，跳过尽可能多的字符，提高匹配效率。
  • 时间复杂度：O(N * M) 最坏情况，O(N / M) 平均情况
  • 空间复杂度：O(M)
  • 代码示例：

    function boyerMooreSearch(text, pattern) {
        function buildBadCharTable(pattern) {
            const table = Array(256).fill(-1);
            for (let i = 0; i < pattern.length; i++) {
                table[pattern.charCodeAt(i)] = i;
            }
            return table;
        }
    
        const badCharTable = buildBadCharTable(pattern);
        let s = 0;
        while (s <= text.length - pattern.length) {
            let j = pattern.length - 1;
            while (j >= 0 && pattern[j] === text[s + j]) {
                j--;
            }
            if (j < 0) {
                return s; // 找到匹配
            }
            s += Math.max(1, j - badCharTable[text.charCodeAt(s + j)]);
        }
        return -1; // 未找到匹配
    }

2. 字符串转换

• 反转字符串 (Reverse String)

  • 描述：将字符串的字符顺序反转。
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)
  • 代码示例：

    function reverseString(s) {
        return s.split('').reverse().join('');
    }

• 字符替换 (Character Replacement)

  • 描述：替换字符串中的字符。
  • 代码示例：

    function replaceChars(s, target, replacement) {
        return s.split(target).join(replacement);
    }

3. 字符串编辑距离

• 编辑距离 (Edit Distance)
  • 描述：计算将一个字符串转换为另一个字符串所需的最小操作数，包括插入、删除和替换。
  • 时间复杂度：O(m * n) 其中 m 和 n 分别是两个字符串的长度
  • 空间复杂度：O(m * n)
  • 代码示例：

    function minDistance(word1, word2) {
        const m = word1.length;
        const n = word2.length;
        const dp = Array(m + 1).fill(null).map(() => Array(n + 1).fill(0));
    
        for (let i = 0; i <= m; i++) {
            for (let j = 0; j <= n; j++) {
                if (i === 0) {
                    dp[i][j] = j;
                } else if (j === 0) {
                    dp[i][j] = i;
                } else if (word1[i - 1] === word2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1]));
                }
            }
        }
        return dp[m][n];
    }

4. 字符串匹配和查找

• 正则表达式匹配 (Regular Expression Matching)
  • 描述：使用正则表达式模式匹配字符串，包括通配符和重复符号。
  • 时间复杂度：O(m * n) 其中 m 和 n 分别是字符串和模式的长度
  • 代码示例：

    function isMatch(s, p) {
        const dp = Array(s.length + 1).fill(null).map(() => Array(p.length + 1).fill(false));
        dp[0][0] = true;
    
        for (let j = 1; j <= p.length; j++) {
            if (p[j - 1] === '*') {
                dp[0][j] = dp[0][j - 2];
            }
        }
    
        for (let i = 1; i <= s.length; i++) {
            for (let j = 1; j <= p.length; j++) {
                if (p[j - 1] === '.' || p[j - 1] === s[i - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (p[j - 1] === '*') {
                    dp[i][j] = dp[i][j - 2] || (p[j - 2] === '.' || p[j - 2] === s[i - 1]) && dp[i - 1][j];
                }
            }
        }
        return dp[s.length][p.length];
    }

5. 字符串压缩

• 字符串压缩 (String Compression)
  • 描述：将字符串中的重复字符压缩为字符加上出现次数。
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)
  • 代码示例：

    function compressString(s) {
        let compressed = '';
        let count = 1;
        for (let i = 1; i < s.length; i++) {
            if (s[i] === s[i - 1]) {
                count++;
            } else {
                compressed += s[i - 1] + count;
                count = 1;
            }
        }
        compressed += s[s.length - 1] + count;
        return compressed.length < s.length ? compressed : s;
    }

总结

字符串算法涵盖了从基本的字符串查找、替换到更复杂的编辑距离和正则表达式匹配等操作。掌握这些算法可以帮助你有效地解决各种字符串处理问题，特别是在处理文本数据、进行模式匹配和字符串转换时非常有用。在实现这些算法时，理解其时间复杂度、空间复杂度以及适用场景是非常重要的。

同构字符串

给定两个字符串 s 和 t ，判断它们是否是同构的。如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。

var isIsomorphic = function (s, t) {
    if (s.length !== t.length) return false;//长度不相等直接返回false

    let sMap = new Map();
    let tMap = new Map();
    for (let i = 0; i < s.length; i++) {
        let schar = s[i];
        let tchar = t[i];

        if (sMap.has(schar)) {
            if (sMap.get(schar) !== tchar) {
                return false;
            }
        } else {
            sMap.set(schar, tchar)
        }
        if (tMap.has(tchar)) {
            if (tMap.get(tchar) !== schar) {
                return false;
            }
        }
        else {
            tMap.set(tchar, schar)
        }
    }
    return true;

};

这段代码是用来判断两个字符串 s 和 t 是否是同构的。两个字符串是同构的意思是，一个字符串中的字符可以按照某种一一映射关系替换得到另一个字符串，且这种映射关系必须是双向的，即不能有不同的字符映射到同一个字符上。

逐行解释

var isIsomorphic = function (s, t) {

定义一个名为 isIsomorphic 的函数，它接受两个字符串 s 和 t 作为参数，返回一个布尔值，表示这两个字符串是否是同构的。

if (s.length !== t.length) return false;

如果两个字符串的长度不相等，则它们不可能是同构的，直接返回 false。

let sMap = new Map();
let tMap = new Map();

创建两个 Map 对象 sMap 和 tMap，分别用于存储从 s 到 t 和从 t 到 s 的字符映射关系。

for (let i = 0; i < s.length; i++) {
    let schar = s[i];
    let tchar = t[i];

使用一个 for 循环遍历字符串的每个字符，schar 是 s 中的字符，tchar 是 t 中的对应字符。

if (sMap.has(schar)) {
    if (sMap.get(schar) !== tchar) {
        return false;
    }
} else {
    sMap.set(schar, tchar);
}

检查 sMap 是否包含字符 schar 的映射关系：

• 如果存在，检查 schar 在 sMap 中的映射值是否等于 tchar。如果不相等，则说明 schar 在 s 中的字符被映射到不同的字符，这说明不是同构，返回 false。
• 如果不存在，设置 schar 到 tchar 的映射。

if (tMap.has(tchar)) {
    if (tMap.get(tchar) !== schar) {
        return false;
    }
} else {
    tMap.set(tchar, schar);
}

检查 tMap 是否包含字符 tchar 的映射关系：

• 如果存在，检查 tchar 在 tMap 中的映射值是否等于 schar。如果不相等，则说明 tchar 在 t 中的字符被映射到不同的字符，这说明不是同构，返回 false。
• 如果不存在，设置 tchar 到 schar 的映射。

}
return true;

遍历结束后，如果没有发现任何不一致的映射关系，说明两个字符串是同构的，返回 true。

解题分析

1. 映射关系：

   • 使用两个 Map 对象分别维护 s 到 t 的映射和 t 到 s 的映射。这确保了每个字符映射关系的双向一致性。

2. 双向检查：

   • 对每个字符进行检查，确保字符之间的映射关系是双向一致的：即字符 schar 映射到字符 tchar，并且字符 tchar 也必须映射回字符 schar。

3. 时间复杂度：

   • 由于每个字符最多会被检查和存储两次，因此时间复杂度是 O(n)，其中 n 是字符串的长度。

4. 空间复杂度：

   • 使用了两个 Map，每个 Map 中最多存储 n 个字符的映射，因此空间复杂度是 O(n)。

这段代码有效地利用 Map 进行双向映射的检查，以确保两个字符串是否具有一致的字符映射关系，从而确定它们是否是同构的。

单词规律

给定一种规律 pattern 和一个字符串 s ，判断 s 是否遵循相同的规律。这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律。

要解决这个问题，我们需要确保字符串 s 中的每个非空单词与模式 pattern 中的每个字母之间存在着双向的映射关系。这意味着我们需要检查 pattern 和 s 中的单词是否遵循相同的映射关系，并且这种映射关系是双向一致的。

解决思路

1. 将字符串 s 分割成单词：使用空格作为分隔符将字符串 s 分割成单词列表。
2. 检查长度匹配：确保 pattern 的长度与分割后的单词列表长度一致。
3. 建立映射关系：
   • 使用两个映射：一个从 pattern 字符到单词的映射，另一个从单词到 pattern 字符的映射。
4. 双向映射验证：
   • 对于 pattern 中的每个字符和 s 中的每个单词，检查映射是否一致。如果存在冲突，则返回 false。
5. 最终验证：所有的映射关系符合预期则返回 true。

代码实现：

var wordPattern = function(pattern, s) {
    // 将字符串 s 按空格分割成单词数组
    const words = s.split(' ');
    
    // 如果 pattern 和 words 长度不同，直接返回 false
    if (pattern.length !== words.length) {
        return false;
    }
    
    // 创建两个映射：pattern 到单词 和 单词 到 pattern
    const patternToWord = new Map();
    const wordToPattern = new Map();
    
    // 遍历 pattern 和 words
    for (let i = 0; i < pattern.length; i++) {
        const char = pattern[i];
        const word = words[i];
        
        // 检查 pattern 到单词的映射
        if (patternToWord.has(char)) {
            if (patternToWord.get(char) !== word) {
                return false;
            }
        } else {
            patternToWord.set(char, word);
        }
        
        // 检查单词到 pattern 的映射
        if (wordToPattern.has(word)) {
            if (wordToPattern.get(word) !== char) {
                return false;
            }
        } else {
            wordToPattern.set(word, char);
        }
    }
    
    // 所有映射关系都符合要求
    return true;
};

逐行解释

1. 分割字符串：

   const words = s.split(' ');

   将字符串 s 按空格分割成单词数组 words。

2. 检查长度匹配：

   if (pattern.length !== words.length) {
       return false;
   }

   如果 pattern 的长度与 words 的长度不同，则返回 false，因为无法建立一一映射关系。

3. 创建映射：

   const patternToWord = new Map();
   const wordToPattern = new Map();

   创建两个 Map 对象：patternToWord 用于存储模式字符到单词的映射，wordToPattern 用于存储单词到模式字符的映射。

4. 遍历和建立映射：

   for (let i = 0; i < pattern.length; i++) {
       const char = pattern[i];
       const word = words[i];
       
       if (patternToWord.has(char)) {
           if (patternToWord.get(char) !== word) {
               return false;
           }
       } else {
           patternToWord.set(char, word);
       }
       
       if (wordToPattern.has(word)) {
           if (wordToPattern.get(word) !== char) {
               return false;
           }
       } else {
           wordToPattern.set(word, char);
       }
   }

   • 对于每个字符 char 和对应的单词 word，检查 patternToWord 和 wordToPattern 的映射。
   • 如果 char 已经映射到不同的单词 word，或者 word 已经映射到不同的字符 char，则返回 false。
   • 否则，建立或更新映射关系。

5. 返回结果：

   return true;

   如果所有映射关系都符合预期，则返回 true，表示 s 遵循模式 pattern。

总结

这个算法通过双向映射确保了模式字符和单词之间的映射关系是一一对应且一致的。时间复杂度为 O(n)，其中 n 是字符串 s 的长度，因为每个字符和单词仅被访问一次。空间复杂度也是 O(n)，用于存储两个映射。

有效的字母异位词

给定两个字符串 *s* 和 *t* ，编写一个函数来判断 *t* 是否是 *s* 的字母异位词。

注意：若 *s* 和 *t* 中每个字符出现的次数都相同，则称 *s* 和 *t* 互为字母异位词。

解决方案一

可以通过分别计数 s 和 t 中每个字符的出现次数，然后比较两个计数器来确定是否是字母异位词。

实现代码

var isAnagram = function(s, t) {
    // 如果长度不同，直接返回 false
    if (s.length !== t.length) return false;

    // 创建两个 Map 对象，用于计数
    let countS = new Map();
    let countT = new Map();

    // 计数 s 中字符的出现次数
    for (let char of s) {
        countS.set(char, (countS.get(char) || 0) + 1);
    }

    // 计数 t 中字符的出现次数
    for (let char of t) {
        countT.set(char, (countT.get(char) || 0) + 1);
    }

    // 比较两个 Map 是否相同
    if (countS.size !== countT.size) return false;
    for (let [char, count] of countS) {
        if (countT.get(char) !== count) return false;
    }

    return true;
};

逐行解释

1. 长度检查：

   if (s.length !== t.length) return false;

   如果 s 和 t 的长度不同，则它们不可能是字母异位词，直接返回 false。

2. 计数字符出现次数：

   let countS = new Map();
   let countT = new Map();
   
   for (let char of s) {
       countS.set(char, (countS.get(char) || 0) + 1);
   }
   
   for (let char of t) {
       countT.set(char, (countT.get(char) || 0) + 1);
   }

   • 使用两个 Map 对象 countS 和 countT 分别记录字符串 s 和 t 中每个字符的出现次数。

3. 比较计数器：

   if (countS.size !== countT.size) return false;
   for (let [char, count] of countS) {
       if (countT.get(char) !== count) return false;
   }

   • 首先检查两个计数器的大小是否相同。
   • 然后逐个比较每个字符的计数是否一致。

4. 返回结果：

   return true;

   如果所有字符的计数都匹配，返回 true，表示 s 和 t 是字母异位词。

方法2：sort排序

return s.length==t.length&& [...s].sort().join('')===[...t].sort().join('');

总结

通过分开计数字符的出现次数并比较这些计数，确保了判断字母异位词的准确性。时间复杂度为 O(n)，空间复杂度也是 O(n)，其中 n 是字符串的长度。