数据结构算法高频题
在面试中，由于时间的限制，一般不会出太难的题，这和笔试是不同的。因此必须有针对性地学习和总结，比如分专题学习总结。把常见基础题掌握好，再去追求一些很trick的题。一题多解时，还要注意分析算法复杂度。另外，STL容器、算法等API要多熟悉。
数组
多总结
- 42.
Trapping Rain Water
- 对于每个柱子，找到其左右两边最高的柱子，该柱子能容纳的面积就是
min(max_left-max_right)-height - Two-pass：1) 从左往右算max_left，从右往左算max_right；2) 从左往右算面积累加
- 时间O(n)，空间O(n)
- 对于每个柱子，找到其左右两边最高的柱子，该柱子能容纳的面积就是
- 80.
Remove Duplicates from Sorted Array II
- 双指针。注意扩展性。
- 88.
Merge Sorted Array 合并两个有序数组
- 由后往前合并。空间O(1)，时间O(n)
- 从前往后合并。空间O(n)，时间O(n)
- 169.
Majority Element 求众数
- 经典投票算法，模拟投票选举的过程，不同的数字抵消
- 189. Rotate
Array 旋转数组
- 三次reverse。时间O(n)，空间O(1)。此外还有许多其他方法。
- 283. Move
Zeroes 移动零
- 用一个队列记录前面零的index即可
- 384.
Shuffle an Array 打乱数组
- 视频讲解，关键：index+swap
- 比较巧妙，STL中random_shuffle就是用的这种算法
- 334.
Increasing Triplet Subsequence 递增的三元子序列
- 记录最小、次小值。时间O(n)，空间O(1)
- 240.
Search a 2D Matrix II 搜索二维矩阵
- 从右上角开始搜索
- 238. Product of Array Except Self 除自身以外数组的乘积
- Two-pass：从左往右算，从右往左算
滑动窗口法
substring、subarray问题常用双指针滑动窗口法或DP。滑动部分的时间复杂度为O(n)。
- 3.
Longest Substring Without Repeating Characters 最长不重复子串
- 哈希表记录（值、index）+双指针（一个记录当前位置，一个记录不重复子串的起始位置）
- TODO: Longest Substring with At Most Two Distinct Characters
- 76.
Minimum Window Substring 最小窗口子串
- 滑动窗口法+哈希表
- 根据两个哈希表是否包含，进行window的扩张或收缩
- 参考：视频讲解
- 209.
Minimum Size Subarray Sum 最小长度子数组
- 滑动窗口法。根据sum大小有两个选择：
- 右边界快指针负责扩张window
- 左边界的慢指针负责收缩window
- 滑动窗口法。根据sum大小有两个选择：
- 395.
Longest Substring with At Least K Repeating Characters
至少有K个重复字符的最长子串
- 滑动窗口法+哈希表
- 需要numUnique和numNoLessThanK计数，对26个numUniqueTarget依次计算并取最大
- 参考：参考讲解
- 参考：一个通用解题模板
字符串
多数问题与数组类似
- 5.
Longest Palindromic Substring 最长回文子串
- 分奇偶两个情况，由中心往两边计算
- 208.
Implement Trie (Prefix Tree) 实现前缀树
- 树节点：
- char val;
- unordered_map<char,TreeNode*> children;
- bool isWord;
- 树节点：
- KMP
- TODO
栈
对称性与顺序性。如括号匹配等问题。
- 84.
Largest Rectangle in Histogram 直方图中最大的矩形
- TODO
- 参考讲解，时间O(n)，空间O(n)
- 150. Evaluate Reverse Polish Notation 逆波兰表达式求值
- 155. Min Stack
最小栈
- 用两个栈模拟
- 227.
Basic Calculator II 基本计算器II
- Two-pass：先把乘除算了，再算加减。用stack或vector存数据。
- 232.
Implement Queue using Stacks 用栈实现队列
- 第一个栈用于push缓冲，第二个栈用于pop
- 其他：225.
Implement Stack using Queues 用队列实现栈
- TODO
- 341.
Flatten Nested List Iterator 扁平化嵌套列表迭代器
- 用栈存储数据。从右往左入栈。
队列
- 239.
Sliding Window Maximum 滑动窗口的最大值
- 视频讲解，使用双向队列记录最大值、后面可能出现的次大值。双向队列数值呈非递增序。
哈希
- 128.
Longest Consecutive Sequence 最长连续序列
- 参考讲解，Two-pass
- 时间复杂度O(n)
- 380.
Insert Delete GetRandom O(1) 常数时间插入、删除和获取随机元素
- 一个vector+一个哈希表记录（值，index）
- O(1)删除这个地方比较巧妙，思路是用末尾元素替换待删除元素
- 454. 4Sum II 四数之和II
链表
画图结合、快慢指针等技巧
- 19.
Remove Nth Node From End of List 删除链表倒数第N个节点
- 快慢指针
- 82. Remove Duplicates from Sorted List II 删除链表重复节点
- 138.
Copy List with Random Pointer 复制带随机指针的链表
- Two-pass：先复制链表，再复制随机指针
- 记录链表相对位置0-size-1，根据相对位置找到对应链表
- 或者哈希表记录新旧链表映射关系
- Two-pass：先复制链表，再复制随机指针
- 142.
Linked List Cycle II 环形链表II
- 判断是否有环，快慢指针：慢指针一次一步，快指针一次走两步，直到相遇
- 找到回环入口：头指针一次一步，慢指针一次一步，直到相遇
- 146. LRU Cache
LRU缓存
- 一个list为了O(1)时间插入删除移动，一个hashmap为了O(1)时间查找
- 注意list.splice(const_iterator position, list& x, const_iterator i)用法
- 160.
Intersection of Two Linked Lists 相交链表
- Two-pass：先统计两个链表长度，长度差为x
- 快慢指针：快指针先走x步，然后一起走，直到相遇
- 206.
Reverse Linked List 原地反转链表
- 需要三个指针：previous，current，next
- 画个图，原地反转即可。其他方法：递归等
- 234.
Palindrome Linked List 回文链表
- 快慢指针：慢指针一次一步，同时反转前半段链表。快指针一次两步。最终慢指针走到中间。
- 对比两半是否相等。
- 或者直接使用栈。
- 237.
Delete Node in a Linked List 删除链表中的节点
- 分两种情况：
- 如果不是尾节点：用下一个结点的值替换当前结点的值，结点的next指向下一个结点的next，然后删除下一个结点。复杂度O(1)
- 如果是尾结点：需要提供头指针，然后顺序查找到结点的上一个指针prev，然后删除。O(n)复杂度
- 总时间复杂度
[(n-1)*O(1)+O(n)]/n，所以仍是O(1)
- 分两种情况：
- 287.
Find the Duplicate Number 寻找重复数
- 同环形链表II思路
- 328.
Odd Even Linked List 奇偶链表
- 画图调指针
树
首先考虑递归。求树的深度、树是否对称、是否平衡、是否BST、树的翻转(镜像)，排序数组转BST等
follow up考虑迭代。
- 树的各种遍历
- 前序、中序、后序遍历
- 144.
Binary Tree Preorder Traversal 前序非递归
- 参考讲解，使用栈
- 94.
Binary Tree Inorder Traversal 中序非递归
- 参考讲解，使用栈
- 145.
Binary Tree Postorder Traversal 后序非递归
- 参考讲解，使用2个栈：第一个栈类似前序遍历，第二个栈用来reverse顺序。
- 102.
Binary Tree Level Order Traversal 层次遍历
- 参考讲解，使用队列、vector等数据结构存储
- 98.
Validate Binary Search Tree 验证BST
- 在递归时，约束子节点的最小、最大范围
- 105. Construct Binary Tree from Preorder and Inorder Traversal 重建二叉树
- 236.
Lowest Common Ancestor of a Binary Tree 二叉树最近公共祖先
- 分类讨论，base case和norma case的几种情况
- 297.
Serialize and Deserialize Binary Tree 二叉树的序列化与反序列化
- 用先序遍历
- 视频讲解
- 450.
Delete Node in a BST 删除BST节点
- 视频讲解，分三种情况
- TODO
- 701.
Insert into a Binary Search Tree 插入BST节点
- 直接递归做
- 中序遍历下一个节点
- 节点右孩子存在：中序遍历，得到下一个节点
- 节点右孩子不存在：向上遍历其父节点们，找到第一个位于右侧的父节点（如果该节点是其父节点的左孩子，则返回父节点）。如没找到则返回空。
图
思路与“树”类似。图的几种表示、图的DFS、BFS遍历等。
- 127. Word
Ladder 单词等长变换
- 求最短路径，故用BFS。使用队列存储邻居节点，用哈希表存储待访问节点。
- 防止TLE的trick:
- 不要遍历整个字典，而是逐个字符地更改待测试单词
- 将已访问节点从哈希表中删除
- 130.
Surrounded Regions 包围区域
- DFS：以边界
O为种子点生长，设置为# - 设置其他
O为X - 设置
#为O
- DFS：以边界
- 200.
Number of Islands 岛屿的个数
- eraseIslands+DFS，又叫种子填充法
- 数字图像中的连通区域算法，也属于一类问题。四连通
- 207. Course
Schedule 课程表
- 有向图判断有环，视频讲解
- DFS+设置3个访问状态
- 时间复杂度O(V+E)，空间复杂度O(E)
- 210.
Course Schedule II 课程表II
- 跟课程表题一样：只不过使用容器保存访问顺序
排序
排序的实现、复杂度分析、链表排序
- 插入排序类
- 直接插入排序。从左往右排序，从右往左swap（插入到正确位置）。类似扑克牌理牌。适用于基本有序数据。
- 希尔排序。略。
- 选择排序类
- 简单选择排序。每次选择最小的元素，并交换（每次只交换了一次）
- 堆排序
- 时间复杂度O(nlogn)，空间复杂度O(1)。不稳定。
- 属于选择排序。每次取堆顶元素
- 交换排序类
- 归并排序类
- 时间复杂度O(nlogn)，空间复杂度O(n)。稳定。
- 关键代码：merge two sorted array
- 适用于：大数据量排序、外排序、链表排序、统计逆序对等
- 75. Sort Colors
颜色排序
- 计数排序。已知先验信息：数字在一定范围内
- 148. Sort List
排序链表
- 链表归并排序：快慢指针找中点，然后归并
- merge链表时不需额外空间
- 179. Largest
Number 最大数
- 比较函数：str1+str2>str2+str1
- 注意多个0情况下，去除leading zero
- 315.
Count of Smaller Numbers After Self 逆序对数
- 归并排序，merge数组时，统计逆序对数。O(nlogn)
搜索
二分
- 33.
Search in Rotated Sorted Array 搜索旋转排序数组
- 根据target和锚点的大小分两种情况，以锚点为界设置INT_MIN、INT_MAX。
- 然后按普通二分查找做
- 34.
Find First and Last Position of Element in Sorted Array
排序数组中查找元素的左右边界
- 两次二分查找：一次找左边界，一次找右边界
- trick：找左边界时，查找target - 0.5；找右边界时，查找target + 0.5；
- 153.
Find Minimum in Rotated Sorted Array 旋转排序数组的最小数字
- 根据锚点进行二分搜索
- 162. Find
Peak Element 寻找峰值
- nums[-1] = nums[n] =LONG_MIN
- 二分搜索，四种情况（nums[i-1]，nums[i]，nums[i+1]之间大小关系）
堆
topK，第K大等类似问题
BuildHeap时间复杂度O(n)，Heapify时间复杂度O(logn)。follow up：如何实现这两个函数。
23. Merge k Sorted Lists k路归并排序
- 类似归并排序，小顶堆保存最小值
- 时间复杂度O(nlogk)，空间复杂度O(k)，其中n是待排序元素个数
- 适用于海量数据排序
215. Kth Largest Element in an Array 第K大
- 堆排序思路：大顶堆pop() k-1次。时间O(n+klogn)
topK思路：维护一个大小为k的小顶堆。时间O(nlogk)
- 部分排序思路：类似快排思路。时间平均O(n)，最差O(n^2)
- STL中nth_element使用Introsort；本题也可使用STL中partial_sort。
1
2
3
priority_queue<int> maxHeap; # 大顶堆（默认参数）
priority_queue<int, std::vector<int>, std::greater<int>> minHeap; # 小顶堆- 部分排序思路：类似快排思路。时间平均O(n)，最差O(n^2)
295. Find Median from Data Stream 数据流的中位数
- 两个堆：数据小的前半段用大顶堆，数据大的后半段用小顶堆
378. Kth Smallest Element in a Sorted Matrix 有序矩阵中第k小元素
- 参考：使用最小堆
- 关键在于运用多路归并排序思想，每次弹出每一列中最小的那个，共弹出k-1次。
- 需要注意使用堆时，记录value、行、列坐标三个值。
347. Top K Frequent Elements 前K个高频元素
- 先统计频率，再按TopK问题求解
回溯
回溯是进行暴力搜索，当中途发现已不满足求解条件时，则“回溯”返回，并尝试其他路径。用于Generate all xxx、Compute all xxx等问题，如八皇后、数独等。一般具有三要素：
choice：递归得到，normal case。
constraint：条件约束，if statement
goal：终止情况，base case
- 10.
Regular Expression Matching 正则表达式
- TODO
- 22.
Generate Parentheses 括号生成
- 约束：剩余左括号的数量 <= 剩余右括号的数量
- 46.
Permutations 排列
- swap+递归。迭代法：swap+迭代，但是代码没有递归法简洁
- 77.
Combinations 组合
- 39. Combination Sum 组合之和，约束不同，解法类似
- 79. Word Search
单词搜索
- 矩阵中路径寻找问题
- 131.
Palindrome Partitioning 分割回文串
- 约束：是否是回文；终止条件：分解完字符串
- 视频讲解
- 回溯法时间复杂度一般是O(r^n)，r是每一次选择的个数，n是递归的深度
- 参考：油管博主讲backtracking，强推这个博主的视频。Backtracking Wikipedia
DP
DP问题有时可以先思考暴力递归的情况（top down方式），再思考如何记忆存储一些重复计算的子问题的解（top down+memoization），进一步地思考如何据此得到的DP方法（bottom up方式）。
易混概念：子序列subsequency可以不连续，而子串substring、子数组subarray必须连续
线性DP
- 53.
Maximum Subarray 最大子数组和
- Kadane算法。参考：《编程珠玑》第8章，视频讲解
- 简单的DP做法可以用O(n)空间复杂度，但使用globalMin可优化成O(1)空间复杂度。时间复杂度都是O(n)。
- 121.
Best Time to Buy and Sell Stock 买卖股票的最佳时机
- 把利润看作数组的值，转换为最大子数组和问题
- 122.
Best Time to Buy and Sell Stock II
- 短线操作，两两求和
- 152.
Maximum Product Subarray 乘积最大子数组
- 经典的子数组问题变种。本题需要考虑nums[i]正负号，因此需要两个值：localMin和localMax。如果nums[i]为负，swap二者。
- localMin=min(localMin*nums[i], nums[i]);
- localMax=max(localMax*nums[i],nums[i]);
- globalMax=max(globalMax, localMax);
- 经典的子数组问题变种。本题需要考虑nums[i]正负号，因此需要两个值：localMin和localMax。如果nums[i]为负，swap二者。
子串子序列DP
注意DP的初始状态
- 72. Edit
Distance 编辑距离
- 双串问题，二维矩阵DP
- 如果
str1[i]==str2[j]，dp[i][j]=dp[i-1][j-1]。表示当前两字符相等，编辑距离为0 - 如果
str1[i]!=str2[j]，dp[i][j]=1+min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])。表示三种选择取最小：replace，delete，insert
- 如果
- 视频讲解
- 双串问题，二维矩阵DP
- 300.
Longest Increasing Subsequence 最长上升子序列
- 经典单串问题
- 简单方法可以从右往左算，时间复杂度O(n^2)
- 718.
Maximum Length of Repeated Subarray 最长公共子数组（或子串）
- 经典双串问题，二维矩阵DP
- 如果
str1[i]==str2[j]，dp[i][j]=1+dp[i-1][j-1] - 如果
str1[i]!=str2[j]，dp[i][j]=0。没得选择，重置为0
- 如果
- TODO：如何输出这个字符串
- 经典双串问题，二维矩阵DP
- 1143.
Longest Common Subsequence 最长公共子序列
- 经典双串问题，二维矩阵DP
- 如果
str1[i]==str2[j]，dp[i][j]=1+dp[i-1][j-1] - 如果
str1[i]!=str2[j]，dp[i][j]=max(dp[i-1][j],dp[i][j-1])。有两个选择
- 如果
- 视频讲解，子问题和DP的转换讲的很好
- 经典双串问题，二维矩阵DP
递推型DP
找到线性递推公式，归纳法。通常只用O(n)时间复杂度，O(1)空间复杂度。
- 70. Climbing Stairs 爬楼梯
- 91. Decode Ways
解码方法数
- f(n)=f(n-1)+f(n-2)，if str[n-2:n-1]满足约束条件
- 视频讲解，如何由回溯得到递归版DP（空间复杂度O(n)），再得到优化后的DP，空间复杂度O(1)。
- 96.
Unique Binary Search Trees 不同BST数量
- 卡特兰数：f(n)=f(0)f(n-1)+f(1)f(n-2)+...+f(n-1)f(0)，物理意义表示左右子树数量相乘
- 198. House
Robber 打家劫舍
- f(n)=val[n]+max(f(n-2), f(n-3))
- 338. Counting
Bits 二进制位1的个数
- 两种方法：
- dp[i]=1+dp[i-last]; last表示1，2，4，8...，离i最接近的那个。表示每次把该整数最左边一个1变成0。
- dp[i]=1+dp[i&(i-1)]; 表示每次把该整数最右边一个1变成0。见下面位运算部分的总结
- 两种方法：
- 509.
Fibonacci Number 斐波那契数列
- 同爬楼梯、变态爬楼梯、矩形覆盖等问题。
背包DP
0/1背包
- 0/1背包问题
0-1 Knapsack Problem
- 每一次的选择：0和1。在总weight有限的约束下，每一步都去最大化这两个Value
- 要：
V[i-1][w-wi]+Vi，前提要的起（w>=wi） - 不要：
V[i-1][w]
- 要：
- 时间复杂度O(mn)，空间复杂度O(mn)。因为每次只用到了上一行的结果，因此空间复杂度可以优化为O(n)，即每次只保存上一行结果。
- 每一次的选择：0和1。在总weight有限的约束下，每一步都去最大化这两个Value
- 416.
Partition Equal Subset Sum 分割等和子集
- 0/1背包问题，要求恰好取到背包容量。状态用bool表示，每次对两个状态取或
- 要：
V[i-1][w-wi]，前提要的起（w>=wi） - 不要：
V[i-1][w]
- 要：
- 0/1背包问题，要求恰好取到背包容量。状态用bool表示，每次对两个状态取或
- 494. Target Sum
目标和
- 0/1背包问题，求方案数。
- 两个状态+或-，而不是要或不要。因此需要注意列的范围是-sum到sum。每次对两个状态的方案数求和。
- 参考讲解
完全背包
- 139. Word Break
单词拆分
- 类似完全背包，用bool表示每一个字母是否reachable
- 140. Word
Break II 单词拆分II
- 首先利用Word Break I检查单词是否可拆分，然后再进行下一步（防止超时）
- 基本思路和Word Break I一样：利用容器，存储单词拆分的中间结果
- 279.
Perfect Squares 完全平方数
- 背包的总重是n；各物体的重量是1，4，9，...，x2，其中x2<=n
- 322. Coin
Change 零钱兑换
- 完全背包(Unbounded Knapsack Problem)：物体可以无限重复利用。使用1维数组存储即可
- dp[i] = min(dp[i], dp[i-coin[j]] +1)，j从0到n-1，i-coin[j]>=0
- 完全背包问题中，一般会用两个循环。改变内外循环的先后顺序，运行的速度和效率可能不同。
- 343. Integer
Break 剪绳子
- dp[i] = max(dp[i], dp[i]*dp[i-j])，j从1到i/2
- follow up：贪心算法
矩阵路径类DP
记忆化 memoization
- 120. Triangle
金字塔
- 自底向上算
- 329.
Longest Increasing Path in a Matrix 矩阵中的最长递增路径
- DP+DFS
- 使用额外矩阵空间存储记忆之前计算结果。其他类似问题：
模拟
- 134. Gas
Station 加油站
- 总gas>=总cost时，一定存在解
- 第一个tank大于等于0的地方就是开始的位置
- 扑克牌顺子
- 排序，然后三步：统计0，统计gap（如遇到对子，则false），统计0是否足够弥补gap
数学与位运算
- 位运算总结
- 7. Reverse
Integer 反转整数
- 方法一：int转string，reverse string，string转int
- 方法二：直接由低位到高位逐位反转。时间O(n)，空间O(1)
- 29.
Divide Two Integers 位运算做除法
- 一般累减会超时，所以每次累减2倍、4倍、8倍…然后用余数再继续累减。
- 因为不能用乘法，用<<1代替。此外，注意溢出情况处理。
- 参考讲解
- 371. Sum of Two Integers 位运算做加法
- 50. Pow(x, n)
求幂
- 递归法比较简洁：即利用
pow(x,n/2)推得pow(x,n)
- 递归法比较简洁：即利用
- 69. Sqrt(x)
求平方根
- 二分
- 136. Single
Number 只出现一次的数字
- 异或。不仅能处理两次的情况，只要出现偶数次，都能清零。
- 172.
Factorial Trailing Zeroes 阶乘后的零
- Trailing 0s in n! =floor(n/5) + floor(n/25) + floor(n/125) + ....
- 参考讲解
- 191.
Number of 1 Bits 二进制位1的个数
- 方法一：与1进行&（统计最后一位是否是1），并不断右移（统计其他位）。不适用于负数
- 方法二：与n-1进行&（把该整数最右边一个1变成0），直到n为0。
- 204. Count
Primes 计算质数
- 参考视频，用容器存储每个数字bool型的状态，每次不断排除质数的倍数
- 233. Number of Digit One 十进制位1的个数
- 263. Ugly
Number 丑数
- 递归，base case：1为丑数，0不是丑数
- 264. Ugly
Number II 第N个丑数
- 参考讲解，三指针递推
- 268. Missing
Number 缺失数字
- 利用求和
- 326. Power
of Three 3的幂
- 判断319%num==0，319是int型最大的3的幂