面试-算法基础

面试
留言

记录算法基础内容：数据结构基础、一些比较重要的题目、问的较多的原理和 Python 刷算法的基础操作。

基础参考

算法通关手册（LeetCode）

算法题目

记录一些比较重要的题目

数组：

  • 1. 两数之和：使用 hash 表来存储其中一个数字，然后找另一个数字即可
  • 15. 三数之和：第一层循环作为第一个数字（跳过相同的数字），后边使用双指针，查找三数相加等于 0 的元组（在等于 0 的条件内部，双指针跳过相同的数字）
  • 415. 字符串相加：逆序，逐个字符处理即可
  • 28. 找出字符串中第一个匹配项的下标：KMP 算法，先生成 next 数组，然后再根据 next 数组来判别匹配的大小
  • 5. 最长回文子串：最长回文（马拉车或者动态规划），动态规划方法单独考虑两个字符相邻的情况（i 从小到大，j从大到小）
  • 912. 排序数组：快速排序实现（设置 flag，从右侧找小于 flag 填到 flag_idx_l，从左侧找大于 flag 填到 flag_idx_h，最后将 flag 回填）
  • 215. 数组中的第 K 个最大元素：快速排序的应用，只排需要的部分（这个题可能要用三路快排，要不然有一个变态样例过不了）
  • 347. 前 K 个高频元素：Top-K，先统计频率，再使用优先队列排序
  • 128. 最长连续序列：构建 hash 表，遍历元素找到以该元素为起点的最长连续序列（起点判断方法是看上一个元素在不在，如果有上一个元素则该元素就不是起点）

链表：

  • 21. 合并两个有序链表：创建新的头 h 和移动 p，依次续上两个链表中值比较大的节点（选择节点后并向后移动游标）
  • 328. 奇偶链表：创建两个链表，分成奇节点和偶节点续上，最后将其中一个链表续到另一个末尾
  • 92. 反转链表 II：设置游标 + 上一个节点指针，逐个逆转即可
  • 25. K 个一组翻转链表：循环，判断位置并截断，子函数反转，再对接到新链表上
  • 142. 环形链表 II：快慢指针判断是否有环；将 slow 重置到 head，再一步一步走，与 fast 相遇的时候就是环的入口

二叉树：

  • 236. 二叉树的最近公共祖先：向上传递 NULL 或者目标节点或者祖先（三种情况），递归操作，如果一边为 NULL 则肯定在另一边（另一边可能也没有），如果两边都不是 NULL（p 和 q 就是从两边传上来的） 则说明本节点就是祖先
  • 226. 翻转二叉树：每个节点交换左右子树即可（递归操作）
  • 687. 最长同值路径：分别判断左右最长，然后合并求跨当前节点最长；向上返回左右最长之一（注意最长路径是边数，不是节点数）
  • 501. 二叉搜索树中的众数：二叉搜素树中序遍历是是有序的数组
  • 124. 二叉树中的最大路径和：DFS 遍历，记录左右节点的值与 0（忽略子节点） 相比的较大值，计算左右与当前节点相加的值并记录最大值，向上返回根节点+左右节点中的较大值
  • LCR 145. 判断对称二叉树：check 当前节点是否相等，递归遍历左与右对比，右与左对比
  • 二叉树遍历：前序、中序、后续（递归 or 非递归——使用栈）；层序——队列
  • 二叉树还原：中序 + 前序或者后续；如果是前序 + 后续则存在多种情况
  • 平衡二叉树：树的高度平衡（旋转方法，也就是代码中的操作流程）
  • 红黑树：相对平衡二叉树（AVL）旋转次数变少，效率更高（增加、删除操作比查找操作多的情况下）
  • 手写子典树：树节点分叉（分叉类型，可以是字母类型，边上代表字母） + 终止标记（标记单词结束）子典树

图：

  • 207. 课程表：map 记录 next，数组记录入度；首次将入度为 0 的节点加入到队列，依次处理队列，处理 map 中该值并修改入度数组，将新入度 0 加入到队列；判断入度数组是否全为 0 即可
  • 547. 省份数量：并查集（并查集，记住基本函数即可）。初始省份数量是节点个数，每次进行合并操作减 1。
  • 1971. 寻找图中是否存在路径：并查集（并查集，记住基本函数即可）。如果存在路径，则起始和结束节点属于同一个根节点
  • 695. 岛屿的最大面积：深度优先搜索，搜索过的点设置为 0（标记）。转向序列（{0，1}，{1，0}，{0，-1}，{-1，0}）

动态规划 & 贪心：

回溯：

  • 93. 复原 IP 地址：回溯方法，查找起点开始的 1-3 个字符，判断是否是有效字符，追加到总 path 里

栈 & 队列：

  • 20. 有效的括号：栈操作（如果不用栈怎么解决？）
  • 接雨水：维护单调递减栈，遇到增量值时拿出来计算与左挡板距离，和底部元素高度差
  • 两个栈实现队列：两个栈倒来倒去就可以了
  • 两个队列实现栈：用辅助队列实现弹出操作（出队直到剩余一个，即弹出的数据）

设计：

  • 146. LRU 缓存：map 存储 key 和 Node* 的映射关系，方便快速找到 Node*；双向链表维护节点访问顺序（如果节点超了就从末尾删一个）。 get（没有返回-1；访问到挪到双向链表头部）；put（没有，添加进去，并判断容量，删除超的；有，更新，挪到头部）
    • 带过期时间的 LRU 算法：将过期时间使用另一个 map 来维护（put 和 get 分别判断过期和重置过期时间）；可以使用一个额外的线程来惰性删除
  • 460.LFU 缓存：最近最少次数使用（将双向链表改成优先队列？）
  • 224. 基本计算器：使用栈来表示当前括号层次的符号，遇到左括号则保存符号到栈，遇到右括号则弹出符号，本质上是表示各层次括号外部的符号

其它：

  • 题目：有一个长度 100 的 01 数组，可以反转 K 个1成为0，求解反转后的最大连续0的长度
    • 解法：滑动窗口算法，统计窗口内1 的数量并记录窗口的最大长度

算法原理

哈希表：

  • 哈希算法：加法哈希、乘法哈希、异或哈希、旋转哈希
  • 哈希冲突：链表法（相同的节点后面加链表）；开放寻址法（向后找一个空位置）

红黑树与 AVL 树对比：

  • 红黑树是没那么平衡的平衡树，是查找效率与插入效率的折中

算法操作

Python 算法基础操作：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
# 列表
copy_list = a[:]
reverse_list = a[::-1]

# 字典
d = collections.defaultdict(int)

# 计数
s_c = Counter(s)

# 栈
sta = []
sta.append(val)
val = sta.pop()

# 队列
q = deque()
q.pop()
q.popleft()
q.append(val)
q.appendleft(val)

# 集合
s = set()
s.add(val)
s.discard(val)
s.remove(val)
v = s.pop()

# 有序集合
from sortedcontainers import SortedList
s.add()

# 堆
import heapq
# 默认小顶堆，加负号成大顶堆
heap = []
heapq.heappush(heap, val)
val = heapq.heappop(heap)

# node 自定义小于比较器
ListNode.__lt__ = lambda a, b : a.val < b.val

# 输入处理
num = int(input())
num_list = [list(map(int, input().split())) for _ in range(lines)]