打怪之旅-数据结构与算法

发表于 | 分类于 | 次阅读
字数统计: 17.8k 字 | 阅读时长 ≈ 79 分钟
leetcode刷题记录以及总结

刷题顺序： 数组 ->字符串 ->链表->二分查找->排序->哈希表-> 栈->队列 ->树 、递归、回溯 -> 堆

根据这位作者（代码随想录）的刷题步骤

刷题网站：https://programmercarl.com/

数据结构相关

基础的数据结构：数组、字符串、树、堆、栈、队列、哈希表

数组

数组是存放在连续内存空间上的相同类型数据的集合。

一维数组在内存空间的地址是连续的，而二维数组在内存中是存放各个一维数组的首地址的一维数组，再指向各个一维数组的连续内存地址。

题：

35. 搜索插入位置

（二分）

27. 移除元素

(同26. 删除排序数组中的重复项）双指针

209. 长度最小的子数组

滑动窗口(类似于双指针)

59. 螺旋矩阵 II

注意循环边界

链表

链表节点的定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 单链表
struct ListNode {
    int val;  // 节点上存储的元素
    ListNode *next;  // 指向下一个节点的指针
    ListNode(int x) : val(x), next(NULL) {}  // 节点的构造函数
};

struct ListNode {
   	 int val;
     ListNode *next;
     ListNode() : val(0), next(nullptr) {}
     ListNode(int x) : val(x), next(nullptr) {}
     ListNode(int x, ListNode *next) : val(x), next(next) {}
};

C++默认生成一个构造函数，但是这个构造函数不会初始化任何成员变化（在初始化的时候就不能直接给变量赋值）。在C++里最好是手动释放内存

题：

203. 移除链表元素

(设置虚拟头节点，这样避免头节点的特殊处理~)

707. 设计链表

（链表的增删查改）

206. 反转链表

（改变指针的指向）

142. 环形链表 II

（快慢指针）

有关于慢指针进入环的第一圈就一定会和快指针相遇的解释，也可这么理解:从慢指针进入环（环长为m）那一刻开始算，假设相遇时，慢指针走了x,快指针则为2x。x若大于等于m/2，那快指针一定遇上了慢指针。（也可以理解为物理里面的相对运动~~）

哈希表

（牺牲空间换时间）

「一般来说哈希表都是用来快速判断一个元素是否出现集合里」。

对于哈希表，要知道「哈希函数」和「哈希碰撞」在哈希表中的作用.

哈希函数是把传入的key映射到符号表的索引上。

哈希碰撞处理有多个key映射到相同索引上时的情景，处理碰撞的普遍方式是拉链法（链表）和线性探测法（移动到空位）。

哈希法的数据结构

  • 数组

  • set （集合）

  • map(映射)

    C++

图片

图片

红黑树是一种平衡二叉搜索树，所以key值是有序的，但key不可以修改，改动key值会导致整棵树的错乱，所以只能删除和增加。

使用集合来解决哈希问题的时候，优先使用unordered_set，因为它的查询和增删效率是最优的，如果需要集合是有序的，那么就用set，如果要求不仅有序还要有重复数据的话，那么就用multiset。

set 与 map 的异同：

均为关联式容器，有序的key 均以RBTree作为底层容器 。

但set所得元素的只有key没有value，value就是key ，不能通过迭代器来改变set的值；而map所有元素都是键+值存在 , map的键是不能修改的，但是其键对应的值是可以修改的.

题：

242. 有效的字母异位词

数组哈希（比map空间消耗要少，因为map要维护红黑树或者符号表，而且还要做哈希函数的运算。）

349. 两个数组的交集

set哈希 （set与vector的相互转换）

1
2
3
vector<int> nums1
// 无重复数的num1
unordered_set<int> nums_set(nums1.begin(), nums1.end());

无法使用数组来做哈希表了。

「主要因为如下两点：」

  • 数组的大小是有限的，受到系统栈空间（不是数据结构的栈）的限制。
  • 如果数组空间够大，但哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。

202. 快乐数

（所谓“无限循环”，unordered_set来判断一个数是否重复出现过）

1. 两数之和

(利用map的key-value特性)

1
unordered_map<int, int> map;

15. 三数之和

18. 四数之和

（15，18都有难度，和二数之和不太一样，双指针更好一些）

454. 四数相加 II

（只需要求次数，而且可重复，因此~用map）

字符串

字符串与数组的区别

字符串是若干字符组成的有限序列，也可以理解为是一个字符数组.

在C语言中，把一个字符串存入一个数组时，也把结束符 ‘\0’存入数组，并以此作为该字符串是否结束的标志。

在C++中，提供一个string类，string类会提供 size接口，可以用来判断string类字符串是否结束，就不用’\0’来判断是否结束

vector< char > 和 string: 在基本操作上没有区别，但是 string提供更多的字符串处理的相关接口，例如string 重载了+，而vector却没有。

题：

344. 反转字符串

541. 反转字符串 II

剑指 Offer 05. 替换空格

151. 翻转字符串里的单词

(先整体反转，再局部反转)

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
48
49
50
方法一:双指针+栈  时间复杂度 O(n),空间复杂度 O(n)
    
 // 思路： 先利用双指针将单词分割出来存入栈中，然后依次弹出
        int len = s.size();
        if(len < 2) return s;

        stack<string> word;
        int slow = 0, fast = 0;

        // 用slow过空格
        while(slow < len){
            if( s[slow] != ' '){
                fast = slow;
                while(s[fast] != ' ' && fast < len) fast++;
                word.push(s.substr(slow,fast-slow));
                slow = fast;
            }
            slow++;
        }

        // 用fast去过空格
        // // 去除开头的空格
        // while(s[slow] == ' ') slow++;
        //     fast = slow;

        // while(slow < len){
        //     // cout<<slow<<' '<<fast<<endl;
        //     if (s[fast] == ' ' || fast == len){
        //         // s.substr(a,b)是从a数到后面第b个
        //         // cout<<s.substr(slow,fast-slow)<<endl;
        //         word.push(s.substr(slow,fast-slow));
        //         // cout<<slow<<' '<<fast<<endl;
        //         // 去除单词之间的空格
        //         while(s[fast] == ' ') fast++;
        //         slow = fast;
        //     }
        //     else
        //         fast++;
            
        // }
       
        string result="";
        while(!word.empty()){
            result += word.top() + ' ';
            // cout<<word.top()<<endl;
            word.pop();
        } 
        //删去最后一个空格
        result.pop_back();
        return result;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
方法二:流+栈 时间复杂度 O(n),空间复杂度 O(n)
    
        // istringstream是C++ 里面的一种输入输出控制类，istringstream类用于执行C++ 风格的串流的输入操作，istringstream对象可以绑定一行字符串，然后以空格为分隔符把该行分隔开来。

        istringstream s_string(s);
        stack<string> word;
        string str;
        while(s_string >> str){
            word.push(str);
            word.push(" ");
        }
        // 去掉最后一个空格.
        word.pop();


        string result = "";
        while( ! word.empty()){
            result += word.top();
            word.pop();
        }
        return result;
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
方法三:
// 时间复杂度 O(n),空间复杂度 O(1)
 // 双指针
// 思路： 移除多余空格,再整个字符反转.最后反转每个单词

    // 交换
    void change(char& a, char& b){
        a ^= b;
        b ^= a;
        a ^= b;
    }

    // 移除多余的空格（快慢指针）
    void removeExtraSpace(string& s ){
        int slow = 0, fast = 0;
        int len = s.size();
        // 去除前面的空格
        while(s[fast] == ' ' && fast < len) fast++;
        for(; fast < len; fast++){
            // 去除单词之间多余的空格
            if (fast > 1 && s[fast] == ' ' && s[fast-1] == ' ')
                continue;
            else{
                s[slow++] = s[fast];
            }
        }

        removeExtraSpace(s);
        cout<<s<<endl;
        int len = s.size();
        reverse(s,0,len-1);
        cout<<s<<endl;
        int start = 0, end = 0;
        for(;start < len; start++){
            // cout<<start<<' '<<end<<endl;
            if(s[start] != ' '){
                end = start;
                while(s[end] != ' ' && end < len) end++;
                // cout<<start<<' '<<end<<endl;
                reverse(s,start,end-1);
                start = end;
                // end++;
            }
        }
        return s;

剑指 Offer 58 - II. 左旋转字符串

（先局部反转再整体反转．）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
方法一：栈
//　栈（时间复杂度Ｏ(n),空间复杂度Ｏ(ｎ)）
class Solution {
public:

    string reverseLeftWords(string s, int n) {
        
        int len = s.size();
        stack<string> word;
        word.push(s.substr(0,n));
        word.push(s.substr(n,len-n));
        // cout<<s.substr(n,len-n)<<s.substr(0,n);

        string str;
        while(! word.empty()){
            str += word.top();
            word.pop();
        }
        return str;
    }
};
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
方法二：
//　局部反转＋整体反转（时间复杂度Ｏ(n),空间复杂度Ｏ(1)）
class Solution {
public:

    // 交换
    void change(char& a, char &b){
        a ^= b;
        b ^= a;
        a ^= b;
    }
    // 反转区间在［start, end］
    void reverse(string& s, int start, int end){
        for (int i = start, j = end; i <  j; i++, j--){
            change(s[i], s[j]);
        }
    }

    string reverseLeftWords(string s, int n) {
        
        int len = s.size();

        reverse(s, 0, n-1);
        reverse(s, n, len-1);
        reverse(s, 0 ,len-1);
        return s;
    }
};

或者用自带的库函数
class Solution {
    public:
        string reverseLeftWords(string s, int n) {
            reverse(s.begin(), s.begin() + n);
            reverse(s.begin() + n, s.end());
            reverse(s.begin(), s.end());
            return s;
        }
};

KMP算法

时间O(m+n),空间O(m)

大佬讲解文章

对应视频

主要解决字符串匹配．重复子串问题

KMP的经典思想就是:「当出现字符串不匹配时，可以记录一部分之前已经匹配的文本内容，利用这些信息避免从头再去做匹配。」

核心：前缀表

（前缀包含首字母，不包含尾字母的子串；后缀则是不包含首字母，包含尾字母的子串）
定义大体是这样: 设S为非空字符串。若字符串A=BS,则B是A的前缀子串；若A=SB,B是A的后缀子串。比如aabaa:

前缀 后缀
a a
aa aa
aab baa
aaba abaa

「前缀表是用来回溯的，它记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配。」

前缀表的任务是当前位置匹配失败，找到之前已经匹配上的位置，在重新匹配，此也意味着在某个字符失配时，前缀表会告诉你下一步匹配中，模式串应该跳到哪个位置。

寻找最长相等前后缀（前缀表存放的值）

i 后缀末尾，　j前缀末尾；

j也代表了ｉ包括ｉ之前子串的最长相等前后缀．

28. 实现 strStr()

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
48
class Solution {
public:

    // 生成前缀表
    void getNext(int *next, const string& s){
        // 前缀表的值均减１
        int j = -1, len = s.size();
        next[0] = -1;
        // 求下一个i
        for(int i = 1; i < len; i++){
            // 前后缀不相同,回退到之前相同的地方
            while (j > -1 && s[j + 1] != s[i]) 
                j = next[j];
            // 前后缀相同,下移
            if (s[j + 1] == s[i])　j++;
            // 将j（前缀的长度）赋给next[i]
            next[i] = j;
        }

    }
    int strStr(string haystack, string needle) {
        int len = needle.size();
        if (len == 0) return 0;

        // 得到needle的前缀表
        int next[len];
        getNext(next,needle);

        int j = -1;
        // 字符串匹配
        for(int i = 0; i < haystack.size(); i++){
            // 不匹配，j向前移 
            while(j > -1 && haystack[i] != needle[j + 1])
                j = next[j];

             // 匹配，j和i同时向后移动 
            if (haystack[i] == needle[j + 1])
                j++;
            // 如果j到了needle的末尾,则匹配成功
            if (j == len-1)
            // 返回当前在文本串匹配模式串的位置i 减去 模式串的长度，就是文本串字符串中出现模式串的第一个位置
                return (i-j);
        }
        return -1;
        

    }
};

459. 重复的子字符串

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
// KMP
class Solution {
public:
     
    // 得到前缀表
    void getNext(int* next, string &s){
        // 整体减1
        int j = -1;
        next[0] = j;

        for(int i = 1; i < s.size(); i++){
            // 匹配不对,回到上次匹配的地方
            while(j > -1 && s[i] != s[j+1])
                j = next[j];
            
            // 匹配则下移
            if(s[i] == s[j+1])
                j++;
            
            // 更新
            next[i] = j;
        }
    }

    bool repeatedSubstringPattern(string s) {
        
        int len = s.size();
        int next[len];
        getNext(next, s);

        int max_equal = next[len-1] + 1;
        // cout<< max_equal<<' '<<len;
        //重复子串的判断方式
        if( max_equal != 0 && len % (len - max_equal) == 0) return true;
        return false;

        // for(int i = 0; i < len; i++)
        //     cout<<next[i]+1<<' ';
        
    }
};

栈和队列（C++）

  1. C++中stack 是容器么？

    不是，是container adapter（容器适配器）【同队列】

  2. 我们使用的stack是属于那个版本的STL？

    SGI STL 由Silicon Graphics Computer Systems公司参照HP STL实现，被Linux的C++编译器GCC所采用，SGI STL是开源软件，源码可读性甚高。

  1. 我们使用的STL中stack是如何实现的？

    栈的内部结构，栈的底层实现可以是vector，deque，list 都是可以的， 主要就是数组和链表的底层实现。

    「栈是以底层容器完成其所有的工作，对外提供统一的接口，底层容器是可插拔的（也就是说我们可以控制使用哪种容器来实现栈的功能）。」

    「我们常用的SGI STL，如果没有指定底层实现的话，默认是以deque为缺省情况下栈的低层结构。」deque是一个双向队列，只要封住一段，只开通另一端就可以实现栈的逻辑了。「SGI STL中 队列底层实现缺省情况下一样使用deque实现的。」

    1
    std::stack<int, std::vector<int> > third;  // 使用vector为底层容器的栈
    1
    std::queue<int, std::list<int>> third; // 定义以list为底层容器的队列

  1. stack 提供迭代器来遍历stack空间么？

    不允许有遍历行为，不提供

题:

232. 用栈实现队列

225. 用队列实现栈

(一个栈: 将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部)

20. 有效的括号

由于栈结构的特殊性，非常适合做对称匹配类的题目

1047. 删除字符串中的所有相邻重复项

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
// 原地操作
class Solution {
public:
    string removeDuplicates(string S) {
        int len = S.size();
        if (len < 2) return S;

        int slow = 0;
        
        // 这种也可以
        // for(int i = 1; i < len; i++){
            
        //     if (slow > -1 && S[i] == S[slow])
        //         slow--;
        //     else
        //         S[++slow] = S[i];
        // }
        // S.resize(slow+1);

        for(int i = 0; i < len; i++){
            // 试探移至下一位
            if (slow > 0 && S[i] == S[slow - 1])
                slow--;
            else
                S[slow++] = S[i];
        }
        S.resize(slow);
        return S;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 字符串作栈
class Solution {
public:
    string removeDuplicates(string S) {
        int len = S.size();
        if (len < 2) return S;
        string result;

        for(int i = 0; i < len; i++){
            if (result.empty() || S[i] != result.back())
                result.push_back(S[i]);   
            else
                result.pop_back();

        }
        return result;
    }
};
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
// 反向入栈
class Solution {
public:
    string removeDuplicates(string S) {
        int len = S.size();
        if (len < 2) return S;

        stack<char> st;
        // 从后面往前读
        for(int i = len - 1; i > -1; i--){
            if (st.empty() || S[i] != st.top())
                st.push(S[i]);   
            else
                st.pop();
        }
           
        string result;

        while( ! st.empty()){
            result += st.top();
            st.pop();
        }
        return result;
    }
};

150. 逆波兰表达式求值—有一点小问题

在C++中是不能对字符串std::string使用switch/case语句的,把string 做一下hash处理,变成一个int数.

  • 如何哈希

  • atoi 与 stoi的区别

    相同点：
    ①都是C++的字符处理函数，把数字字符串转换成int输出
    ②头文件都是#include
    不同点：
    ①atoi()的参数是 const char ,因此对于一个字符串str我们必须调用 c_str()的方法把这个string转换成 const char类型的,而stoi()的参数是const string,不需要转化为 const char；

    ②stoi()会做范围检查，默认范围是在int的范围内的，如果超出范围的话则会runtime error！
    而atoi()不会做范围检查，如果超出范围的话，超出上界，则输出上界，超出下界，则输出下界；

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
class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int>  st;
        unordered_map<string,int> mapStringValues;
        mapStringValues["+"] = 0;
        mapStringValues["-"] = 1;
        mapStringValues["*"] = 2;
        mapStringValues["/"] = 3;

        for (int i = 0; i < tokens.size(); i++){
            if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/") {
                int a = st.top();
                st.pop();
                int b = st.top();
                st.pop();
            // if (tokens[i] == "+") st.push(a+b);
            // if (tokens[i] == "-") st.push(b-a);
            // if (tokens[i] == "*") st.push(a*b);
            // if (tokens[i] == "/") st.push(b/a);
            // // 把string 做一下hash处理,变成一个int数
                switch(mapStringValues[tokens[i].data()]){
                    case 0: st.push(a+b); break;
                    case 1: st.push(b-a); break;
                    case 2: st.push(a*b); break;
                    case 3: st.push(b/a); break;
                }
            }
            else 
                //stoi将string 转换为 int 
                // st.push(tokens[i]);
                st.push(stoi(tokens[i]));
        }

        return st.top();
    }
};

239. 滑动窗口最大值

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
48
49
class Solution {
private:
    // 单调队列(用双向队列来实现)
    class DecreaseQue{
        // 只需要维护有可能成为窗口里最大值的元素就可以了，同时保证队列里的元素数值是由大到小的。
        public:
            deque<int> que;
            
            void pop(int value){
                // 每次弹出的时候，比较当前要弹出的数值是否等于队列出口(前)元素的数值，如果相等则弹出。
                // 相等就弹出 是 舍弃滑动窗口移动后前一位的值
                if( ! que.empty() && value == que.front())
                     que.pop_front();
            }
            
            void push(int value){
                // 压入比入口小的值
                while( !que.empty() &&  value > que.back())
                    que.pop_back();
                que.push_back(value);
            }

            // 出口最大值
            int front(){
               return que.front();
            }
    };
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int len = nums.size();
        if (len < 2) return nums;
        
        DecreaseQue de;
        vector<int> result;

        for( int i = 0; i < len; i++){
            if (i < k) de.push(nums[i]);
            else{
                de.pop(nums[i-k]);
                de.push(nums[i]);
                result.push_back(de.front());
            }
            // 保存第一个滑动窗口的值
            if(i == k-1) result.push_back(de.front());
        }

        return result;
    }
};

