leetcode-learning

本文最后更新于：5 个月前

前情提要

🔴 -> 一般是指hard的题目,且没pass出来的,就是连暴力解法都想不到的

🔵 -> 表示十拿九稳的题目

C的字符数组和C++的string转换以及常用函数

1
2
string s = "hahaha";
const char* c_s = s.c_str();

c++中通过导入iomanip,可以用fixed来使浮点数定位(无论double d 里的值是整数浮点数,统统给它输出浮点数形式)
通过setprecision(n)来确定整体数字位数,若没有结合fixed使用,则代表的位数是整数位+小数位n;结合fixed使用则代表的位数是小数位n

C++一些流

istream& getline(istream& is,string& s,char delim)

  • is是输入流对象, 可以是标准输入cin,可以是输入文件流对象ifstream,可以是输入字符串流对象istringstream等等
  • s存储读到的一行文本的字串
  • delim分隔符,表示在哪个字符处停止读取,默认是\n
  • 返回值是输入流对象的引用

参考文件:

algorithm一些算法

sort

排序算法,很经典,c++里用的是快排实现的,我们的容器可以通过如下方式使用它:

sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp)

  • 第一个参数是迭代器的起始地址
  • 第二个参数是迭代器的结束地址(就是那个end(),结束位置的下一位)
  • 第三个参数是排序规则

这里主要讲自定义排序规则,默认是升序(即默认采用<运算符进行比较,谁小谁排前面).可以通过:

  • lambda表达式(本质上是定义一个返回值为bool的两个待比较参数的比较函数)

  • 重载运算符

    主要运用在结构体里,以指示如何对结构体里的成员进行比较,然后调用c++自带的仿函数less<T>()/greater<T>()(头文件是<functional>)来对序列中的T类型排序,示例如下:

    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
    struct Person{
      int id;
      int score;
      Person():id(0),score(0){}
      Person(int _id,int _score):id(_id),score(_score){}
      // 重载>运算符
      bool operator> (const Person& other) const{
      	if(score != other.score)
      		return score > other.score;
      	return id < other.id;
      }
    };
    int n=5;
    vector<Person> people(n);
    int scores[5] = {100,100,80,80,90};
    int main(){
        for(int i=0;i<n;i++){
            people[i].id = i + 1;
            people[i].score = scores[i];
        }
        // 使用greater仿函数来通过'>'运算符进行比较,则会调用到Person里重载的'>'运算符里的规矩来进行排序
        sort(people.begin(),people.end(),greater<Person>());
        for(auto p:people)
        	cout << p.id << " "<< p.score <<endl;
    	return 0;
    }
    cpp_functional_greater

  • 仿函数

    仿函数(functor)是一个类/结构体,里面重载了operator(),从而仿函数的对象可以像函数一样被调用,大致如下:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    class Greater{	// 定义一个仿函数
    	public:
    		bool operator()(const int& x,const int& y){
    			return x>y;
    		}	
    };
    void main(){
    	vector<int> v = {3,5,2,1,8,6,7,4,9,0};
    	Greater g;	// 仿函数的对象
    	sort(v.begin(),v.end(),g); 
    	
        // 下面这种也可以,跟c++提供的仿函数greater<int>()一样,这里的greater是个struct
        //	sort(v.begin(),v.end(),Greater());
    }

以上三种方式的任一方式来实现自己的排序功能,乃至多级排序:

1
2
/*下面演示的是对vector降序排序*/
sort(a.begin(),a.end(),[](const int& i,const int& j)->bool{return i>j;});

可以这么理解i>j就是谁大谁排前面(i是第一个参数,j是第二个参数),当然上面的也可以写成普通的函数;

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
/*下面演示的是多级排序,对自定义结构体Person*/
struct Person{
  int id;
  int score;
  Person():id(0),score(0){}
  Person(int _id,int _score):id(_id),score(_score){}
};
int n=5;
vector<Person> people(n);
int scores[5] = {100,100,80,80,90};
int main(){
    for(int i=0;i<n;i++){
        people[i].id = i + 1;
        people[i].score = scores[i];
    }
    /*
    排序规则:
    	1.先按分数由高到低排
    	2.分数相同的id小的排前面
    */
    sort(people.begin(),people.end(),[](const Person& a,const Person& b)->bool{
    	if(a.score != b.score)
            return a.score > b.score;
        return a.id < b.id;
    });
    return 0;
}

参考资料:

iota

这是一个区间填充函数,所在头文件为numeric,函数原型如下:

1
2
template <class ForwardIt, class T>
void iota(ForwardIt first, ForwardIt last, T value);

前两个参数用迭代器指定区间范围,最后的参数用来指示起始值,可以迅速的填充好一个区间,比如:

1
2
3
int size = n;
vector<int> idx(n);
iota(idx.begin(),idx.end(),0); // [0, ..., n-1]

unique

用于去除容器中重复出现的相邻元素,显然需要排序后使用,那得到的返回值是一个迭代器,是指向新的最后一位元素的下一位的迭代器

它并不是真的将重复元素去掉,而是把它们全部隐藏在了容器后面,这样去除后的新的元素个数是通过:int n = unique(nums.begin(),nums.end())-nums.begin();来获取得到的,当然如果想真正去除它们,也可以结合erase搭配使用,如nums.erase(unique(nums.begin(),nums.end()),nums.end());

一些STL容器回顾

这里主要记着主要方法,后续有新的会来补充,以便于一开始训练的时候查方法,当然也会说一下不同容器/相似容器间的差别

参考资料:

字符串

因为字符串涉及的函数非常多,且有些函数很少用,但在一些机试的时候会遇到,而且自己重写非常繁琐,因此这里记录一下一些函数,这里会混杂字符的内容

数字,字母,大小写部分:

  • isalpha()用于判断一个字符是否是字母
  • isalnum()用于判断一个字符是否是字母或数字
  • isupper()用于判断一个字符是否是大写的
  • islower()用于判断一个字符是否是小写的
  • toupper()将一个字符转为大写
  • tolower()将一个字符转为小写

上面的是针对字符的,源自<ctype.h>

对于字串来说的话,导入algorithm库可有以下转换方式:

  • transform(s.begin().s.end(),s.begin(),::tolower) 转换整个字串为小写,其中第一二个参数是输入容器的起始和终止迭代器(终止不含),第三个参数是输出容器的开始迭代器,第四个参数是一元函数对象
  • transform(s.begin(),s.end(),s.begin(),::toupper) 转换整个字串为大写

字符串和整型的转换:

  • stoi(string,nullptr,base) 字串转整数,base是string的进制,比如string是二进制的,则这里就写个2,会自动做进制转换
  • to_string(int/long/float) 将一个数字常量转为字符串

还有一种atoi(),itoa的字串和整型的转换,但是需要注意这种针对的是字符数组,而非string

字符串做切片

  • substr(start,len) 从start处,切len这么长的子串,不指定len则到结尾
  • substring(start,end) 从start处开始,切到end,其中不包括end索引的字符,不指定end则到结尾[这是java/js才有的,搞错了= =]

初始化函数

在结构体或者类中,需要对一些为指针的成员实现初始化(别的也尽量初始化),不然会报内存不对齐的错误,传统的C在cstring这个库里有**memset(void* s,int c,size_t n)**可以对一块内存进行初始化,如:

1
2
3
4
5
6
7
8
9
10
class Trie{
private:
    bool isEnd;
    Trie* next[26];
public:
    Trie(){
        isEnd=false;
        memset(next,0,sizeof(next));
    }
};

注意:由于memset是按字节对内存块进行初始化,也就是说第二个参数c只会取低八位,然后赋值给一块地址(一块地址是一字节).比如int是4字节,那如果给的c是1,就会变成0x01010101,每个字节分别是0000 0001这么一个情况,所以一般第二位填0或-1就好了,它跟那种vector<int>v(10,5) // 十个数,每个都是5不一样

由于LeetCode检测机制更加严格，所以我们在创建节点是，还需将指针域赋值。

参考文件:runtime error: member access within misaligned address(力扣最常见错误之一)

顺序容器

vector

  • push_back()
  • emplace_back()

上面两个函数都是向容器尾部添加元素

push_back():1. 创建元素; 2. 调用移动构造函数/拷贝构造函数,将元素弄到容器中

emplace_back(): 1. 直接在容器尾部创建元素,减少了拷贝/移动的开销

其中移动构造函数和拷贝构造函数是不同的:后者是将一个已存在的对象复制到一个新的对象中;前者是将一个对象的资源移动到一个新的对象中.因为一般自己写的拷贝构造是深拷贝(为了避免浅拷贝指向同一块内存的问题)所以涉及到内存分配,而拷贝又涉及到数据复制

