基于《算法通关之路》的前端算法学习总结

文章基于《算法通关之路》的分类进行总结，针对面试场景进行训练和自我总结。涵盖个人掌握情况指标，算法面试技巧，各分类根据指标的掌握情况，不同分类的自我理解，方便自己能够快速捡起来。

一、个人掌握分析

以下是一些可以用于评估个人算法掌握程度的指标：

一、知识理解层面

算法原理理解
- 准确性：能够准确阐述常见算法（如排序算法中的快速排序、归并排序，搜索算法中的深度优先搜索、广度优先搜索等）的基本原理、步骤和时间复杂度、空间复杂度分析。例如，是否能清晰地解释快速排序是如何通过选择一个基准值将数组分为两部分，并递归地对这两部分进行排序的。
- 深度：对于复杂算法（如动态规划、贪心算法在复杂场景下的应用），理解其背后的数学模型和理论依据。比如理解动态规划中的最优子结构性质和重叠子问题性质，以及它们如何决定算法的设计和实现。
算法复杂度分析
- 时间复杂度计算：对于给定的算法代码或算法描述，能够准确计算其时间复杂度，包括最好情况、最坏情况和平均情况（如果不同）。例如，对于一个嵌套循环的算法，能正确分析出其时间复杂度是多项式级还是指数级，并给出具体的大 O 表示，如 $O(n^2)$ 或 $O(2^n)$ 。
- 空间复杂度计算：准确评估算法在执行过程中所需的额外空间，考虑数据结构的存储需求和递归调用栈等因素。比如判断一个递归算法是否会因大量递归调用导致栈溢出问题，以及如何优化其空间复杂度。

二、实践应用层面

算法实现能力
- 代码准确性：能够用至少一种编程语言（如 Python、Java、C++等）准确实现各种算法，包括处理边界情况和异常情况。例如，在实现二叉树的遍历算法时，正确处理空树的情况；在实现排序算法时，确保对于相同元素的数组也能正确排序。
- 代码效率优化：能够对实现的算法代码进行性能优化，如减少不必要的计算、优化数据结构的使用等。例如，在实现搜索算法时，使用合适的数据结构（如哈希表）来降低查找时间复杂度；在递归算法中，通过尾递归优化或迭代方式改进以减少栈空间的使用。
算法选择与应用场景匹配
- 合适算法选择：面对实际问题，能够从众多算法中选择最合适的算法来解决问题。例如，对于需要快速查找元素是否存在的问题，能选择哈希表相关算法；对于图的遍历问题，根据图的特点（有向/无向、是否有环等）选择深度优先搜索或广度优先搜索。
- 应用场景拓展：理解算法在不同领域和场景中的变体和应用。比如知道排序算法在数据库索引、数据可视化等场景中的应用；了解搜索算法在游戏开发中的路径搜索、社交网络中的关系查找等场景的使用方式。

三、问题解决层面

问题分析与拆解能力
- 问题理解：对于给定的算法相关问题，能够快速理解问题的本质和要求，识别出问题的关键特征和约束条件。例如，对于一个复杂的组合优化问题，能从中提取出元素、目标函数和约束条件等关键信息。
- 问题拆解：将复杂问题分解为可通过已知算法解决的子问题，并确定子问题之间的关系。比如将一个大型图的最短路径问题分解为多个小区域的最短路径问题，然后考虑如何合并这些子问题的解。
调试与改进能力
- 错误定位：当算法实现出现错误（如结果不正确、性能不达标等）时，能够通过调试工具（如断点调试、打印中间结果等）快速定位问题所在，确定是算法逻辑错误、边界条件处理不当还是其他原因导致的。
- 改进策略制定：根据问题诊断结果，制定有效的改进策略，可能包括修改算法实现、调整数据结构或更换算法等。例如，如果发现某个排序算法在处理大量数据时性能不佳，能够分析是比较操作过多还是数据移动过于频繁的问题，并针对性地改进。

四、创新与拓展层面

算法改进与创新能力
- 现有算法改进：能够在理解现有算法的基础上，提出对算法的改进方案，以提高算法的性能、降低复杂度或增强算法的适应性。例如，对经典的排序算法提出一种新的划分策略来提高排序速度，或者对搜索算法提出一种新的启发式规则来减少搜索空间。
- 新算法设计：对于特定的新问题场景，能够设计全新的算法来解决问题，并证明其正确性和分析其复杂度。这需要对算法设计的基本原理和方法有深入的理解，以及创新思维能力。
算法知识更新与拓展能力
- 新知识学习：关注算法领域的最新发展动态，能够主动学习新出现的算法、数据结构和相关技术，并理解其原理和应用价值。例如，及时了解机器学习算法在大数据和人工智能领域的新应用和改进。
- 跨领域融合：能够将算法知识与其他领域（如数学、物理、计算机图形学等）的知识相结合，拓展算法的应用范围和解决问题的能力。比如将图算法应用于电路设计中的网络分析，或者将数值计算算法用于物理模拟中的方程求解。

二分查找⭐⭐

知识理解层面：⭐⭐⭐实践应用层面：⭐⭐问题解决层面：⭐创新与拓展：

深度优先和广度优先⭐⭐

贪心算法 ⭐

知识理解层面：⭐⭐⭐实践应用层面：⭐⭐⭐问题解决层面：⭐创新与拓展：

双指针 ⭐⭐⭐

滑动窗口 ⭐⭐⭐

分治法 ⭐⭐

回溯法 ⭐

回文⭐⭐

查并集 ⭐

博弈问题

股票问题

位运算

设计

二、算法面试注意事项

好代码的三大支柱

可读性：代码易于理解和阅读。
时间复杂度：衡量算法运行时间与输入规模之间的关系。
空间复杂度：衡量算法运行过程中占用的内存空间与输入规模之间的关系。

面试官关注的技能

分析能力：能够思考和分析问题。
编码能力：编写清晰、简单、有条理、可读的代码。
技术知识：了解所申请工作的基础知识。
沟通能力：个性与公司文化相匹配。

解决问题的步骤

记录关键信息：面试时听到问题，写下要点，确保掌握所有细节，展示条理性。
仔细检查：明确输入、输出，确定问题最重要的价值、目标，以及时间、空间等限制条件。
避免过度提问：不要频繁提问以免引起厌烦。
采用朴素/暴力方法：说出脑海中第一个想到的方法，体现思考能力，无需写代码。
分析方法优劣：说明该方法为何不是最佳，如时间复杂度高、可读性差等。
阐述自己的方法：讲解思路，注释代码，寻找可能的问题，如重复工作、瓶颈（时间复杂度高的部分），确保利用了所有给定信息。
规划代码步骤：写代码前，梳理并写下步骤。
模块化代码：将代码分成小模块，必要时添加注释。
编写代码：开始编写，提前准备充分有助于白板面试顺利进行，若忘记方法可自定义函数，从简单部分入手，处理错误检查，不假设输入情况，考虑如何防止代码被破坏。
测试代码：检查无参数、0、undefined、null、大数组、异步代码等情况，询问面试官能否对代码做假设，测试能否返回错误，检查是否有重复代码。
讨论改进：与面试官探讨代码的改进方向，如是否可行、有无其他方法、可读性如何、可通过谷歌搜索改进之处、性能提升方法，也可询问面试官见过的最有趣解决方案。
处理扩展问题：若面试官满意，面试可能结束；若不满意，可能会提出扩展问题，如输入过大无法存入内存或输入为流时如何处理，通常采用分治方法，如分布式处理数据，从磁盘读取部分输入到内存，写回输出后合并。

好代码检查清单

功能正常：代码能够正确运行。
合理使用数据结构：根据问题选择合适的数据结构。
代码复用：遵循“不要重复自己”原则。
模块化：使代码更可读、可维护和可测试。
时间复杂度低：尽量避免嵌套循环，若有两个循环，独立循环优于嵌套循环。
空间复杂度低：注意递归可能导致栈溢出，复制大数组可能超出机器内存。

解决问题的启发式方法

哈希表优化时间复杂度：通常可用于提高算法效率。
利用排序数组：若为排序数组，使用二叉树可实现O(log N)复杂度，采用分治思想，如二分查找。
尝试排序输入：有时对输入排序有助于解决问题。
哈希表和预计算信息优化代码：如利用预先排序的数据。
权衡时间与空间：适当存储额外状态可能优化运行时间。
遵循面试官建议：若面试官给出提示，应予以采纳。
空间换时间：哈希表常可用于此权衡，使用更多空间换取时间优化，在编程中常可通过牺牲少量空间来提高速度。