347. 前 K 个高频元素—有一点小问题

如何手写堆，优先队列.:https://leetcode-cn.com/problems/top-k-frequent-elements/solution/python-dui-pai-xu-by-xxinjiee/

小顶堆，因为要统计最大前k个元素; 大顶堆，因为要统计最小前k个元素.

可以这么理解：（小顶堆求最大TOPK）堆（size = k）里存放的是当前元素的频率，其中堆顶的元素最小。加入新进来的元素，此时若size>k，弹出堆顶元素，调整堆。【大顶堆求最小TOPK类似】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//利用 multimap
vector<int> topKFrequent(vector<int>& nums, int k) {
            unordered_map<int, int> cout_map;

            for(int i = 0; i < nums.size(); i++){
                cout_map[nums[i]]++;
            }

            // 降序排序
            multimap<int,int,greater<int>> ordermap;

            for( auto num : cout_map){
                ordermap.insert(pair<int, int>(num.second, num.first));
            }

            // 输出
            vector<int> result;
            for( auto num : ordermap){
                result.push_back(num.second);
                if(--k) break;
            }

            return result;
    }
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
// 优先级队列 「就是一个披着队列外衣的堆」，因为优先级队列对外接口只是从队头取元素，从队尾添加元素，再无其他取元素的方式，看起来就是一个队列。缺省情况下priority_queue利用max-heap（大顶堆）完成对元素的排序，这个大顶堆是以vector为表现形式的complete binary tree（完全二叉树）。

