网站导航
> 文章列表 > JavaScript前端面试常考算法模板

JavaScript前端面试常考算法模板

网友: 文章列表 2024-03-22 00:56:04

JavaScript前端面试常考算法模板

一、二分查找

使用条件

  • 排序数组 (30-40%是二分)
  • 当面试官要求你找一个比 O(n) 更小的时间复杂度算法的时候(99%)
  • 找到数组中的一个分割位置，使得左半部分满足某个条件，右半部分不满足(100%)
  • 找到一个最大/最小的值使得某个条件被满足(90%)

复杂度

  • 时间复杂度： O(log(n))
  • 空间复杂度： O(1)
function binarySearch(nums, target) {// corner case 处理if (!nums || nums.length === 0) {return -1;}let start = 0, end = nums.length - 1;// 用 start + 1 < end 而不是 start < end 的目的是为了避免死循环// 在 first position of target 的情况下不会出现死循环// 但是在 last position of target 的情况下会出现死循环// 样例： nums = [1， 1] target = 1// 为了统一模板，我们就都采用 start + 1 < end，就保证不会出现死循环while (start + 1 < end) {// Math.floor() 确保 mid 是整数let mid = Math.floor((start + end) / 2);// > , =, < 的逻辑先分开写， 然后在看看= 的情况是否能合并到其他分支里if (nums[mid] < target) {start = mid;} else if (nums[mid] === target) {end = mid;} else {end = mid;}}// 因为上面的循环退出条件是 start + 1 < end// 因此这里循环结束的时候， start 和 end 的关系是相邻关系（1 和 2， 3 和 4 这种）// 因此需要再单独判断 start 和 end 这两个数谁是我们要的答案// 如果是找 first position of target 就先看 start，否则就先看 endif (nums[start] === target) {return start;}if (nums[end] === target) {return end;}return -1;
}

二、双指针

使用条件

  • 滑动窗口 (90%)
  • 时间复杂度要求 O(n) (80%是双指针)
  • 要求原地操作，只可以使用交换，不能使用额外空间 (80%)
  • 有子数组 subarray /子字符串 substring 的关键词 (50%)
  • 有回文 Palindrome 关键词(50%)

复杂度

  • 时间复杂度： O(n)
    • 时间复杂度与最内层循环主体的执行次数有关
    • 与有多少重循环无关
  • 空间复杂度： O(1)
    • 只需要分配两个指针的额外内存

1、相向双指针

function partition(A, start, end) {if (start >= end) {return;}let left = start,right = end;const pivot = A[Math.floor((start + end) / 2)];while (left <= right) {while (left <= right && A[left] < pivot) {left++;}while (left <= right && A[right] > pivot) {right--;}if (left <= right) {[A[left], A[right]] = [A[right], A[left]];left++;right--;}}
}

2、背向双指针

function backwardPointers(s, position) {let left = position,right = position + 1;while (left >= 0 && right < s.length) {if (left 可以停下来了 && right 可以停下来了) {break;}left--;right++;}
}

3、同向双指针

function forwardPointers(n) {let j = 0;for (let i = 0; i < n; i++) {while (j < n && !满足条件(i, j)) {j++;}if (满足条件(i, j)) {处理(i, j);}}
}

4、合并双指针

function merge(list1, list2) {const newList = [];let i = 0,j = 0;while (i < list1.length && j < list2.length) {if (list1[i] < list2[j]) {newList.push(list1[i]);i++;} else {newList.push(list2[j]);j++;}}while (i < list1.length) {newList.push(list1[i]);i++;}while (j < list2.length) {newList.push(list2[j]);j++;}return newList;
}

三、二叉树分治

使用条件

  • 二叉树相关的问题 (99%)
  • 可以一分为二去分别处理之后再合并结果 (100%)
  • 数组相关的问题 (10%)

复杂度

时间复杂度 O(n)
空间复杂度 O(n) (含递归调用的栈空间最大耗费)

