Skip to main content

知识点

我们可以将算法分解成小的知识点，并且逐个制定计划进行针对性练习。如果你没有足够的经验，你可能不知道自己没有掌握哪些知识点，以下表格列出了每个类型中面试要求的所有知识点，如果你刚开始接触算法练习的话可能不理解部分内容。

面试技巧​

时空复杂度​

编程语言基础​

链表​

二叉树​

  • 树的不同形态与类型，完美二叉树，完全二叉树，满二叉树区别
  • 使用递归以及非递归实现树的前序，中序，后序，使用队列实现层序遍历
  • 二叉树可以先尝试使用递归解决问题
  • 理解如何通过观察父子节点的依赖关系来选择合适的递归实现（前序遍历子节点依赖父节点的返回值，后序遍历则是父节点依赖子节点的返回值）

二叉搜索树​

  • 实现二叉搜索树，实现增删查改功能
  • 了解如何找到某个节点的前一个/后一个节点
  • 了解带统计信息的二叉搜索树以及其可以用来统计数据

前缀树​

*线段树​

矩阵​

  • 如何将二维坐标转化为一维 (i * col + j)
  • 如何使用编程语言用不同方式遍历矩阵 1）常规按行遍历 1）先遍历列再遍历行 2）对角线遍历
  • 转置和翻转矩阵

数组​

  • 获取倒数第 k 个元素
  • 从后到前遍历数组
  • 每隔 k 个元素遍历数组
  • 高效轮转数组（189. 轮转数组）
  • 前缀和的模版，前缀和的使用场景
  • 差分数组的实现与使用场景
  • 建立等差等比数组以及其基本公式

排序​

  • 实现快速排序，归并排序，堆排序，桶排序，计数排序，了解它们的时间复杂度
  • 重写排序比较方式，例如对于 [(i1, j1), (i2, j2)]，1）根据 j 的大小来排序，2）根据 j 的长度来排序，3）先根据 j 再根据 i 排序

栈​

  • 了解前缀，中缀，后缀表达式，知道如何将中缀转换成前缀/后缀
  • 使用栈判断括号是否合法
  • 使用栈找到每个括号对应的另一半（"(())"，对于每个左括号找到右括号对应的索引）
  • 使用栈解决 Leetcode 基本计算器 I, II, III
  • 使用栈模拟递归
  • 实现单调栈，实现四种不同的单调栈，分别找到每个元素左边/右边第一个比其大/小的元素

堆​

  • 使用最大堆，最小堆解决 Top k 问题
  • 贪心算法优先考虑堆以及自平衡二叉搜索树
  • 使用堆计算数据流中位数

二分查找​

  • 了解二分查找的基本模版
  • lower_bound 以及 upper_bound 两个 API 的使用场景与实现

位运算​

  • 将 num 的二进制的第 K 位设置为 1
  • 将 num 的二进制的第 K 位设置为 0
  • 将 num 的二进制的第 K 位取反
  • 计算 num 的二进制中 1 的数量
  • 判断 num 是否是 2 的非负整数次幂
  • 删除 num 最低有效位（5 的二进制为 101，删除最低有效位得到 4）
  • 遍历 num 的所有非空子集合（5 的二进制为 101，其非空子集合为 [001, 100, 101]）
  • 二，八，十六进制互相转换
  • 不同位运算（异或，或，和）的运算律（交换律，结合律）
  • 遍历 32 位来计算结果（

双指针与滑动窗口​

  • 了解排序后使用双指针的使用场景
  • 尝试证明双指针的正确性

回溯​

  • 回溯与动态规划的区别
  • 使用递归实现回溯
  • 如何计算回溯的时间复杂度

分治​

  • 使用递归树分析时间复杂度
  • 了解分治与回溯的区别

动态规划​

  • 动态规划与暴力解的区别
  • 动态规划的四个常规步骤
  • 动态规划状态转移方程的常见形式
  • Top Bottom & Botton Up 的实现区别
  • 了解状态压缩动态规划
  • 了解计算动态规划时间复杂度的技巧

贪心​

  • 了解贪心与动态规划的关系，什么情况下可以使用贪心
  • 尝试使用数学证明某一道贪心题目

图论​

  • 图的表达方式（链接矩阵，链接链表）
  • 了解有向图，无向图，图的环，简单图的概念
  • 了解图论的基本解题模式（BFS, DFS, 并查集）

DFS​

  • 使用 DFS 判断无向图是否有环
  • 了解 DFS 的步骤，递归前后的状态恢复
  • 使用 DFS 实现拓扑排序
  • 了解 DFS 与 BFS 的优缺点对比，什么时候使用其中一种
  • 了解什么是剪枝，如何在过程中剪枝

BFS​

  • 了解 BFS 的步骤
  • 了解 BFS 遍历中三种颜色节点的含义（学习图的染色）
  • 使用 BFS 实现拓扑排序
  • 了解什么是剪枝，如何在过程中剪枝

并查集​

  • 实现并查集
  • 了解其使用场景以及时间复杂度计算

设计​

  • 了解什么是迭代器
  • 了解如何通过拆分与抽象子函数解决问题

特殊问题以及代码模版​

*数学​

  • 数学证明的方式与技巧（反证法）
  • 如何求最大公约数，找素树
  • 了解常见定理（欧几里得定理，勾股定理）

*几何​

  • 线段，向量基础
  • 常见几何题类型以及核心点