//「堆是一颗完全二叉树，树中每个结点的值都不小于（或不大于）其左右孩子的值。」 如果父亲结点是大于等于左右孩子就是大顶堆，小于等于左右孩子就是小顶堆。而且优先级队列内部元素是自动依照元素的权值排列。

//「所以我们要用小顶堆，因为要统计最大前k个元素，只有小顶堆每次将最小的元素弹出，最后小顶堆里积累的才是前k个最大元素。」

// 小顶堆，因为要统计最大前k个元素;  大顶堆，因为要统计最小前k个元素.

class Solution {
private:
    // 小顶堆
    class mycomparison{
        public:
            bool operator()(const pair<int, int>& lhs, const pair<int, int> &rhs){
                return lhs.second> rhs.second;
            }
    };

public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
            unordered_map<int, int> cout_map;

            for(int i = 0; i < nums.size(); i++){
                cout_map[nums[i]]++;
            }

            // 小顶堆-优先队列
            priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;

            for(unordered_map<int, int>::iterator it = cout_map.begin(); it != cout_map.end(); it++){
                    pri_que.push(*it);
                    if (pri_que.size() > k){
                        pri_que.pop();
                    }
            }

            // 输出,因为小顶堆先弹出的是最小的，所以倒叙来输出到数组
            vector<int> result(k);
            for(int i = k - 1; i > -1; i--){
                result[i] = pri_que.top().first;
                pri_que.pop();
            }

            return result;
    }
};

NC119.最小的K个数

大根堆：首先利用前k个数构建“大顶堆”，剩余元素依次与堆顶元素相比较。

  • 如果大于堆顶元素，则不做处理

  • 如果小于堆顶元素，则将堆顶元素与这个元素交换，然后再恢复堆序。

    这样的话最后这个堆里面保存的就是最小的k个数（无序），可以通过。

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
48
49
50
51
52
53
54
55
//  大顶堆 a[i]< a[2i+1] a[i]<a[2i+2]   
    void swap(vector<int> &a, int i, int j){
        a[i] ^= a[j];
        a[j] ^= a[i];
        a[i] ^= a[j];
    }
    
    void adjustHeap(vector<int> &a, int i, int k){
        int curVal = a[i];
        for(int kidIndex = 2*i+1; kidIndex < k; kidIndex = 2*kidIndex+1){
            //比较 左右孩子
            if(kidIndex+1 < k && a[kidIndex] < a[kidIndex+1])
                kidIndex++;
            
            if(a[kidIndex] > curVal){
                a[i] = a[kidIndex];
                i = kidIndex;
            }
            else{
                break;
            }
        }
        a[i] = curVal;
            
    }
    
    void heapSort(vector<int> &a, int k){
        // 创建k堆,从第一个非叶子节点 从下至上，右至左       
        for(int i = k/2-1; i > -1; i--){
            adjustHeap(a, i, k);
        }

        //剩余元素依次与堆顶比较
        for(int i = k; i < a.size(); i++){
            if(a[i] < a[0]){
                swap(a, 0, i);
                adjustHeap(a, 0, k);
            }
        }
 //         //这一步若不要求K个排好序的，可以省去
//         //堆排序(交换堆顶与末尾元素，调整堆,逐渐将最大值沉到最后)
//         for(int i = k-1; i > 0; i--){
//                 swap(a, 0, i);
//                 adjustHeap(a, 0, i);
//         }
        
    }
    
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        int len = input.size();
        if (len <= 0 || len < k || k <= 0 )
             return vector<int>();
         heapSort(input, k);
         return vector<int>(input.begin(), input.begin()+k);
    }

NC88 寻找第K大

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
48
49
50
51
52
53
54
55
56
57
58
//  小顶堆 a[i]> a[2i+1] a[i]>a[2i+2]   
    void swap(vector<int> &a, int i, int j){
        a[i] ^= a[j];
        a[j] ^= a[i];
        a[i] ^= a[j];
    }
    
    void adjustHeap(vector<int> &a, int i, int k){
        int curVal = a[i];
        for(int kidIndex = 2*i+1; kidIndex < k; kidIndex = 2*kidIndex+1){
            //比较 左右孩子
            if(kidIndex+1 < k && a[kidIndex] > a[kidIndex+1])
                kidIndex++;
            
            if(a[kidIndex] < curVal){
                a[i] = a[kidIndex];
                i = kidIndex;
            }
            else{
                break;
            }
        }
        a[i] = curVal;
            
    }
    
    void heapSort(vector<int> &a, int k){
        // 创建k堆,从第一个非叶子节点 从下至上，右至左       
        for(int i = k/2-1; i > -1; i--){
            adjustHeap(a, i, k);
        }        
        //剩余元素依次与堆顶比较
        for(int i = k; i < a.size(); i++){
            if(a[i] > a[0]){
                swap(a, 0, i);
                adjustHeap(a, 0, k);
            }
        }
        
//         //这一步若不要求K个排好序的，可以省去
//         //堆排序(交换堆顶与末尾元素，调整堆,逐渐将最小值沉到最后)
//         for(int i = k-1; i > 0; i--){
//                 swap(a, 0, i);
//                 adjustHeap(a, 0, i);
//         }
    }
    
    int findKth(vector<int> a, int n, int K) {
  
        heapSort(a, K);
        for(auto val : a){
            cout<<val<<" ";
        }
//         没有排好序
        return a[0];
//         排好序
//         return a[K-1];
    }

NC97 出现次数的TopK问题

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
48
49
50
51
52
#include <unordered_map>

class Solution {
public:
    /**
     * return topK string
     * @param strings string字符串vector strings
     * @param k int整型 the k
     * @return string字符串vector<vector<>>
     */
    class cmp{
        public:
         bool operator()(const pair<string, int> &a, const pair<string, int> &b){
             //频率相同
             if (a.second == b.second) return a.first < b.first;
             //频率不相同
             return a.second > b.second;      
         }
    };

    vector<vector<string> > topKstrings(vector<string>& strings, int k) {
        // write code here
        vector<vector<string>>  res;
        unordered_map<string, int> mp;
        
        //统计频率
        for(string str : strings)
            mp[str]++;
        
        //优先队列（小顶堆）
        priority_queue<pair<string, int>, vector<pair<string, int>>, cmp> pri_qe;
        
        for(unordered_map<string, int>::iterator it = mp.begin(); it != mp.end(); it++){
            pri_qe.push(*it);
            if (pri_qe.size() > k){
                        pri_qe.pop();
                    }
        }
        
        //由优先级从小到大依次取出
        while(!pri_qe.empty()) { 
            //emplace_back 函数的作用是减少对象拷贝和构造次数，是C++11中的新特性，主要适用于对临时对象的赋值。
            res.emplace_back(vector<string> {pri_qe.top().first, to_string(pri_qe.top().second)});
            pri_qe.pop();
        }
        
        // 输出,因为小顶堆先弹出的是最小的，所以倒叙来输出到数组
       reverse(res.begin(), res.end());
        
        return res;
    }
};

二叉树

二叉树的种类

在我们解题过程中二叉树有两种主要的形式：满二叉树和完全二叉树。

满二叉树【国内定义】：如果一棵二叉树只有度为0的结点（叶子节点）和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。也可以说深度为k，有2^k-1个节点的二叉树。【国外定义：满二叉树就是没有度为1的节点】

image-20210405162207653

完全二叉树: 在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点.

image-20210304214456883

优先级队列其实是一个堆，堆就是一棵完全二叉树，同时保证父子节点的顺序关系。

二叉搜索树:二叉搜索树是有数值的了，「二叉搜索树是一个有序树」。

  • 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
  • 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
  • 它的左、右子树也分别为二叉排序树

图片

平衡二叉搜索树:又被称为AVL（Adelson-Velsky and Landis）树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

图片

「C++中map、set、multimap，multiset的底层实现都是平衡二叉搜索树」，所以map、set的增删操作时间时间复杂度是logn，注意我这里没有说unordered_map、unordered_set，unordered_map、unordered_map底层实现是哈希表,时间复杂度是o(1)。