而其中移动构造涉及到右值引用的知识,可以看看参考文件

参考文件:

queue[容器适配器]

  • push()
  • pop()

push,pop遵循FIFO

  • size()
  • empty()
  • front()
  • back()

queue参考资料:queue基本方法

deque(双端队列)

相比于vector,可以更好更迅速的处理头部元素

list(双向链表)

forward_list(单链表)

stack(栈)[容器适配器]

  • push() #压入
  • pop() # 弹出
  • top() # get栈顶
  • back() # get栈底
  • empty()
  • size()

不能通过索引遍历,用while(!s.empty())遍历

stack参考资料:stack基本方法

priority_queue(优先队列)[容器适配器]

底层是通过堆实现的优先队列,常数时间的最大/最小元素查找,默认是大顶堆(less<T>),则最大元素位于top(),当调用pop()则会发生类似adjust_down()一类的内部函数的操作

具备自动排序的特性,所以对如前k个…最大/最小的题目都很适用

优先队列的定义如下:

1
2
#include <queue>
priority_queue<int,vector<int>,less<int>> pq; // 其中只有第一个是要具体定义的,三个分别是:元素类型,容器类型,比较函数类型

注:这里传入的是比较函数的类型,而不是具体的对象,因此不用像sort里的加多个(); 这个跟自定义map的key的比较方式很相似,传的是类型而不是匿名对象

  • push()
  • pop()
  • top()
  • size()
  • empty()

有一个比较可能会遇到的问题就是重写比较函数,这里给出一个模板:

1
2
3
4
auto cmp = [&](const auto& a,const auto& b){
    return a.xxx > b.xxx;					//这样构造的是该规则下的小顶堆,可以按sort理解为这是降序,然后堆排序降序的话是小顶堆弄的
}
priority_queue<T,vector<T>,decltype(cmp)> pq(cmp);

这么一个模板可以重写比较规则,使得出来的大顶堆/小顶堆(也就是最大值/最小值)符合我们的需求

参考文件:

关联容器

set

内部是通过红黑树实现的,去重且递增(自动有序),遍历只可以通过iterator遍历,插入值是insert的方式

set方法大全

以下这俩函数是针对的容器中的数值是有序的,而set有序,故可以用:

  • lower_bound():实参用个val,会找到set容器中>=val的iterator,找不到就滑到end()了
  • upper_bound():实参用个val,会找到set容器中>val的首个iterator,找不到就滑到end()

set参考资料:set

unordered_map

底层是通过哈希表实现的无序map

map

  • insert()
  • begin()
  • end()
  • clear()
  • count() # 返回指定元素出现的次数,key唯一就是0/1
  • empty()
  • erase() # 删除一个元素,并返回下一个元素的迭代器(使用特别注意,要承接这个return值,而不是自增)
  • find() # 查找一个元素,找得到返回对应位置迭代器,否则滑倒end()去
  • size()
  • rbegin()
  • rend()
  • lower_bound() # 返回键值≥\ge给定元素的第一个位置
  • upper_bound() # 返回键值>\gt给定元素的第一个位置
  • swap() # 交换两个map

参考文件:

multimap

允许key重复,没有重载operator[],底层红黑树

  • insert()

注:只可以用这个加值,不像map可以用[]来加值,需要注意

其它数据结构

bitset

在一些需要涉及到整体区间移动的位运算时,而数据的范围远大于32,64的情况下,可以选用bitset即位图这种数据结构来进行优化

位图位图,本质上就是许多的bit,可以很方便的进行位运算,也可以在海量数据情况下很快进行检索,也相对不那么占空间(因为一般用作1个位来表示1个数)

  • bitset<N> f; //N表示位数,用以初始化,[0,N-1]位
  • set(i) // 第i位设置为1.不指定具体的位则为全置1
  • reset(i) // 第i位设置位0,不指定具体的位则为清0
  • size() // 获取位图的总位数
  • test(i) // 获取第i位的状态,1-true,0-false

一些板子

写题记录总结,并记忆一些板子,以便后期快速完成题目

dfs

不撞南墙不回头

实现手段: 递归

适用于: 树,图

经典题目: 迷宫找通路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void dfs(/*状态*/) {
    if(/*递归结束条件*/){
        // ...
        return;
    }
    for(/*找寻新状态*/){
        // 定义新状态
    	if(/*新状态满足边界条件*/ && /*新状态满足题意*/ && /*新状态满足标志位*/){
            flag[/*新状态*/]=...// 设置标志位
            dfs(/*新状态*/);
            flag[/*新状态*/]=...// 设置为旧的flag以回溯
        }
    }
}

状态是指比如迷宫里的坐标xy一类的东西

bfs

像波一样,由近及外

实现手段: 队列

适用于: 最短路径

因为广度优先搜索和层序遍历概念很像,这里举的模板是按着层序遍历的写的,可以在这基础上根据题意进行变通,变通版本在下面:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
queue<int> q;
q.push(node); 				// 这里push的是类似于"头节点"或"符合题目要求的!首类节点!"
while(!q.empty()){			// 遍历队列里的点
    /*跳出条件*/ 			// 有些题目需要设置跳出条件
    int sz = q.size();
    for(int i=0;i<sz;i++){	// 一层层的遍历,这个sz代表的是这一次波及到的点,可以从树的层序遍历和矩阵中点逐个向外扩散进行想象
		auto node = q.front();
         q.pop();
        
        for(/*候选点*/){
            /*
            	获取一个候选点
            */
            if(/*满足边界*/ && /*满足题意*/ && /*满足标志位*/){	// 筛选符合状态的点
        		flags[candidateNode] = ... 					// 设置标志位
                 q.push(candidateNode);						// 满足条件的点加入队列中(这是下一层)
            }
        }
    }
}

前缀和

使用场景:原数组不变动,但需要对子数组进行频繁的累和操作(频繁查询区间和),则可以构建前缀和数组

前缀和数组即prefix[i]表示的是原数组nums在[0,i-1]这个区间的元素的累和

1
2
3
4
5
6
7
8
9
10
//	假设题目给的数组是:vector<int>& nums
int len = nums.size();
int* prefix = new int[len+1]; // 要多一个位置
prefix[0] = 0;	// 初值
for(int i = 1; i<=len; i++)
    prefix[i] = prefix[i-1] + nums[i-1];
/*
... 对前缀和数据的操作,如想获得[i,j]区间的累和,则可以通过prefix[j+1] - prefix[i]获得
*/
delete []prefix;

前缀和+哈希表

这里以560题和为k的子数组为例,前缀和一般喜欢考某一个区间的和是k值的情况(会变形),如果按照暴力的思路,开个前缀和数组,计算每一个[i,j]区间的和,判断是否为k,如此处理,则需要两重循环,时间复杂度是O(n2)O(n^2),其实跟暴力做没太大区别

这时要怎么优化呢?首先我们期望求**[i,j]区间值为k的个数,即等价于prefix[j+1] - prefix[i] = k**,就是上面二重循环的循环判断条件

这其实跟两数之和:i + j = target是一样的,对于两数之和,我们是转换成i = target-j,然后遍历得到j,通过哈希表判断存不存在target-j,存在则返回,不存在则把j加入哈希表中来处理

对于利用前缀和求区间和满足题意的个数的题目(就是上面那个题),也可以这样转换:prefix[i] = prefix[j+1] - k,即求满足这样条件的prefix[i]的数量,也即等价于求满足prefix[j+1]-k的数量,所以遍历就可以只遍历一个维度,同时利用prefix[j+1]-k去哈希表里看,有没有match的,match就加上去,最后统计prefix[j+1]:ump[prefix[j+1]]++;,这里统计的是prefix[j+1]的次数,也即前缀和为某一个值的个数

由此则利用哈希表,把时间复杂度降到了O(n)O(n)

当然,也可以只利用一个变量preSum去统计当前区间的和(比如[0:j-1])然后利用ump.count(preSum-k)来判断是否存在区间[i,j-1]满足区间和(由于累和顺序是从左到右,依次把值加入哈希表中,所以保证了区间i<j),满足则加上满足的区间数量.这样的话,开前缀和的空间复杂度就降到了O(1)O(1)

典型例题

差分数组

当我们需要对一个数组的区间批量的进行数据增改操作时,可以考虑使用差分数组~

数组a = [1,2,3,4,5]转换为差分数组则为diff=[1,1,1,1,1],其中diff[0]=a[0];别的则是通过a[i]-a[i-1]项获得的,具体构造见下方:

1
2
3
4
5
int n = a.size();
vector<int> diff(n);
diff[0] = a[0];
for(int i=1;i<n;i++)
    diff[i] = a[i]-a[i-1];

