学习笔记|算法
本文最后更新于:5 个月前
一、框架
1.如何精通一个领域?
- Chunk it up 切碎知识点
- Deliberate Practicing 刻意练习
- 做题做五遍
- Feedback 反馈
- 主动式反馈:看高手代码
- 被动式反馈:高手指点
2.数据结构
所有的数据结构不是直接创造的,而是现实中已有的逻辑,然后抽象成计算机语言。
一维数据结构
基础:数组 array(string)、链表 linked list
高级:栈 stack、队列 queue、双端队列 deque、集合 set、映射 map(hash or map)
二维数据结构
- 基础:树 tree、图 graph、
- 高级:二叉搜索树 binary search tree、红黑树 red-black tree,AVL、堆 heap、并查集 disjoint set、字典树 Trie
特殊数据结构
- 位运算 Bitwise、布隆过滤器 BloomFilter
- LRU Cache
3.算法
if-else,switch:branch 跳转语句
for,while loop:lteation 循环语句
递归 Recursion(Divide & Conquer 分治,Backtrace 回溯)
搜索 Search:深搜 Depth frist search,广搜 Breadth frist seach
动态规划 Dynamic Program
二分查找 Binary Search
贪心 Greedy
数学 Math,几何 Geometry
4.如何做算法题
Clarification:理解清楚题意
Possible solutions:把所有可能的方法过一遍
- compare 比较时间空间复杂度
- optimal 最理想的
Coding:多写
Test case:有始有终
(1)第一遍做题
10 分钟:读题 + 思考。
直接看解法:多解法,比较解法优劣。
背诵和默写下来(理解)。
(2)第二遍做题
- 经过第一遍之后,马上自己写。
- debug。
- 直至通过、优化。
(3)第三遍做题
过了一天之后做题
(4)第四遍做题
过了一周之后做题
(5)第五遍做题
面试前一周练习
5.自顶向下编程
- 先写主干逻辑。
- 再写细节。
6.遇见题目没有思路?
能不能暴力?
暴力可不可以优化?(一维变二维,空间换时间)
…
基本情况能否解决?
找重复子问题。
数学归纳法——递推公式
…
二、时间复杂度
Big O notation
O(1):Constant Complexity 常数时间复杂度
O(log(n)):Logarithmic Complexity 对数时间复杂度
O(n):Linear Complexity 线性时间复杂度
O(n^2):N square Complexity 平方
O(n^3):N cube Complexity 立方
O(2^n):Exponential Growth 指数
O(n!):Factorial 阶乘
举个例子:
(1)时间复杂度为 O(log(n))。
因为 2^x = n,所以 x = log2 (n)。底数2可省略。
for (int i = 0; i < n; i *= 2) {
cout << "once";
}
(2)时间复杂度为 O(k^n)
int fib(int n) {
if (n <= 2) return n;
return fib(n - 1) + fib(n - 2);
}
按树状排列,最多有 n 层,每层 k 个,在本程序中,k = 2。所以最下一层有 2^n 个。
graph TD
A(fib_6) --> B(fib_5)
A --> C(fib_4)
B --> D(fib_4)
B --> E(fib_3)
C --> F(fib_3)
C --> G(fib_2)
D --> J(fib_3)
D --> K(fib_2)
J --> L(fib_2)
J --> M(fib_1)
L --> N(fib_1)
1.主定理
2.思考
二叉树的前序/中序/后序遍历,时间复杂度是多少?
O(n),因为每个节点访问一次。
图的遍历,时间复杂度是多少?
O(n),因为每个节点访问一次。
搜索算法:深搜、广搜,时间复杂度是多少?
O(n),因为每个节点搜索一次。
二分查找
O(log(n)),次数为x,2^x = n。
三、数组、链表、跳表
1.数组 array
连续的一段内存空间,利用内存管理器管理。
随机访问时间复杂度:O(1)。
插入删除效率低,时间复杂度:O(n)。
2.链表 linked list
- 不需要一段连续的内存空间。
- 随机访问效率低,时间复杂度:O(n)。
- 插入删除效率高,时间复杂度:O(1)。
3.跳表 skip list
为了补足链表随机访问效率低的缺点。
(1)思想
主要思想:升维、空间换时间。
做法:增加多级索引,将一维链表,升级为二维数据结构。
(2)索引个数
n 个元素最多有多少级索引?
log2(n) - 1 个索引,因为 2^x = n。
(3)随机读取的时间复杂度
O(log(n)),每级索引都要访问一次,log2(n) - 1 个索引加上本身的链表,一共访问 log2(n) 次。
(4)空间复杂度
O(n),从最高级索引到第一级索引:{ n/2,n/4,n/8,… 8,4,2 },求和 = a1*((1 - q^n) / (1 - q))= n - 1。
(5)实际跳表形态
由于增加和删除,会使索引不完全工整,有的地方会多跨几步,有的地方会少跨几步。
索引的维护成本高:每次插入和删除的时候,索引都要更新一遍。
4.例题
一维数组的坐标变换。
题目 | 要点 |
---|---|
#283. 移动零 | 快慢指针(不一定是指针) |
#11. 盛最多水的容器 | 左右夹逼,左右向中间收敛 |
动态规划 | |
#1. 两数之和 | 双指针(相向而行,夹逼) 或者 哈希表 |
#15. 三数之和 | 双指针 |
#283. 移动零
- i == 快指针,它从 0 遍历到 n;
- j == 慢指针,它指的是第一个 0 的位置(如果 i 遍历到了 0),或者区间 [0, i] 中最后一个非零元素(如果 i 还未遍历到零)。
当 i 遍历到 非零数 时,和 j 位置的数交换,j++。我们将会发现:
慢指针之前的所有元素都是非零的。
快指针和慢指针之间的所有元素都是零。
void moveZeroes(vector<int>& nums) {
int n = nums.size(), j = 0;
for (int i = 0; i < n; i++) {
if (nums[i]) {
swap(nums[i], nums[j]);
j++;
}
}
return;
}
#11. 盛最多水的容器
从两边向中间收敛,遍历 n 次。
最初以 0、n-1 为两边边界,宽度最长,但是高度不一定最高。
矮的一边向中间移动,以寻求更高的边界(宽度不一定够大,但是可以在高度上取得优势)。
移动边界后并计算容量,记录容量最大值。
int maxArea(vector<int>& height) {
int max_ans = 0;
int n = height.size();
for (int i = 0, j = n - 1; i < j; ) {
int min_height = height[i] > height[j] ? height[j--] : height[i++];
int ans = (j - i + 1) * min_height;
max_ans = max(ans, max_ans);
}
return max_ans;
}
#15. 三数之和
先排序,从 0 遍历每一个数 nums[k]。
- nums[k] 右边的第一个元素索引标为 i;
- nums[k] 右边的最后一个元素索引标为 j。
即 nums[i] 是子序列的最小元素,nums[j] 是子序列的最大元素。
如果 nums[i] + nums[j] < 0 - nums[k],最小元素右移动(变大)。
如果 nums[i] + nums[j] > 0 - nums[k],最大元素左移动(变小)。
特殊优化:
- 因为和为 0,比较特殊,也就意味着至少有一个元素 <= 0。if nums[k] > 0,break;
去重判断:
为了保持组合不重复,
- k 遍历的点的值不可以重复。
- i 在 i、j 的一个循环内,遍历的点的值不可以重复。
- j 在 i、j 的一个循环内,遍历的点的值不可以重复。
那为什么不将重复的元素直接合并?
因为有 [-1, -1, 2] 这种组合。这种组合是当 nums[k] 和 nums[i] 重复的时候出现的。
vector<vector<int>> threeSum(vector<int>& nums) {
int n = nums.size();
sort(nums.begin(), nums.end());
vector< vector<int> > ans;
vector<int> tmp_ans(3);
for (int k = 0; k < n - 2; k++) {
if (nums[k] > 0) {
break;
}
if (k > 0 && nums[k] == nums[k - 1]) {
continue;
}
for (int i = k + 1, j = n - 1; i < j;) {
if (i > k + 1 && nums[i] == nums[i + 1]) {
i++;
continue;
}
if (j < n - 1 && nums[j] == nums[j - 1]) {
j--;
continue;
}
int sum = nums[k] + nums[i] + nums[j];
if (sum < 0) {
i++;
} else if (sum > 0) {
j--;
} else {
tmp_ans[0] = nums[k];
tmp_ans[1] = nums[i];
tmp_ans[2] = nums[j];
ans.push_back(tmp_ans);
i++;
j--;
}
}
}
return ans;
}
四、堆栈和队列
1.Stack 栈
Last in,First out.
2.Queue 队
First in, First out.
3.Double-End Queue (Deque)双端队列
4.Priority Queue 优先队列
- 和 Queue 的区别在于,队列中的数,有顺序,当从尾部插入个数据,队列的数据会重新排列。
- 底层可能使用 heap 实现的。
5.复杂度
插入 | 删除/取出 | 查询 | |
---|---|---|---|
Stack \ Queue \ Deque | O(1) | O(1) | O(n),因为数据没有顺序 |
Priority Queue | O(1) | O(log N) | O(log N) |
6.例题
(1)什么问题用栈解决?
最近相关性:类似于洋葱,从内到外,或者从外到内一层层逐渐扩散的样子,而且最外层和最内层时一对。
(2)什么问题用队来解决?
强调 先来后到 的顺序。
所有的数据结构不是直接创造的,而是现实中已有的逻辑,然后抽象成计算机语言。
堆栈和队列的应用。
题目 | 要点 |
---|---|
#20. 有效的括号 | 最近相关性,stack |
#155. 最小栈 | 双栈(辅助栈),延伸:双栈实现队列 |
#84. 柱状图中最大的矩形 | 单调栈 + 哨兵(妙不可言,多看几遍) |
#239. 滑动窗口最大值 | 双端队列(单调队列) |
#155. 最小栈
要在常数时间内,找到最小值。显而易见的思路就是,在入栈的时候,进行比较,并保存最小值。但是问题是,如果最小值被弹出栈,新的最小值该如何寻找?
用辅助栈解决,当数据栈入栈一个数据,辅助栈同步的入栈此刻的最小值;反之,弹栈的话也是数据栈辅助栈同步的。
class MinStack {
public:
MinStack() {
min_num.push(INT_MAX);
}
void push(int x) {
min_num.push(min(min_num.top(), x)); // 同步入栈
data.push(x);
}
void pop() {
data.pop(); // 同步弹栈
min_num.pop();
}
int top() {
return data.top();
}
int getMin() {
return min_num.top();
}
private:
stack<int> data; // 数据栈
stack<int> min_num; // 辅助栈
};
#84. 柱状图中最大的矩形
(1)先尝试暴力思路
for i -> 0, n+2 {
for j -> 0, i-1 { 找出比 当前高度 高的做左边界 left }
for j -> i+1, n { 找出比 当前高度 高的做右边界 right }
left, right -> 计算面积;
updata max_area;
}
在这个过程中,我们发现,后出现的高度可以先算出面积,符合 LIFO 的特点。
而且我们还发现,
- 当遇到高度比 heights[i] 高 时,继续遍历,
- 当遇到高度比 heights[i] 低 时,停止遍历。
符合单调增的情况,考虑单调栈(以单调增栈为例,当前元素小于栈顶,弹栈;当前元素大于栈顶,当前元素入栈)。这里不理解见视频分析:官方题解视频。
(2)使用单调栈
单调栈在添加元素的时候靠删除元素保持栈的单调性。
stack<int> s;
for i -> 0, n-1 {
if 当前元素 < s.top()
计算以 heights[s.top()] 为高度的面积 (其中宽为 栈顶的前一个元素 到 i 的间隔。)
s.push_back(当前元素)
}
if s 不为空
弹栈,并计算面积。
易错:
- 取 s.top() 之前,应该判断栈顶不为空!
- 注意特殊情况:栈中只有一个元素、栈中有全部元素。
- 栈中存入的应该是索引,便于计算宽度。
实现为代码如下:
int largestRectangleArea(vector<int>& heights) {
stack<int> s;
int n = heights.size();
int max_area = 0;
int area = 0;
for (int i = 0; i < n; i++) {
if (s.empty()) {
s.push(i);
continue;
}
while (!s.empty() && heights[i] < heights[s.top()]) { // 易错,先判断栈不为空
int tmp = s.top();
s.pop();
if (s.empty()) {
area = i * heights[tmp];
} else {
area = (i - s.top() - 1) * heights[tmp];
}
max_area = max(max_area, area);
}
s.push(i);
}
int left = 0;
if (!s.empty()) {
// left = s.top() + 1; // 也可以写成这样。
left = n; // 左边的边界一定是 最右边元素的索引 + 1。
}
while (!s.empty()) {
int tmp = s.top();
s.pop();
if (s.empty()) {
area = left * heights[tmp];
} else {
area = (left - s.top() - 1) * heights[tmp];
}
max_area = max(max_area, area);
}
return max_area;
}
(3)单调栈 + 哨兵
为什么要加入哨兵?因为有两种情况,我们无法规避 if 讨论:
- 当栈中只有一个元素的时候,无法取出栈顶的前一个元素;
- 当所有元素全部入栈时,我们必须有段弹栈代码。
如何把两种特殊情况,统一起来呢?
- 加入哨兵,在 heights 数组前后,各加一个 0 的高度。
这样我们就可以不用考虑头和尾的情况了。
int largestRectangleArea(vector<int>& heights) {
int n = heights.size();
vector<int> new_heights(n + 2, 0); // 拷贝新的数组
for (int i = 0 ; i < n; i++) {
new_heights[i + 1] = heights[i];
}
n += 2;
stack<int> s;
s.push(0); // 栈中加入高度为 0 的柱子
int max_area = 0;
int area = 0;
for (int i = 1; i < n; i++) {
while (new_heights[i] < new_heights[s.top()]) {
int tmp = s.top();
s.pop();
area = (i - s.top() - 1) * heights[tmp];
max_area = max(max_area, area);
}
s.push(i);
}
return max_area;
}
#239. 滑动窗口最大值
(1)如何 O(1) 找出最大值?——单调队列!
一堆数,增加一个数,可以 O(1) 找到最值,但是减小一个数,就不能 O(1) 找到最值。要想减小一个数,也能 O(1) 找到最值,需要用到单调队列。
单调队列在添加元素的时候靠删除元素保持队列的单调性(和单调栈一样)。
最大值在最前面,为 q.front().
当
nums[i] > 队尾元素
,队尾元素出队,直到nums[i] < 队尾元素
或者 队空【核心代码_2】。因为,当 num[i] 比前面的值都大时,前面的元素就没必要存在了(返回的永远是最大值)。
当
nums[i] < 队尾元素
或者 队空 时,nums[i] 入队。因为一旦,nums[i] 前面的最大值脱离窗口区间,nums[i] 就会成为新的最大值(只要它不被后面的数据取代)。
(2)如何及时让 脱离口区间的 老的 最大值出队?
- 队里不能存数值,应该存索引,便于知道,老的最大值是否已经脱离窗口区间【核心代码_1】。
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
deque<int> q;
vector<int> ans;
int n = nums.size();
int count = 0;
for (int i = 0; i < n; i++) {
if (!q.empty() && q.front() < i - k + 1) { // 核心代码_1
q.pop_front();
}
count ++;
while (!q.empty() && nums[q.back()] < nums[i]) { // 核心代码_2
q.pop_back();
}
q.push_back(i);
if (count >= k) {
ans.push_back(nums[q.front()]);
}
}
return ans;
}
本博客所有文章均个人原创,除特别声明外均采用 CC BY-SA 4.0协议,转载请注明出处!