学习笔记｜算法

1.框架

1.1 如何精通一个领域？

Chunk it up 切碎知识点
Deliberate Practicing 刻意练习
- 做题做五遍
Feedback 反馈
- 主动式反馈：看高手代码
- 被动式反馈：高手指点

1.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

1.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

1.4 如何做算法题

Clarification：理解清楚题意
Possible solutions：把所有可能的方法过一遍
- compare 比较时间空间复杂度
- optimal 最理想的
Coding：多写
Test case：有始有终

（1）第一遍做题

10 分钟：读题 + 思考。
直接看解法：多解法，比较解法优劣。
背诵和默写下来（理解）。

（2）第二遍做题

经过第一遍之后，马上自己写。
debug。
直至通过、优化。

（3）第三遍做题

过了一天之后做题

（4）第四遍做题

过了一周之后做题

（5）第五遍做题

面试前一周练习

1.5 自顶向下编程

先写主干逻辑。
再写细节。

1.6 遇见题目没有思路？

能不能暴力？
暴力可不可以优化？（一维变二维，空间换时间）
…
基本情况能否解决？
找重复子问题。
数学归纳法——递推公式
…

2.时间复杂度

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可省略。

1
2
3

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)

2.1 主定理

2.2 思考

二叉树的前序/中序/后序遍历，时间复杂度是多少？
O(n)，因为每个节点访问一次。
图的遍历，时间复杂度是多少？
O(n)，因为每个节点访问一次。
搜索算法：深搜、广搜，时间复杂度是多少？
O(n)，因为每个节点搜索一次。
二分查找
O(log(n))，次数为x，2^x = n。

3.数组、链表、跳表

3.1 数组 array

连续的一段内存空间，利用内存管理器管理。
随机访问时间复杂度：O(1)。
插入删除效率低，时间复杂度：O(n)。

3.2 链表 linked list

不需要一段连续的内存空间。
随机访问效率低，时间复杂度：O(n)。
插入删除效率高，时间复杂度：O(1)。

3.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）实际跳表形态

由于增加和删除，会使索引不完全工整，有的地方会多跨几步，有的地方会少跨几步。
索引的维护成本高：每次插入和删除的时候，索引都要更新一遍。

3.4 例题

一维数组的坐标变换。

题目	要点
#283. 移动零	快慢指针（不一定是指针）
#11. 盛最多水的容器	左右夹逼，左右向中间收敛
~~#70. 爬楼梯~~	动态规划
#1. 两数之和	双指针（相向而行，夹逼）或者哈希表
#15. 三数之和	双指针

#283. 移动零

#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. 盛最多水的容器

#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. 三数之和

#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;
}

4.堆栈和队列

4.1 Stack 栈

Last in，First out.

4.2 Queue 队

First in, First out.

4.3 Double-End Queue （Deque）双端队列

4.4 Priority Queue 优先队列

和 Queue 的区别在于，队列中的数，有顺序，当从尾部插入个数据，队列的数据会重新排列。
底层可能使用 heap 实现的。

4.5 复杂度

	插入	删除/取出	查询
Stack \ Queue \ Deque	O(1)	O(1)	O(n)，因为数据没有顺序
Priority Queue	O(1)	O(log N)	O(log N)

4.6 例题

（1）什么问题用栈解决？

**最近相关性：**类似于洋葱，从内到外，或者从外到内一层层逐渐扩散的样子，而且最外层和最内层时一对。

（2）什么问题用队来解决？

强调 先来后到 的顺序。

所有的数据结构不是直接创造的，而是现实中已有的逻辑，然后抽象成计算机语言。

堆栈和队列的应用。

题目	要点
#20. 有效的括号	最近相关性，stack
#155. 最小栈	双栈（辅助栈），延伸：双栈实现队列
#84. 柱状图中最大的矩形	单调栈 + 哨兵（妙不可言，多看几遍）
#239. 滑动窗口最大值	双端队列（单调队列）

#155. 最小栈

#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. 柱状图中最大的矩形

#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. 滑动窗口最大值

#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;
}

Mark

#算法

学习笔记｜算法

https://www.aimtao.net/algorithm-training/

Posted on

2020-08-07

Licensed under

求职简历 Previous

leetcode｜动态规划 Next