那差分数组diff怎么变回a呢只需要第i项加上第i-1项,见下方(这里用数组b代替):

1
2
3
4
5
vector<int> b(n);
b[0] = diff[0];
for(int i =1;i<n;i++){
    b[i] = diff[i] + b[i-1];
}

那差分数组是如何发挥作用的,当面对批量对区间元素进行增改,比如我们需要对数组a的[1,3]这个区间每个元素加3(这里的区间从0开始),[0,2]每个元素减5:

1
2
3
4
5
6
7
vector<tuple<int,int,int>> vec = {{1,3,3},{0,2,-5}};
for(auto [i,j,val]:vec){
    diff[i]+=val;
    if(j+1<n){
    	diff[j+1]-=val;
    }
}

经过修改有:diff={-4,4,1,6,-2},根据题意我们直接翻译出a被修改为a={-4,0,1,7,5},将diff还原出b有:b={-4,0,1,7,5}

以上,便是差分数组的概念,我们可以通过原数组经过处理得到差分数组,同时差分数组可以变换回原数组,并且对区间的操作[i,j,val],是对diff[i]+=val;,diff[j+1]-=val;,因为[i,j]的元素在变回去的时候会加到diff[i]上多出来的val,我们只需要加到j即可,因此在j+1的时候要把累加的这个val给它收回去,则保证了只有[i,j]区间的数增加了val

典型例题:

  • 1109 航班预定统计
  • 1094 拼车

反转链表系列

"反转链表,反转链表Ⅱ,K个一组链表进行翻转"这三道题目本质上是针对反转链表的层层深入,如果采用朴素的头插法进行实现,其实罗里吧嗦要写比较多的代码.因此有了这个模板系列:

针对反转链表,主要需要建立三个指针,pre,cur,nxt,用以进行反转,最终返回pre指针即可,而判断循环终止的条件是cur!=nullptr

1
2
3
4
5
6
7
8
9
10
// 1. 反转链表
ListNode* pre,*cur,*nxt;
pre = nullptr;
while(cur!=nullptr){
    nxt = cur->next;
    cur->next = pre;
    pre = cur;
    cur = nxt;
}
return pre;

针对反转链表Ⅱ,是针对区间[left,right]进行的反转,因此我们还需要一个前序节点p0来在left对应的节点前面,以在最后反转结束时,将区间反转的结果与链表中未进行反转的节点进行拼接.但是left如果是1,即是头节点,那么就相对麻烦,因此可以new1个dummy节点,这样一来整体代码就统一了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 2. 反转链表Ⅱ
ListNode* dummy = new ListNode(0,head);
ListNode* p0 = dummy;
ListNode* pre = nullptr,*cur,*nxt;
int sz = right - sz + 1;
while(left>1){
    p0 = p0->next;
    left--;
}
cur = p0->next;
for(int i=0;i<sz;i++){
    nxt = cur->next;
    cur->next = pre;
    pre = cur;
    cur = nxt;
}
p0->next->next = cur;
p0->next = pre;
return dummy->next;

针对K个一组链表进行反转,实际上就是在上面的反转链表Ⅱ的基础上,①每次需要满足剩余节点大于K才可以进行反转;②并且p0应该指向的是下一个cur的前序节点(原先就是p0->next指向的那个点),你得后面给p0指回去.把这两点满足了这题就出来了

典型套题:

滑动窗口

滑动窗口常见于字符串匹配一类的题目,通常暴力求解会遇到TLE的问题,因此需要借助滑动窗口这一算法思想来实现

滑动窗口本质上是左右指针,通过右端的指针不断扩张,直至满足一定条件,再经由左端的指针不断收缩,收缩到一定条件,则继续右端指针扩张,循环往复,直至右端指针越了字串的界

右端指针扩张的过程,可以看作是正在寻找可行解,当满足可行解的条件,则停止扩展,通过左端指针收缩,来优化可行解,寻找到当前小区间里的局部最优解,当不再满足可行解的条件,则不再收缩,而是还给右端指针继续扩张.如此遍历完整个数组,我们便在局部最优解中挑选出了全局最优解(有些题目是要找全局最优解,有些是要收集所有符合条件的解,因题而异,这里只是说一种思想)

模板如下:

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 slidingWindow(string s,string t){
    // need表示需要满足的条件,window表示的是滑动窗口内的数据
    unordered_map<char,int> need,window;
    for(auto c:t)
        need[c]++;
    // 左右指针,左闭右开[left,right)
    int left=0,right=0;
    // valid表示符合要求的字符数目,比如t="aabc"; need = {{'a',2},{'b',1},{'c',1}};
    // 则当'a'的数目window中收集满了2个,才会给valid自增(后续还可能收集到a,且没有达到进入收缩区间的条件,即a的数目>=2),因此当valid数目和need.size()相等时,则表明t中的字符都在我们的滑动区间里,且可能是"aaabaababc"的形式,则需要收缩区间,找到符合题意的!
    int valid=0; 
    while(right < s.size()){
        char c = s[right];
        right++;
        // 1.对c处理,怎么个扩张法
        // ...
        // ...
        while(/* 2.满足条件,开始收缩*/){
            // 3.怎么更新局部最优解
            char d = s[left];
            left++;
            // 4.对d处理,怎么收缩法
            // ...
            // ...
        }
    }
}

上面是一个模板,在写同类型题目的时候要思考以下四个问题:

  1. 右端指针扩张,怎么更新值;

  2. 满足什么条件开始收缩;

    一般来说,如果是字串匹配系列的题目,我们会有两个字串,一个字串s(source)要包含另一个字串t(target),当valid==need.size()的时候,则说明目前滑动窗口[left,right)里面已经包含了该字串t(滑动窗口是在s上滑动的)

    • [76-最小覆盖字串] : 目的最小覆盖,则意味着覆盖(包含)之后再收缩,并在里面更新局部最优解,收缩至不再覆盖为止,则跳出收缩.即此时的收缩条件是valid == need.size()
    • [567-字符串的排列 438-找到字符串的所有字母异位词] : 明确要找匹配到字串t的别的排列形式(即t="abc",s里有"cab"也满足),即意味滑动窗口里的尺寸如果比字串t大,必不满足字串t的排列,因此收缩条件应该是right-left == t.size(),而判断是不是满足排列(这里就不是局部最优解的问题了,因为没有最…之类的限定词),就是valid==need.size()
    • [3-无重复字符的的最长子串] : 这个题目它只有s没有t,则不要need这个容器了,直接在滑动窗口里统计就好,当window[c]>1则表明有重复的了,那就要开始收缩,直至没有重复的,此刻则需要在收缩循环的外面统计最长字串

  3. 怎么更新局部最优解;(结合2看)

  4. 左端指针收缩,怎么更新值;

参考资料:

典型例题:

  • 3 无重复字符的最长字串
  • 438 找到字符串中的所有字母异位词
  • 76 最小覆盖字串
  • 567 字符串的排列
  • 239 滑动窗口最大值(搭配单调队列食用)
  • 209 长度最小的数组
  • 219 存在重复元素Ⅱ
  • 30 串联所有单词的子串(滑动窗口以一种技巧被应用,优化算法)
  • 1004 最大连续1的个数Ⅲ

DP系列

递归->记忆化搜索->递推

对于这一类题目,比如涉及到子序列,最长递增子序列,最长上升子序列一类的问题,可以采用dp来进行思考,那如何思考出动规的状态/子问题呢?

我们思考的时候先按照**递归**的思路来思考:

考虑最后一个索引或最前一个的索引对应的子问题,这个子问题dfs(…)的表述与所求的结果相关,比如组合数/最大值/最小值,然后根据题目类型:

  • 背包/LCS,则是选和不选的问题,可以定义为[0,i]这个区间的最大/最小,此时这个状态需要对索引i对应的值进行选/不选的处理;
  • LIS,则是枚举选哪个,可以定义为以第i个索引作为结尾的最大上升子序列长度,然后就是以这个索引定了区间的右端,来枚举看前面的最大上升子序列选哪个,然后计算完毕要+1,即加上以第i个索引作为结尾的长度

由上则可以写出对应的子问题和转移方程(选和不选 / 枚举选哪个)

递归边界,递归入口则根据题目而定

之后可以采用与状态同维的memo用作记忆化,选取一个永远不会计算到的值作为初值,当它为初值则update它,下次遇到同样的状态则直接获取并return即可

完成了记忆化搜索后,可以**通过以下方法将递归翻译成递推**(就是DP):

  • dfs -> f(可能需要放缩一下,避免索引为负数)
  • 递归 -> 循环
  • 边界 -> 初值