通用要点

面试过程中，要尽可能多地与面试官沟通自己的思维过程，不要只追求快速完成，面试的每个部分都很重要。

三、准备工作

js 算法中常用的操作

数组操作

遍历

for 循环：for (let i = 0; i < array.length; i++) { console.log(array[i]); }
forEach：array.forEach(element => console.log(element));
for...of：for (let element of array) console.log(element);
循环如何退出

查找

indexOf：array.indexOf(element)返回索引或 -1。
lastIndexOf：从后往前找，array.lastIndexOf(element)。
find：array.find(element => condition)找满足条件的首个元素。

排序

sort：array.sort((a, b) => a - b)按数字大小升序排序。

修改与添加

push：array.push(element)（在数组末尾添加一个或多个元素，返回新的数组长度）
pop：array.pop()（删除数组末尾的一个元素，返回被删除的元素）
unshift：array.unshift(element)（在数组开头添加一个或多个元素，返回新的数组长度）
shift：array.shift()（删除数组开头的一个元素，返回被删除的元素）
splice：array.splice(index, count, element)（根据参数删除、替换或添加数组元素，返回被删除的元素组成的数组，若没有删除元素则返回空数组）

字符串操作

遍历

for...of：for (let char of str) console.log(char);（无返回值，遍历字符串每个字符）
charAt：for (let i = 0; i < str.length; i++) console.log(str.charAt(i));（无返回值，按索引获取字符）

拼接与截取

concat：str1.concat(str2)连接字符串。
substring：str.substring(start, end)截取部分字符串。（截取从start（包含）到end（不包含）的字符串部分，返回截取后的字符串）
substr：str.substr(start, length) （从start索引开始截取length个字符，返回截取后的字符串）
slice：str.slice(start, end)，截取从start（包含）到end（不包含）的字符串部分，可接受负索引，返回截取后的字符串）

映射（`Map`）和集合（`Set`）操作

`Map`

创建：let myMap = new Map();
添加：myMap.set('key', 'value');
获取：myMap.get('key');
检查：myMap.has('key');
遍历：for (let [key, value] of myMap) console.log(key, value);或myMap.forEach((value, key) => console.log(key, value));

`Set`

创建：let mySet = new Set();
添加：mySet.add(element); - 检查：mySet.has(element);
删除：mySet.delete(element);
遍历：for (let element of mySet) console.log(element);或mySet.forEach(element => console.log(element));

函数操作

函数作为参数如`array.forEach(callback)`。

递归函数如

function factorial(n) { 
    if (n <= 1) return 1; 
    return n * factorial(n - 1); 
}

while 语句

一、概念

while语句是一种循环控制结构，只要给定的条件为真，就会重复执行一段代码块。它提供了一种灵活的方式来实现迭代计算、遍历数据结构以及处理需要重复执行直到满足特定条件的任务。

二、应用场景

（一）数值计算

示例：计算一个数的阶乘
- 思路：阶乘是从1开始连续乘到给定的数n，可以使用while循环，从1开始，每次乘以一个递增的数，直到达到n。
- 代码示例（JavaScript）：

function factorial(n) {
    let result = 1;
    let i = 1;
    while (i <= n) {
        result *= i;
        i++;
    }
    return result;
}
console.log(factorial(5));

示例：生成斐波那契数列的前n项
- 思路：斐波那契数列的特点是前两项为1，从第三项开始每一项是前两项的和。可以使用while循环来生成数列，通过记录前两项的值，不断计算并添加新的项到数列中。
- 代码示例（JavaScript）：

function fibonacci(n) {
    let result = [];
    let a = 1, b = 1;
    let i = 0;
    while (i < n) {
        if (i === 0 || i === 1) {
            result.push(1);
        } else {
            let temp = a + b;
            a = b;
            b = temp;
            result.push(b);
        }
        i++;
    }
    return result;
}
console.log(fibonacci(6));

（二）数组操作

示例：在有序数组中查找元素（简单的线性查找）
- 思路：从数组的开头开始，逐个比较元素与目标元素，直到找到目标元素或者遍历完整个数组。
- 代码示例（JavaScript）：

function linearSearch(arr, target) {
    let i = 0;
    while (i < arr.length) {
        if (arr[i] === target) {
            return i;
        }
        i++;
    }
    return -1;
}
let array = [1, 3, 5, 7, 9];
console.log(linearSearch(array, 5));

示例：数组元素的累积计算（例如计算数组元素的乘积）
- 思路：使用while循环遍历数组，将每个元素与一个累积变量相乘，从而得到数组所有元素的乘积。
- 代码示例（JavaScript）：

function arrayProduct(arr) {
    let result = 1;
    let i = 0;
    while (i < arr.length) {
        result *= arr[i];
        i++;
    }
    return result;
}
let array = [2, 3, 4];
console.log(arrayProduct(array));

（三）字符串处理

示例：统计字符串中某个字符的出现次数
- 思路：遍历字符串，每次遇到目标字符就增加计数变量的值。
- 代码示例（JavaScript）：

function countCharacter(str, charToCount) {
    let count = 0;
    let i = 0;
    while (i < str.length) {
        if (str[i] === charToCount) {
            count++;
        }
        i++;
    }
    return count;
}
let string = "hello world";
console.log(countCharacter(string, 'l'));

示例：字符串反转
- 思路：通过交换字符串首尾字符，逐步向中间移动，直到完成整个字符串的反转。可以使用两个指针，一个从字符串头部开始，一个从尾部开始，在while循环中交换它们指向的字符，直到两个指针相遇。
- 代码示例（JavaScript）：

function reverseString(str) {
    let left = 0;
    let right = str.length - 1;
    let result = str.split('');
    while (left < right) {
        let temp = result[left];
        result[left] = result[right];
        result[right] = temp;
        left++;
        right--;
    }
    return result.join('');
}
let string = "hello";
console.log(reverseString(string));

（四）链表操作

示例：遍历链表并打印节点值
- 思路：对于链表，通常会有一个头节点指针，通过while循环，只要当前节点指针不为null，就打印当前节点的值，并将指针移动到下一个节点。
- 代码示例（假设链表节点有val属性和next指针，以下是JavaScript示例）：

function printLinkedList(head) {
    let current = head;
    while (current) {
        console.log(current.val);
        current = current.next;
    }
}
// 构建一个简单链表示例
let node1 = {val: 1, next: {val: 2, next: {val: 3, next: null}}};
printLinkedList(node1);

示例：在链表中查找特定值的节点
- 思路：类似于遍历链表，在while循环中比较每个节点的值与目标值，当找到匹配的节点或者遍历完链表（当前节点为null）时停止。
- 代码示例（假设链表节点有val属性和next指针，以下是JavaScript示例）：

function findNodeInLinkedList(head, target) {
    let current = head;
    while (current) {
        if (current.val === target) {
            return current;
        }
        current = current.next;
    }
    return null;
}
// 构建一个简单链表示例
let node1 = {val: 1, next: {val: 2, next: {val: 3, next: null}}};
console.log(findNodeInLinkedList(node1, 2));

四、基础定义

❌

递归

定义和原理

递归是一种函数调用自身的编程技巧。在解决问题时，将一个大问题逐步分解为相同结构的小问题，直到小问题可以直接求解，然后通过回溯将小问题的解组合起来得到大问题的解。

应用场景举例

深度遍历（以二叉树为例）
- 如前面提到的二叉树的前序、中序和后序遍历。在这些遍历方式中，通过递归不断深入树的节点，直到叶子节点，然后回溯。以前序遍历为例，先访问根节点，然后递归地访问左子树和右子树，这是一种深度优先的方式，不断沿着树的深度方向探索。
分治算法（以归并排序为例）
- 归并排序是一种典型的分治算法，它利用递归将数组分成两半，直到子数组只有一个元素（这是基本情况，可以直接认为是有序的）。然后通过合并有序的子数组来得到最终排序后的数组。
- 代码示例（JavaScript）：

