fly刷题笔记

---

回溯

https://leetcode-cn.com/problems/subsets/solution/c-zong-jie-liao-hui-su-wen-ti-lei-xing-dai-ni-gao-/
按照这个思路来看就好

个人理解：全部的组合情况，全部的排列情况，全部的子集情况等，遇到这类题想到回溯，其实回溯是dfs的一种，需要在dfs子层后复原状态。
ps：像后面的dfs模版中，若visit数组是全局变量/传引用的话，也需要这样进行回溯，不过会很麻烦，所以就直接传值，避免去考虑这个事情。

classic: leetcode 17

随机

//全部随机
vector<int> vec(n);
iota(vec.begin(), vec.end(), 0); //从0开始递增1
random_suffle(vec.begin(),vec.begin());

//单个值
rand()
1
2
3
4
5
6
7

二分

必看：自己对于两种模版的整理+总结，。 链接

以下为选看：
关于如何确定l<r 以及+1 -1 链接
关于为什么要用下面这两个模版 以及最终ans的值的选择 链接

模版1

int n = nums.size();
int l = 0, r = n - 1, mid = 0;

while(l < r){
	mid = l + (r-l)/2;
    if(check){
        l = mid + 1;
    }else{
        r = mid;
    }
}
1
2
3
4
5
6
7
8
9
10
11

模版2 better

while(l <= r){
	mid = l + (r-l)/2;
	if(正确情况) return mid;（大概率使用）
    if(check){
        l = mid + 1;
    }else{
        r = mid - 1;
    }
}
//有时候需要判断return的l/r谁满足条件 
if(xxx) return l;
else return r;
1
2
3
4
5
6
7
8
9
10
11
12

upper_bound & lower_bound & equal_range可

vector和list 可以用 STL的upper_bound

static bool cmp(const T & t1, const T & t2){
	return t1.a < t2.a;
}
upper_bound(vec.begin(),vec.end(),target, (cmp));
upper_bound(l.begin(),l.end(),target, (cmp));
1
2
3
4
5

map和set 可以用 容器自带的upper_bound

map<int,int> mp;
set<int> st;
mp.upper_bound(target);
st.upper_bound(target);
暂时不确定cmp怎么写，应该就是set/map cmp自定义的方法
1
2
3
4
5

lower_bound:返回第一个>=p的role的下标
upper_bound:返回第一个>p的role的下标
使用时一般减去begin()
lower_bound(role.begin(),role.end(),p)-role.begin();
若结果为role.end(),即不存在这样的下标。

equal_range相当于lower和upper的集合体
.first返回lower_bound
.second返回upper_bound
1
2
3
4
5
6
7
8
9

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int n,m;
        cin>>n>>m;
        vector<int> peo(n);
        vector<int> role(m);
        for(int i=0;i<n;i++) cin>>peo[i];
        for(int i=0;i<m;i++) cin>>role[i];
        sort(role.begin(),role.end());

        for(auto p:peo)
        {
            int res=0;
            //自带二分
            // lower_bound:返回第一个>=p的role的下标
            // upper_bound:返回第一个>p的role的下标
            //要减去role.begin()才返回下标
            res =m - (lower_bound(role.begin(),role.end(),p)-role.begin());
//            for(int j=m-1;j>=0;j--)
//            {
//                if(role[j]>=p) res++;
//                else break;
//            }
            cout<<res<<" ";
        }
        cout<<endl;
    }
    return 0;
}
-------------
//手写
#include <bits/stdc++.h>
//先排序
using namespace std;
// [l,r)

int bs(int a[], int n, int x) { //lower 返回第一个>=x的下标
    int l = 0, r = n, mid;
    while (l < r) {
        mid = (l + r) / 2;
        if (a[mid] < x) {
            l = mid + 1;
        } else {
            r = mid;
        }
    }
    return l;
}

int us(int a[], int n, int x) { //upper 返回第一个>x的下标
    int l = 0, r = n;
    while (l < r) {
        int mid = l + r / 2;
        if (a[mid] <= x) {
            l = mid + 1;
        } else {
            r = mid;
        }
    }
    return l;
}

int b[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};