二叉树的存储方式

「二叉树可以链式存储(指针)，也可以顺序存储(数组)。」

「如果父节点的数组下表是i，那么它的左孩子就是i * 2 + 1，右孩子就是 i * 2 + 2。」

二叉树的遍历方式

  1. 深度优先遍历：先往深走，遇到叶子节点再往回走。
  2. 广度优先遍历：一层一层的去遍历。

「这两种遍历是图论中最基本的两种遍历方式」

  • 深度优先遍历(前中后其实指的就是中间节点的遍历顺序)

    • 前序遍历（递归法，迭代法）
    • 中序遍历（递归法，迭代法）
    • 后序遍历（递归法，迭代法）

图片

栈其实就是递归的一种是实现结构，也就说前中后序遍历的逻辑其实都是可以借助栈使用非递归的方式来实现的。

  • 广度优先遍历

    层次遍历（迭代法）

一般使用队列来实现，这也是队列先进先出的特点所决定的，因为需要先进先出的结构，才能一层一层的来遍历二叉树。

1
2
3
4
5
6
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

二叉树的定义

  • 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数。
  • 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数。
  • 求深度可以从上到下去查 所以需要前序遍历（中左右），而高度只能从下到上去查，所以只能后序遍历（左右中）

问题

  1. 平衡二叉搜索树是不是二叉搜索树和平衡二叉树的结合？

    是的，是二叉搜索树和平衡二叉树的结合。

  2. 平衡二叉树与完全二叉树的区别在于底层节点的位置？

    是的，完全二叉树底层必须是从左到右连续的，且次底层是满的。

  3. 堆是完全二叉树和排序的结合，而不是平衡二叉搜索树？

    堆是一棵完全二叉树，同时保证父节点一定>=子节点的顺序关系（有序）。「完全二叉树一定是平衡二叉树，搜索树是中大于左小于右，堆不是平衡二叉搜索树」

递归三要素

  1. 「确定递归函数的参数和返回值：」确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
  2. 「确定终止条件：」写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。
  3. 「确定单层递归的逻辑：」确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。

题:

二叉树大纲

144. 二叉树的前序遍历

94. 二叉树的中序遍历

145. 二叉树的后序遍历–Morris 遍历(面试几乎不会考)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
递归版
    //前序
class Solution {
public:
    void treeVisit(TreeNode* node, vector<int>& result){
        if (node == nullptr) return;
        result.push_back(node->val);
        treeVisit(node->left, result);
        treeVisit(node->right, result);
    }
    
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        treeVisit(root, result);
        return result;
    }
};
	只需要将treeVisit中节点顺序替换
  //中序
  //后序
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
迭代版
// 前序
//前序遍历的顺序是中左右，先访问的元素是中间节点，要处理的元素也是中间节点，所以刚刚才能写出相对简洁的代码，「因为要访问的元素和要处理的元素顺序是一致的，都是中间节点。」
    
 过程如下：
    初始化栈，并将根节点入栈；
    当栈不为空时：
        弹出栈顶元素 node，并将值添加到结果中；
        如果 node 的右子树非空，将右子树入栈；
        如果 node 的左子树非空，将左子树入栈；
    
 // 关键点:前序入栈就输出. 
class Solution {
public:

    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode *> st;

        // 根节点入栈
        if (root != nullptr) st.push(root);

        // 遍历节点
        while( ! st.empty()){
            // 访问
            TreeNode *node = st.top();  // 中
            st.pop();
            if(node != nullptr)
                // 处理
                result.push_back(node->val);
            else
                continue;
            // 先进后出
            st.push(node->right); // 右
            st.push(node->left); //左
        }
      
        //或者这么写
        // 根节点入栈
        if (root) st.push(root);

        // 遍历节点
        while( ! st.empty()){
            // 访问
            TreeNode *node = st.top();
            st.pop();
            if(node != nullptr)
                        // 先放入中间节点,然后访问左节点,最后访问右节点
                        result.push_back(node->val);
            // 先进后出
            if(node->right) st.push(node->right);
            if(node->left)  st.push(node->left);
        }
        
        return result;
    }
};

// 思路二: 先遍历左孩子,到末尾后回退到右孩子,再找右孩子的左节点.
class Solution {
public:
   
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        // 保存访问过的节点
        stack<TreeNode*> st;
        // 用于访问节点(遍历)
        TreeNode* cur = root;

        while(cur != nullptr || ! st.empty()){
            if (cur != nullptr){
                // 中
                result.push_back(cur->val);
                st.push(cur);
                //左
                cur = cur->left; 
            }
            else{
                // 右
                cur = st.top();
                st.pop();
                cur = cur->right;
            }
        }
        return result;
    }
};

// 中序
//中序遍历是左中右，先访问的是二叉树顶部的节点，然后一层一层向下访问，直到到达树左面的最底部，再开始处理节点（也就是在把节点的数值放进result数组中），这就造成了「处理顺序和访问顺序是不一致的。


// 关键点:出栈再输出
class Solution {
public:
   
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        // 保存访问过的节点
        stack<TreeNode*> st;
        // 用于访问节点(遍历)
        TreeNode* cur = root;

        while(cur != nullptr || ! st.empty()){
            if (cur != nullptr){
                // 访问节点并进栈
                st.push(cur);
                //左
                cur = cur->left; 
            }
            else{
                // 处理数据
                cur = st.top();
                st.pop();
                // 中
                result.push_back(cur->val);
                // 右
                cur = cur->right;
            }
        }
        return result;
    }
};
//思路二:标记法
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        if (root != NULL) st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();
            if (node != NULL) {
                st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
                if (node->right) st.push(node->right);  // 添加   右     节点（空节点不入栈）

                st.push(node);                          // 添加中节点
                st.push(NULL); // 中      节点访问过，但是还没有处理，加入空节点做为标记。

                if (node->left) st.push(node->left);    // 添加    左         节点（空节点不入栈）
            } else { // 只有遇到空节点的时候，才将下一个节点放进结果集
                st.pop();           // 将空节点弹出
                node = st.top();    // 重新取出栈中元素
                st.pop();
                result.push_back(node->val); // 加入到结果集
            }
        }
        return result;
    }
};


// 后序
//思路二: 仅利用栈去判断该节点是否为父结点，创新性思路是每次在栈中压入父节点后压入nullptr，之后再依次压入右子节点和左子节点。(标记法)
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        if (root == nullptr) return {};
        stack<TreeNode*> stk;
        stk.push(root);
        vector<int> res;
        while (!stk.empty()) {
            TreeNode* node = stk.top();
            
            if (node == nullptr) {
                // 只有遇到空节点的时候，才将下一个节点放进结果集
                stk.pop();
                res.push_back(stk.top()->val);//中
                stk.pop();
                continue;
            }
            // 标记父节点
            stk.push(nullptr);
            
            // 空节点不入栈
            if (node->right) {
                stk.push(node->right);//右
            }
            if (node->left) {
                stk.push(node->left); //左
            }
        }
        return res;
    }
};

作者：dcoliversun
链接：https://leetcode-cn.com/problems/binary-tree-postorder-traversal/solution/a-li-mian-shi-ti-zhi-yong-zhan-qu-zuo-er-cha-shu-d/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。


//思路一(取巧):先序遍历是中左右，后续遍历是左右中，那么我们只需要调整一下先序遍历的代码顺序，就变成   中右左   的遍历顺序，然后在     反转result数组，输出的结果顺序就是  左右中
class Solution {
public:
    
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;

        // 访问root
        if (root != nullptr) st.push(root);

        //遍历
        while( ! st.empty()){
            // 中
            TreeNode* node = st.top();
            st.pop();
            if( node != nullptr){
                // 处理
                result.push_back(node->val);
            }
            else{
                // 返回上一节点
                continue;
            }

            // 左
            st.push(node->left);
            //右
            st.push(node->right);
        }

        reverse(result.begin(), result.end());
        return result;
    }
};

102. 二叉树的层序遍历

在 BFS 遍历的基础上区分遍历的每一层，就得到了层序遍历。在层序遍历的基础上记录层数，就得到了最短路径.

BFS 遍历中某个时刻队列的状态

此时队列中的结点是 3、4、5，分别来自第 1 层和第 2 层。这个时候，第 1 层的结点还没出完，第 2 层的结点就进来了，而且两层的结点在队列中紧挨在一起，我们无法区分队列中的结点来自哪一层。

因此，在每一层遍历开始前，先记录队列中的结点数量 n（也就是这一层的结点数量），然后一口气处理完这一层的 n 个结点。

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
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        queue<TreeNode*> qe;
        if(root) {
            qe.push(root);
            qe.push(NULL);
        }
        while( ! qe.empty()){
            vector<int> temp;
            int len = qe.size();
            // 遍历当前队列,不包括新增节点(二叉树的每一层))
            for(int i = 0; i < len; i++ ){
                TreeNode* node = qe.front();
                qe.pop();
                if(node != nullptr){
                    temp.push_back(node->val);
                    if(node->left) qe.push(node->left);
                    if(node->right) qe.push(node->right);
                }
                // else{
                    
                // }
            }
            
            result.push_back(temp);
        }

        return result;

    }
};

层序遍历的一些变种题目

107. 二叉树的层序遍历 II

199. 二叉树的右视图 DFS 与 BFS的运用

637. 二叉树的层平均值

429. N 叉树的层序遍历

589. N 叉树的前序遍历 有用到C++ STL 反向迭代器适配器（reverse_iterator）详解

LeetCode 103. Binary Tree Zigzag Level Order Traversal 之字形层序遍历
LeetCode 515. Find Largest Value in Each Tree Row 计算每一层的最大值