空间优化暂时忽略,一般不会爆内存,不管!

背包系列

在说起背包系列的问题前,先说下动规题的四大步骤:

  1. 确定子问题/状态,这一步需要好好分析,一般是前k个…/直到第k个…的最大/最小…,要保证无后效性,后来的结果不会影响前面的结果,可以通过叠定语或增加数组维度来实现,如果读起来自己觉得有问题的一般就是有问题;子问题是具备最优子结构的,可以通过求解子问题,最终获得原问题的解,如果奔头不是这个,那求来也没用
  2. 推导出状态转移方程,DP具备子问题重叠的性质,也就是说状态转移方程会出现至少两个dp的某种转移的等式
  3. 确定初值
  4. 确定原问题的答案

其中当涉及到多维dp的时候,遍历的顺序也是一个考虑的点,如0/1背包滚动数组版本和完全背包滚动数组版本,内嵌循环的正向遍历和倒序遍历就是这两个问题的关键区别,即取的物品可否重复

0/1背包

有一个承重为W的背包,N件物品,第i件物品对应的重量是weight[i],对应的价值是value[i],每件物品只能被取一次,问如何能使得背包的物品总价值最大?

遍历顺序:需要好好思考(说是先遍历物品数量,再遍历背包容量;和反过来的情况是否符合题意)

以二维的为例:

dp[i][j]表示从以[0,i]为下标的物品中任取,但每个物品只可以取一次,放到容量为j的背包里,所能达到的最大价值.要获得dp[i][j]的值可以从以下两个状态中转移过来,并取其中最大的进行转移:

  • dp[i-1][j],表示不取第i个物品,不取可能是背包容量不够,也可能是此时的最大价值更大;此时的最大价值延用dp[i-1][j]
  • dp[i-1][j-weights[i]] + value[i],表示取第i个物品,value[i]是第i个物品的价值,前面的一串则表示放入第i个物品的话,
    此时的背包(j-weight[i])的最大价值是多少,以加上物品i的价值

本质上01背包就是选和不选问题,用回溯法来处理复杂度为O(2^n)(物品数目)

经上面分析可以得到转移方程:

dp[i][j] = max(dp[i-1][j],dp[i-1][j-weights[i]] + values[i]);

关于初值设置,求最大值,若物品价值都是正数,则初值置为0;若物品价值有负数,则初值置为负无穷(根据题意设置)

关于遍历顺序,对于二维dp来说其实遍历物品先还是遍历容量先,对于一个二维的表格来说,就是行主序列主序的那个折线图,实质无影响,因为都构建出了下一步需要的数据

但为了易于理解和记忆,之后关于01背包统一先遍历物品后遍历背包容量

在考虑第i个物品的加入时,是从[0,i-1]个物品任取的情况下出发考虑的,也就是说: 第i行的数据是基于第i-1行而创建的

正因如此,所以可以把第i-1行的数据拷贝到第i行,如此的话,不如舍去i这个维度,则引出了一维的01背包dp(只是dp这个数组是一维的,实质遍历还是两层for)

以一维的为例:

dp[j],表示容量为j的背包,所能存放的最大价值

显然,它要么维持dp[j],要么则取dp[j-weights[i]] + values[i],表示为容量为j-weights[i]的背包所能获得的最大价值加上第i件物品的价值;

由此得出转移方程:dp[j] = max(dp[j],dp[j-weights[i]] + values[i]);

初值选取跟二维的一样

遍历顺序,在二维dp中,我们的背包容量是正序遍历(从小到大),但是如果这里从小到大遍历,则会存在小容量背包先更新,后面大容量背包更新时则会用到更新后的小容量背包的值,即物品被重复取了

因此它得倒序遍历,即从大到小遍历,这样大容量的背包用到的是上一个状态的小容量背包

同时两个for循环也得是先物品再容量,把一个物品正确放入后,再滑到下个物品,若是先容量再物品,则存在大容量背包会取到价值最高且能放入的一个物品,因为小容量背包的状态没有更新,所以它只会取能放入自己背包的最大价值的单个物品

模板代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
vector<int> weights = {1, 3, 4};	  // 物品对应的权重
vector<int> values = {10, 25, 30};	  // 物品对应的价值
int bagWeight = 4;					// 背包容量

int main()
{
	// 01bag problem,1-dimension
	vector<int> dp(bagWeight + 1, 0);
	for (int i = 0; i < weights.size(); i++)
	{
		for (int j = bagWeight; j >= 0; j--)
		{
			if (j >= weights[i])
				dp[j] = max(dp[j], dp[j - weights[i]] + values[i]);
		}
	}
	cout << dp[bagWeight] << endl;
	return 0;
}
完全背包

在01背包的基础上,允许重复取,也就是对于一维的01背包dp而言,正序遍历,则此时小容量的背包先更新,大容量的背包后更新,会用到更新后的小容量背包,恰好是满足无限次取(重复取),求得最大价值

它的两个for的遍历顺序则无所谓,都可以了

模板代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<int> weights = {1, 3, 4};
vector<int> values = {15, 20, 30};
int bagWeight = 4;

int main()
{
    vector<int> dp(bagWeight + 1, 0);
    for (int i = 0; i < weights.size(); i++)
    {
        for (int j = 0; j <= bagWeight; j++)
        {
            if (j >= weights[i])
                dp[j] = max(dp[j], dp[j - weights[i]] + values[i]);
        }
    }
    cout << dp[bagWeight] << endl;
    return 0;
}

package change

最长公共子序列(LCS)

典型例题:

最长递增子序列(LIS)

典型例题:

树状DP

树具有天然的递归性,树的问题可以拆分到树的左子树和树的右子树,这种天然的子问题的特性,很容易让我们代入DP的思想

  • 树的直径

    树的直径是一类DP题目(后序遍历),可以从二叉树推广到一般树

    比如你求一个树的直径(有些以边定义,有些以点定义,此处以543题为例,以边定义),其实就是求它的左子树的最大链和右子树的最大链,再加上左右子树与当前根节点的两条边,则为此根节点的直径

    向上更新的话则更新的是链,什么意思呢?就是更新这个节点所在的链的最大值,就是左子链和右子链找到一个最大的+1,向上更新即为此节点的最大链(链是用来计算直径的!)

典型例题:

状态机DP

状态机DP,即通过状态机来清晰地描述一些状态转换关系,因为这些关系可能比较多,比较复杂,用状态机可以更好地描述

这里的典型例题是股票系列的题目,可以分为无限次交易和至多k次交易两种情况:

  • 以122题为例子,它代表了无限次交易的情形
    我们可以从最后一天考虑,dfs(n-1)表示到最后一天的最大利润,它是由dfs(n-2)和到第n-1天的利润决定的,那么第n-1天的利润有买入/卖出/什么也不做,而这个买入卖出又依赖于前面的,因此需要增设1个状态用以表示现在是持有股票还是未持有股票,因此可以用状态机进行表示!见下图:

    statusDP-unlimited sell
    • dfs(i,0)表示到第i天不持有股票最大利润;
    • dfs(i,1)表示到第i天持有股票的最大利润;

    这两个状态可以什么都不做,或发生买入/卖出,得出以下的状态转移方程:

    • dfs(i,0) = max(dfs(i-1,0),dfs(i-1,1)+prices[i]); // 第i天卖出
    • dfs(i,1) = max(dfs(i-1,1),dfs(i-1,0)-prices[i]); // 第i天买入

    递归边界是i<0:

    • 若是未持有股票,则返回0;
    • 若是持有股票,则是非法的状态,返回INT_MIN

    递归入口:
    显然最后肯定不可能自己还藏一股股票,肯定卖出去利润更大,因此是dfs(n-1,0)

  • 以123,188题为例子,它代表了另一类,至多交易k次:
    需要加多一个状态用以表示至多允许进行j次交易,因此状态修改为:

    statusDP-mostlyKth sell
    • dfs(i,j,0)表示至多允许j次交易,到第i天未持有股票的最大利润;
    • dfs(i,j,1)表示至多允许j次交易,到第i天持有股票的最大利润;

    状态转移方程也跟上面的差不多,但是需要注意,因为限制了至多允许的交易次数,买入卖出算一次交易,因此我们可以在买入的时候修改交易次数:
    dfs(i,j,1) = max(dfs(i-1,j,1),dfs(i-1,j-1,0)-prices[i]);
    递归入口一致,只是增加了个维度
    递归边界多了个j<0,直接return INT_MIN即可,因为至多允许负数次交易,一听就很非法状态

需要注意,这类问题加上记忆化搜索一般维度比较多,要细细做;若是翻译成递推形式,更要注意塞入头部的状态,以及从而影响到的初始值(对应递归边界)和答案(对应递归入口)的空间开辟的大小