function divide_conquer(root) {// 递归出口if (!root) {return ...;}// 处理左子树let left_result = divide_conquer(root.left);// 处理右子树let right_result = divide_conquer(root.right);// 合并答案let result = merge(left_result, right_result); // 这里需要自己实现merge函数return result;
}

四、二叉搜索树非递归 BST

使用条件

  • 用非递归的方式（Non-recursion / Iteration） 实现二叉树的中序遍历
  • 常用于 BST 但不仅仅可以用于 BST

复杂度

时间复杂度 O(n)
空间复杂度 O(n)

function inorder_traversal(root) {if (!root) {return [];}// 创建一个 dummy node，右指针指向 root// 并放到 stack 里，此时 stack 的栈顶 dummy 是 iterator 的当前位置let dummy = new TreeNode(0);dummy.right = root;let stack = [dummy];let inorder = [];// 每次将 iterator 挪到下一个点，也就是调整 stack 使得栈顶到下一个点while (stack.length) {let node = stack.pop();if (node.right) {node = node.right;while (node) {stack.push(node);node = node.left;}}if (stack.length) {inorder.push(stack[stack.length - 1]);}}return inorder;
}

五、宽度优先搜索 BFS

使用条件

  • 拓扑排序(100%)
  • 出现连通块的关键词(100%)
  • 分层遍历(100%)
  • 简单图最短路径(100%)
  • 给定一个变换规则，从初始状态变到终止状态最少几步(100%)

复杂度

  • 时间复杂度： O(n + m)
    • n 是点数, m 是边数
  • 空间复杂度： O(n)
function get_indegrees(nodes) {let counter = {};nodes.forEach(node => {counter[node] = 0;});nodes.forEach(node => {node.get_neighbors().forEach(neighbor => {counter[neighbor]++;});});return counter;
}function topological_sort(nodes) {// 统计入度let indegrees = get_indegrees(nodes);// 所有入度为 0 的点都放到队列里let queue = [];nodes.forEach(node => {if (indegrees[node] === 0) {queue.push(node);}});// 用 BFS 算法一个个把点从图里挖出来let topo_order = [];while (queue.length) {let node = queue.shift();topo_order.push(node);node.get_neighbors().forEach(neighbor => {indegrees[neighbor]--;if (indegrees[neighbor] === 0) {queue.push(neighbor);}});}// 判断是否有循环依赖if (topo_order.length !== nodes.length) {return "有循环依赖(环),没有拓扑序";}return topo_order;
}

六、深度优先搜索 DFS

使用条件

  • 找满足某个条件的所有方案 (99%)
  • 二叉树 Binary Tree 的问题 (90%)
  • 组合问题(95%)
    • 问题模型：求出所有满足条件的“组合”
    • 判断条件： 组合中的元素是顺序无关的
  • 排列问题 (95%)
    • 问题模型：求出所有满足条件的“排列”
    • 判断条件： 组合中的元素是顺序“相关”的。

不要用 DFS 的场景

  • 连通块问题（一定要用 BFS，否则 StackOverflow）
  • 拓扑排序（一定要用 BFS，否则 StackOverflow）
  • 一切 BFS 可以解决的问题复杂度

时间复杂度

  • O(方案个数 * 构造每个方案的时间)
    • 树的遍历 ： O(n)
    • 排列问题 ： O(n! * n)
    • 组合问题 ： O(2^n * n)
function dfs(参数列表) {if (递归出口) {记录答案;return;}for (所有的拆解可能性) {修改所有的参数;dfs(参数列表);还原所有被修改过的参数;}return something; // 如果需要的话，很多时候不需要 return 值除了分治的写法
}

七、动态规划

使用条件

使用场景：

  • 求方案总数(90%)
  • 求最值(80%)
  • 求可行性(80%)

不适用的场景：

  • 找所有具体的方案（准确率 99%）
  • 输入数据无序(除了背包问题外，准确率 60%~70%)
  • 暴力算法已经是多项式时间复杂度（准确率 80%）