对于最短路径问题，还有两道题目也是求网格结构中的最短路径，和我们讲解的距离岛屿的最远距离非常类似：

LeetCode 542. 01 Matrix
LeetCode 994. Rotting Oranges

还有一道在真正的图结构中求最短路径的问题：

LeetCode 310. Minimum Height Trees

作者：nettee
链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal/solution/bfs-de-shi-yong-chang-jing-zong-jie-ceng-xu-bian-l/
来源：力扣（LeetCode）

226. 翻转二叉树

关键点在于 每个节点遍历一次

———-遍历————

101. 对称二叉树

104. 二叉树的最大深度

111. 二叉树的最小深度

222. 完全二叉树的节点个数

110. 平衡二叉树

257. 二叉树的所有路径

404. 左叶子之和

513. 找树左下角的值

如果需要遍历整颗树，递归函数就不能有返回值。如果需要遍历某一条固定路线，递归函数就一定要有返回值！;后序遍历需要根据左右递归的返回值推出中间节点的状态,这种需要有返回值

112. 路径总和

———-属性————

106. 从中序与后序遍历序列构造二叉树

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
// 分解成一个子问题:找到中间节点,左右子树的中序&&后序, 每层递归定定义了新的vector（就是数组），既耗时又耗空间
class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        
        
        int post_len  = postorder.size();
        // 空节点
        if (post_len == 0)  return nullptr;
       
        // 找到后序遍历的最后一个节点,为中间节点 (左右中)
        int mid_val = postorder[post_len-1];
        TreeNode* root = new TreeNode(mid_val);
        
        // 叶子节点
        if (post_len == 1)  return root;

        // 找到中序遍历的切割点
        int i = 0;
        for(; i < post_len; i++){
            if(inorder[i] == mid_val) break;
        }
        // 找到左右子树的中序遍历,和后序遍历
        // 关键点:中序和后序的大小是一样的
        //  左闭右开区间

        // 中序遍历
        vector<int> left_inorder(inorder.begin(), inorder.begin() + i);
        vector<int> right_inorder(inorder.begin() + i + 1, inorder.end());
        
        // 后序遍历
        // 舍弃中间节点
        postorder.resize(post_len - 1);
        // 左子树中序遍历的大小
        int lo = left_inorder.size();
        vector<int> left_postorder(postorder.begin(), postorder.begin() + lo);
        vector<int> right_postorder(postorder.begin() + lo, postorder.end());
        
        // 查找下一层
        // root->val = mid_val;
        root->left = buildTree(left_inorder, left_postorder);
        root->right = buildTree(right_inorder, right_postorder);

        return root;
        
    }
};
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
48
49
//  优化版
class Solution {
public:
   //左开右闭
    TreeNode* build(vector<int>& inorder, vector<int>& postorder, int ib, int ie, int pb, int pe){
        // 空节点 返回
        if(ie - ib == 0) return nullptr;
        // 找到中间节点,
        int mid_val = postorder[pe-1];
        TreeNode * root = new TreeNode(mid_val);
        // 找到分割索引
        int mid_index = 0;
        for(; mid_index < ie; mid_index++){
            if(inorder[mid_index] == mid_val) break;
        }
        
        //叶子节点
        if(ie - ib == 1) return root;

        // 左右子树的中序\后序
        // 中序
        int left_ib = ib;
        int left_ie = mid_index;
        int right_ib = mid_index + 1;
        int right_ie = ie;

        int left_pb = pb;
        // 终止位置是 需要加上 中序区间的大小size
        int left_pe = pb + (mid_index - ib);
        int right_pb = pb + (mid_index - ib);
        int right_pe = pe - 1;

        // cout << "----------" << endl;
        // cout<<mid_val<< ' '<<mid_index <<endl;
        // cout <<"左子树中序: "<< left_ib<<" "<< left_ie<<" 左子树后序: "<<left_pb<<" "<<left_pe<< endl;
        // cout <<"右子树中序: "<< right_ib<<" "<< right_ie<<" 右子树后序: "<<right_pb<<" "<<right_pe<< endl;

        root->left = build(inorder, postorder, left_ib, left_ie, left_pb, left_pe);
        root->right = build(inorder, postorder, right_ib, right_ie, right_pb, right_pe);
        
        return root;  
    }

    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        
        return build(inorder, postorder, 0, inorder.size(), 0, postorder.size());
        
    }
};
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
//再次优化版:因为后序是左右中，反过来就需要先构建完右子树再构建左子树
//很巧妙利用率后序的特性: [[左子树], [右子树], 根],每次取最后一个节点( post_index--;),优先拿到的是上个节点对应的右树.构建完所有的右子树才会构建左子树(从最下一层的右子树兄弟-左子树开始)
class Solution {
public:
    // 根节点所在位置
    int post_index;
    unordered_map<int, int> idx_map;
   //左闭右闭, 仅分割中序, 左子树[in_left,mid_index - 1] ,右子树[mid_index + 1,in_right]
    TreeNode* build(vector<int>& postorder, int in_left, int in_right){
        // 空节点 返回
        if(in_left > in_right) return nullptr;
        // 找到中间节点,
        int mid_val = postorder[post_index];
        TreeNode * root = new TreeNode(mid_val);
        // 找到分割索引
        int mid_index =idx_map[mid_val];

        // 舍弃最后一个节点
        post_index--;
        // 构造右子树
        root->right = build(postorder, mid_index+1, in_right);
        // 构造左子树
        root->left = build(postorder, in_left, mid_index-1);
        
        return root;  
    }

    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        // 建立 中序 值-下标 map
        int index = 0;
        for (auto it : inorder)
            idx_map[it] = index++;
        int order_len = postorder.size();
        post_index = order_len - 1;
        return build(postorder, 0, order_len-1);
    }
};

105. 从前序与中序遍历序列构造二叉树

「前序和后序不能唯一确定一颗二叉树！」，因为没有中序遍历无法确定左右部分，也就是无法分割。

图片

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
//沿用上一题的方法三思路
class Solution {
public:
    int pre_index;
    unordered_map<int, int> idx_map;

    TreeNode* build(vector<int>& preorder, int left_index, int right_index){
        if(left_index > right_index) return nullptr;
        // 分割点
        int mid_val = preorder[pre_index];
        int mid_index = idx_map[mid_val];

        TreeNode *root = new TreeNode(mid_val);
        pre_index++;

        // 先构建完所有的左子树
        root->left = build(preorder, left_index, mid_index-1);
        //再构建右子树
        root->right = build(preorder, mid_index+1, right_index);

        return root;

    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {

        pre_index = 0;
        int order_len = inorder.size();
        int index = 0;
        for (auto it : inorder){
            idx_map[it]=index++;
        }

        return build(preorder, 0, order_len-1);
    }
};

654. 最大二叉树

617. 合并二叉树

——修改与构造——-

700. 二叉搜索树中的搜索

98. 验证二叉搜索树

特性:中序遍历下，输出的二叉搜索树节点的数值是有序(递增)序列

递归踩雷:左子树所有节点小于中间节点，右子树所有节点大于中间节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//递归版
class Solution {
public:

    //保存前一个访问的结点
    TreeNode *pre = nullptr;

    bool isValidBST(TreeNode* root) {
        
        if (root == nullptr) return true;
    
        bool left_flag = isValidBST(root->left);
        // 这一操作 每次和前一个节点比较, 验证递增
        if(pre && pre->val >= root->val) return false;
        pre = root;

        bool right_flag = isValidBST(root->right);

        return  left_flag && right_flag;
    }
};
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
//迭代版
class Solution {
public:

    //保存前一个访问的结点
    TreeNode *pre = nullptr;

    bool isValidBST(TreeNode* root) {
        
        if (root == nullptr) return true;
        // 保存访问过的节点
        stack<TreeNode*> st;
        // 遍历树
        TreeNode* cur = root;

        while(cur != nullptr || ! st.empty()){
            if(cur){
                // 存储中间节点
                st.push(cur);
                // 访问左孩子
                cur = cur->left;
            }
            else{
                // 处理中间节点
                cur = st.top();
                st.pop();

                // 判断
                if(pre && pre->val >= cur->val) return false;
                pre = cur;
                cur = cur->right;
            }
        }
        
        return true;

    }
};

530. 二叉搜索树的最小绝对差

在有序数组求任意两数最小值差等价于相邻两数的最小值差

501. 二叉搜索树中的众数

236. 二叉树的最近公共祖先

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//自底向上查找 (后序遍历-回溯)
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == nullptr || root == p || root == q) return root;
        
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        // 左右子树找到
        if (left != nullptr && right != nullptr) return root; 
        // 右子树没找到
        else if (left != nullptr && right == nullptr) 
            return left;
        // 左子树没找到
        else if (left == nullptr && right != nullptr)
            return right;
        // 左右子树没找到
        else
            return left;
        
    }
};

235. 二叉搜索树的最近公共祖先

只要从上到下遍历的时候，cur节点是数值在[p, q]区间中则说明该节点cur就是最近公共祖先

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    // 前序遍历
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {

        // root 在 [p,q] 之间
        if (root == nullptr || (root->val >= p->val && root->val <= q->val) || (root->val >= q->val && root->val <= p->val)) 
            return root;

        // root 大于 max[p,q], 往左子树走
        else if(root->val > p->val && root->val > q->val){
            TreeNode *left = lowestCommonAncestor(root->left, p ,q);
            if (left) return left;
        }
        
         // root 小于 min[p,q], 往右子树走
        if(root->val < p->val && root->val < q->val){
            TreeNode *right = lowestCommonAncestor(root->right, p ,q);
            if (right) return right;
        }

        return nullptr;
    }
};