典型例题:

区间DP

数位DP

模板如下,此模板可以用于求方案数(这里是对着2376题写的),此类型的变形题可以在此模板上进行修改得到,详细内容见代码及注释:

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
/* 
  子问题被表示成"在第i位及其之后,在集合为mask情况下的方案数"
  
  is_limit用于标识当前第i位的上限,比如123,i=1表示第2位，如果is_limit是true则说明前1位选了1，那么你上限up就是2;否则是9.用此标志位规定每一位的选数的上限
  
  is_num用于标识前面的数据是否选了,如果没选则为false.以123为例,如果第一位和第二位都是false,则表示第三位是: _ _ ? 在这样的情况下选的话,选的值是从1开始选的.用此标志位是为了规避前导零
  
  mask是集合的体现,主要是通过位运算体现的:mask = {0,0,0,0,0,0,0,0,0,0}
  - 当0被选了,则mask={0,0,0,0,0,0,0,0,0,1},转换为二进制的形式:0000000001(b),转换成十进制:1==1<<0
  - 当9被选了,则mask={1,0,0,0,0,0,0,0,0,0},转换为二进制的形式:1000000000(b),转换成十进制:512==1<<9
  因此可以通过判断`mask>>d & 1 ==0 (d∈[0,9])`来判断某一数位是否已经在集合中了,为0则表示不在,通过`mask | 1<<d`来使得某一个数位加入集合中
*/

auto dfs = [&](auto&& dfs,int i,int mask,bool is_limit,bool is_num){
	if(i == m){	// m是题目所给数据的总位数    
		return is_num;
    }	
    
    long long  res =0;
    if(!is_num){
        res = dfs(dfs,i+1,mask,false,false);
    }
    
    int up = is_limit ? s[i] - '0' : 9;	// 当前第i位取数的上限
    for(int d = is_num ? 0 : 1; d<=up ; d++){
        if( (mask >> d & 1) == 0){
            res += dfs(dfs,i+1,mask | 1<<d, is_limit&&d==up, true);
        }
    }
    
    return res;
}

/*
这种类型的题目加上记忆化搜索的话,需要注意,并不一定所有状态都要用上,就比如这一题,它的is_limit状态其实只会走一遍,is_num即前面所选数字为空也只会走一遍,因此只需要记忆:memo[i][mask]的状态即可!
*/

典型例题:

多路归并

以丑数Ⅱ来说,所构造的丑数序列中的数,都是从2,3,5的倍数中变幻出来的,即:丑数序列:[1, 2, 3, 4, 5, 6, 8, 9, 10, 12, ...]中的数是:

  • 丑数序列中的数是2的倍数1*2,2*2,3*2,4*2,5*2,...
  • 丑数序列中的数是3的倍数1*3,2*3,3*3,4*3,5*3,...
  • 丑数序列中的数是5的倍数1*5,2*5,3*5,4*5,5*5,...

是上面这三条路径经过一定规则的归并从而获得了丑数序列,针对于这道题的规则,即是丑数序列是按照升序的规则进行排列的,因此从三条路径中取数要每次取最小的,取完了这个数,你就滑到丑数序列的下一位,继续滑到该路径的最前面,跟另外两条路经的最前面的数进行对比

这里的意思就是:比如丑数序列初始化为:[1]对于三条路径是:

  • 1*2; (这里的1是通过指向丑数序列第0位的索引得到的)
  • 1*3
  • 1*5

找出最小的放入丑数序列并滑动,则变为:[1,2]

  • 2*2(滑动到丑数序列的下一位索引1,对应丑数是2)
  • 1*3 (上次的数你不是最小的,你没滑动,保持原样)
  • 1*5

而针对于比如373题这种两个数组nums1和nums2,比如nums1是m,nums2是n,从俩数组对应的组合出m*n个数,从这里取第k个最小的,而nums1,nums2又是升序排列的,显然这些个数可以看作是m条路径,每个路径首先取自己的数(就是nums1对应的)和nums2的第0位;然后依据规则:取最小的,而后弹出最小的数,最小的数后面的数顶上来,假设当前最小的数是第i条路径产生的,则下一个数就是第i条路径的[i,1];由此取数即可

当然后面这个题目相对于丑数Ⅱ的题目而言不是固定的路径数,因此不可以通过具体的多少个指针来滑动,可以结合优先队列一起做~

综上,个人总结的多路归并是:题目所要求的结果可以通过多条路径经过一定规则的归并而获得某一个具体的序列,序列中的某个数,是题目所求的,则可以采用多路归并+优先队列的思想来做

典型例题:

dijkstra-单源最短距离

dijkstra算法是用与寻求单个源点到所有顶点的最短路径,或者说是最短耗时(因题而异,但是都是求最短的~)

这里提供一种利用优先队列来使用dj算法的模板,其中,dj算法如果只用求最短路径,就只需要

  • adjacency 邻接矩阵
  • dist 用以表示源点到所有顶点的最短距离的数组
  • pq 优先队列,一般求最短最少一类的,用的是greater<>这个比较类型,即小顶堆,一般的参数类型选用pair<int,int>,first是最短距离,second表示的是某一个结点

当需要打印出源点到某一点的最短距离所经过的点时,可以借助

  • prev 数组,用于统计每个节点的前序节点

以下是很粗糙的模板(后续看需不需要改一下):

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
// start表示起始点; n表示顶点个数; paths表示边的关系,内含<u,v>=w;
vector<int> dist(n,INT_MAX);
vector<vector<int>> adjacency(n);
for(int i=0;i<paths.size();i++){
    auto vec = paths[i];
    int u = vec[0], v = vec[1], w = vec[2];
    adjacency[u].push_back({v,w});
}
dist[start]=0;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<>> pq;
pq.push({0,start}); // 表示从start到start最短距离是0
while(!pq.empty()){
    auto [cost,u] = pq.top();
    pq.pop();
    if(cost>dist[u])
        continue;
   	while(auto& [v,w]:adjacency[u]){
        int newCost = cost + w;
        if(newCost<dist[v]){
            dist[v] = newCost;
            pq.push({newCost,v});
        }
    }
}
// 至此就得到了一个从start到所有顶点的最短路径dist数组~

网络上可能还充斥着另外一种写法,就是把优先队列替换成一个visited数组用以显示尚未处理过的节点,其实visited结合dist就是寻求尚未处理过且当前最短距离的点

而优先队列本质上就隐含这一种关系:出队的是最短距离的点,如果是处理过的点,则会看是不是最小的,因为有可能先入队的并不是最短的,后续更新时一个更短的入了队,则同时它也会更早的出队,更新邻接的点的最短距离,则处理过的点存在不一定是最短距离的情况,就是 auto [cost,node] = pq.top();pq.pop(); if(cost>dist[node]) continue;所以由于这一条件语句的设定,实际上pq寻求的也是没处理过的最短距离的点,因此visited和pq这俩二选一就好,但是用pq更方便~

典型例题:

floyd-多源最短距离

构建一个矩阵vector<vector<int>> adjacency(n,vector<int>(n,INF))(大概长这样,一开始假设都不可达,就是INF远嘛),通过已有的距离更新这个阵(就是直接相邻的点,邻接点嘛),然后利用松弛的思想,就是a->c顶点a到顶点c的距离,可能是这样最近,也可能是a->b->c,先途径顶点b再到达顶点c会更快,通过一个min即可比较出来,如何进行n个点的松弛呢

对一个二维阵操作,需要两重for,再进行n个点的松弛,显然需要套多一层循环,即三重循环可以完成

模板如下:

1
2
3
4
5
6
7
for(int k=0;k<n;k++){
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            adjacency[i][j] = min(adjacency[i][j],adjacency[i][k] + adjacency[k][j]);
        }
    }
}

典型例题

并查集

并查集它的名字指示了它的功能:支持合并(union)以及查找(find)功能的集合

集合用树来表示,许多集合即许多树构成了森林.当然如果真的整个树形结构蛮麻烦的,因此都是转成数组来处理

我们可以对这些集合中的元素进行如下操作:

  • 该元素所属的集合(即这个元素所属哪一棵树,树用其根来代表);
  • 查看两个元素是否属于一个集合(这俩元素是否是一棵树上,即根节点是否相同);
  • 合并两个集合(让其中一棵树的根节点指向另一棵树的根节点);