动态规划四要素(对比递归的四要素)：

  • 状态 (State) – 递归的定义
  • 方程 (Function) – 递归的拆解
  • 初始化 (Initialization) – 递归的出口
  • 答案 (Answer) – 递归的调用

几种常见的动态规划：

  • 背包型
    • 给出 n 个物品及其大小,问是否能挑选出一些物品装满大小为 m 的背包
    • 题目中通常有“和”与“差”的概念，数值会被放到状态中
    • 通常是二维的状态数组，前 i 个组成和为 j 状态数组的大小需要开 (n + 1) * (m + 1)
  • 区间型
    • 题目中有 subarray / substring 的信息
      • 大区间依赖小区间
      • 用 dp[i][j] 表示数组/字符串中 i, j 这一段区间的最优值/可行性/方案总数
  • 匹配型
    • 通常给出两个字符串
    • 两个字符串的匹配值依赖于两个字符串前缀的匹配值
    • 字符串长度为 n,m 则需要开 (n + 1) x (m + 1) 的状态数组
    • 要初始化 dp[i][0] 与 dp[0][i]
    • 通常都可以用滚动数组进行空间优化
  • 划分型
    • 是前缀型动态规划的一种, 有前缀的思想
    • 如果指定了要划分为几个部分：
      • dp[i][j] 表示前 i 个数/字符划分为 j 个 部分的最优值/方案数/可行性
    • 如果没有指定划分为几个部分:
      • dp[i] 表示前 i 个数/字符划分为若干个 部分的最优值/方案数/可行性
  • 接龙型
    • 通常会给一个接龙规则， 问你最长的龙有多长
    • 状态表示通常为: dp[i] 表示以坐标为 i 的元素结尾的最长龙的长度
    • 方程通常是: dp[i] = max{dp[j] + 1}, j 的后面可以接上 i
    • LIS 的二分做法选择性的掌握，但并不是所有的接龙型 DP 都可以用二分来优化

复杂度

  • 时间复杂度:
    • O(状态总数 * 每个状态的处理耗费)
    • 等于 O(状态总数 * 决策数)
  • 空间复杂度：
    • O(状态总数) (不使用滚动数组优化)
    • O(状态总数 / n)(使用滚动数组优化, n 是被滚动掉的那一个维度)

八、堆

使用条件

  • 找最大值或者最小值(60%)
  • 找第 k 大(pop k 次 复杂度 O(nlogk))(50%)
  • 要求 logn 时间对数据进行操作(40%)

堆不能解决的问题

  • 查询比某个数大的最小值/最接近的值（平衡排序二叉树 Balanced BST 才可以解决）
  • 找某段区间的最大值最小值（线段树 SegmentTree 可以解决）
  • O(n)找第 k 大 (使用快排中的 partition 操作)
class ValueIndexPair {constructor(val, index) {this.val = val;this.index = index;}
}
class Heap {constructor() {this.minheap = new PriorityQueue((p1, p2) => p1.val - p2.val);this.deleteSet = new Set();}push(index, val) {this.minheap.add(new ValueIndexPair(val, index));}lazyDeletion() {while (this.minheap.size() !== 0 && this.deleteSet.has(this.minheap.peek().index)) {const pair = this.minheap.poll();this.deleteSet.delete(pair.index);}}top() {this.lazyDeletion();return this.minheap.peek();}pop() {this.lazyDeletion();this.minheap.poll();}delete(index) {this.deleteSet.add(index);}isEmpty() {return this.minheap.size() === 0;}
}

九、并查集

使用条件

  • 需要查询图的连通状况的问题
  • 需要支持快速合并两个集合的问题

复杂度

  • 时间复杂度 union O(1), find O(1)
  • 空间复杂度 O(n)