——-二叉搜索树——

701. 二叉搜索树中的插入操作

450. 删除二叉搜索树中的节点

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
class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (root == nullptr) return root; // 第一种情况：没找到删除的节点，遍历到空节点直接返回了
        if (root->val == key) {
            // 第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回NULL为根节点
            // 第三种情况：其左孩子为空，右孩子不为空，删除节点，右孩子补位 ，返回右孩子为根节点
            if (root->left == nullptr) return root->right; 
            // 第四种情况：其右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
            else if (root->right == nullptr) return root->left; 
            // 第五种情况：左右孩子节点都不为空，则将删除节点的左子树放到删除节点的右子树的最左面节点的左孩子的位置
            // 并返回删除节点右孩子为新的根节点。
            else {  
                TreeNode* cur = root->right; // 找右子树最左面的节点
                while(cur->left != nullptr) { 
                    cur = cur->left;
                }
                cur->left = root->left; // 把要删除的节点（root）左子树放在cur的左孩子的位置
                TreeNode* tmp = root;   // 把root节点保存一下，下面来删除
                root = root->right;     // 返回旧root的右孩子作为新root
                delete tmp;             // 释放节点内存（这里不写也可以，但C++最好手动释放一下吧）
                return root;
            }
        }
        if (root->val > key) root->left = deleteNode(root->left, key);
        if (root->val < key) root->right = deleteNode(root->right, key);
        return root;
    }
};
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
48
49
50
51
52
53
54
// 根据递归返回值 确定节点的父子关系 (自己理解后重新写的)
class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        // 没有找到key
        if( ! root) return nullptr;
        // 找到了
        if(root->val == key){
            // 判断此时根节点左右孩子的状态
            // 只有右孩子
            if( ! root->left && root->right){
                return root->right;
            }
            // 只有左孩子
            if(root->left &&  ! root->right){
                return root->left;
            }
            // 叶子节点
            if( ! root->left && ! root->right){
                delete root;
                return nullptr;
            }
            // 左右孩子存在
            else{
                // 找到右孩子的最左节点, 将左孩子 放置在 该节点的左侧
                TreeNode *cur = root->right;
                while (cur->left != nullptr){
                    cur = cur->left;
                }
                cout<<cur->val;
                cur->left = root->left;
                
                // 删除根节点
                TreeNode *node = root;
                // 更新根节点
                root = root->right;
                delete node;
                return root;

            }
            
        }
        // 走右子树
        else if (root->val < key){
            root->right = deleteNode(root->right, key);
        }
        //走左子树
        else{
            root->left = deleteNode(root->left, key);
        }

        return root;
    }
};

669. 修剪二叉搜索树

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
//递归版
class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if (root == nullptr) return root;

        // 小于下限
        if(root->val < low){
            // 找到满足条件的右孩子
            TreeNode *cur =  trimBST(root->right, low, high);
            return cur;
        }

        // 大于上限
        else if(root->val > high ){
            // 找到满足条件的左孩子
            TreeNode *cur =  trimBST(root->left, low, high);
            return cur;
        }

        root->left  = trimBST(root->left, low, high);
        root->right = trimBST(root->right, low, high);
        return root;

    }
};
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
// 迭代版
class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if (root == nullptr) return root;

        // 根节点满足条件
        while(root->val < low || root->val > high){
            if(root->val < low)
                root = root->right;
            else
                root = root->left;
            // 发现整棵树都不满足条件
            if(!root) return nullptr;
        }

        
        TreeNode *cur = root;
        // 左孩子元素小于L的情况
        while(cur){
            // 若小于,则用 左孩子的右节点代替
            while(cur->left && cur->left->val < low){
                cur->left = cur->left->right;
            }
            cur = cur->left;
        }

        cur = root;
        // 右孩子元素大于H的情况
        while(cur){
            // 若小于,则用 左孩子的右节点代替
            while(cur->right && cur->right->val > high){
                cur->right = cur->right->left;
            }
            cur = cur->right;
        }

        return root;
    }
};

108. 将有序数组转换为二叉搜索树

538. 把二叉搜索树转换为累加树

二叉搜索树的修改与构造

算法思想

基础的算法： 枚举遍历，排序， 二分查找，递归，回溯

回溯

「因为回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案」，如果想让回溯法高效一些，可以加一些剪枝的操作，但也改不了回溯法就是穷举的本质。

适合: (性能分析)

子集问题：一个N个数的集合里有多少符合条件的子集

  • 时间复杂度：O(n * 2^n)，因为每一个元素的状态无外乎取与不取，所以时间复杂度为O(2^n)，构造每一组子集都需要填进数组，又有需要O(n)，最终时间复杂度：O(n * 2^n)
  • 空间复杂度：O(n)，递归深度为n，所以系统栈所用空间为O(n)，每一层递归所用的空间都是常数级别，注意代码里的result和path都是全局变量，就算是放在参数里，传的也是引用，并不会新申请内存空间，最终空间复杂度为O(n)

组合问题：N个数里面按一定规则找出k个数的集合

  • 时间复杂度：O(n * 2^n)，组合问题其实就是一种子集的问题，所以组合问题最坏的情况，也不会超过子集问题的时间复杂度。
  • 空间复杂度：O(n)，和子集问题同理。

排列问题：N个数按一定规则全排列，有几种排列方式

  • 时间复杂度：O(n!)，这个可以从排列的树形图中很明显发现，每一层节点为n，第二层每一个分支都延伸了n-1个分支，再往下又是n-2个分支，所以一直到叶子节点一共就是 n n-1 n-2 * ….. 1 = n!。
  • 空间复杂度：O(n)，和子集问题同理。

切割问题：一个字符串按一定规则有几种切割方式

  • 棋盘问题：N皇后，解数独等等

N皇后

  • 时间复杂度：O(n!) ，其实如果看树形图的话，直觉上是O(n^n)，但皇后之间不能见面所以在搜索的过程中是有剪枝的，最差也就是O（n!），n!表示n (n-1) …. * 1。
  • 空间复杂度：O(n)，和子集问题同理。

解数独

  • 时间复杂度：O(9^m) , m是’.’的数目。

  • 空间复杂度：O(n^2)，递归的深度是n^2

组合问题

组合问题、切割问题和子集问题都是类似的问题,可转换成组合问题

如果是一个集合来求组合的话，就需要startIndex，例如：回溯算法：求组合问题！，回溯算法：求组合总和！。

如果是多个集合取组合，各个集合之间相互不影响，那么就不用startIndex，例如：回溯算法：电话号码的字母组合

77. 组合

方法一:经典的回溯剪枝-满足题目要求的k个元素

官网方法二:简单来说就是一开始把所有的1放在尾部，比如00111这样，然后按顺序把1往前移动。如果所有的1都在最前头了，比如11100，就留一位1，其余的全部移到末尾，比如10011，然后再重复这个操作，直到所有的1都“被”留在了最前面，即11100，便完成了全部穷举。

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
// 二进制法
class Solution {
public:
    vector<int> temp;
    vector<vector<int>> ans;

    vector<vector<int>> combine(int n, int k) {
        // 初始化
        // 将 temp 中 [0, k - 1] 每个位置 i 设置为 i + 1，即 [0, k - 1] 存 [1, k]
        // 末尾加一位 n + 1 作为哨兵
        for (int i = 1; i <= k; ++i) {
            temp.push_back(i);
        }
        temp.push_back(n + 1);
        
        int j = 0;
        while (j < k) {
            ans.emplace_back(temp.begin(), temp.begin() + k);
            j = 0;
            // 寻找第一个 temp[j] + 1 != temp[j + 1] 的位置 t
            // 我们需要把 [0, t - 1] 区间内的每个位置重置成 [1, t]
            while (j < k && temp[j] + 1 == temp[j + 1]) {
                temp[j] = j + 1;
                ++j;
            }
            // j 是第一个 temp[j] + 1 != temp[j + 1] 的位置
            ++temp[j];
        }
        return ans;
    }
};

216. 组合总和 III

17. 电话号码的字母组合

回溯法有点像(递归有几种类型,循环是第i个类型有几种选择)

「for循环横向遍历，递归纵向遍历，回溯不断调整结果集」。

39. 组合总和

40. 组合总和 II

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
class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    
    void find(vector<int>& candidates, int target, int startI, vector<int>&use){
        if(target == 0){
            result.push_back(path);
            return;
        }
        if(target < 0){
            return;
        }

        for(int i = startI; i < candidates.size(); i++){
            // used[i - 1] == 1，说明同一树支candidates[i - 1]使用过
            // used[i - 1] == 0，说明同一树层candidates[i - 1]使用过
            // 要对同一树层使用过的元素进行跳过
            // 循环是第i个类型有几种选择,去掉与之前重复的选择,use[i-1]似乎不必要
            // if (i > 0 && candidates[i] == candidates[i - 1] && use[i - 1] == 0) {
            //     continue;
            // }
            if (i > startI && candidates[i] == candidates[i - 1] ) {
                continue;
            }

            use[i] = 1;
            target -= candidates[i];
            path.push_back(candidates[i]);
            
            find(candidates, target, i+1, use);
            
            target += candidates[i];
            path.pop_back();
            use[i] = 0;
        }
    }

    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<int> use(candidates.size(), 0);
        sort(candidates.begin(), candidates.end());
        find(candidates, target, 0, use);
        return result;
    }
};

131. 分割回文串