function mergeSort(arr) {
    if (arr.length <= 1) {
        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 = [];
    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(i < left.length? left.slice(i) : right.slice(j));
}
let array = [5, 3, 8, 4, 2];
console.log(mergeSort(array));

斐波那契数列计算
- 斐波那契数列的定义是： $F(n)=F(n - 1)+F(n - 2)$ ，其中 $F(0)=0$ ， $F(1)=1$ 。可以通过递归函数来计算斐波那契数列的第 $n$ 项。
- 代码示例（JavaScript）：

function fibonacci(n) {
    if (n === 0) {
        return 0;
    }
    if (n === 1) {
        return 1;
    }
    return fibonacci(n - 1)+fibonacci(n - 2);
}
console.log(fibonacci(6));

自己的理解总结

深度优先搜索是通过递归对树形结构进行函数调用自身操作，所以，递归是一种广泛应用的编程策略，深度遍历只是其中一个应用场景，它还在分治算法、数学计算等许多领域发挥重要作用。

迭代

迭代是一种重复执行一段代码块的过程，每次执行时会基于上一次执行的结果或者状态进行更新，目的是逐步逼近一个目标状态或者计算出一个最终结果。它是计算机编程中常用的基本控制结构之一，与递归相对应。迭代通常使用循环结构（如for循环、while循环）来实现。

五、算法与数据结构总结

<span id="二叉树">二叉树</span>

场景

二叉树在计算机科学中有广泛应用：

表示层次关系：如文件系统目录结构、组织结构图等。
搜索算法：二叉搜索树可用于快速查找元素。
表达式求值：语法树以二叉树形式构建，用于计算表达式的值。

<span id="深度优先搜索（DFS）">深度优先搜索（DFS）</span>

1. 概念

深度优先搜索是一种用于遍历或搜索图（包括树，树是一种特殊的图）的算法策略。它从起始节点开始，沿着一条路径尽可能深地探索，直到无法继续，然后回溯到前一步，继续探索其他路径。这种搜索方式就像走迷宫，一直沿着一条路走，直到碰壁才回头尝试其他分支。

2. 实现方式（以树结构为例）

递归实现：
- 思路：对于树的每个节点，先访问根节点，然后递归地对左子树进行深度优先搜索，再递归地对右子树进行深度优先搜索。这种方式代码简洁，但可能会受到系统栈大小的限制。
- 代码示例（以二叉树的前序遍历为例）：

// 二叉树节点定义
function TreeNode(val) {
    this.val = val;
    this.left = this.right = null;
}

function preorderTraversal(root) {
    let result = [];
    function dfs(node) {
        if (node) {
            result.push(node.val);
            dfs(node.left);
            dfs(node.right);
        }
    }
    dfs(root);
    return result;
}
// 构建一个简单二叉树示例
let root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
console.log(preorderTraversal(root));

栈实现（非递归）：
- 思路：使用一个栈来模拟递归调用的过程。首先将根节点入栈，然后在栈不为空时循环。每次从栈顶取出一个节点，访问该节点，然后将其右子节点和左子节点（顺序很重要，先右后左是为了模拟递归先左后右的相反顺序）依次入栈，这样就保证了深度优先的遍历顺序。
- 代码示例（以二叉树的中序遍历为例）：

function inorderTraversal(root) {
    let result = [];
    let stack = [];
    let current = root;
    while (current || stack.length > 0) {
        while (current) {
            stack.push(current);
            current = current.left;
        }
        current = stack.pop();
        result.push(current.val);
        current = current.right;
    }
    return result;
}
// 构建一个简单二叉树示例
let root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
console.log(inorderTraversal(root));

3. 应用场景

图的连通性检测：

判断一个图是否是连通图，或者在一个图中找到与给定节点相连通的所有节点。

生成树问题：

例如最小生成树算法（如Prim算法和Kruskal算法）的一些实现过程中会用到深度优先搜索的思想来遍历图。

拓扑排序（对于有向无环图）：

通过深度优先搜索标记节点的访问状态，根据节点的后序遍历顺序得到拓扑排序结果。
以下以一个简单的二叉树为例，展示前序、中序和后序遍历的数据访问顺序：

递归的前序、中序和后序

      1
    /   \
   2     3
  / \   / \
 4   5 6   7

前序遍历顺序

先访问根节点：1。
访问左子树：先访问左子树的根节点 2，再访问 2 的左子树节点 4，接着访问 2 的右子树节点 5。
访问右子树：先访问右子树的根节点 3，再访问 3 的左子树节点 6，最后访问 3 的右子树节点 7。

所以前序遍历结果为：1、2、4、5、3、6、7。

中序遍历顺序

访问左子树：先访问 2 的左子树节点 4，再访问左子树的根节点 2，接着访问 2 的右子树节点 5。
访问根节点：1。
访问右子树：先访问 3 的左子树节点 6，再访问右子树的根节点 3，最后访问 3 的右子树节点 7。

所以中序遍历结果为：4、2、5、1、6、3、7。

后序遍历顺序

访问左子树：先访问 2 的左子树节点 4，再访问 2 的右子树节点 5，最后访问左子树的根节点 2。
访问右子树：先访问 3 的左子树节点 6，再访问 3 的右子树节点 7，最后访问右子树的根节点 3。
访问根节点：1。

所以后序遍历结果为：4、5、2、6、7、3、1。

广度优先搜索（BFS）

1. 概念

广度优先搜索是一种从起始节点开始，按照层次顺序逐层遍历图（或树）的算法。它先访问起始节点的所有邻居节点，然后再依次访问这些邻居节点的邻居节点，以此类推，就像一层一层地扫描整个图。

2. 实现方式（以树结构为例）

队列实现：
- 思路：首先将根节点放入队列。在队列不为空时，取出队首节点，访问该节点，然后将其所有子节点（对于树来说是左右子节点）放入队列。重复这个过程，直到队列为空，这样就实现了按层遍历。
- 代码示例（以二叉树的层序遍历为例）：

function levelOrder(root) {
    if (!root) return [];
    let queue = [root];
    let result = [];
    while (queue.length > 0) {
        let levelSize = queue.length;
        let currentLevel = [];
        for (let i = 0; i < levelSize; i++) {
            let node = queue.shift();
            currentLevel.push(node.val);
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        result.push(currentLevel);
    }
    return result;
}
// 构建一个简单二叉树示例
let root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
console.log(levelOrder(root));

3. 应用场景

最短路径问题（无权图）：在一个无权图中，从一个节点到另一个节点的最短路径可以通过广度优先搜索来找到。例如，在一个迷宫中找到从起点到终点的最短路径。
社交网络分析：比如在社交网络中，查找与一个用户距离为k（朋友的朋友的……经过k层关系）的所有用户。
网页爬虫：广度优先搜索可以用来遍历网页链接，先爬取一个网页上的所有链接（第一层），再依次爬取这些链接指向的网页（第二层），以此类推。

二分查找

场景总结：

适用于在有序数据集合中快速查找特定元素，如在有序数组中查找某个值、数据库索引搜索（索引通常有序）等场景，可提高查找效率。

常见算法题解题思路

在有序数组中查找目标值：
使用双指针，分别指向数组的首尾（left 和 right）。
在循环中（条件为 left <= right）：
- 计算中间索引 mid = Math.floor((left + right) / 2)。
- 如果 arr[mid] 等于目标值，返回 mid。
- 如果 arr[mid] 小于目标值，说明目标值在右半部分，将 left 更新为 mid + 1。
- 如果 arr[mid] 大于目标值，说明目标值在左半部分，将 right 更新为 mid - 1。
如果循环结束未找到目标值，返回 -1。

代码示例：

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

let sortedArray = [1, 3, 5, 7, 9];
console.log(binarySearch(sortedArray, 5));

动态规划

以二维数组的方式进行理解

解题思路快查

场景总结：

用于解决具有重叠子问题和最优子结构性质的问题。在优化递归算法、资源分配（如背包问题）、序列相关问题（如最长公共子序列、最长递增子序列）等场景表现出色，通过避免重复计算子问题提高效率。

常见算法题解题思路 - 斐波那契数列（动态规划实现）：

创建一个长度为 n + 1 的 dp 数组（n 为要计算的斐波那契数的索引）。
初始化 dp[0] = 0 和 dp[1] = 1，这是斐波那契数列的基础情况。
从索引 2 到 n 遍历，根据状态转移方程 dp[i] = dp[i - 1] + dp[i - 2] 计算每个位置的值。
返回 dp[n] 作为结果。
代码示例（以斐波那契数列为例）：

function fibonacci(n) {
    if (n === 0 || n === 1) return n;
    let dp = [0, 1];
    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

console.log(fibonacci(10));

爬楼梯：

`dp[i - 1] + dp[i - 2]`

爬楼梯为什么是dp[i - 1] + dp[i - 2] 题目一般是定义的一次爬1 - 2层。因为到达第i层楼梯，只能从第i - 1层跨 1 步或者从第i - 2层跨 2 步到达，所以到达第i层的方法数是到达第i - 1层的方法数与到达第i - 2层的方法数之和。如果改为一次爬1 - 3层，方程式变为dp[i] = dp[i - 1]+dp[i - 2]+dp[i - 3]，因为此时到达第i层可以从第i - 1层跨 1 步、从第i - 2层跨 2 步或者从第i - 3层跨 3 步到达。

打家劫舍问题

`dp[i] = Math.max(dp[i - 1], dp[i - 2]+nums[i]);`

问题描述：给定一个代表每个房屋存放金额的非负整数数组nums，要求计算在不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。不能同时偷窃相邻的房屋。
解题思路：
- 定义状态：设dp[i]表示偷窃到第i个房屋时的最大偷窃金额。
- 确定边界条件：dp[0] = nums[0]，即只有一个房屋时，最大偷窃金额就是这个房屋的金额；dp[1] = Math.max(nums[0], nums[1])，当有两个房屋时，选择金额较大的那个房屋进行偷窃。
- 状态转移方程：对于i > 1，dp[i] = Math.max(dp[i - 1], dp[i - 2]+nums[i])。这是因为到第i个房屋时，有两种选择：一是不偷第i个房屋，那么最大偷窃金额就是偷窃到第i - 1个房屋时的金额dp[i - 1]；二是偷第i个房屋，那么最大偷窃金额就是偷窃到第i - 2个房屋时的金额加上第i个房屋的金额dp[i - 2]+nums[i]，取两者中的较大值作为dp[i]的值。
- 最终答案：dp[n - 1]就是整个数组（n为房屋数量）中的最大偷窃金额。
- 代码示例（JavaScript）：

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

不同路径问题

`dp[i][j] = dp[i - 1][j]+dp[i][j - 1]`

问题描述：一个机器人位于一个m x n网格的左上角（起始点在[0,0]）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（终点在[m - 1,n - 1]）。问总共有多少条不同的路径？
解题思路：
- 定义状态：设dp[i][j]表示机器人从左上角走到[i,j]位置的不同路径数量。
- 确定边界条件：dp[0][0] = 1，起始位置的路径数量为1；对于第一行（i = 0）和第一列（j = 0），因为机器人只能向右或者向下移动，所以dp[0][j] = 1（j > 0），dp[i][0] = 1（i > 0）。
- 状态转移方程：对于i > 0且j > 0，dp[i][j] = dp[i - 1][j]+dp[i][j - 1]。这是因为机器人到达[i,j]位置只能是从[i - 1,j]位置向下移动一步或者从[i,j - 1]位置向右移动一步，所以到达[i,j]位置的路径数量是到达[i - 1,j]位置的路径数量与到达[i,j - 1]位置的路径数量之和。
- 最终答案：dp[m - 1][n - 1]就是从左上角到右下角的不同路径数量。
代码示例（JavaScript）：

function uniquePaths(m, n) {
    let dp = [];
    for (let i = 0; i < m; i++) {
        dp[i] = [];
        for (let j = 0; j < n; j++) {
            if (i === 0 && j === 0) {
                dp[i][j] = 1;
            } else if (i === 0) {
                dp[i][j] = 1;
            } else if (j === 0) {
                dp[i][j] = 1;
            } else {
                dp[i][j] = dp[i - 1][j]+dp[i][j - 1];
            }
        }
    }
    return dp[m - 1][n - 1];
}

零钱兑换问题 ❌

问题描述：给定不同面额的硬币coins和一个总金额amount，计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
解题思路：
- 定义状态：设dp[i]表示凑成金额i所需的最少硬币个数。
- 确定边界条件：dp[0] = 0，因为金额为0时不需要任何硬币；对于i > 0，初始时可以将dp[i]设为一个较大的值（如amount + 1），表示暂时还没有找到合适的硬币组合来凑成该金额。
- 状态转移方程：对于每个金额i，遍历所有硬币面额coins[j]，如果i - coins[j] >= 0，则dp[i] = Math.min(dp[i], dp[i - coins[j]]+1)。这表示尝试用每一种硬币面额去凑金额i，如果用面额为coins[j]的硬币去凑时，剩下的金额i - coins[j]的最少硬币个数dp[i - coins[j]]已经知道，那么凑成金额i的最少硬币个数就可能是dp[i - coins[j]]再加上这一枚硬币（即dp[i - coins[j]] + 1），取所有可能情况中的最小值作为dp[i]的值。
- 最终答案：如果dp[amount] <= amount，则返回dp[amount]，表示找到了凑成总金额amount的最少硬币个数；否则返回 -1，表示无法凑出总金额。
代码示例（JavaScript）：

function coinChange(coins, amount) {
    let dp = new Array(amount + 1).fill(amount + 1);
    dp[0] = 0;
    for (let i = 1; i <= amount; i++) {
        for (let j = 0; j < coins.length; j++) {
            if (i - coins[j] >= 0) {
                dp[i] = Math.min(dp[i], dp[i - coins[j]]+1);
            }
        }
    }
    return dp[amount] <= amount? dp[amount] : -1;
}

贪心算法

解题思路快查

场景总结：
在每一步选择当前状态下的最优策略，适用于具有最优子结构且局部最优解能导致全局最优解的问题。常见于资源分配（如找零问题）、任务调度问题（选择执行顺序以达最优结果）等场景。
常见算法题解题思路 - 找零问题（贪心算法实现）：
- 对硬币面额数组进行排序（从小到大）。
- 从面额最大的硬币开始遍历（从后往前）：
  - 只要目标金额大于等于当前硬币面额，就尽可能多地使用该硬币（通过循环减少目标金额并增加硬币数量）。
- 如果最后目标金额为 0，返回使用的硬币总数；否则返回 -1，表示无法用给定的硬币组合凑出目标金额。
代码示例（以找零问题为例）：

function coinChange(coins, amount) {
    coins.sort((a, b) => a - b);
    let count = 0;
    for (let i = coins.length - 1; i >= 0; i--) {
        while (amount >= coins[i]) {
            amount -= coins[i];
            count++;
        }
    }
    return amount === 0? count : -1;
}

let coins = [1, 5, 10];
console.log(coinChange(coins, 18));

分发饼干问题（贪心算法）

遍历小孩，两个指针，如果当前饼干不满足小孩则移动到下个饼干

问题描述：有一群孩子和一堆饼干，每个孩子有一个饥饿度，每个饼干有一个尺寸。每个孩子只能吃最多一块饼干，且只有饼干的尺寸大于等于孩子的饥饿度时，孩子才能吃饱。求最多可以让多少个孩子吃饱。
解题思路：
- 首先将孩子的饥饿度数组g和饼干尺寸数组s分别进行排序，一般是从小到大排序。
- 使用两个指针i和j，分别指向孩子数组和饼干数组的起始位置。
- 遍历两个数组，当饼干尺寸s[j]大于等于孩子饥饿度g[i]时，说明这个饼干可以满足这个孩子，此时孩子吃饱的数量加1，并且将孩子指针i向后移动一位，表示考虑下一个孩子；同时，无论这个饼干是否满足孩子，都将饼干指针j向后移动一位，因为一块饼干只能用一次。
  - 重复上述步骤，直到孩子数组或者饼干数组遍历完。
  - 最终孩子吃饱的数量就是最多可以满足的孩子数量。
代码示例（JavaScript）：

function findContentChildren(g, s) {
    g.sort((a, b) => a - b);
    s.sort((a, b) => a - b);
    let i = 0;
    let j = 0;
    while (i < g.length && j < s.length) {
        if (s[j] >= g[i]) {
            i++;
        }
        j++;
    }
    return i;
}
let g = [1, 2, 3];
let s = [1, 1];
console.log(findContentChildren(g, s));

跳跃游戏问题（贪心算法）

每次都跳最大值，最后如果能跳的最大值涵盖最后数组length 则满足

问题描述：给定一个非负整数数组nums，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个位置。
解题思路：
- 定义一个变量maxReach，用于记录当前能到达的最远位置，初始值为0。
- 遍历数组，对于每个位置i，如果i小于等于maxReach，说明当前位置是可以到达的，更新maxReach为maxReach和i + nums[i]（从当前位置能跳到的最远位置）中的最大值。
- 如果在遍历过程中，maxReach大于等于数组的长度减1，说明可以到达最后一个位置，返回true；如果遍历完数组，maxReach仍然小于数组长度减1，说明无法到达最后一个位置，返回false。
代码示例（JavaScript）：

function canJump(nums) {
    let maxReach = 0;
    for (let i = 0; i < nums.length; i++) {
        if (i <= maxReach) {
            maxReach = Math.max(maxReach, i + nums[i]);
            if (maxReach >= nums.length - 1) {
                return true;
            }
        }
    }
    return false;
}
let nums = [2, 3, 1, 1, 4];
console.log(canJump(nums));

任务调度器问题 ❌

问题描述：给定一个用字符数组表示的任务集合和一个整数n，表示相同任务之间需要间隔的时间。计算完成所有任务所需的最短时间。
解题思路：
- 首先统计每个任务出现的次数，创建一个任务频率数组counts。
- 找到出现次数最多的任务的频率maxCount。
- 计算至少需要的时间块数，公式为(maxCount - 1) * (n + 1)，这是考虑了出现最频繁任务之间的间隔。
  - 然后遍历任务频率数组，对于频率等于maxCount的任务，需要额外增加时间块，因为它们和出现最频繁的任务一样，会占据相同的时间位置。
  - 最后，取计算得到的时间块数和任务数组长度中的最大值，作为完成所有任务所需的最短时间。因为如果任务数量较多，即使没有间隔要求，也需要足够的时间来完成所有任务。
- 代码示例（JavaScript）：

function leastInterval(tasks, n) {
    let counts = new Array(26).fill(0);
    for (let task of tasks) {
        counts[task.charCodeAt(0) - 'A'.charCodeAt(0)]++;
    }
    counts.sort((a, b) => b - a);
    let maxCount = counts[0];
    let time = (maxCount - 1) * (n + 1);
    for (let count of counts) {
        if (count === maxCount) {
            time++;
        }
    }
    return Math.max(time, tasks.length);
}
let tasks = ["A", "A", "A", "B", "B", "B"];
let n = 2;
console.log(leastInterval(tasks, n));

分发糖果问题（贪心算法）

根据要求分别从 left 和 right 分别计算出需要分发的糖果数，再将左右两个结果方案进行比较选取`max`，保证最小糖果消耗的同时，也满足分发糖果的要求。在分发糖果问题中，我们采用了两次贪心的过程。从左到右遍历保证每个孩子相对于左边孩子糖果数满足条件，从右到左遍历保证相对于右边孩子的条件。

问题描述：有N个孩子站成一排，每个孩子都有一个评分。你需要按照以下要求给这些孩子分发糖果：每个孩子至少得到一个糖果；如果一个孩子的评分比他相邻的孩子高，那么这个孩子得到的糖果数要多于相邻的孩子。求最少需要分发多少糖果。
解题思路：
- 从左到右遍历孩子的评分数组ratings，如果当前孩子的评分大于前一个孩子的评分，就给当前孩子比前一个孩子多1个糖果；否则，给当前孩子1个糖果。这样就完成了从左到右的一次贪心分配，保证了每个孩子相对于左边孩子的糖果数满足条件。
- 然后从右到左再次遍历数组，如果当前孩子的评分大于后一个孩子的评分，并且当前孩子的糖果数不大于后一个孩子的糖果数，就给当前孩子比后一个孩子多1个糖果。这样就保证了每个孩子相对于右边孩子的糖果数也满足条件。
- 最后，将所有孩子的糖果数相加，得到最少需要分发的糖果总数。
代码示例（JavaScript）：

function candy(ratings) {
    let n = ratings.length;
    let candies = new Array(n).fill(1);
    for (let i = 1; i < n; i++) {
        if (ratings[i] > ratings[i - 1]) {
            candies[i] = candies[i - 1] + 1;
        }
    }
    for (let i = n - 2; i >= 0; i--) {
        if (ratings[i] > ratings[i + 1] && candies[i] <= candies[i + 1]) {
            candies[i] = candies[i + 1] + 1;
        }
    }
    return candies.reduce((a, b) => a + b);
}
let ratings = [1, 2, 2];
console.log(candy(ratings));

无重叠区间问题

子集合排序，比对current 和子集的start,如果大于则说明重叠，并更新current 为end，并计数count

问题描述：给定一个区间的集合，找到需要移除区间的最小数量，使得剩余区间互不重叠。
解题思路：
- 首先将区间数组intervals按照区间的结束时间进行排序，这样可以优先选择结束时间早的区间，为后面的区间留出更多空间。
- 初始化一个变量end为负无穷，表示当前已选择区间的结束时间，同时初始化一个变量count为0，表示需要移除的区间数量。
- 遍历排序后的区间数组，对于每个区间[start, end]，如果当前区间的开始时间大于等于end，说明这个区间和前面已选择的区间不重叠，可以选择这个区间，更新end为当前区间的结束时间；否则，说明这个区间和前面已选择的区间有重叠，需要移除这个区间，count加1。
- 遍历完所有区间后，count就是需要移除的区间的最小数量。
代码示例（JavaScript）：

function eraseOverlapIntervals(intervals) {
    intervals.sort((a, b) => a[1] - b[1]);
    let end = -Infinity;
    let count = 0;
    for (let interval of intervals) {
        if (interval[0] >= end) {
            end = interval[1];
        } else {
            count++;
        }
    }
    return count;
}
let intervals = [[1, 2], [2, 3], [3, 4], [1, 3]];
console.log(eraseOverlapIntervals(intervals));

双指针

适用数据结构

字符串，数组，链表

解题思路快查

反转字符串：使用双指针，一个指针指向字符串开头，一个指向结尾，然后交换两个指针所指字符，直到两个指针相遇。
数组拆分（例如，两数之和问题）：先对数组排序，然后使用双指针，一个指针指向数组开头，一个指向末尾。计算两指针所指元素之和，与目标值比较。如果和等于目标值，找到解；如果和大于目标值，将尾指针向左移；如果和小于目标值，将头指针向右移。

场景总结：

在处理数组、字符串、链表等数据结构时有用，可解决元素交换、查找、配对等问题，通过两个指针协同操作简化问题复杂度，降低时间复杂度。

常见算法题解题思路 - 反转字符串（双指针实现）：

将字符串转换为字符数组。
初始化左指针 left = 0 和右指针 right = 字符数组长度 - 1。
在循环中（条件为 left < right）：
- 交换 left 和 right 指针所指的字符。
- left 指针向右移动一位，right 指针向左移动一位。
将处理后的字符数组转换回字符串并返回。

代码示例（以反转字符串为例）：

function reverseString(str) {
    let arr = str.split('');
    let left = 0;
    let right = arr.length - 1;
    while (left < right) {
        [arr[left], arr[right]] = [arr[right], arr[left]];
        left++;
        right--;
    }
    return arr.join('');
}

console.log(reverseString("hello"));

两数相加（这里假设是单链表表示的两数相加）

问题描述：给定两个用链表表示的非负整数，每个节点包含一个数字，数字按逆序存储，要求将这两个数相加并以链表形式返回结果。
解题思路：
- 使用两个指针p1和p2分别指向两个链表的头节点，模拟竖式加法。
- 同时遍历两个链表，逐位相加。将当前位的和（加上上一位的进位）计算出来，新和的个位数作为新节点的值，新和除以10的商作为进位。
- 如果一个链表遍历完，另一个链表还有节点，则继续处理剩余节点，同样要考虑进位。
- 最后，如果还有进位，需要在结果链表末尾添加一个值为1的节点。
代码示例（JavaScript）：

function ListNode(val) {
    this.val = val;
    this.next = null;
}

function addTwoNumbers(l1, l2) {
    let dummyHead = new ListNode(0);
    let p = dummyHead;
    let carry = 0;
    let p1 = l1;
    let p2 = l2;
    while (p1 || p2) {
        let sum = carry;
        if (p1) {
            sum += p1.val;
            p1 = p1.next;
        }
        if (p2) {
            sum += p2.val;
            p2 = p2.next;
        }
        carry = Math.floor(sum / 10);
        p.next = new ListNode(sum % 10);
        p = p.next;
    }
    if (carry > 0) {
        p.next = new ListNode(carry);
    }
    return dummyHead.next;
}

盛水问题（双指针法解决容器盛水问题，也叫接雨水问题）

问题描述：给定n个非负整数a1，a2，...，an，每个数代表坐标中的一个点(i, ai)。在坐标内画n条垂直线，垂直线i的两个端点分别为(i, ai)和(i, 0)。找出其中的两条线，使得它们与x轴共同构成的容器可以容纳最多的水。
解题思路：
- 使用两个指针left和right，分别指向容器的最左边和最右边。
- 计算当前容器的面积，面积 = （right - left）* Math.min(height[left], height[right])，这里height是存储垂直线高度的数组。
- 然后移动指针，将高度较小的指针向中间移动一位，因为移动高度较大的指针只会使面积变小（宽度减小且高度受限于较小值）。
- 重复上述步骤，不断更新最大面积，直到left和right相遇。
代码示例（JavaScript）：

function maxArea(height) {
    let left = 0;
    let right = height.length - 1;
    let maxAreaValue = 0;
    while (left < right) {
        let currentArea = (right - left) * Math.min(height[left], height[right]);
        maxAreaValue = Math.max(maxAreaValue, currentArea);
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    return maxAreaValue;
}

环形链表

问题描述：给定一个链表，判断链表中是否有环。
解题思路（快慢指针）：
- 使用两个指针slow和fast，初始都指向链表头。
- slow指针每次移动一步，fast指针每次移动两步。
- 如果链表中有环，那么fast指针一定会追上slow指针（即二者指向同一个节点），如果fast指针遍历到链表末尾（fast或fast.next为null），则说明链表无环。
代码示例（JavaScript）：

function hasCycle(head) {
    if (!head) 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;
}

无重复字符串的最长子串

问题描述：给定一个字符串s，找出其中不含有重复字符的最长子串的长度。
解题思路：
- 使用两个指针left和right，left指向子串的左边界，right指向右边界，初始都为0。
- 使用一个数据结构（如Map）来记录每个字符在当前窗口内出现的次数。
- 移动right指针来扩大窗口，将新字符加入窗口，更新其在Map中的出现次数。
- 如果窗口内出现重复字符（即新字符的出现次数大于1），移动left指针收缩窗口，同时更新窗口内字符的出现次数，直到窗口内不再有重复字符。
- 在每次移动指针后，更新无重复字符的最长子串长度（取当前长度和之前记录的最长长度的最大值）。
代码示例（JavaScript）：

/**
 * @param {string} s
 * @return {number}
 */
 
var lengthOfLongestSubstring = function(s) {
    let maxLen = 0;
    let left = 0;
    let map = new Map();

    for(let right = 0; right < s.length; right++) {
      if (map.has(s[right])) {
        left = Math.max(left, map.get(s[right]) + 1) // left 移动到重复字符的下一位
        
      }
      maxLen = Math.max(maxLen, right - left + 1)
      console.log(left, right)
      map.set(s[right], right )
    }
    return maxLen
};

滑动窗口

要注意判断是否有连续性的要求，没有则默认不是

场景总结：

主要用于处理连续区间相关问题，特别是在字符串和数组中查找满足特定条件的子串或子数组，如在字符串中查找包含所有指定字符的最小子串、在数组中查找和大于等于某个值的最小连续子数组等场景。

常见算法题解题思路 - 无重复字符的最长子串：

使用双指针（left 和 right），left 指向子串的左边界，right 指向右边界，初始都为 0。
使用一个数据结构（如 Map）来记录每个字符在当前窗口内出现的次数。
移动右指针 right，扩大窗口：
- 将新字符加入窗口，更新其在 Map 中的出现次数。
- 如果窗口内出现重复字符（即新字符的出现次数大于 1），移动左指针 left 收缩窗口，同时更新窗口内字符的出现次数，直到窗口内不再有重复字符。
- 在每次移动指针后，更新无重复字符的最长子串长度（取当前长度和之前记录的最长长度的最大值）。
代码示例（以无重复字符的最长子串为例）：

function lengthOfLongestSubstring(s) {
    let maxLength = 0;
    let left = 0;
    let usedChars = new Map();
    for (let right = 0; right < s.length; right++) {
        if (usedChars.has(s[right]) && usedChars.get(s[right]) >= left) {
            left = usedChars.get(s[right]) + 1;
        }
        usedChars.set(s[right], right);
        maxLength = Math.max(maxLength, right - left + 1);
    }
    return maxLength;
}

console.log(lengthOfLongestSubstring("abcabcbb"));

滑动窗口最大值❌

给定一个数组nums和一个整数k，返回滑动窗口（大小为k）中的最大值数组。

使用一个单调递减队列来解决这个问题。单调递减队列的头部是当前窗口中的最大值。

遍历数组nums：

当队列不为空且当前元素大于队列尾部元素时，将队列尾部元素弹出，以保持队列的单调递减性质。
将当前元素的索引加入队列。
如果队列头部元素的索引小于i - k + 1（表示窗口已经滑过了该元素），则将队列头部元素弹出。
当i >= k - 1（即窗口已经形成）时，将队列头部元素（当前窗口的最大值）加入结果数组。

function maxSlidingWindow(nums, k) {
    let result = [];
    let queue = [];
    for (let i = 0; i < nums.length; i++) {
        while (queue.length && nums[i] > nums[queue[queue.length - 1]]) {
            queue.pop();
        }
        queue.push(i);
        if (queue[0] < i - k + 1) {
            queue.shift();
        }
        if (i >= k - 1) {
            result.push(nums[queue[0]]);
        }
    }
    return result;
}
let nums = [1, 3, -1, -3, 5, 3, 6, 7];
let k = 3;
console.log(maxSlidingWindow(nums, k));

最小覆盖子串

给定一个字符串s和一个字符串t，找到s中包含t所有字符的最小子串。

使用两个指针left和right来表示滑动窗口的左右边界，初始都指向0。

用一个map（在JavaScript中可以使用Object）来统计字符串t中每个字符出现的次数（目标字符频率），同时用一个变量count来记录当前窗口中已经包含了多少个t中的字符。
移动right指针来扩大窗口，当窗口中包含了t中所有字符（count等于t的长度）时，尝试移动left指针来缩小窗口，同时更新最小子串的长度和内容。
在缩小窗口的过程中，要注意更新count和目标字符频率的统计。
重复上述过程，直到right指针到达字符串s的末尾。

function minWindow(s, t) {
    let left = 0;
    let right = 0;
    let minLen = Infinity;
    let minStr = "";
    let targetMap = {};
    let windowMap = {};
    let count = 0;
    for (let char of t) {
        targetMap[char] = (targetMap[char] || 0) + 1;
    }
    while (right < s.length) {
        let charRight = s[right];
        windowMap[charRight] = (windowMap[charRight] || 0) + 1;
        if (windowMap[charRight] <= targetMap[charRight]) {
            count++;
        }
        while (count === t.length) {
            if (right - left + 1 < minLen) {
                minLen = right - left + 1;
                minStr = s.slice(left, right + 1);
            }
            let charLeft = s[left];
            windowMap[charLeft]--;
            if (windowMap[charLeft] < targetMap[charLeft]) {
                count--;
            }
            left++;
        }
        right++;
    }
    return minStr;
}
let s = "ADOBECODEBANC";
let t = "ABC";
console.log(minWindow(s, t));

替换后的最长重复字符

给你一个字符串s和一个整数k，你可以将s中的任意字符替换成另外的字符，总共可替换k次。请你返回在替换k次之后，最长的重复字符子串长度。

使用两个指针left和right来表示滑动窗口的左右边界，初始都指向0。

用一个map（在JavaScript中可以使用Object）来统计窗口内每个字符出现的次数。
移动right指针来扩大窗口，同时记录窗口内出现次数最多的字符的频率maxCount。
当窗口的长度减去maxCount大于k时（表示需要替换的字符数超过了允许的k次），移动left指针来缩小窗口，同时更新窗口内的字符统计。
在整个过程中，记录窗口的最大长度，即为替换k次之后最长的重复字符子串长度。

function characterReplacement(s, k) {
    let left = 0;
    let right = 0;
    let maxCount = 0;
    let charCount = {};
    let maxLen = 0;
    while (right < s.length) {
        let charRight = s[right];
        charCount[charRight] = (charCount[charRight] || 0) + 1;
        maxCount = Math.max(maxCount, charCount[charRight]);
        if (right - left + 1 - maxCount > k) {
            let charLeft = s[left];
            charCount[charLeft]--;
            left++;
        }
        maxLen = Math.max(maxLen, right - left + 1);
        right++;
    }
    return maxLen;
}
let s = "ABAB";
let k = 2;
console.log(characterReplacement(s, k));

字符串的排列

给定两个字符串s1和s2，写一个函数来判断s2是否包含s1的排列。如果是，返回true；否则，返回false。

首先统计s1中每个字符出现的次数，存储在一个map（在JavaScript中可以使用Object）中，作为目标字符频率。
使用两个指针left和right来表示滑动窗口的左右边界，初始都指向0。
用一个map来统计窗口内每个字符出现的次数。
移动right指针来扩大窗口，同时比较窗口内的字符频率和目标字符频率是否一致。
当窗口的长度等于s1的长度时，检查窗口内的字符频率是否与目标字符频率完全一致，如果是，则返回true。
当窗口长度大于s1的长度时，移动left指针来缩小窗口，同时更新窗口内的字符统计。
如果遍历完s2后没有找到符合条件的窗口，则返回false。

function checkInclusion(s1, s2) {
    let left = 0;
    let right = 0;
    let s1Len = s1.length;
    let s2Len = s2.length;
    if (s1Len > s2Len) {
        return false;
    }
    let targetMap = {};
    let windowMap = {};
    for (let char of s1) {
        targetMap[char] = (targetMap[char] || 0) + 1;
    }
    while (right < s2Len) {
        let charRight = s2[right];
        windowMap[charRight] = (windowMap[charRight] || 0) + 1;
        if (right - left + 1 === s1Len) {
            let isPermutation = true;
            for (let char in targetMap) {
                if (windowMap[char]!== targetMap[char]) {
                    isPermutation = false;
                    break;
                }
            }
            if (isPermutation) {
                return true;
            }
            let charLeft = s2[left];
            windowMap[charLeft]--;
            left++;
        }
        right++;
    }
    return false;
}

分治法

将复杂问题拆分为多个性质相同但规模更小的子问题
1、分，拆分小问题
2、治，对子问题分别进行处理
3、合，将子问题进行合并，从而得到原问题

解题思路快查

合并 K 个排序链表**：可以先将链表两两合并，然后将合并后的链表继续两两合并，直到最终合并成一个链表。每次合并两个链表的过程就是一个小规模的子问题。
搜索二维矩阵**：可以将二维矩阵看作是一个有序的一维数组，利用二分查找的思想来搜索目标元素。或者将矩阵分成四个子矩阵，分别在子矩阵中搜索，这体现了分治法的思想。

场景总结：

将复杂问题拆分为多个性质相同但规模更小的子问题，分别解决子问题后再合并结果得到原问题的解。常用于排序算法（如归并排序）、计算几何问题（如平面最近点对问题）、大整数乘法等场景。

常见算法题解题思路 - 归并排序（分治法实现）：

分：如果数组长度小于等于 1，直接返回该数组，因为它已经是有序的。否则，计算数组的中间索引，将数组分成左右两部分。
治：递归地对左右两部分分别调用归并排序函数，得到两个有序的子数组。
合：创建一个空的结果数组，使用两个指针分别遍历两个有序子数组，比较指针所指元素的大小，将较小的元素放入结果数组，直到其中一个子数组遍历完。然后将另一个子数组剩余的元素全部添加到结果数组。返回合并后的有序数组。
代码示例（以归并排序为例）：

function mergeSort(arr) {
    if (arr.length <= 1) 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 merged = [];
    let i = 0;
    let j = 0;
    while (i < left.length && j < right.length) {
        if (left[i] < right[j]) {
            merged.push(left[i]);
            i++;
        } else {
            merged.push(right[j]);
            j++;
        }
    }
    return merged.concat(left.slice(i)).concat(right.slice(j));
}

let arrayToSort = [5, 3, 8, 4, 7];
console.log(mergeSort(arrayToSort));

回溯法

概念

回溯法是一种用于搜索问题解空间的算法策略。它通过深度优先搜索的方式遍历解空间树，在搜索过程中，当发现当前路径不可能达到目标解时，就回溯到上一步，尝试其他可能的路径。回溯法通常用于解决组合问题、排列问题、子集问题等需要列举出所有可能解的情况。

常见应用场景

组合问题：

问题描述：例如给定一组数字nums和一个目标数字k，找出所有和为k的数字组合。
解题思路：使用回溯法，从空组合开始，逐步添加数字。在每一步中，尝试添加下一个数字，如果添加后超过目标k或者不符合其他条件，则回溯，撤销上一步的添加操作，尝试其他数字。通过递归实现深度优先搜索解空间，维护一个当前组合的列表和一个起始索引，以避免重复的组合。
代码示例（简单的组合求和示例）：

let result = [];
function combinationSum(candidates, target) {
    backtrack(candidates, target, [], 0);
    return result;
}
function backtrack(candidates, target, path, start) {
    if (target === 0) {
        result.push([...path]);
        return;
    }
    for (let i = start; i < candidates.length; i++) {
        if (candidates[i] <= target) {
            path.push(candidates[i]);
            backtrack(candidates, target - candidates[i], path, i);
            path.pop();
        }
    }
}
let candidates = [2, 3, 6, 7];
let target = 7;
console.log(combinationSum(candidates, target));

排列问题：

问题描述：给定一个数组nums，输出它的所有全排列。
解题思路：对于排列问题，每个位置都可以放置数组中的任意一个未使用过的元素。通过回溯，在每一层递归中，遍历数组，将未使用的元素放置在当前位置，然后继续下一层递归，直到所有位置都填充完毕，得到一个排列。使用一个布尔数组来标记元素是否已经被使用，以避免重复使用同一个元素。
代码示例（生成全排列示例）：

let result = [];
function permute(nums) {
    let used = new Array(nums.length).fill(false);
    backtrackPermute(nums, [], used);
    return result;
}
function backtrackPermute(nums, path, used) {
    if (path.length === nums.length) {
        result.push([...path]);
        return;
    }
    for (let i = 0; i < nums.length; i++) {
        if (!used[i]) {
            used[i] = true;
            path.push(nums[i]);
            backtrackPermute(nums, path, used);
            path.pop();
            used[i] = false;
        }
    }
}
let nums = [1, 2, 3];
console.log(permute(nums));

子集问题：

问题描述：给定一个集合，求出它的所有子集。
解题思路：通过回溯，从空子集开始，在每一步中，可以选择将当前元素加入子集或者不加入，然后继续下一层递归。这样可以生成所有可能的子集。同样，可以使用一个索引来控制遍历的起始位置，以避免重复生成子集。
代码示例（生成子集示例）：

let result = [];
function subsets(nums) {
    backtrackSubsets(nums, [], 0);
    return result;
}
function backtrackSubsets(nums, path, start) {
    result.push([...path]);
    for (let i = start; i < nums.length; i++) {
        path.push(nums[i]);
        backtrackSubsets(nums, path, i + 1);
        path.pop();
    }
}
let nums = [1, 2, 3];
console.log(subsets(nums));

回溯法的一般步骤

定义解空间：确定问题的解空间结构，例如是排列、组合还是其他形式的解空间。
确定状态空间树：将解空间表示为一棵树，每个节点代表一个状态，边代表状态之间的转移。
深度优先搜索：使用递归实现深度优先搜索解空间树。
剪枝条件：在搜索过程中，根据问题的约束条件确定剪枝条件，当满足剪枝条件时，回溯到上一层，避免不必要的搜索。
记录解：当找到一个满足条件的解时，将其记录下来。

并查集

概念

并查集是一种处理不相交集合的合并与查询问题的数据结构，它支持两种主要操作：

合并（Union）：将两个不相交的集合合并为一个集合。
查找（Find）：查询某个元素属于哪个集合。

并查集通常使用树结构来实现，每个集合是一棵树，树的根节点代表整个集合。

应用场景

连通性问题：
- 问题描述：例如在一个无向图中，判断两个节点是否连通，或者计算图中有多少个连通分量。
- 解题思路：将每个节点初始化为一个独立的集合。对于图中的每条边，使用并查集的合并操作将边连接的两个节点所在的集合合并。当需要判断两个节点是否连通时，通过查找操作判断它们是否属于同一个集合。若要计算连通分量个数，则统计根节点的个数，每个根节点代表一个连通分量。
动态连通性问题（如动态添加边的图）：在动态场景下，不断有新的边加入图中，需要实时维护图的连通性信息。并查集可以高效地处理这种情况，每次添加新边时，执行合并操作，然后可以随时查询任意两个节点的连通性。

实现方式及操作步骤

数据结构表示：

可以使用一个数组parent来表示并查集，其中parent[i]表示元素i的父节点。初始时，parent[i]=i，即每个元素自己是一个集合的根。

查找（Find）操作：

目的是找到元素所在集合的根节点。
可以通过不断向上查找父节点，直到找到parent[x] = x的节点，这个节点就是根。
路径压缩优化：在查找过程中，可以将查找路径上的节点直接指向根节点，这样可以减少后续查找的时间复杂度。例如：

function find(x) {
    if (parent[x]!== x) {
        parent[x] = find(parent[x]);
    }
    return parent[x];
}

合并（Union）操作：

先通过查找操作找到两个元素所在集合的根节点。
然后将其中一个根节点的父节点设置为另一个根节点，实现两个集合的合并。通常采用按秩合并（将较小树的根连接到较大树的根）来优化，以避免树的高度过高。例如：

function union(x, y) {
    let rootX = find(x);
    let rootY = find(y);
    if (rootX!== rootY) {
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
    }
}

时间复杂度分析

在不进行优化的情况下，并查集的单次操作时间复杂度接近线性。但通过路径压缩和按秩合并优化后，每次查找和合并操作的平均时间复杂度接近常数级别，对于n次操作的时间复杂度可以近似看作 $O(n\alpha(n))$ ，其中 $\alpha(n)$ 是阿克曼函数的反函数，增长极其缓慢，在实际应用中可认为是常数。

博弈问题

概念

博弈问题是指两个或多个参与者（玩家）按照一定的规则进行决策，每个决策都会影响游戏的状态和结果，参与者的目标是最大化自己的利益或者达到某种最优的局面。这类问题通常涉及到策略选择、状态转移以及对对手行为的推测。

常见类型及场景

石子游戏

问题描述与解题思路：这里假设是一种简单的石子游戏，比如有一堆石子，两人轮流取，每次可以取 1 - 3 颗石子，取到最后一颗石子的人获胜。我们可以通过分析石子总数与每次可取数量的关系来确定胜负策略。如果石子总数除以每次可取数量的最大数与最小数之和（这里是 4）有余数，先手有获胜策略，因为先手可以控制每次两人取石子的总数，使得最后自己取到最后一颗石子。
代码实现：

// 判断先手是否能赢
function stoneGame(n) {
    return n % 4!== 0;
}
// 测试示例，比如有7颗石子
console.log(stoneGame(7));

预测赢家

问题描述与解题思路：给定一个整数数组，两个玩家轮流从数组的两端选择一个数字，玩家的得分是他选择的所有数字的总和，最后得分高的玩家获胜，我们要预测先手是否能成为赢家。这里使用动态规划来解决。我们创建一个二维dp数组，dp[i][j]表示在数组区间[i, j]中先手能获得的最大得分与后手能获得的最大得分的差值。通过从小区间逐步计算到大区间来填充dp数组，最后根据dp[0][nums.length - 1]的值判断先手是否能赢。初始化长度为 1 的子数组情况，先手取走唯一的数，差值就是这个数。然后对于长度大于 1 的子数组，先手选择取左边的数或者右边的数，取两者中的较大值（即考虑后手的最优选择后，先手能得到的最大差值）。
代码实现：

function PredictTheWinner(nums) {
    const n = nums.length;
    const dp = new Array(n).fill(0).map(() => new Array(n).fill(0));
    // 初始化长度为1的子数组情况，先手取走唯一的数，差值就是这个数
    for (let i = 0; i < n; i++) {
        dp[i][i] = nums[i];
    }
    // 从长度为2的子数组开始计算
    for (let len = 2; len <= n; len++) {
        for (let start = 0; start <= n - len; start++) {
            const end = start + len - 1;
            // 先手选择取左边的数或者右边的数，取两者中的较大值
            dp[start][end] = Math.max(
                nums[start] - dp[start + 1][end],
                nums[end] - dp[start][end - 1]
            );
        }
    }
    return dp[0][n - 1] >= 0;
}
// 测试示例
console.log(PredictTheWinner([1, 5, 2]));

Nim 游戏

问题描述与解题思路：有k堆物品（这里用数组表示每堆物品数量），两个玩家轮流从任意一堆中取走任意数量的物品（至少取 1 个），最后取光物品的玩家获胜。通过计算所有堆物品数量的异或和来判断胜负。若异或和为 0，则后手必胜；否则，先手必胜。这是因为异或和为 0 代表一种平衡状态，任何操作都会打破平衡，而后手可以通过相应操作恢复平衡，直到最后获胜。
代码实现：

function nimGame(nums) {
    let xorSum = 0;
    for (let num of nums) {
        xorSum ^= num;
    }
    return xorSum!== 0;
}
// 测试示例，假设有3堆物品，数量分别为3、4、5
const gameNums = [3, 4, 5];
console.log(nimGame(gameNums));

猜数字大小

问题描述与解题思路：给定一个目标数字（这里假设在一个范围内），玩家猜测一个数字，系统会提示猜测的数字是大了还是小了，要求用最少的次数猜中目标数字。使用二分查找算法，设定一个搜索区间，初始时为整个可能的数字范围，每次猜测区间的中间值，根据提示缩小搜索区间。如果猜的数字大了，就将搜索区间的上界调整为猜测值减 1；如果猜的数字小了，就将搜索区间的下界调整为猜测值加 1。重复这个过程，直到猜中目标数字。
代码实现：

// 假设目标数字是6，这里只是模拟猜数字过程，实际使用时目标数字是未知的
function guessNumber() {
    let low = 1;
    let high = 10; // 假设猜的范围是1 - 10
    while (low <= high) {
        let mid = Math.floor((low + high) / 2);
        if (mid === 6) { // 这里假设目标是6，实际需要根据比较结果来调整
            return mid;
        } else if (mid < 6) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
}
console.log(guessNumber());

这是一份面试速查表，涵盖了面试中好代码的三大支柱、面试官关注的技能、解决问题的步骤、好代码的检查清单以及解决问题的启发式方法等内容，旨在帮助面试者在面试中更好地表现，以下是详细总结：

最后编辑于：2024.11.11 16:21:59

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 206,968评论 6赞 482
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 88,601评论 2赞 382
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 153,220评论 0赞 344
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 55,416评论 1赞 279
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 64,425评论 5赞 374
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 49,144评论 1赞 285
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 38,432评论 3赞 401
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 37,088评论 0赞 261
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 43,586评论 1赞 300
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 36,028评论 2赞 325
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 38,137评论 1赞 334
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,783评论 4赞 324
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 39,343评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 30,333评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,559评论 1赞 262
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 45,595评论 2赞 355
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,901评论 2赞 345

基于《算法通关之路》的前端算法学习总结

一、个人掌握分析

一、知识理解层面

二、实践应用层面

三、问题解决层面

四、创新与拓展层面

二分查找⭐⭐

深度优先和广度优先⭐⭐

贪心算法 ⭐

双指针 ⭐⭐⭐

滑动窗口 ⭐⭐⭐

分治法 ⭐⭐

回溯法 ⭐

回文⭐⭐

查并集 ⭐

博弈问题

股票问题

位运算

设计

二、算法面试 注意事项

好代码的三大支柱

面试官关注的技能

解决问题的步骤

好代码检查清单

解决问题的启发式方法

通用要点

三、准备工作

js 算法中常用的操作

数组操作

遍历

查找

排序

修改与添加

字符串操作

遍历

拼接与截取

映射（Map）和集合（Set）操作

Map

Set

函数操作

函数作为参数 如array.forEach(callback)。

递归函数 如

while 语句

一、概念

二、应用场景

（一）数值计算

（二）数组操作

（三）字符串处理

（四）链表操作

四、基础定义

递归

定义和原理

应用场景举例

自己的理解总结

迭代

相关算法

动态规划问题的求解

五、算法与数据结构总结

<span id="二叉树">二叉树</span>

场景

<span id="深度优先搜索（DFS）">深度优先搜索（DFS）</span>

1. 概念

2. 实现方式（以树结构为例）

3. 应用场景

图的连通性检测：

生成树问题：

拓扑排序（对于有向无环图）：

递归的前序、中序和后序

前序遍历顺序

中序遍历顺序

后序遍历顺序

广度优先搜索（BFS）

1. 概念

2. 实现方式（以树结构为例）

3. 应用场景

二分查找

场景总结：

常见算法题解题思路

代码示例：

动态规划

二、算法面试注意事项

映射（`Map`）和集合（`Set`）操作

`Map`

`Set`

函数作为参数如`array.forEach(callback)`。

递归函数如

`dp[i - 1] + dp[i - 2]`

`dp[i] = Math.max(dp[i - 1], dp[i - 2]+nums[i]);`

`dp[i][j] = dp[i - 1][j]+dp[i][j - 1]`

子集合排序，比对current 和子集的start,如果大于则说明重叠，并更新current 为end，并计数count