class UnionFind {constructor() {this.father = new Map();this.sizeOfSet = new Map();this.numOfSet = 0;}add(x) {if (this.father.has(x)) {return;}this.father.set(x, null);this.sizeOfSet.set(x, 1);this.numOfSet++;}merge(x, y) {const rootX = this.find(x);const rootY = this.find(y);if (rootX !== rootY) {this.father.set(rootX, rootY);this.numOfSet--;this.sizeOfSet.set(rootY, this.sizeOfSet.get(rootX) + this.sizeOfSet.get(rootY));}}find(x) {let root = x;while (this.father.get(root) !== null) {root = this.father.get(root);}while (x !== root) {const originalFather = this.father.get(x);this.father.set(x, root);x = originalFather;}return root;}isConnected(x, y) {return this.find(x) === this.find(y);}getNumOfSet() {return this.numOfSet;}getSizeOfSet(x) {return this.sizeOfSet.get(this.find(x));}
}

十、字典树

使用条件

  • 需要查询包含某个前缀的单词/字符串是否存在
  • 字符矩阵中找单词的问题

复杂度

  • 时间复杂度 O(L) 增删查改
  • 空间复杂度 O(N * L) N 是单词数， L 是单词长度
class TrieNode {// 儿子节点children = new Map();// 根节点到该节点是否是一个单词isWord = false;// 根节点到该节点的单词是什么word = null;constructor() {}
}class Trie {constructor() {this.root = new TrieNode();}getRoot() {return this.root;}// 插入单词insert(word) {let node = this.root;for (let i = 0; i < word.length; i++) {let letter = word.charAt(i);if (!node.children.has(letter)) {node.children.set(letter, new TrieNode());}node = node.children.get(letter);}node.isWord = true;node.word = word;}// 判断单词 word 是不是在字典树中hasWord(word) {let L = word.length;let node = this.root;for (let i = 0; i < L; i++) {let letter = word.charAt(i);if (!node.children.has(letter)) {return false;}node = node.children.get(letter);}return node.isWord;}// 判断前缀 prefix 是不是在字典树中hasPrefix(prefix) {let L = prefix.length;let node = this.root;for (let i = 0; i < L; i++) {let letter = prefix.charAt(i);if (!node.children.has(letter)) {return false;}node = node.children.get(letter);}return true;}
}

十一、LRU 缓存

复杂度

  • 时间复杂度 get O(1), set O(1)
  • 空间复杂度 O(n)
class LRUCache {// 单链表节点class ListNode {constructor(key, val) {this.key = key;this.val = val;this.next = null;}}// cache 的最大容量constructor(capacity) {this.capacity = capacity;this.size = 0;this.keyToPrev = new Map();// dummy 点的 key 和 value 随意this.dummy = new ListNode(0, 0);this.tail = this.dummy;}// 将 key 节点移动到尾部moveToTail(key) {const prev = this.keyToPrev.get(key);const curt = prev.next;// 如果 key 节点已经再尾部，无需移动if (this.tail === curt) {return;}// 从链表中删除 key 节点prev.next = prev.next.next;this.tail.next = curt;curt.next = null;// 分两种情况更新当前节点下一个节点对应的前导节点为 previf (prev.next !== null) {this.keyToPrev.set(prev.next.key, prev);}this.keyToPrev.set(curt.key, this.tail);this.tail = curt;}get(key) {// 如果这个 key 根本不存在于缓存，返回 -1if (!this.keyToPrev.has(key)) {return -1;}// 这个 key 刚刚被访问过，因此 key 节点应当被移动到链表尾部this.moveToTail(key);// key 节点被移动到链表尾部，返回尾部的节点值，即 tail.valreturn this.tail.val;}set(key, value) {// 如果 key 已经存在，更新 keyNode 的 valueif (this.get(key) !== -1) {const prev = this.keyToPrev.get(key);prev.next.val = value;return;}// 如果 key 不存在于 cache 且 cache 未超上限// 再结尾存入新的节点if (this.size < this.capacity) {this.size++;const curt = new ListNode(key, value);this.tail.next = curt;this.keyToPrev.set(key, this.tail);this.tail = curt;return;}// 如果超过上限，删除链表头，继续保存。此处可与上边合并const first = this.dummy.next;this.keyToPrev.delete(first.key);first.key = key;first.val = value;this.keyToPrev.set(key, this.dummy);this.moveToTail(key);}
}
网络标签：

相关问题