93. 复原 IP 地址

78. 子集

「在树形结构中子集问题是要收集所有节点的结果，而组合问题是收集叶子节点的结果」。

90. 子集 II

通过排序,比较相邻重复元素是否被访问,达到去重.

491. 递增子序列

(回溯套路小陷阱)

本层去重，是指同一个父节点下的本层，而不是整颗树的本层。

父节点的同一层公用一个visit[201]数组(哈希),完成访问登记,

排列问题

  • 每层都是从0开始搜索而不是startIndex
  • 需要used数组记录path里都放了哪些元素了

“树层去重”和“树枝去重”的重要性, 明显看出“树层去重”效率更高(「可以看出在candidates[i] == candidates[i - 1]相同的情况下：」)

树层上去重(used[i - 1] == false)，的树形结构如下：

图片

树枝上去重（used[i - 1] == true）的树型结构如下：

图片

46. 全排列

47. 全排列 II

—-未做—-

332. 重新安排行程

图论扩展

51. N 皇后

棋盘的宽度就是for循环的长度，递归的深度就是棋盘的高度，这样就可以套进回溯法的模板里

37. 解数独

「二维递归」

贪心

「贪心的本质是选择每一阶段的局部最优，从而达到全局最优」

贪心算法一般分为如下四步：

  • 将问题分解为若干个子问题
  • 找出适合的贪心策略
  • 求解每一个子问题的最优解
  • 将局部最优解堆叠成全局最优解

题:

455. 分发饼干

376. 摆动序列

让序列有尽可能多的局部峰值。

局部最优：删除单调坡度上的节点（不包括单调坡度两端的节点），那么这个坡度就可以有两个局部峰值。

整体最优：整个序列有最多的局部峰值，从而达到最长摆动序列。

53. 最大子序和

贪心：「不能让“连续和”为负数的时候加上下一个元素，而不是 不让“连续和”加上一个负数」

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int maxsumofSubarray(vector<int>& arr) {
       // write code here
       int sum = INT_MIN;
       int count = 0;
       
       for(int i = 0; i < arr.size(); i++){
           count += arr[i];
           // 负数就没必要在往下加了
           if(count < 0){
               count = 0;
           }
           sum = sum > count? sum : count;
       }
       
       return sum;
       
   }

动态规划：arr[i]代表i的累加和，便记录其累加和最大值

动态转移方程：arr[i] = max(arr[i-1]+arr[i] ,arr[i])

1
2
3
4
5
6
7
8
9
10
11
12
int maxsumofSubarray(vector<int>& arr) {
       // write code here
       int sum = arr[0];
 
       for(int i = 1; i < arr.size(); i++){
           arr[i] = max(arr[i-1]+arr[i], arr[i]);
           sum = max(sum, arr[i]);
       }
       
       return sum;
       
   }

122. 买卖股票的最佳时机 II

「局部最优：收集每天的正利润，全局最优：求得最大利润」

55. 跳跃游戏

45. 跳跃游戏 II

1005. K 次取反后最大化的数组和

134. 加油站

135. 分发糖果

需要考虑两个维度(先考虑其中一个维度，再考虑其他的)

860. 柠檬水找零

406.根据身高重建队列

注意 数据结构的区别，vector的底层实现也是普通数组（使用vector来做insert的操作，此时「虽然表面上复杂度是O(n^2)，但是其底层都不知道额外做了多少次全量拷贝了，所以算上vector的底层拷贝，整体时间复杂度可以认为是O(n^2 + t * n)级别的，t是底层拷贝的次数」）

动态规划

动态规划，英文：Dynamic Programming，简称DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的。

动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的.

核心: 状态转移公式（递推公式）

对于动态规划问题，如下五步曲

  • 确定dp数组（dp table）以及下标的含义
  • 确定递推公式
  • dp数组如何初始化
  • 确定遍历顺序
  • 举例推导dp数组

题:

509. 斐波那契数

70. 爬楼梯

746. 使用最小花费爬楼梯

62. 不同路径

343. 整数拆分

96. 不同的二叉搜索树

——子序列系列——-

674. 最长连续递增序列

300. 最长递增子序列

该题与674的区别在于子序列的元素可以在位置上不连续。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int lengthOfLIS(vector<int>& nums) {
       if (nums.size() == 1) return 1;
       //dp[i] i之前包括i的最长上升子序列数
       vector<int> dp(nums.size(), 1);
       //记录最长上升子序列数
    	int maxNum = 0;
       for(int i = 0; i < nums.size(); i++){
           for(int j = 0; j < i; j++){
               if(nums[i] > nums[j]) 
                   dp[i] = max(dp[i], dp[j]+1);
               maxNum = max(dp[i], maxNum);
           }
       }
       return maxNum;
   }

优化版

二分区间的选择（来源）：

  • while (left < right) 退出循环的时候有 left == right 成立，因此无需考虑返回 left 还是 right

  • 每一轮区间被划分成 2 部分，理解 区间划分 决定中间数取法（ 无需记忆，需要练习 + 理解 ），在调试的过程中理解 区间和中间数划分的配对关系：
    划分 [left, mid] 与 [mid + 1, right] ，mid 被分到左边，对应 int mid = left + (right - left) / 2;；
    划分 [left, mid - 1] 与 [mid, right] ，mid 被分到右边，对应 int mid = left + (right - left + 1) / 2;。

  • 至于为什么划分是这种对应关系，原因在于区间只有 2 个数的时候，如果中间数的取法不对，一旦进入的分支不能使得区间缩小，会出现 死循环。

  • 退出循环的时候有 left == right 成立，此时如果能确定问题一定有解，返回 left 即可，如果不能确定，需要单独判断一次。

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
//二分+动态规划
   int lengthOfLIS(vector<int>& nums) {
       int len = nums.size();
       if (len == 1) return 1;
       //dp[i]  长度为 i + 1 的 所有 上升子序列的结尾的最小值,运用了贪心的思想
       vector<int> dp(len, 0);
       //记录长度
       int maxNum = 0;
       dp[0] = nums[0];
       for(int i = 1; i < nums.size(); i++){
           if(nums[i] > dp[maxNum]){
               dp[++maxNum] = nums[i];
           }
           else if(nums[i] < dp[maxNum]){
               // //二分，找到合适插入的位置
               int l = 0, r = maxNum;
              
               while(l < r){
                   int mid = l + ((r - l) >> 1);
                   if(dp[mid] < nums[i]){
                       l = mid+1;
                   }
                   else{
                       r = mid;
                   } 
               }
               dp[l] = nums[i];
           }
           else 
               continue;

       }
       return maxNum+1;
   }

718. 最长重复子数组

1143. 最长公共子序列

与上一题相比，子序列（原字符串元素相对顺序不变，删除某些字符（也可以不删除任何字符）后组成的新字符串），难度加大.还是要理清dp[i][j]所代表的含义以及对应的递推公式、初始值.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//优化版，只保留相邻两行的状态，空间复杂度降低为O（min(m,n)）
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        if (text1.size() < text2.size()) {
            swap(text1, text2);
        }
        vector<vector<int>> m (2, vector<int>(text2.size(), 0));
        int ans = 0;
        for (int i = 0; i < text1.size(); ++i) {
            for (int j = 0; j < text2.size(); ++j) {
                if (text1[i] == text2[j]) {
                    m[1][j] = j?m[0][j-1]+1:1;
                } else {
                    m[1][j] = max(m[0][j], j?m[1][j-1]:0);
                }
            }
            swap(m[0], m[1]);
        }
        return m[0][text2.size() - 1];
    }
};

——01背包——-

416. 分割等和子集

其他

42. 接雨水

来源：https://leetcode-cn.com/problems/trapping-rain-water/solution/jie-yu-shui-by-leetcode/精选评论第一条

先明确几个变量的意思：

1
2
3
4
left_max：左边的最大值，它是从左往右遍历找到的
right_max：右边的最大值，它是从右往左遍历找到的
left：从左往右处理的当前下标
right：从右往左处理的当前下标

定理一：在某个位置i处，它能存的水，取决于它左右两边的最大值中较小的一个。

定理二：当我们从左往右处理到left下标时，左边的最大值left_max对它而言是可信的，但right_max对它而言是不可信的。（见下图，由于中间状况未知，对于left下标而言，right_max未必就是它右边最大的值）

定理三：当我们从右往左处理到right下标时，右边的最大值right_max对它而言是可信的，但left_max对它而言是不可信的。

1
2
3
4
5
6
                                   right_max
 left_max                             __
   __                                |  |
  |  |__   __??????????????????????  |  |
__|     |__|                       __|  |__
        left                      right

对于位置left而言，它左边最大值一定是left_max，右边最大值“大于等于”right_max，这时候，如果left_max<right_max成立，那么它就知道自己能存多少水了。无论右边将来会不会出现更大的right_max，都不影响这个结果。 所以当left_max<right_max时，我们就希望去处理left下标，反之，我们希望去处理right下标。

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
int trap(vector<int>& height) {

        int sum = 0;
        int len = height.size();
        //双指针
    	//从左往右处理的当前下标
        int left = 0;
    	//从右往左处理的当前下标
        int right = len - 1;
        //左边最高墙
        int left_max = 0;
        //右边最高墙
        int right_max = 0;

        while(left <= right){
            if(left_max < right_max){
                sum += max(0, left_max-height[left]);
                //更新左边最高墙
                left_max = max(left_max, height[left]);
                left++;
            }
            else{
                sum += max(0, right_max-height[right]);
                //更新右边最高墙
                right_max = max(right_max, height[right]);
                right--;
            }
        }

        return sum;
    }