int main() {
    cout << bs(b, 9, 5) << endl;
    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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

有变化的二分题

单调栈

模版

stack<int> st;
for(int i = 0; i < nums.size(); i++)
{
	while(!st.empty() && st.top() > nums[i])
	{
		st.pop();
	}
	st.push(nums[i]);
}

1
2
3
4
5
6
7
8
9
10

关于单调栈的使用情况

每个元素找到它右边第一个比它大的元素的位置，求它们的距离
从左到右遍历，维护一个从栈底到栈顶递减的栈，因为遇到新元素大于栈顶元素时，栈顶元素就遇到了对应的比它大的最近元素，要弹栈。这也是栈从底到顶单调递减的原因

每个元素找到它右边第一个比它小的元素的位置，求它们的距离
从左到右，维护栈底到栈顶递增的栈，遇到递减元素，弹栈

每个元素找到它左边第一个比它大的元素的位置，求它们的距离
相当于把1的数组头尾调过来，只需要从右向左遍历维护栈底到栈顶递减栈即可

每个元素找到它左边第一个比它小的元素的位置，求它们的距离
相当于把2的数组头尾调过来，只需要从右向左遍历维护栈底到栈顶递增栈即可

question:
经典739
稍复杂（base left right 计算面积的） 42接雨水（凹进去的 递减栈）84（突出来的递增栈）

自动机

https://leetcode-cn.com/problems/string-to-integer-atoi/solution/zi-fu-chuan-zhuan-huan-zheng-shu-atoi-by-leetcode-/

设计类题目

设计类题目一般指通过自己选取合适的数据结构，去实现题目规定的操作。
一般需要设计出索引结构（index table）以及数据库结构（database）。
大致可以分为两类题目。

1. 哈希 配合 链表（双向）
   经典题：LRU - 剔除最近没有被访问过的节点
   大致思路：
   使用哈系实现索引，索引的key为题干中要去改变/访问的key，value为链表的迭代器，用这样的方式最快速找到元素在链表中的位置。使用链表作为数据库，链表的node可以存储某个结构/pair/tuple。
   使用原因：
   因为链表没有排序能力，所以这种题适合不需要排序的情况，例如LRU只需要移除某个节点+插入/去除首尾。

2. 哈希 配合 set
   经典题：LFU - 剔除被访问频率最低的节点
   大致思路：
   使用hash实现索引，索引的key为题干中要去改变/访问的key，value为一个结构A（可以是pair/tuple或者struct）。使用set< A >作为数据库，根据题意重载<，实现set中的排序。
   使用原因：
   这类题在数据库具备自定义排序能力，所以采用set。先用hash索引到对应结构A，再通过se去erase和emplace。

   上述这种思路是logn的思路，还有一种O(1)的思路，面试有考到过。
   这里用到了一个性质，list的iterator可以当作地址，找到不同的链表的某一位（即，不拘泥于同一个链表）
   使用两个hash
   hash1：key为freq，value是一个list< Node（key,value,freq）>, 这个list中放所有freq为这个freq的Node，同时每次都是从前面插入，后面pop，所以越靠后的时间越久。
   hash2: key为key， value为list< Node >::iterator， 即这个key对应的Node的迭代器，可以直接找到hash1的对应的list中对应的那个位置（很强）
   有了这两个结构，get可以直接找到位置，并把freq+1，去掉原先的Node，加到freq+1的list中，并更新hash2
   set如果满了的话直接去掉hash1中的minFreq的第一个Node，同时过程中维护一个minFreq, 每次erase freq的node时候判断下，若当前freq没了需要erase掉整个freq且这个freq就是minFreq，将minFreq+1.

3. 其他演变的类型
   在LRU基础上，演变出了432这种，可以通过list进行排序，不过这种排序要求每次变化可以通过前后模拟得到，较为特殊。
   在LFU的基础上，演变出了6126这种题，本质上是通过set来做数据库，但由于题目要求的获取情况要分类，所以将数据库set改为unordered<分类指标，set< A >>，实现功能。

一道涵盖颇多技巧的题 432

### 解题思路


### 代码

```cpp
/*
精髓：
怎么解决排序问题？使链表的node结构 表示某个数量及这个数量的所有key(用一个set存)；而不是只想着一个key的事儿 

https://leetcode-cn.com/problems/all-oone-data-structure/solution/quan-o1-de-shu-ju-jie-gou-by-leetcode-so-7gdv/ 官方题解 使用stl

理解上：看宫水三叶的题解

//emplace的好处：1 少了一个构造函数 2 参数列表语法糖 详见
https://www.jianshu.com/p/3906f24d2697

//list stl 
//emplace的返回值是新增node的迭代器
//prev() next()用法
//http://c.biancheng.net/view/7384.html

//struct构造函数
//https://www.cnblogs.com/wlw-x/p/11566191.html
*/
class AllOne {
public:
    struct Node
    {
        set<string> st;
        int nums = 0; //node对应的数
        //构造函数:方便下文使用
        Node(set<string> a, int b):st(a),nums(b){}
        //https://www.cnblogs.com/wlw-x/p/11566191.html
    };
    unordered_map<string,list<Node>::iterator> hash;
    list<Node> delist;
    AllOne() {
    }
    
    void inc(string key) {
        //find
        if(!hash.count(key))//not exist
        {
            if(delist.size()==0||delist.front().nums>1)//直接放在首位
            {
                set<string> st({key});
                delist.emplace_front(st,1);
            }
            else //跟首位合并 set加上该key
            {
                //.front()是返回一个copy,不影响该node本身，
                //.begin()是返回对应的迭代器，可以直接对该node进行操作
                delist.begin()->st.emplace(key);
            }
            hash[key] = delist.begin();
        }
        else //exist
        {
            auto cur = hash[key];
            auto nxt = next(cur);

            if(nxt == delist.end() || nxt->nums > cur->nums +1 ) //需要新增node的情况
            {
                set<string> st({key}); 
                hash[key] = delist.emplace(nxt,st,cur->nums+1); //语法糖 也可以像下面这样
                //hash[key] = delist.emplace(nxt,Node(st,cur->nums+1));
                //插入后返回值为插入node对应的迭代器
            }
            else
            {
                nxt->st.emplace(key);
                hash[key] = nxt;
            }

            //对当前cur减去该key 并判断是否需要erase掉node 
            //最后再erase,先erase会造成cur迭代器失效，无法进行其他操作
            cur->st.erase(key);
            if(cur->st.empty())
            {
                delist.erase(cur);
            }
        }
    }
    
    void dec(string key) {
        auto cur = hash[key];
        auto pre = prev(cur);

        if(cur->nums==1)//key不存在的情况 
        {
            hash.erase(key);
        }
        else //key还存在的情况
        {
            if(cur==delist.begin()||pre->nums < cur->nums-1)//需要新增node的情况
            {
                set<string> st({key});
                hash[key] = delist.emplace(cur,st,cur->nums-1);
                //插入后返回值为插入node对应的迭代器
            }
            else
            {
                pre->st.emplace(key);
                hash[key]=pre;
            }
        }

        cur->st.erase(key);
        if(cur->st.empty())
        {
            delist.erase(cur);
        }
    }
    
    string getMaxKey() {
        return (delist.empty())?"":*(delist.back().st.begin());
    }
    
    string getMinKey() {
        return (delist.empty())?"":*(delist.front().st.begin());
    }
};

/**
 * Your AllOne object will be instantiated and called as such:
 * AllOne* obj = new AllOne();
 * obj->inc(key);
 * obj->dec(key);
 * string param_3 = obj->getMaxKey();
 * string param_4 = obj->getMinKey();
 */
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

经典LRU 146

### 解题思路
1 思路：LRU，所以要维护一个链表/队列，去排任务的顺序，又因为要求get和put的复杂度为O(1)，因此可以构造(key,list::interator)的hash，最快速度索引到链表的位置。
2 pair的原因是：get的时候要得到value
3 emplace进pair时可以省略掉make_pair
4 更新的过程中要考虑hash是否更新
5 list.back()是新建的一个值，不影响远list
### 代码

```cpp
class LRUCache {
public:
    unordered_map<int,list<pair<int,int>>::iterator> hash;
    list<pair<int,int>> list;
    int capacity = 0;
    LRUCache(int capacity) {
        this -> capacity = capacity; 
    }
    
    int get(int key) {
        if(!hash.count(key)) return -1;
        auto e = hash[key];
        int val = e->second;
        list.erase(e);
        list.emplace_front(key,val);
        hash[key] = list.begin();
        return val;
    }
    
    void put(int key, int value) {
        int val = 0;
        if(hash.count(key)){
            auto e = hash[key];
             list.erase(e);
             list.emplace_front(key,value);
             hash[key] = list.begin();
        }else{
            list.emplace_front(key,value);
            hash[key] = list.begin();
        }
        if(list.size()>capacity){
            hash.erase(list.back().first);
            list.pop_back();
        }
        return ;
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */
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

460 LFU
同样涵盖技巧+细节

/*
看官方题解：https://leetcode-cn.com/problems/lfu-cache/solution/lfuhuan-cun-by-leetcode-solution/
两种方法这里用第一种实现
1 利用set的自带排序 olgn

2 一个hash<int,list<Node>::iterator> 一个hash<int,list<Node>> o1
第一个hash中的value可以是任意一条list（第二个hash的value）的某一个地址


//Node类的比较函数 定义在结构体中 
//https://zhuanlan.zhihu.com/p/368510835

//结构体注意事项
//https://www.jianshu.com/p/18307f614c5b

*/

class LFUCache {
public:
    struct Node{
        int key;
        int value;
        int freq;
        int time;

        //注意：如果写了带参数的构造函数，一定要把不带参数的也写上，因为重写后，默认构造函数会失效。
        Node():key(),value(),freq(),time(){}
        Node(int a,int b,int c,int d):key(a),value(b),freq(c),time(d){}
        
        //Node类的比较函数 定义在结构体中 
        //这两处一定要写const 不然编译不过
        bool operator < (const Node &a) const{  
            return freq == a.freq ? time < a.time : freq < a.freq;
        }  
    };
    int capacity;
    unordered_map<int,Node> hash;
    set<Node> st;
    int time = 0;

    LFUCache(int capacity) {
        this->capacity = capacity;
    }
    
    int get(int key) {
        if(capacity==0) {
            return -1;
        }
        if(!hash.count(key)) {
            return -1;
        }
        time++;
        Node node = hash[key];
        st.erase(node);
        node.freq++;
        node.time = time;
        st.emplace(node);
        hash[key] = node;
        return node.value;
    }
    
    void put(int key, int value) {
        if(capacity==0) {
            return;
        }
        time++;
        if(!hash.count(key)) {
            if(st.size()==capacity) {
                hash.erase(st.begin()->key);
                st.erase(*st.begin());
            }
            st.emplace(key,value,1,time);
            hash[key] = Node(key,value,1,time);
        }else{
            Node node = hash[key];
            st.erase(node);
            node.freq++;
            node.time = time;
            node.value = value;
            st.emplace(node);
            hash[key]=node;
        }

        return;
    }
};
/**
 * Your LFUCache object will be instantiated and called as such:
 * LFUCache* obj = new LFUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

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

6126
链接

/*
类似 LFU 
这种类型 无法像LRU那样通过链表来存储，因为需要存储结构带有排序，因此用set来存
需要注意的是：在重载<时，set和bq是相反的
*/
class FoodRatings {
public:
    struct Food{
        string food;
        string cuisine;
        int rating;
        Food():food(),cuisine(),rating(){}
        Food(string food, string cuisine, int rating):food(food),cuisine(cuisine),rating(rating){}
        bool operator<(const Food &t)const {
            if(rating != t.rating){
                return rating > t.rating;
            }else{
               return food < t.food;
            }
        }
    };
    //index table
    //food's name - Food
    unordered_map<string,Food> hash;
    //database table
    //cuisines - Foods(rating & name & with sort): so use set
    unordered_map<string, set<Food>> db;

    FoodRatings(vector<string>& foods, vector<string>& cuisines, vector<int>& ratings) {
        int n = foods.size();
        for(int i = 0; i < n; i++){
            Food f = Food(foods[i],cuisines[i],ratings[i]);
            hash[foods[i]] = f;
            db[cuisines[i]].emplace(f);
        }
    }
    
    void changeRating(string food, int newRating) {
        auto f = hash[food];
        auto newf = Food(f.food,f.cuisine,newRating);
        //auto st = db[f.cuisine];
        db[f.cuisine].erase(f);
        db[f.cuisine].emplace(newf);
        hash[food].rating = newRating;
    }
    
    string highestRated(string cuisine) {
        return db[cuisine].begin()->food;
    }
};




/**
 * Your FoodRatings object will be instantiated and called as such:
 * FoodRatings* obj = new FoodRatings(foods, cuisines, ratings);
 * obj->changeRating(food,newRating);
 * string param_2 = obj->highestRated(cuisine);
 */
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

355 设计推特
最优做法应该是合并k个有序链表
个人做法

背包汇总

三叶nice汇总

dp[i][j]
i:考虑前i个物品
j:背包体积
值：价值
1
2
3
4

外层循环：考虑前i个物品
内层循环：遍历背包容量（压缩成一维后：01->从右往左；完全->从左到右）

01与完全的区别

01背包：该格子的点的  上面格子 和 左上格子；
dp[i][j] = max (dp[i-1][j],dp[i-1][j-weight[i]]+val[i]);
压缩成一维后，为了左上格子的变化不影响该点，从右往左遍历背包容量（内层循环从右往左）


完全背包： 该格子点的  上面格子 和 左边格子；
dp[i][j] = max (dp[i-1][j],dp[i][j-weight[i]]+val[i]);
可以这么理解，即使到外层遍历考虑前i个物品的这一层了，这一层依然可以选若干回，所以是同层的左边
压缩成一维后，为了左边格子先更新（内层循环从左往右）


状态转移的定义除了max/min，还可以“或”（针对不同题目）
1
2
3
4
5
6
7
8
9
10
11
12

01背包

每个物品只能一次

vector<int> weight(n); //物品质量；n为物品数量
vector<int> val(n); //物品价值
vector<int> dp(m+1); //m为背包称重上限
/*
  1 这里m+1是增加一个为0的哨兵排，使得初始化更方便
  2 很多情况val就是weight，或者val恒为1
  3 初始化dp的时候
    一般 转移方程为max-> 初始化为0
    转移方程为min-> 初始化为INT_MAX，并将dp[0]=0
    状态定义除了max（），还可以或（针对不同题目）
*/
for(int i=0;i<n;i++){ //考虑前i个物品
   for(int j=m; j>=weight[i]; j--){ //为了能装进去 遍历到weight[i]
  	dp[j]=max(dp[j],dp[j-weight[i]]+val[i]);
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

例子

完全背包

每个物品若干次

vector<int> weight(n); //物品质量；n为物品数量
vector<int> val(n); //物品价值
vector<int> dp(m+1); //m为背包称重上限
/*
  1 这里m+1是增加一个为0的哨兵排，使得初始化更方便
  2 很多情况val就是weight，或者val恒为1
  3 初始化dp的时候
    一般 转移方程为max-> 初始化为0
    转移方程为min-> 初始化为INT_MAX，并将dp[0]=0
*/
for(int i=0;i<n;i++){ //考虑前i个物品
   for(int j=weight[i]; j<=m; j++){ //为了能装进去 从weight[i]开始
  	dp[j]=max(dp[j],dp[j-weight[i]]+val[i]);
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

例子
322 硬币兑换

分组背包

每组物品中只能抽一个（一次）
类似01背包，外层加一个组的循环，有空详细看看
例子

区间变化\染色问题

静态询问：所有改变结束后在查询
动态查询：过程中的查询 – 线段树法

静态询问

差分数组法（区间修改，静态询问）

https://leetcode.cn/problems/range-addition/solution/370-qu-jian-jia-fa-by-flytowns-vnjh/

非线段树解法

https://leetcode-cn.com/problems/QO5KpG/solution/lcp-52-by-flytowns-2ivu/

动态询问

以后补

dfs

void dfs

一般适用于地图和回溯
整理了一个自己习惯用的模版

class Solution {
public:
	//把一些dfs过程中用的变量定义为全局变量
	//可以节省dfs的参数列表的数量
    int res = INT_MAX;
    vector<int> st; //start
    vector<int> ed; //end
    vector<string> mx;
    vector<vector<bool>> visit;
    //方向数组
    int dir[4][2] = {{0,1},{1,0},{0,-1},{-1,0}}; 
    void dfs(int x, int y, int xxxx){
        if(x==end[0]&&y==emd[1]){
            res = min(res,time); 
            return;
        }
        for(int i=0;i<4;i++){
			int newx = x + dir[i][0];
			int newy = y + dir[i][1];
			if(newx<0||newy<0||newx>=mx.size()||newy>=mx[0].size()||visit[newx][newy]) continue;
			//这里使用了回溯思想，当然也可以直接把visit作为函数的参数，就不需要visit->false这步复原了，但这样会占据更多空间
			visit[x][y] = true;
            dfs(x+dir[i][0],y+dir[i][1],xxx);
            visit[x][y] = false;
        }
    }
    int conveyorBelt(vector<string>& matrix, vector<int>& start, vector<int>& end) {
        //首先 把全局变量赋值 + 初始化visit数组（vector）
        st = start;
        ed = end;
        mx = matrix;
        int m = mx.size();
        int n = mx[0].size();
        visit.resize(m,vector<bool>(n,false));
        //开始dfs
        dfs(start[0],start[1],0);
        return res;
    }
};
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

有返回值的dfs

例子
树的dfs有的情况不好采用返回值为空的dfs。即使传参变为引用有时逻辑也不好想。
dfs时不用想内部怎么实现的，只需要想三件事。

1 边界return
2 获取子层dfs的值（按照期望的dfs的定义）
3 用子层dfs的值更新该层/res/return

ps:
后来思考了一下，其实用void dfs也能做。只不过需要再dfs前把传入的引用变量赋值，并且dfs函数的最后，要更新引用值。

这道题做的时候自己的问题在于，想的有点多，因为从理解上外层dfs只拿到了根root的sum和num，但是在遍历过程中其实把每一个node都算了。
所以编码时，可以先不思考复杂的递归逻辑，定义好每一个递归干了啥，ex。该dfs只获取以该root为跟的sum和num，只判断该树是否满足即可。

！！！！这类题有时候有种特点->最终结果是在过程中更新的，不作为返回值，返回值用作其他更直观的属性。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
 
class Solution {
public:
    int ans = 0;
    vector<int> dfs(TreeNode* root){
        if(root==nullptr) return {0,0};
        auto l = dfs(root->left);
        auto r = dfs(root->right);
        int num = l[0]+r[0]+root->val, sum = l[1]+r[1]+1;
        if(root->val == num/sum) ans++;
        return {num,sum};
    }
    int averageOfSubtree(TreeNode* root) {
        dfs(root);
        return ans;
    }
};

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

树的dfs&路径类问题

路经总和1
路经总和2
路经总和3
路经总和4

可以通过prefix优化

还有一些树的dfs见leetcode之路

树形dp 配合 dfs

用一次dfs解决，dfs返回一个值，同时在过程中维护ans，将路径拆成两部分的和
543
1245树的直径
2538

位操作 + dfs

__builtin_popcount可以计算一个数中二进制为1的数量
1239

记忆化 + dfs

个人理解：
首先肯定这类题可以通过dfs本身解决，使用记忆化可以降低复杂度。
这类dfs有个特性，dfs过程中各个部分可以相对独立开，这样就可以把dfs过程中的量保存下来，之后再dfs到了同样情况的时候，直接使用。
一般是返回值作为要保存的量，用一个hashmap去保存（dfs的位置，返回值）
word break 2
longest increasing path in a matrix
241

bfs

bfs跟dfs的一个区别在于：
bfs的边界判断在入队前就进行了。
dfs的边界判断可以在dfs前，也可以在下一轮dfs开始的时候。

//200 岛屿数量
/*
bfs
遍历矩阵，值为1，岛屿数++，从这个点开始进行bfs遍历
bfs遍历到值为1的点后，把该点值变为0，相当于标记
*/
class Solution {
public:
    int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};//二维数组的初始化
    int numIslands(vector<vector<char>>& grid) 
    {
        int res=0;
        int n=grid.size();
        if(n==0) return 0;
        int m=grid[0].size();
        queue<pair<int,int>> que;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(grid[i][j]=='1')
                {
                    res++;
                    grid[i][j]='0';
                    que.push(make_pair(i,j));
                    while(!que.empty())
                    {
                        auto cur = que.front();
                        que.pop();
                        for(int a=0;a<4;a++)
                        {
                            int newi=cur.first+dir[a][0];
                            int newj=cur.second+dir[a][1];
                            if(newi<0||newj<0||newi>=n||newj>=m||grid[newi][newj]=='0')continue;
                            grid[newi][newj]='0';
                            que.push(make_pair(newi,newj));
                        }
                    }
                }
            }
        }
        return res;           
    }
};

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

toposort with bfs

拓扑排序一般针对于如下问题：
有一堆有序的item，让你给出整体的顺序。

经典： 207
复杂一些的如下

class Solution{
    
public:
    
    vector<pair<char,int>> equationSolve(vector<string> v){
    // we return by empty vector if system is not solvable
    // otherwise we return by a single solution (note that there exists an integer solution)
    // assume that each variable is a char
    /*
    A = B + C
    B = C + D + 5
    C = 4
    D = 6
    */
        unordered_map<char,pair<bool,int>> vars; // key: char(ex. A); pair <true, val of it>
        vector<pair<vector<char>,int>>equations; // vec[0]等式左边 vec[1-n]等式右边的变量 int等式最后的variable
        vector<pair<char,int>>ans;  
        
        // extract variable and integer form the equations
        for(string s:v){
            pair<vector<char>,int>eq;
            
            eq.second=0;
            for(int i=0;i<s.length();i++){
                char d=s[i];
                if(d>='A'&&d<='Z'){
                    eq.first.push_back(d);
                    vars[d]={false,0};
                }
                else if(d>='0'&&d<='9'){ 
                    for(;i<s.length();i++) //这里假定只有加法 且等式右边只有一个且最后一个是
                        eq.second=10*eq.second+(s[i]-'0');                    
                }                
            }
            equations.push_back(eq); 
        }
        
        int N=0;// number of unknown variables
        unordered_map<char,int>id; //每个var给一个id
        for(auto it=vars.begin();it!=vars.end();++it)id[it->first]=N++; 
        
        int num_eq=equations.size(); 
        vector<int>numedges(num_eq,0); //记录每个equation的右侧含有几个变量
        vector<vector<int>>graph(num_eq); // i: 每个等式右侧的变量 j:等式id
        for(int k=0;k<num_eq;k++){ 
            int size=equations[k].first.size();
            //int x=id[equations[k].first[0]];
            for(int i=1;i<size;i++){
                int y=id[equations[k].first[i]]; 
                numedges[k]++;
                graph[y].push_back(k);                
            }
        }
        
        queue<int>q;
        for(int i=0;i<num_eq;i++)if(numedges[i]==0)q.push(i); //把等式右侧没有变量的作为初始 即 x = 5之类
        while(!q.empty()){
            for(int i=q.size()-1;i>=0;i--){
                int k=q.front();q.pop();
                char d=equations[k].first[0];
                int x=id[d]; //获取想求的var的id
                int val=equations[k].second; 
                if(vars[d].first&&vars[d].second!=val)return ans; //这步是验证是否正确，我觉得醉开始可以不写
                vars[d]={true,val}; //求出
                for(int j=0;j<graph[x].size();j++){ //因为已经求出了x，现在用x去更新当x作为等式右边变量时候的式子
                    int l=graph[x][j]; 
                    numedges[l]--;
                    equations[l].second+=val;
                    if(numedges[l]==0)q.push(l);
                }
            }
        }

        for(auto a:equations){ //可以先不写
            char d=a.first[0];
            if(vars[d].second != a.second)return ans;
        }
        
        for(auto it=vars.begin();it!=vars.end();++it)
            ans.push_back({it->first,it->second.second});
        return ans;
    }
};            

int main(void){
    
    Solution* s=new Solution;
    
    auto a=s->equationSolve({"A=B+C","B=C+D+5","C=4","D=6"});
    for(auto p:a)cout<<p.first<<" "<<p.second<<endl;cout<<endl;
    
    a=s->equationSolve({"A=B+C","B=C+A","C=A+B"});
    for(auto p:a)cout<<p.first<<" "<<p.second<<endl;cout<<endl;
    
    a=s->equationSolve({"A=B+24","B=A+3"});
    for(auto p:a)cout<<p.first<<" "<<p.second<<endl;
    
    return 0;
}
// output (note that the 3rd test has no solution
D 6
C 4
A 19
B 15

C 0
A 0
B 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
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

优先队列+bfs

例子

有些时候，常规dfs和bfs会超时，这时候可以用bfs+优先队列解决。
因为bfs一旦到达终点，便结束，无需像dfs那样全部遍历完。
bfs配合上优先队列的排序，即，将bfs的队列换为优先队列，并重载小于号。
这样可以达到剪枝的作用。

ex. 走迷宫问题，当每个砖消耗时间不同的时候。

值得注意的是：
bfs的visit数组的更新位置需要根据题意进行选择。
1 入队时，更新visit
2 pop前，更新visit
取决于，已经入队但尚未出队的点，是否允许再次访问。
下面代码中进行了标注

若想要输出路径，可以在每一个点上记录来源方向，最后结果反推

class Solution {
public:
    int res = INT_MAX;
    
    struct st {
        int x, y, time;
        st(int x, int y, int time): x(x), y(y), time(time) {}
        bool operator<(const st& s) const& { return s.time < time; }
    };

    int dir[4][2] = {{0,1},{1,0},{0,-1},{-1,0}}; //> v < ^
    int check(char c){
        if(c=='>') return 0;
        else if(c=='v') return 1;
        else if(c=='<') return 2;
        else return 3;
    }
   
    int conveyorBelt(vector<string>& matrix, vector<int>& start, vector<int>& end) {    
        priority_queue<st> pq;
        pq.emplace(start[0],start[1],0);
        vector<vector<bool>> visit(matrix.size(),vector<bool>(matrix[0].size(),false));
        while(!pq.empty()){
            st s = pq.top();
            //cout<<s.x<<" "<<s.y<<" "<<s.time<<endl;
            //2 pop update visit
            visit[s.x][s.y] = true;
            pq.pop();
            if(s.x==end[0]&&s.y==end[1]){
                res = s.time;
                break;
            }
            int di = check(matrix[s.x][s.y]);
            
            for(int i=0;i<4;i++){
                int newx = s.x+dir[i][0], newy = s.y+dir[i][1];
                if(newx<0||newx>=matrix.size()||newy<0||newy>=matrix[0].size()||visit[newx][newy]) continue;
                //1 emplace update visit
                //visit[][]=true;
                if(i==di) pq.emplace(s.x+dir[i][0],s.y+dir[i][1],s.time);
                else pq.emplace(s.x+dir[i][0],s.y+dir[i][1],s.time+1);
            }
        }
        return res;
    }
};
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

DP

1.字符串DP

a.思路一

提示 1-1
将所有子串按照其末尾字符的下标分组。
提示 1-2
考虑两组相邻的子串：以 s[i-1] 结尾的子串、以 s[i] 结尾的子串。
提示 1-3
以s[i]结尾的子串，可以看成是以s[i-1]结尾的子串，在末尾添加上s[i]组成。
上面这一串提示是思考子串统计类问题的通用技巧之一。
例子1
例子2 300最长递增子序列 见个人blog—leetcode之路

b.思路二

遍历长度，两边扩展
例子 5最长回文子串 见个人blog—leetcode之路

2. 常规dp

a.单层

word break
跳跃问题 45 403

b.双层

可以第二维度用一个[k]
ex. 股票系列问题 见leetcode之路2

3.特殊

二分+dp 1235规划兼职工作

对空间复杂度有限制的题目

ex. 要求在原数组上处理

1.自己定义新的状态

ex. 原先数组只有0，1；自己新增2，3表明变化
例子

2. 分块进行

例子

经典“最”问题

1. LIS 最长递增子序列

最优方法：二分+贪心
300
朴素方法：dp

2.LCS 最长公共子序列

二维dp
1143题（见leetoce之路）

3. 最长公共子串

在LCS基础上稍微改动
见leetcode之路

spilt

使用getline和istringstream实现

 void split(const string& s, vector<string>& sv,const char flag = ' ') {
    sv.clear();
    istringstream iss(s);
    string temp;

    while (getline(iss, temp, flag)) {
        sv.push_back(temp);
    }
}
1
2
3
4
5
6
7
8
9

使用find实现
str.find(c,pos); //从pos之后开始找
用这个比较好，可以自定义多种分隔的情况

void split( const string &str, vector<string> &vec, char c){
	vec.clear();
	string sub;
	for (size_t start=0, end=0; end!=string::npos; start=end+1){
		end = str.find( c, start );
		sub = str.substr( start, end-start );
		if (!sub.empty()){
			vec.push_back(sub);
		}
	}
}
void split(string & str, vector<string> & vec, vector<char> c){ //分隔符有三种的情况
    vec.clear();
    string sub;
    for(size_t start = 0, end = 0; end != string::npos; start = end+1){
        end = min(str.find(c[0],start),min(str.find(c[1],start),str.find(c[2],start)));
        sub = str.substr(start,end-start);
        if(!sub.empty()){
            vec.emplace_back(sub);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

链表

1. 快慢指针

模版（奇数位于中间 偶数位于靠后的）

 ListNode* middleNode(ListNode* head) {
     ListNode* slow = head;
     ListNode* fast = head;
     while(fast && fast->next){
         slow = slow -> next;
         fast = fast -> next -> next;
     }
     return slow;
 }
1
2
3
4
5
6
7
8
9

进阶版，找到相遇点
287 142

 ListNode* middleNode(ListNode* head) {
     ListNode* slow = head;
     ListNode* fast = head;
     while(fast && fast->next){
         slow = slow -> next;
         fast = fast -> next -> next;
         if(slow==fast) break;
     }
     while(l!=slow){
         l=l->next;
         slow=slow->next;
     }
     return l;
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

2. 反转链表

三种题
1 全部反转
2 反转部分（提供left, right）
3 间隔k个反转

总结：
反转操作需要 pre cur next三个节点
对于后两种，需要在head前新建一个节点。反转时要先将pre = end->next。循环条件(cur!=end)
对于第一种，反转时pre = nullptr.循环条件（nxt）

优先队列

1. 题型

a. topK

ex. 347
通过优先队列末位淘汰

维护过程注意事项：先emplace 再判断>k进行pop 最稳妥

for(auto e : mp){
    pq.emplace(make_tuple(e.second, e.first));
    if(pq.size() > k) pq.pop();
}
1
2
3
4

b. 合并有序链表/数组

ex. 23, 378
通过优先队列选择想要的点

c.与排序配合的

253 会议室2

2. 关于优先队列的排序方法

a. 用自带第三个参数的greater和less，封装到pair/tuple中（目测最简单的）

greater 升序
less 降序
例子

b. 重载()

//cmp重载方法 1.放到结构体里 2.排序与sort正好相反（升序 return a>b;降序 return a<b）
struct cmp1{  
    bool operator ()(int a,int b){  
        return a>b;//最小值优先  
    }  
};  
struct cmp2{  
    bool operator ()(int a,int b){  
        return a<b;//最大值优先  
    }  
};  
struct cmp3{
	bool operator (){pair<int,int> a, pair<int,int> b}{
		return a.second<b.second; //第二个元素最大值优先
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

例子

c. 结构体内重载<

一定重载小于号
https://www.acwing.com/blog/content/5069/

//val小顶堆（val从小到大）
    struct Node{
        int x, y, val;
        Node(int x, int y, int val):x(x),y(y),val(val){}
        bool operator<(const Node &t)const {
            return val > t.val; 
        }
    };
//val大顶堆（val从大到小）
    struct Node{
        int x, y, val;
        Node(int x, int y, int val):x(x),y(y),val(val){}
        bool operator<(const Node &t)const {
            return val < t.val;
            /*
            可以这样记，首先优先队列的重载都是反的。
            参数中：this < t
            return this->val < t.val
            正常顺序就是 this < t了，应该是升序
           	然后反过来，变成降序，即大顶堆。
            */
        }
    };

//使用的时候
priority_queue<Node, vector<Node>> pq;
//不加第三个参数！
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

例子

d. lambda

优先队列的重载方法

auto cmp = [](const pair<int,int> & a, const pair<int,int> & b){return a.first > b.first;}; //优先队列反过来 依据first升序
priority_queue<pair<int,int>, vector<pair<int,int>>, decltype(cmp)> q(cmp);
//按照first的最小堆
//ex. https://leetcode.cn/problems/network-delay-time/solution/743-wang-luo-yan-chi-by-flytowns-t2r9/ 
1
2
3
4

set的重载方法 （类似优先队列）

auto cmp = [](int & a, int & b){return a < b;}; //min heap set是正常的顺序，不用反过来
set<int,decltype(cmp)> st(cmp);
1
2

注意！

auto cmp = [](const std::vector<int>& a, const std::vector<int>& b) {
    if (a[3] != b[3]) {
        return a[3] < b[3];
    }

    // 如果第四个元素相同，比较整个向量
    return a < b;
};
std::set<std::vector<int>, decltype(cmp)> q(cmp);
q.insert({2, 3, 4, 3});
q.insert({2, 3, 3, 5});

这种如果cmp中只有 return a[3] < b[3]; 会有问题，需要这么写一下
1
2
3
4
5
6
7
8
9
10
11
12
13
14

map的重载方法

auto cmp = [](const int &a, const int &b) { return a > b; };
std::map<int, int, decltype(cmp)> myMap(cmp);
1
2

sort的重载方法（可以直接写在里面）

vector<int> vec;
sort(vec.begin(), vec.end(), [](int & a, int & b){
	return a < b;
});
1
2
3
4

upper_bound/lower_bound重载方法

 auto iter = lower_bound(vec.begin(), vec.end(), cur, [](const int & a, const int & b){return a < b;});
 //注意这里有时编译不过要加const 且后面 a < b 不要 =, upper_bound也是一样
1
2

3 补充 关于set（heap）的排序方法（注意：与优先队列相反）

当使用set时，要自定义set的排序函数时，从小到大就是从小打大，不用反过来，与优先队列相反。
eg.

//set（val从大到小）
    struct Node{
        int x, y, val;
        
        Node():x(),y(),z(){} // 若编译过不去，需要加一下
        Node(int x, int y, int val):x(x),y(y),val(val){}
        bool operator<(const Node &t)const {
            return val < t.val; //这里也可以写为 this->val < t.val;
            /*
           
            参数中：this < t
            return this->val < t.val
            正常顺序就是 this < t了，是升序，又因为不像pq那样需要反过来，所以就是升序。
            */
        }
    };

//使用的时候
set<Node> pq;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

双指针

背向双指针

回文串 按长度从小到大dp
ex 5,125

相向双指针

几数之和- 先排序 再相向双指针（>2个数 先从左到右确定一个 另外一边进行双指针）
ex 1,15,18

同向双指针（滑动窗口）

模版

/*
同向双指针 --- 滑动窗口
以leetcode_3 无重复字符的最长字串 为例：给定一个字符串s，请你找出其中不含有重复字符的最长子串的长度。
模版如下
*/
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int slow = 0, fast = 0, res = 0;
        int n = s.size();
        unordered_map<char,int> mp;
        /*
        定义变量：
        快慢指针int slow = 0, int fast = 0; 输入的string s; 
        hashmap用于记录string s当中slow到fast（包含）之间所有的字母出现的频率；
        int res记录符合题目要求的最长substring长度等
        */
        while(fast < n){
            //更新fast指针位置的mp
            mp[s[fast]]++;
            //满足某种条件->需要滑动slow指针 ex. 该题：若当前点mp>1 说明前面有重复的 进行循环滑动
            while(mp[s[fast]]>1){
                mp[s[slow]]--;
                slow++;
            }
            //更新res
            res = max(res, fast - slow + 1);
            //递增fast
            fast++;            
        }
        return res;
    }
};
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

1 基础题：

3 链接

2 中等类型：

while内部需要进行一些条件判定 ex. 340 76

3 特殊类型：

保持相对顺序去掉某种字符（更简单）ex.26 283

4 复杂类型：

自己在最外层加循环条件的 一般遇不到（或有其他方法）ex. 395

排序

基数排序

例子+解析

字典树 Trie Tree

实现Trie Tree
trie tree + 记录过程
dfs + 字典树 word search 2

位操作

见c++个人总结

OOD

class A{
};
class Farm{
public:
    int kind;
    Farm(int kind);
    virtual int getKind();
    int getKind(int isOutput); //重载
    void setKind(int kind);
    ~Farm();
    A * a; //调用A类的对象

};
Farm::Farm(int kind){
    this->kind = kind;
}
Farm::~Farm() {

}
int Farm::getKind() {
    cout << "Farm getKind" << endl;
    return kind;
}
void Farm::setKind(int kind) {
    this->kind = kind;
}
class SmallFarm : public Farm {
public:
    using Farm::Farm;
    int showKind();
    int getKind();
    void interface();
};
int SmallFarm::showKind() {
    return kind;
}
int SmallFarm::getKind() { //多态
    cout << "smallFarm getKind" << endl;
    return kind;
}
void SmallFarm::interface() {
    cout << "interface" << endl;
}


int main() {
    Farm f(10);
    A *p = new A();
    f.a = p;
    SmallFarm smallFarm(1);
    smallFarm.getKind();
    cout << "----" <<endl;
    Farm * fp = new SmallFarm(1);
    fp->getKind();//基类没加virtual时，这里输出的还是基类的
    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

Union Find

261

//323 （模版）
// https://leetcode.cn/problems/number-of-connected-components-in-an-undirected-graph/submissions/479111070/
class Solution {
public:
    vector<int> father;
    void init(int n) {
        father.resize(n);
        for(int i = 0; i < n; i++) father[i] = i;
    }
    int find(int x) {
        if(x == father[x]) return x;
        else return father[x] = find(father[x]);
    }
    void merge(int x, int y) {
        father[find(x)] = find(y);
    }
    int countComponents(int n, vector<vector<int>>& edges) {
        init(n);
        for(auto e:edges) {
            merge(e[0],e[1]);
        }
        int res = 0;
        for(int i = 0; i < n; i++) {
            if(father[i] == i) res++;
        }
        return res;
    }
};
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

Greedy

快速幂

50

/*
x^77
77: 1   0   0   1   1   0   1
    x64        x8   x4      x1
    64+8+4+1 = 77
*/
//time O(logn)
//space O(1)
class Solution {
public:
    double myPow(double x, int n) {
        long N = n;
        if (N < 0) N = -N;
            double ans = 1.0;
        while (N > 0) {
            if ((N & 1) == 1) {
                ans *= x; //把二进制为1的取出来
            }
            N >>= 1;
            x *= x;//相当于求出x1,x2,x4,x8,x16
        }
        return n >= 0 ? ans : 1.0 / ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

时间复杂度/空间复杂度

全指一般情况，特殊情况特殊分析

一些公式

O(n) + O(n/2) + O(n/4) + … = O(2n) = O(n)
O(log1) + o(log2) + … + o(logn) = o(nlogn)

树的DFS

时间：O(N) N为节点数量
空间: O(d) d为树的深度，一般为logN

树的BFS

时间：O(N) N为节点数量
空间：O(d) d是树的宽度，即为节点最多的一层的节点个数

图 DFS/BFS

时间：O(N) 空间：看存储的大小
（DFS加上递归本身的深度，BFS加上queue，但一般这两部分都小于存储本身）

图 toposort

时间：O(N + E) N为节点数量, E为边的数量 （邻接表存储）邻接矩阵是O(N^2)
空间: O(N + E) (邻接表) 临界矩阵是 O（N^2）因为矩阵数组是二维的

图 topsort

时间：O(N + E) N为节点数量, E为边的数量 （邻接表存储）
空间: O(N + E) (邻接表)

普通DFS

时间： O(N) 节点数
空间：存储+递归层数 一般O(N)

普通BFS

时间：O(N)
空间：存储+queue 一般O(N)

注意

有一些求全部排列的，不符合以上，可以考虑为排列组合的感觉，直接相乘
ex. leetcode 17
leetcode 797 分析