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

2024-10-30  本文已影响0人  Ricoywang

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

一、个人掌握分析

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

一、知识理解层面

  1. 算法原理理解

    • 准确性：能够准确阐述常见算法（如排序算法中的快速排序、归并排序，搜索算法中的深度优先搜索、广度优先搜索等）的基本原理、步骤和时间复杂度、空间复杂度分析。例如，是否能清晰地解释快速排序是如何通过选择一个基准值将数组分为两部分，并递归地对这两部分进行排序的。
    • 深度：对于复杂算法（如动态规划、贪心算法在复杂场景下的应用），理解其背后的数学模型和理论依据。比如理解动态规划中的最优子结构性质和重叠子问题性质，以及它们如何决定算法的设计和实现。

  2. 算法复杂度分析

    • 时间复杂度计算：对于给定的算法代码或算法描述，能够准确计算其时间复杂度，包括最好情况、最坏情况和平均情况（如果不同）。例如，对于一个嵌套循环的算法，能正确分析出其时间复杂度是多项式级还是指数级，并给出具体的大 O 表示，如O(n^2)或O(2^n)。
    • 空间复杂度计算：准确评估算法在执行过程中所需的额外空间，考虑数据结构的存储需求和递归调用栈等因素。比如判断一个递归算法是否会因大量递归调用导致栈溢出问题，以及如何优化其空间复杂度。

二、实践应用层面

  1. 算法实现能力

    • 代码准确性：能够用至少一种编程语言（如 Python、Java、C++等）准确实现各种算法，包括处理边界情况和异常情况。例如，在实现二叉树的遍历算法时，正确处理空树的情况；在实现排序算法时，确保对于相同元素的数组也能正确排序。
    • 代码效率优化：能够对实现的算法代码进行性能优化，如减少不必要的计算、优化数据结构的使用等。例如，在实现搜索算法时，使用合适的数据结构（如哈希表）来降低查找时间复杂度；在递归算法中，通过尾递归优化或迭代方式改进以减少栈空间的使用。

  2. 算法选择与应用场景匹配

    • 合适算法选择：面对实际问题，能够从众多算法中选择最合适的算法来解决问题。例如，对于需要快速查找元素是否存在的问题，能选择哈希表相关算法；对于图的遍历问题，根据图的特点（有向/无向、是否有环等）选择深度优先搜索或广度优先搜索。
    • 应用场景拓展：理解算法在不同领域和场景中的变体和应用。比如知道排序算法在数据库索引、数据可视化等场景中的应用；了解搜索算法在游戏开发中的路径搜索、社交网络中的关系查找等场景的使用方式。

三、问题解决层面

  1. 问题分析与拆解能力

    • 问题理解：对于给定的算法相关问题，能够快速理解问题的本质和要求，识别出问题的关键特征和约束条件。例如，对于一个复杂的组合优化问题，能从中提取出元素、目标函数和约束条件等关键信息。
    • 问题拆解：将复杂问题分解为可通过已知算法解决的子问题，并确定子问题之间的关系。比如将一个大型图的最短路径问题分解为多个小区域的最短路径问题，然后考虑如何合并这些子问题的解。

  2. 调试与改进能力

    • 错误定位：当算法实现出现错误（如结果不正确、性能不达标等）时，能够通过调试工具（如断点调试、打印中间结果等）快速定位问题所在，确定是算法逻辑错误、边界条件处理不当还是其他原因导致的。
    • 改进策略制定：根据问题诊断结果，制定有效的改进策略，可能包括修改算法实现、调整数据结构或更换算法等。例如，如果发现某个排序算法在处理大量数据时性能不佳，能够分析是比较操作过多还是数据移动过于频繁的问题，并针对性地改进。

四、创新与拓展层面

  1. 算法改进与创新能力

    • 现有算法改进：能够在理解现有算法的基础上，提出对算法的改进方案，以提高算法的性能、降低复杂度或增强算法的适应性。例如，对经典的排序算法提出一种新的划分策略来提高排序速度，或者对搜索算法提出一种新的启发式规则来减少搜索空间。
    • 新算法设计：对于特定的新问题场景，能够设计全新的算法来解决问题，并证明其正确性和分析其复杂度。这需要对算法设计的基本原理和方法有深入的理解，以及创新思维能力。

  2. 算法知识更新与拓展能力

    • 新知识学习：关注算法领域的最新发展动态，能够主动学习新出现的算法、数据结构和相关技术，并理解其原理和应用价值。例如，及时了解机器学习算法在大数据和人工智能领域的新应用和改进。
    • 跨领域融合：能够将算法知识与其他领域（如数学、物理、计算机图形学等）的知识相结合，拓展算法的应用范围和解决问题的能力。比如将图算法应用于电路设计中的网络分析，或者将数值计算算法用于物理模拟中的方程求解。

二分查找⭐⭐

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

深度优先和广度优先⭐⭐

贪心算法 ⭐

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

双指针 ⭐⭐⭐

滑动窗口 ⭐⭐⭐

分治法 ⭐⭐

回溯法 ⭐

回文⭐⭐

查并集 ⭐

博弈问题

股票问题

位运算

设计

二、算法面试 注意事项

好代码的三大支柱

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

面试官关注的技能

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

解决问题的步骤

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

好代码检查清单

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

解决问题的启发式方法

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

通用要点

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

三、准备工作

js 算法中常用的操作

数组操作

遍历

查找

排序

修改与添加

字符串操作

遍历

拼接与截取

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

Map

Set

函数操作

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

递归函数 如

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

while 语句

一、概念

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

二、应用场景

（一）数值计算

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

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));

（二）数组操作

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)); 

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));

（三）字符串处理

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')); 

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));

（四）链表操作

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); 

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));

四、基础定义

❌

递归

定义和原理

应用场景举例

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));

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、4、5、3、6、7。

中序遍历顺序

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

后序遍历顺序

所以后序遍历结果为：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. 应用场景

二分查找

场景总结：

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

常见算法题解题思路

代码示例：

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));

动态规划

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

解题思路快查

场景总结：

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

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

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]);
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]
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];
}

零钱兑换问题 ❌

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;
}

贪心算法

解题思路快查

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));

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

遍历小孩，两个指针，如果当前饼干不满足小孩则移动到下个饼干
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 则满足
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));

任务调度器问题 ❌

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，保证最小糖果消耗的同时，也满足分发糖果的要求。在分发糖果问题中，我们采用了两次贪心的过程。从左到右遍历保证每个孩子相对于左边孩子糖果数满足条件，从右到左遍历保证相对于右边孩子的条件。
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
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));

双指针

适用数据结构

字符串，数组，链表

解题思路快查

场景总结：

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

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

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

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"));

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

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;
}

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

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;
}

环形链表

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;
}

无重复字符串的最长子串

/**
 * @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
};

滑动窗口

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

场景总结：

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

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

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：

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。

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。

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。

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、合，将子问题进行合并，从而得到原问题

解题思路快查

场景总结：

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

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

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));

回溯法

概念

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

常见应用场景

组合问题：

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));

排列问题：

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));

回溯法的一般步骤

并查集

概念

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

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

应用场景

实现方式及操作步骤

数据结构表示：

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

查找（Find）操作：

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]++;
        }
    }
}

时间复杂度分析

博弈问题

概念

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

常见类型及场景

石子游戏

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

预测赢家

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 游戏

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));

猜数字大小

// 假设目标数字是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());

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

上一篇 下一篇

猜你喜欢

热点阅读