排序

来源：https://blog.csdn.net/yushiyi6453/article/details/76407640 （讲的比较好，而且还有动图显示）

image-20210423144319654

注：
1 归并排序可以通过手摇算法将空间复杂度降到O（1），但是时间复杂度会提高。
2 基数排序时间复杂度为O（N*M），其中N为数据个数，M为数据位数。
辅助记忆

  • 时间复杂度记忆

    冒泡、选择、直接 排序需要两个for循环，每次只关注一个元素，平均时间复杂度为O（n2）（一遍找元素O(n)，一遍找位置O(n)）

    快速、归并、希尔、堆基于二分思想，log以2为底，平均时间复杂度为O(nlogn)（一遍找元素O(n)，一遍找位置O(logn)）

  • 稳定性记忆-“快希选堆”（快牺牲稳定性）

    排序算法的稳定性：排序前后相同元素的相对位置不变，则称排序算法是稳定的；否则排序算法是不稳定的。

交换类排序

冒泡排序

每一次把最大的放到后面【确定最大值，放入合适的位置。直至整个数据位置确定完】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//冒泡
    void maopaoSort(vector<int>& a){
        //排序位
        for(int i = a.size()-1; i > -1; i--){
            //待排序区
            for(int j = 0; j < i; j++){
                if(a[j+1] < a[j]){
                    // a ^ a = 0 ; a ^ 0 = a           
                    a[j+1] ^= a[j];
                    a[j] ^= a[j+1];
                    a[j+1] ^= a[j];
                }
            }
        }
    }

快速排序

  • 挖坑填数:

    • 1．i =L; j = R; 将基准数挖出形成第一个坑a[i]。

    • 2．j–由后向前找比它小的数，找到后挖出此数填前一个坑a[i]中。

    • 3．i++由前向后找比它大的数，找到后也挖出此数填到前一个坑a[j]中。

    • 4．再重复执行2，3二步，直到i==j，将基准数填入a[i]中。

此时，a[i]左边的值 <a[i]右边的值。再排序左区间与右区间，直至左右区间无值。

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
//     左闭右闭
    void quickSort(vector<int>& arr, int l, int r){
        
        int key = arr[l];
        int i = l, j = r;
        
        while(i < j){
            //后往前找到第一个小于key的值
            while(j > i && arr[j] >= key)
                j--;
            if(j > i){
                arr[i] = arr[j];
            }
            //前往后找到第一个大于key的值
            while(j > i && arr[i] <= key)
                i++;
            if(j > i){
                 arr[j] = arr[i];
            }
            
        }
        arr[i] = key;
        if(i > l) quickSort(arr, l, i-1);
        if(r > i) quickSort(arr, i+1, r);
        
    }

插入类排序

直接插入排序

分为排序区和未排序区，每次未排序区依次选择一个数，与排序区比较，若排序区的元素比该数大，就插入（元素后移一位，该数放置其前）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//选择排序
   void selectInsertSort(vector<int>& a){
     
       for(int i = 1; i < a.size(); i++){
           int temp = a[i];
           //排序区
           for(int j = i-1; j > -1; j--){
               //往后移                 
               if(a[j] > temp ){                  
                   a[j+1] = a[j];
                   a[j] = temp;
                  
               }else{
                   break;
               }
           }
       }
   }

希尔排序

将数组分组，在各组中进行直接插入排序。逐渐缩小分组间隙，直至整个数组恰被分成一组.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void shellSort(vector<int> &a){
      int interval = a.size();
      for(; interval > 0; interval /= 2){
          //每组间隔interval的元素进行选择插入排序
          for(int i = interval; i < a.size(); i++){
             int temp = a[i];
              for(int j = i-interval; j > -1 ;j -= interval)
              if(temp < a[j]){
                  a[j+interval] = a[j];
                  a[j] = temp;
              }
          }
      }
  }

选择类排序

简单选择排序

分为排序区和未排序区，每次在未排序区找到最小值，放入排序区的后面。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//     选择排序
    void selectSort(vector<int> &a){
//         i排序区
        for(int i = 0; i < a.size(); i++){
            int minIndex = i;
//             找到未排序区的最小值
            for(int j = i+1; j < a.size(); j++){
                if(a[j] < a[minIndex]){
                    minIndex = j;
                }
             }
             if(i != minIndex){
                 a[i] ^= a[minIndex];
                 a[minIndex] ^= a[i];
                 a[i] ^= a[minIndex];
             }    
        }
    }

堆排序

这位大佬图解很清晰，思路：

a.将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;

b.将堆顶元素与末尾元素交换，将最大元素”沉”到数组末端;

c.重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

用数组表示

大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]

小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2] 

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
//     堆排序
    void swap(vector<int> &a, int i, int j){
        a[i] ^= a[j];
        a[j] ^= a[i];
        a[i] ^= a[j];
    }
    
    void heap(vector<int>& a, int i, int length){
        int curVal = a[i];
        
        for(int k = 2*i+1; k < length; k = k*2+1){
            //左右节点是否大于父节点
            //先找到左右节点的较大值，与父节点比较。
            if( k+1<length && a[k] < a[k+1])
                k++;
            if(a[k] > curVal){
                a[i] = a[k]; 
                //记录替换后的位置
                i = k;
            }
            //均不大于，满足条件，则返回
            else{
                break;    
            }
            
        }
        a[i] = curVal;
    }
    
    void heapSort(vector<int>& a){
//         创建大顶堆: 从第一个非叶子节点 从下至上，右至左
        int length = a.size();
        for(int i = length/2-1; i > -1; i--){
            heap(a, i, length);
        }
        
//         交换堆顶与末尾元素，调整堆,逐渐将最大值沉到最后
        for(int j = length - 1; j > 0; j--){
            swap(a, 0, j);
            heap(a, 0, j);
        }
        
    }

归并类排序

归并排序

采用分治策略（将问题分成一些小的问题，然后递归求解；再将每个阶段的结果合并）

“治”采用双指针的方式合并。

img

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
48
49
50
51
52
53
54
55
56
////在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
void merge(vector<int> &a, int l, int mid, int r, int *temp) {
	// 双指针
	int i = l, j = mid + 1;
	//         临时数组的索引
	int t = 0;
	//         合并
	while (i < mid + 1 && j < r + 1) {
		if (a[i] <= a[j]) {
			temp[t++] = a[i++];
		}
		else {
			temp[t++] = a[j++];
		}

	}

	while (i < mid + 1) {
		temp[t++] = a[i++];
	}
	while (j < r + 1) {
		temp[t++] = a[j++];
	}
	t = 0;
	//         拷贝到a
	for (int k = l; k < r + 1; k++) {
		a[k] = temp[t++];
	}
}

//归并排序
void mergeSort(vector<int> & a, int l, int r, int *temp) {
	//越界
	if (l >= r) return;
    
	int mid = (l + r) / 2;
	//归并左区间
	mergeSort(a, l, mid, temp);
	//归并右区间
	mergeSort(a, mid + 1, r, temp);
	merge(a, l, mid, r, temp);

}

int main() {
	
	vector<int> arr = { 5, 1, 6, 2, 5, 5, 2, 3, 1, 4 };
	int *temp = new int[arr.size()];
	mergeSort(arr, 0, arr.size() - 1, temp);
	for (int i = 0; i < arr.size(); i++) {
		cout<< arr[i] << " ";
	}
	delete[]temp;
	
	return 0;
}

桶排

桶排序

划分多个范围相同的区间，每个自区间自排序，最后合并。

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
48
49
50
51
52
53
54
55
56
57
#include <iostream>
#include <vector>
#include <list>
using namespace std;
void insert(list<int>& bucket,int val)
{
    auto iter = bucket.begin();
    while(iter != bucket.end() && val >= *iter) ++iter;
    //insert会在iter之前插入数据，这样可以稳定排序
    bucket.insert(iter,val);
}

void BucketSort_1(vector<int>& arr)
{
    int len = arr.size();
    if(len <= 1)
        return;
    int min = arr[0],max = min;
    for(int i=1;i<len;++i)
    {
        if(min>arr[i]) min = arr[i];
        if(max<arr[i]) max = arr[i];
    }
    int k = 10;//k为数字之间的间隔
    //向上取整，例如[0,9]有10个数，(9 - 0)/k + 1 = 1;
    int bucketsNum = (max - min)/k + 1;
    vector<list<int>> buckets(bucketsNum);
    for(int i=0;i<len;++i)
    {
        int value = arr[i];
        //(value-min)/k就是在哪个桶里面
        insert(buckets[(value-min)/k],value);
    }
    int index = 0;
    for(int i=0;i<bucketsNum;++i)
    {
        if(buckets[i].size())
        {
            for(auto& value:buckets[i])
                arr[index++] = value;
        }
    }
}
int main()
{
    vector<int> A={-100,13,14,94,33,82,25,59,94,65,23,45,27,43,25,39,10,35,54,90,-200,58};
    for(auto value:A)
        cout<<value<<" ";
    cout<<endl;
    BucketSort_1(A);

    for(auto value:A)
        cout<<value<<" ";
    cout<<endl;

    return 0;
}

计数排序

基数排序

常考题

参考文章

「图文总结」程序员必知必会的十大排序算法

---------------- 本文结束 ----------------

本文标题:打怪之旅-数据结构与算法

文章作者:Pabebe

发布时间:2021年01月24日 - 17:53:37

最后更新:2021年09月10日 - 10:03:46

原始链接:https://pabebezz.github.io/article/737c8fe7/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

0%