主要思想:通过一个数组vector<int> parent来使得数组中的元素指向它们所属树的父节点,一开始的时候各自以自己为父节点,且只有自己这个节点,此时父节点等于元素本身,即体现了它是根节点.通过:iota(parent.begin(),parent.end(),0);初始化,然后通过模板下的_union操作可以使得两棵树合并成一棵树,这时会找到某一元素的根节点,修改该元素所属父节点的指向,则此时parent[rootx]这棵树就指向了以rooty为根的树,如此操作可以使得想合并的元素给它弄到一颗树上.树的总数则可以通过遍历parent数组,利用x==parent[x]则cnt++;来统计树的总数

因为存在层数/节点数目太多导致效率变低,可以借助如vector<int> size或是vector<int> rank来处理:

  • vector<int> size(n,1);表示以i为根节点的size[i]的元素个数,更新(unite)的时候让元素少的挂在元素多的根节点上,同时把元素少的根节点的元素吃掉;
  • vector<int> rank(n,1);表示以i为根节点的rank[i]的深度,更新(unite)的时候让深度小的挂在深度大的根节点上,如果深度相等,则深度需要+1;
  • int setCount;初始化为n,表示有n个集合,合并的时候setCount自减,该变量用来表示这个并查集里的连通分量的个数;

模板如下:

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
class unionFindSet{
  private:
    int n;
    vector<int> parent;
  public:
    unionFindSet(int n):n(n),parent(vector<int>(n)){
        // 初始化,使得每个节点以自己为根节点
        iota(parent.begin(),parent.end(),0);
    }
    // 含路径压缩的find
    int find(int x){
        if(x!=parent[x]){
			parent[x] = find(parent[x]);	// 这里做了路径压缩,在查找的时候会修改元素的父节点,使得元素的父节点直接指向根节点,把树的高度尽量控制在2   
        }
        return parent[x];
    }
    //  不含路径压缩的find
    int no_compress_find(int x){
        while(x!=parent[x]){
            x = parent[x];
        }
        return parent[x];				// 这里没有做路径压缩,直接返回根节点
    }
    
    bool isConnected(int x,int y){
        return find(x) == find(y);
    }
    void unite(int x,int y){
        int rootx = find(x);
        int rooty = find(y);
        if(rootx == rooty)
           	return;
        parent[rootx] = rooty;
    } 
};

注: 路径压缩的和无路径压缩的别写混了,写混了可能出现TLE,比如路径压缩那个分支条件给弄成了while,就不对了

典型例题:

单调栈

单调栈就是具备单调性的栈即栈内元素:

  • 从栈底到栈顶呈现单调递增性的则是单调递增栈;
  • 从栈底到栈顶呈现单调递减性的则是单调递减栈;

一般求解题目,可以转换为求解下一个更大元素,则可以利用上单调栈的方法

那栈内存放的是元素的值吗?一般来说根据题目具体目的而定,但通常存放的是值对应的索引,因为索引包含的信息更多,比如可以求出下一个更大元素和本元素之间的索引差,乃至是最大宽度.

需要注意,我们这里的单调性体现在的是值上,而存在栈中的一般是索引~

而且单调栈的写法还分为从左到右以及从右到左,这里的左和右指的是遍历的顺序:

  • 从左到右,栈内的元素还没有寻求到下一个更大元素,通过在出栈时寻求到最大元素,出栈也维护了栈内的单调性;
  • 从右到左,栈内的元素是候选项,是当前索引到的元素的最大元素的候选项,通过出栈来维护栈内的单调性,通过栈内非空的判断来确定当前元素的最大元素;

经典模板:

从左到右:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/* nums是题目输入的数据,是一个vector<int>的datatpye */
stack<int> st;
int n = nums.size();
vector<int> ans(n,0);	// 初值根据题目而定
for(int i=0;i<n;i++){
    // 维持栈内单调性,并且进循环帮助栈顶元素找到下一个"更大"元素
    while(!st.empty() && 题目条件具体判断以维持栈内需要的单调性){
        int idx = st.top();
        st.pop();
        ans[idx] = ...;
    }
    /* if(...) // 某些情况下需要的条件判断 */
    st.push(i);
}

从右到左:

1
2
3
4
5
6
7
8
9
10
11
12
13
stack<int> st;
int n = nums.size();
vector<int> ans(n,0);
for(int i=n-1;i>=0;i--){
 	while(!st.empty() && 题目条件具体判断,以维持栈内需要的单调性){
        st.pop();
    }
    if(!st.empty() && /*某些情况下需要一定的题目条件*/){
        ans[i] = ...;
    }
    /* if(...) 某些情况下需要的条件判断*/
    st.push(i);
}

一些小技巧:

  • 在需要的时候,可以通过前后补0来避免一些corner case的编写,如84题

典型例题:

最小生成树(Minimal Spanning Tree)

当我们需要连接一个图中所有顶点并使得总路径开销最小时，可以使用最小生成树算法

普通的图可能会存在环，而树不会存在，所谓的生成树，就是将图中的顶点集弄成一个连通分量，像树一样，不会有环；而最小生成树，则是生成树中，代价最小的，所谓代价可以理解为权重和,即找出权重和最小的生成树

有两种算法可以用来解决此类问题,一个是prim算法,一个是kruskal算法;

prim

从点集的角度出发,要把原来属于VoldV_{old}的顶点全部移到VnewV_{new}就完成了prim算法,初始的时候VoldV_{old}就是所有的点的点集,而VnewV_{new}是个空集,这个点什么时候从VoldV_{old}移动到VnewV_{new}呢?初始化的时候随机选一个点移入VnewV_{new},然后计算VoldV_{old}中的点到VnewV_{new}的点的最短距离的向量,从其中选择到VnewV_{new}最短权重/代价最少的点进入VnewV_{new},然后更新这个距离向量,重复这个过程,直到VoldV_{old}为空;

具体做法:创建好邻接矩阵adjacency,并且初始化好距离数组vector<int> dist(n,INT_MAX);,以及一个是否访问过的标志位数组visited,还有一个vector<int> vertexNew;用以记录新集合的节点数目,由这四者通过一个二重循环去更新距离,找到最近的点,打下标记,直至新集合的节点数目为n则说明算法完成~

此算法只用过1次,模板不好总结

kruskal

从边集的角度出发,这种方法无需创建邻接矩阵,直接用vector<vector<int>>或是vector<Edge>来把所有的边信息存起来,边的信息有啥呢,就像下方结构体所示:

1
2
3
4
5
6
struct Edge{
  int x,y;
  int weight;
  Edge(){}
  Edge(int _x,int _y):x(_x),y(_y){}
};

如上所示,两个端点,一个权重/长度(曼哈顿距离/欧式距离,具体依题意而定),构成了一条边,然后对边按照weight进行升序排序,挑选两个不同源(即所属根不同,也就是不同的连通分量)的点进行unite,然后把权重累加到ans(存储权重和的变量),如此进行,借助并查集的unite功能,合并不同的连通分量,直至得到一颗最小生成树~

代码模板:

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
class UnionFindSet{
public:				
    int n;		  // 节点数目
    int setCount; //  连通分量数目
    vector<int> parent;
    vector<int> size;
    
    UnionFindSet(n):n(n),setCount(n),parent(vector<int>(n)),size(vector<int>(n,1)){
        iota(parent.begin(),parent.end(),0);
    }
    
    int find(int x){
        if(x!=parent[x])
            parent[x] = find(parent[x]);
       	return parent[x];
    }
    
    bool unite(int x1,int x2){
        int root1 = find(x1);
        int root2 = find(x2);
        if(root1==root2)
            return false;		// 同源
        if(size(root1)<size(root2)){
            swap(root1,root2);
        }
        size[root1] += size[root2];
        parent[root2] = root1;
        setCount--;				// 合并了,连通分量-1
        return true;
    }
};

struct Edge{
    int x,y,weight;
    Edge(){}
    Edge(int x,int y,int weight):x(x),y(y),weight(weight){}
}

class Solution{
   	// n是节点数目,points是其中的关系,包括(x1,x2)以及它们之间的weight
    int mst_kruskal(int n,vector<vector<int>> points){
        int m = points.size();	// 这是边数的意思
        vector<Edge> edges(m);
        // 遍历points,填充边集edges
        for(auto& p:points){
            edges.push_back({p[0],p[1],p[2]});
        }
        // 边集排序,依据权重升序排序
        sort(edges.begin(),edges.end(),[](const auto& e1,const auto& e2)->bool{
            return e1.len < e2.len;
        });
        // 初始化并查集
        UnionFindSet ufs(n);
        int minVal = 0;
        for(auto& e:edges){
            if(ufs.unite(e.x,e.y)){
                minVal+=e.len;
            }
            if(ufs.setCount==1){	// 只有一个连通分量则跳出
                break;
            }
        }
        return minVal;
    }
}

典型例题:

※ST表

