/algorithm

Primary LanguageJavaScript

algorithm

data structure

tree

  • 654 如何优化？
  • 搜索提示原理？

Algorithmic thinking

binary search

做二分题目时，可以按照以下步骤：

  • 写出循环条件：while (left < right)，注意是 left < right，而非 left <= right；
  • 循环体内，先写出 mid = (left + right) >> 1；
  • 根据具体题目，实现 check() 函数（有时很简单的逻辑，可以不定义 check），想一下究竟要用 right = mid（模板 1） 还是 left = mid（模板 2）； 如果 right = mid，那么写出 else 语句 left = mid + 1，并且不需要更改 mid 的计算，即保持 mid = (left + right) >> 1； 如果 left = mid，那么写出 else 语句 right = mid - 1，并且在 mid 计算时补充 +1，即 mid = (left + right + 1) >> 1。
  • 循环结束时，left 与 right 相等。

注意，这两个模板的优点是始终保持答案位于二分区间内，二分结束条件对应的值恰好在答案所处的位置。 对于可能无解的情况，只要判断二分结束后的 left 或者 right 是否满足题意即可。

sliding window

判断使用滑动窗口的时机：

  1. 问题的输入是一种线性数据结构，比如链表、数组或字符串
  2. 被要求查找最长/最短的子字符串、子数组或所需的值
  • 大小为 K 的子数组的最大和（简单）
  • 带有 K 个不同字符的最长子字符串（中等）
  • 寻找字符相同但排序不一样的字符串（困难）

double pointer（头尾指针，快慢指针）

判断使用双指针的时机：

  1. 可用于处理排序数组（或链接列表）并需要查找满足某些约束的一组元素的问题 e.g. 原地快排

  2. 数组中的元素集是配对、三元组甚至子数组

  • 求一个排序数组的平方（简单）
  • 求总和为零的三元组（中等）
  • 比较包含回退（backspace）的字符串（中等）

判断使用快慢指针的时机：

  1. 处理链表或数组中的循环的问题
  2. 需要知道特定元素的位置或链表的总长度
  • 链表循环（简单）
  • 回文链表（中等）
  • 环形数组中的循环（困难）

backtracking

  • 37. 解数独

greedy(贪心)

  • 621 如何优化？

dynamic programming(动态规划)

  • 不同路径（有无障碍）
    • 62.不同路径
    • 63.不同路径-ii
  • 爬楼梯
  • 分硬币
    • 322.零钱兑换
    • 518.零钱兑换-ii
  • 打家劫舍（有无环）
    • 198.打家劫舍
    • 213.打家劫舍-ii
    • 337.打家劫舍-iii
  • 买卖股票
    • 121.买卖股票的最佳时机
    • 122.买卖股票的最佳时机-ii
    • 123.买卖股票的最佳时机-iii
    • 309.最佳买卖股票时机含冷冻期
    • 714.买卖股票的最佳时机含手续费
  • 子序
    • 53.最大子序和
    • 674.最长连续递增序列
  • 字符串

    • 72.编辑距离

      虚拟DOM问题：Course 71.

    • 115.不同的子序列

      dp 初始化？ Course 69.

    • 392.判断子序列

    • 583.两个字符串的删除操作

    • 1143.最长公共子序列

合并区间

判断使用合并区间的时机：

  1. 得到一个仅含互斥区间的列表
  2. 「重叠区间（overlapping intervals）」
  • 区间交叉（中等）
  • 最大 CPU 负载（困难）

循环排序

判断使用循环排序的时机：

  1. 涉及数值在给定范围内的排序数组的问题
  2. 在一个排序/旋转的数组中找到缺失值/重复值/最小值
  • 找到缺失值（简单）
  • 找到最小的缺失的正数值（中等）

Two Heaps

判断使用 Two Heaps 的时机：

  1. 在优先级队列、调度等场景中有用
  2. 需要找到一个集合的最小/最大/中间元素
  3. 可用于具有二叉树数据结构的问题

子集

如何识别子集模式：找到给定集合的组合或排列的问题

  • 带有重复项的子集（简单）
  • 通过改变大小写的字符串排列（中等）

K 路合并

  • 找到和最大的 K 个配对（困难）

拓扑排序

拓扑排序可用于寻找互相依赖的元素的线性顺序。

如何识别拓扑排序模式：

  1. 处理无向有环图的问题
  2. 以排序顺序更新所有对象
  3. 有一类遵循特定顺序的对象
  • 任务调度（中等）
  • 一个树的最小高度

interview

  • ByteDance
    • 1472.设计浏览器历史记录
    • 剑指 Offer II 045. 二叉树最底层最左边的值
    • 异步任务并发数控制 limit
  • Alibaba
    • 933.最近的请求次数
  • Tecent
    • 148.排序链表
      • 自顶而下归并
      • 自下而上归并
      • 快排？
      • 转换为数组排序
    • 217.存在重复元素
    • 341.扁平化数组
  • Baidu
    • 23.合并k个升序链表
  • NetEase
    • 384.打乱数组(如何打乱？)
  • MeiTuan
    • 380.o-1-时间插入、删除和获取随机元素
  • DiDi
    • 1797.设计一个验证系统
  • Others
    • 2.两数相加
    • 18.四数之和

interview tips

  • 确定面试官限制条件

    • 不用额外空间，空间复杂度O(1) => 只能原地解决

      e.g. 原地反转链表：反转一个子列表，反转每个 K 个元素的子列表

    • 时间复杂度O(1) => 哈希表，对象Map

    • 限制某个函数 => 手动实现

  • 《怎样解题》

    • 暴力解

    • 重复计算考虑缓存，不需要计算考虑剪枝

    • 动态 or 贪心的思路

    • 预处理，空间换时间

      e.g. 三数之和 预排序

图 BFS vs 树 BFS

  • Tree 只有 1 个 root，而图可以有多个源点，所以首先需要把多个源点都入队
  • Tree 是有向的因此不需要标识是否访问过，而对于无向图来说，必须得标志是否访问过！（防止节点多次入队，造成 BFS 超时）