学习笔记|算法

本文最后更新于:2 个月前

一、框架

1.如何精通一个领域?

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

2.数据结构

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

  1. 一维数据结构

    • 基础:数组 array(string)、链表 linked list

    • 高级:栈 stack、队列 queue、双端队列 deque、集合 set、映射 map(hash or map)

  2. 二维数据结构

    • 基础:树 tree、图 graph、
    • 高级:二叉搜索树 binary search tree、红黑树 red-black tree,AVL、堆 heap、并查集 disjoint set、字典树 Trie
  3. 特殊数据结构

    • 位运算 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.如何做算法题

  1. Clarification:理解清楚题意

  2. Possible solutions:把所有可能的方法过一遍

    • compare 比较时间空间复杂度
    • optimal 最理想的
  3. Coding:多写

  4. 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)思想

主要思想:升维、空间换时间。

做法:增加多级索引,将一维链表,升级为二维数据结构。

2020-08-08-BI4elE

(2)索引个数

n 个元素最多有多少级索引?

log2(n) - 1 个索引,因为 2^x = n。

(3)随机读取的时间复杂度

O(log(n)),每级索引都要访问一次,log2(n) - 1 个索引加上本身的链表,一共访问 log2(n) 次。

2020-08-08-1TEaPM

(4)空间复杂度

O(n),从最高级索引到第一级索引:{ n/2,n/4,n/8,… 8,4,2 },求和 = a1*((1 - q^n) / (1 - q))= n - 1。

(5)实际跳表形态

  • 由于增加和删除,会使索引不完全工整,有的地方会多跨几步,有的地方会少跨几步。

  • 索引的维护成本高:每次插入和删除的时候,索引都要更新一遍。

2020-08-08-mFWE8f

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

四、堆栈和队列

1.Stack 栈

Last in,First out.

2.Queue 队

First in, First out.

3.Double-End Queue (Deque)双端队列

2020-08-09-Rt6ZE2

4.Priority Queue 优先队列

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

5.复杂度

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

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

本博客所有文章均个人原创,除特别声明外均采用 CC BY-SA 4.0协议,转载请注明出处!

 目录

致敬李文亮及各路英雄好汉!