ST表(Sparse Table)可以用于解决RMQ(Range Maximum/Minimum Query)问题(就是区间最大最小值查询),当你需要对区间快速的进行最大最小值查询的时候,就可以用到这个数据结构

注:ST表不修改原数组信息,只负责查询区间的最大最小值

这个数据结构的构建总共分为两个步骤:

  • 预处理 O(nlogn);
  • 查询 O(1);

在具体说之前,先说下这个算法的特色:

算法采用倍增思想:f[i][j]表示[i,i+2^j-1]这么一个区间.啥意思呢,为啥区间长这样😲?**实际上就是以i作为区间起点,区间长度为2j2^j**的意思~

  • 预处理

    • 初始化:f[i][0]=...;此时表示的区间是[i,i],也即是给第i个元素赋值,显然如果有N个元素,那么这个二维数组的首个维度就要开到N;

    • 确定边界范围: N个元素,f的第二个维度表示2j2^j,即当前区间有2j2^j个元素,即显然存在2j<=N2^j <= N,取对数就有:j<=floor(log2(N))j<=floor(log2(N))

    • 状态转移方程:(这不是DP的东东吗,实际上就是个递推的关系式)

      f[i][j] = max(f[i][j-1],f[i+2^(j-1)][j-1]) (怎么这么复杂?实际上就是把一个区间[i,i+2^j-1]分成两半(两个区间)取max).

      同时,通过状态转移方程和边界范围不难知道,我们每个起点元素i也对应不同的j,即:i+2^j-1<=N;

      那么在实施状态状态方程的时候,这个二维数组应该先遍历i还是j呢?应当先遍历j,内部遍历i,因为我们是一个一个小区间取max,这样合并到f[i][j]这样一个大区间,然后区间内部的元素再扩增(指j变化),这个过程就像是归并排序里分而治之最后一个一个小区间往上合并的过程~

  • 查询

    查询区间是[l,r];

    计算出k: k=log2(r-l+1); //这里区间是[l,r],这个k实际上用log2给它缩回去,后面用作f的第二维度来用嘛,表示一个区间的元素的个数;

    f[l][k] 和f[r-2^k+1][k],对它俩取max,即: max(f[l][k],f[r−2k+1][k])max(f[l][k],f[r-2^k+1][k]),就可以求出区间[l,r]的最大值了

注: 为啥max右边那个左端点是这个长长的式子呢?可以这样想x+2k−1=rx+2^k-1 = r,则求出的x=r+1−2kx=r+1-2^k,因为f的第一个维度是区间起始端点,计算好了这个端点,第二维度选k(表示2k2^k个元素),即可以从左端点到右端点r,中间有≤r−l+1\le r-l+1zh这么多个元素

显然这样的max的两个区间,中间是存在重叠的,但因为是求max,所以无所谓~

算法模板:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int n;	// 表示元素个数
vector<vector<int>> f(n+1,vector<int>(31,0)); // 第一个维度开元素个数这么多个,考虑有些题目的index_base是1而不是0,加多了1位,下面按照index_base=1的开始计算;
								       // 第二个维度可以用范围算出来,比如元素个数上限是10e9,则一个区间的上限就按这个来									 	  // 算,j即为31,2^31是
// 初始化
for(int i=1;i<=n;i++){
    cin >> f[i][0];
}
// 边界范围
int jRight = floor(log2(n));
// 预处理
for(int j=1;j<=jRight;j++){
    for(int i=1;i+(1<<j)-1<=n;i++){
        f[i][j] = max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
    }
}

// 查询[l,r]区间的最大值
int l,r;
cin >> l >> r;
int k = log2(r-l+1);
int mx = max(f[l][k],f[r+1-(1<<k)][k]);
return mx;

参考文件

典型例题

线段树

线段树(Segment Tree)是一种数据结构,它可以以O(logn)的时间复杂度,进行区间修改和区间查询,是一般CSP考试中末尾两题或是leetcode周赛的题目中常见的数据结构

它的本质是树,但是构建一棵树来管理也太复杂了,因此简化成利用数组来管理一棵完全二叉树,在根节点的索引为1的时候,左子树的根节点为其2倍,右子树的根节点为其2倍再加1;(有的人喜欢写成p<<1和p<<1|1,其中p是父节点的索引)

这一棵树vector<T> tree中的每一个元素代表的是一个范围内的数据的某一种信息,比如值的累和,最大最小值,众数等;具体根据题意而定

考虑到区间修改的时候,如果频繁的递归进行修改,很耗费时间的,因此有个懒惰标记,来延迟修改,这个过程被精简为一个函数:push_down()意思是下放懒惰标记,同时在区间修改的末尾,需要向上更新(父节点)区间信息,因此对称地有:push_up()函数

一棵线段树的构建过程分为:

  • 初始化+建树;
  • 区间查询;
  • 区间修改;
  • push_up()和push_down();

模板如下(提供的是区间和的,具体求区间的啥信息,根据题意灵活处理~):

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
class SegmentTree{
private:
   	int n,n4;	// n是给定的数组的元素大小,开空间要开到4倍,如果不想浪费空间可以动态开点,具体看参考文件的内容
    vector<int> tree,lazy;	// tree是线段树,里面的值代表的是一个范围的所求信息,这里是区间和;lazy是懒惰标记
    vector<int>* arr;		// 用于初始化;
    int root,end;			// root表示起始检索的下标,这里选择1,这样左右子树都2*i,2*i+1,如果选择0,则各自还要加个1
    
public:
    SegmentTree(vector<int> a){
        n = a.size();
        n4 = n<<2;
        tree = vector<int>(n4,0);
        lazy = vector<int>(n4,0);
        arr = &a;
        root =1;
        end = n-1;
        build(0,end,root);
        arr = nullptr;
    }
    
    // 建树
    void build(int s,int t,int p){
        if(s==t){	// 叶子节点,装的是数组中的确切值
            tree[p] = (*arr)[s];
            return;
        }
        int mid = s + (t-s)/2;  // 为啥不直接相加除呢,遇到越界的数据就会老实这么写了
        build(s,mid,p*2);	    // [s,mid]区间
        build(mid+1,t,p*2+1);	// [mid+1,t]区间
        push_up(p);
    }
    // 向上更新
    void push_up(int p){
        tree[p] = tree[p*2] + tree[p*2+1];
    }
    
    // 下放标记
    void push_down(int s,int t,int p){
        int mid = s + (t-s)/2;
        if(!lazy[p] && s!=t){	// s!=t是因为叶子节点没得下放,它也被人update过了
            tree[p*2] += (mid-s+1)*lazy[p];
            tree[p*2+1] += (t-mid)*lazy[p];
            lazy[2*p] += lazy[p];
            lazy[2*p+1] += lazy[p]; 
            lazy[p] = 0;
        }
    }
    
    // 区间查询 所查询的区间是[l,r] 当前p节点所对应的区间是[s,t]
    int range_query(int l,int r,int s,int t,int p){
       if(l<=s && r>=t){	// [s,t]是[l,r]的一部分,直接返回tree[p]
           return tree[p];
       } 
       // 下放懒惰标记
       push_down(s,t,p);
       int mid = s + (t-s)/2;
       int sum = 0;
       if(l<=mid){
           sum+=range_query(l,r,s,mid,p*2);
       }
       if(r>mid){
       	   sum+=range_query(l,r,mid+1,t,p*2+1);    
       }
	   return sum;
    }
    
    // 区间修改,这里是区间和的累加
    void range_add(int l,int r,int val,int s,int t,int p){
        if(l<=s && r>=t){
            tree[p] += (t-s+1)*val;	// 区间更新,求和嘛,那就是这个[s,t]区间的数都加个val
            lazy[p] += val;		    // 懒惰标记,表明它的修改还没有落实到左右子树,乃至更下方的节点
            return;
        }
        // 下放懒惰标记
        push_down(s,t,p);
        int mid = s + (t-s)/2;
        if(l<=mid){
            range_add(l,r,val,s,mid,p*2);
        }
        if(r>mid){
            range_add(l,r,val,mid+1,t,p*2+1);
        }
        // 向上更新
        push_up(p);
    }
};

注: 此类题目灵活性高,根据题意确定区间查询的值的类型,然后还可能需要附加别的算法知识进行题意处理,例题中首个题目是洛谷的模板题,但第二个题目是leetcode的题目,里面就结合了线段树和摩尔投票的算法思想来解决问题

同时,上面的模板也相对粗糙,比如你真正丢给外面的接口,应该是只有(l,r)或者(l,r,value)的接口

参考文件:

典型例题:

排序系列

堆排序

一种选择算法,不稳定(相同值的元素的相对位置可能发生改变),O(nlogn)

堆排序步骤:

  1. 构建大顶堆(升序排序)
  2. 根节点与末尾元素交换
  3. 在除去末尾元素的剩余元素中,重新下沉根节点,以构建大顶堆

重复以上步骤,直至整个序列有序

代码(给出的是小顶堆的构建,是降序):

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
void adjustDown(vector<int> &nums, int parent, int heapSize)
{
    // 左孩子节点
    int child = 2 * parent + 1;
    while (child < heapSize)
    {
        // 在两个孩子节点找最小的
        if (child + 1 < heapSize && nums[child + 1] < nums[child])
        {
            child++;
        }
        // 孩子节点中最小的那个比父节点还小,则这个更小的值要上浮到父节点
        if (nums[child] < nums[parent])
        {
            // swap(nums[child], nums[parent]);
            int tmp = nums[child];
            nums[child] = nums[parent];
            nums[parent] = tmp;
            // 检查孩子节点往下是不是满足小顶堆结构,因为值的上浮可能会破坏原有的小顶堆结构
            parent = child;
            child = 2 * parent + 1;
        }
        else
        {
            break;
        }
    }
}

void buildMinHeap(vector<int> &nums, int heapSize)
{
    // 从最后一个非叶子节点开始,直至根节点;
    for (int i = (heapSize / 2) - 1; i >= 0; i--)
    {
        adjustDown(nums, i, heapSize);
    }
}

void heapSort(vector<int> &nums)
{
    int n = nums.size();
    buildMinHeap(nums, n);
    // 交换首尾元素
    for (int i = n - 1; i > 0; i--)
    {
        // swap(nums[0], nums[i]);
        int tmp = nums[0];
        nums[0] = nums[i];
        nums[i] = tmp;
        // 上面的交换破坏了根节点的堆结构,重新构建小顶堆
        adjustDown(nums, 0, i);
    }
}

大顶堆是一棵完全二叉树,每个节点的值都大于等于其左右孩子节点的值(反之小于等于的则是小顶堆,用于降序排列)

完全二叉树第i个节点的(这里的**i是根据层序遍历得到的编号,从0开始**)左右孩子节点分别是2*i+1和2*i+2(这是它的性质)

用数组表示,即有arr[i] >= arr[2*i+1]和arr[i] >= arr[2*i+2]

也正因为完全二叉树的性质,所以整棵树可以通过简单的数组表示而非复杂的树结构

在构建堆结构的时候,我们要从最后一个非叶子节点开始,从右往左,从下往上(就是最后一个非叶子节点的编号自减1,直至根节点),对它和它的孩子节点实现交换以满足堆有序(大顶堆或小顶堆的父子节点的性质).而这个最后一个非叶子节点是通过整个数组的size除以2再减1得到(如果编号从0开始,则要-1;如果编号从1开始,则不用-1)

参考资料:图解堆排序

归并排序

核心:分治算法

稳定的O(nlogn)

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
void merge(vector<int>& nums,int left,int mid,int right){
    // 左区间的左端点,右区间的左端点
    int l = left, r = mid+1;
    int k = left;
    // 构建一个临时数组
    vector<int> tmp(right-left+1,0);
	// l不大于左区间的右端点,r不大于右区间的右端点
    while(l <= mid && r<=right){
        if(nums[l]<nums[r]){
            tmp[k++] = nums[l++];
        }else{
            tmp[k++] = nums[r++];
        }
    }
    // 对区间剩余的数值搬到tmp上去
    while(l <= mid){
        tmp[k++] = nums[l++];
    }
    while(r <= right){
        tmp[k++] = nums[r++];
    }
    
    // 把结果从临时数组搬运到nums中去
    for(int q=left; q<=right; q++){
        nums[q] = tmp[q];
    }
}
/*
: nums - 待排序数组
: left - 区间左端点
: right - 区间右端点,即整个区间是[left,right]
*/
void mergeSort(vector<int>& nums,int left,int right){
	if(left>=right)
        return;
    int mid = (left + right)/2;
    // 这里是划分区间为更小的区间
    mergeSort(nums,left,mid);
    mergeSort(nums,mid+1,right);
    // 这里是区间合并
    merge(nums,left,mid,right);
}

快速排序

核心:左右指针+分治算法

交换排序中的一种,不稳定的O(nlogn)

思想:根据选定的基准(一般是最初确定左指针后,左指针指向的值),将数据分为大于基准的放在右侧,小于基准的放在左侧,然后对左侧和右侧的列表分别重复上述步骤(此刻即分治),最后直至整个序列有序.

快速排序步骤:

  1. 确定当前的左右指针,并选择基准(注意:取得是基准的索引);
  2. 循环,先处理右指针,右指针一直自减,除非遇到小于基准的值(得>=),则暂停处理右指针,开始处理左指针;左指针一直自增,除非遇到大于(得<=,之所以=是得跳过基准,不然左指针指向的不符合的就一直是基准了)基准的值,则暂停处理左指针,此刻左右指针指向的是各自均错误的值,交换,继续循环,直至左指针不再小于右指针;
  3. 交换基准和左指针;
  4. 对未排序好的左右列表进行快排

示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// left是左指针,right是右指针+1,即整个区间是:[left,right)
void quickSort(vector<int>& nums,int left,int right){
    // 选定基准索引
    int key = left;
    // 确定左右指针
    int l = left,r=right-1;
    while(l<r){
        while(l<r && nums[r] >= nums[key])
            r--;
        while(l<r && nums[l] <= nums[key])
            l++;
        swap(nums[l],nums[r]);
    }
    // 把基准交换到属于它的位置,此刻索引<基准的是值<=它的,索引>基准的是值>=它的
    swap(nums[l],nums[key]);
    if(l > left)
        quickSort(nums,left,l); // [left,l),其中l是基准确定的位置
    if(l+1 < right)
        quickSort(nums,l+1,right); // [l+1,right)
}

shell排序

拓扑排序

拓扑排序是用于有向无环图(下称DAG)来生成一个线性序列,这个序列满足:

  • 序列中的每个顶点有且仅出现一次
  • 在图中如果存在u到v的一条路径,那么在序列中u一定出现在v之前

对于拓扑排序,经典的应用问题是AOV图(Activity Of Vertex),用于给一个活动网络进行排序,以获取其执行的序列

对于拓扑排序,此处采用的是BFS算法进行实现: 通过邻接矩阵装载图信息,并构建一个入度列表,对入度列表中入度为0的点,push进队列,然后依次执行如下步骤:

  • 出队,放入toplo数组
  • 根据邻接矩阵找到以它作为弧尾的点,对它们的入度-1
  • 若有节点入度为0,则push进队列

重复以上三个步骤,则当队列为空时,说明以拓扑排序完毕

需要注意:拓扑排序仅针对DAG图,同时也可以利用上述方法增加一些条件来检查有向图中是否有环(有环的节点,入度无法通过上述操作减为0,但队列会跳出,即意味着toplo数组中的节点数量肯定少于图中给出的节点数量,否则的话是相等的)

板子代码如下:

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
/*
    B
  /  \ 
A      D
  \  /
   C
*/
int main(){
	int vertexNum; // 顶点数
	int edgeNum;   // 边数
	// 4 4
	cin >> vertexNum >> edgeNum;
	vector<vector<int>> adjacency(vertexNum); 	// 邻接矩阵		
	vector<int> indegrees(vertexNum,0);		   // 入度列表 
	/*
	   A B
	   A C
	   B D
	   C D
	*/
	for(int i=0;i<edgeNum;i++){
		char a,b;
		cin >> a >> b;
		int A;
		int B;
		A = a - 'A';
		B = b - 'A';
		adjacency[A].push_back(B);	// 记录有向图的边信息<a,b>
		indegrees[B]++;			   // b的入度增加
	}	
	queue<int> q;
	for(int i=0;i<vertexNum;i++){  // 将入度为零的点,即源点放入队列中
		if(!indegrees[i])
			q.push(i);
	}
	vector<int> toplo;
	while(!q.empty()){			  // BFS
		int pre = q.front();
		q.pop();
		toplo.push_back(pre);
		for(int& i:adjacency[pre]){
			if(--indegrees[i] == 0)
				q.push(i);
		} 
	}
	for(int& i:toplo){
		char c = i + 65;
		cout << c << " "; 
	}
	cout << endl;
	return 0;
}

算法总结

一些数据结构回顾

二叉搜索树

二叉搜索树(BST)是二叉树的一个特别概念,可以理解为排了序的二叉树

左孩子 <= 根节点 <= 右孩子

详细可见BST,AVL,B,B+,RBT

邻接矩阵

algorithm learning

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！