2024-09-03

数据结构

单调栈

特点

单调表示从起点开始单调，遇到破坏单调性的元素时，会去掉栈内的元素来保持单调。以单增栈为例，如果处理了原数组 1 到 n 号元素，那么栈内第一个元素必然是 1 到 n 之间最小的元素，第二个元素必然是 1 到 n 之间第二小的元素，但是无法保证栈的长度等于 n

例题

1、海报

问题描述

N 个矩形房子拍成一排，高度分别是 hi用海报盖住它们，海报所盖之处不能是天空，最少用几张海报？

代码逻辑

先假设答案为 N，如果两个房子同高，且它们之间的房子都比它们高，那么答案就可以减 1

核心代码

cin>>N>>h;
s.push(h);
for(int i=2;i<=N;i++)
   {
       cin>>h;
       while( !s.empty() && h < s.top() )
           s.pop();
       if( !s.empty() && s.top()==h )
           ans--;
      	s.push(h);
   }

单调队列

特点

单调表示从起点开始单调，遇到破坏单调性的元素时，会去掉队列内的元素来保持单调。以单增队列为例，如果处理了原数组 1 到 n 号元素，那么队列内第一个元素必然是 1 到 n 之间最小的元素，第二个元素必然是 1 到 n 之间第二小的元素，但是无法保证队列的长度等于 n

例题

1、k 区间最大极值差

题目描述

有 N 个数字，Fi表示区间[max(1,i-k),i]之间的最大值与最小值的差，求 Fi的最大值

代码逻辑

维护一个单增队列和一个单减队列求极值差
由于 1-2、1-3….1-k 的最大极值差必然是 1-k 的极值差，求出原数组 1-k 之间的极值差，以代表 i<=k 时的答案
i>k 时，每次将 k 区间右移一位，最左边的元素被移出，在队列中删去它

核心代码

#include<deque>
........
    //先处理1-k区间的极值差
    for(int i=1;i<=n;i++)
    {
        while( !dq1.empty() && data[i]<dq1.back() )
            dq1.pop_back();
        dq1.push_back(data[i]);
    }
	for(int i=1;i<=n;i++)
    {
        while( !dq2.empty() && data[i]>dq2.back() )
            dq2.pop_back();
       	dq2.push_back(data[i]);
    }
	ans = dq2.front() - dq1.front();
	//处理后面的k区间
	for(int i=k+1;i<=n-k+1;i++)
    {
     	while( !dq1.empty() && data[i]<dq1.back() )
            dq1.pop_back();
       	dq1.push_back(data[i]);

        while( !dq2.empty() && data[i]>dq2.back() )
            dq2.pop_back();
       	dq2.push_bac(data[i]);
        //处理被移出去的元素
        if(dq1.front()==data[i-k])
            dq1.pop_front();
        if(dq2.front()==data[i-k])
            dq2.pop_front();
        ans = max(ans,dq2.front()-dq1.front());
    }

Map

概述

c++的 map 库中提供了数据类型 map，实现键值对的映射
map 会自动按照 first 第一，second 其次的优先级来排序

例题

1、点赞日志

问题描述

有 N 条点赞记录，每条记录包含被点赞内容的编号 id 和点赞时间 ts，如果存在 T，使得[T,T+D)之间 id 被赞的次数大于 k，那么就输出 id

代码逻辑

用键值对< id,vector<int> >记录数据即可

核心代码

map< string, vector<int> > mp;
for(int i=1;i<=N;i++)
   {
       cin>>id>>ts;
       mp[id].push(ts);
   }
for(auto ver : mp)
   {
    	vector<int> temp = mp.second;
       if(temp.size()<k)
           continue;
       sort(temp.begin(),temp.end());
       //枚举点赞记录时间起点，如果可以找到大于等于k条满足条件的点赞记录，就输出id
       for(int i=0;i<=temp.size()-k+1;i++)
       {
           int ans = 1;
           for(int j=i+1;j<=i+k;j++)
           {
               if(temp[j]-temp[i]<D)
                   ans++;
           }
           if(ans>=k)
           {
               cout<<ver.first<<'\n';
               break;
           }
       }
   }

并查集

概述

将祖先结点相同的结点放入同一个集合

路径压缩算法

如果每次找结点的祖先结点都一个个父节点向上回溯，就多做了很多次不必要的操作
路径压缩算法每回溯一次都把结点的父结点赋值为父结点的父结点，这样下次调用的时候就不用再做已经做过的回溯

代码示例

int FindRoot(int index)
   {
       return root[index]==index ? index : ( root[index] = FindRoot(root[index]) );
   }

例题

1、奶酪

问题描述

奶酪高度 h，有 n 个半径 r 的洞(坐标 xi,yi)，上表面视作高度 h，下表面视作高度 0，是否存在一条路径贯穿上下表面

代码逻辑

枚举与上下表面联通的洞，如果能找到一对洞分别与上表面和下表面联通且它们有公共祖先结点，那么输出”YES”，否则输出”NO”

核心代码

for(int i=1;i<=n;i++)
   {
   	cin>>x>>y;
       if(is_up())
        	up.push_back(x,y);
      	else if(is_down())
           down.push_back(x,y);
       all[i] = {x,y};
       for(int j=1;j<i;j++)
       {
           if(connected())
           {
               root1 = FindRoot(i), root2 = FindRoot(j);
               if(root1!=root2)
            //直接修改祖先结点的祖先结点，表示两个并查集的合并
                   root[root1] = root[root2];
           }
       }
   }

2、关押犯人

问题描述

两个监狱关押 N 个犯人，有 M 对仇恨值，仇恨对象在同一监狱就会爆发等同于仇恨值的冲突，合理放置犯人使最大的冲突值最小

代码逻辑

仇恨值从大到小排列，优先规避大仇恨值，第一个无法规避的仇恨值就是实际爆发的冲突中的最大值，由于可能的更大值已经被规避，所以实际的最大冲突值就是最大冲突值的最小值
规避仇恨的方法就是把仇恨的对象的所有敌人都放入同一个监狱，也就是同一个集合

核心代码

struct node
{
    //表示仇恨对象和仇恨值
    int x,y,c;
}data[maxn];
int enemy[maxn]; //表示犯人的第一个仇人
..................
    sort(data,data+m,[](node n1,node n2){return n1.c > n2.c;});
	for(int i=1;i<=m;i++)
    {
        if( FindRoot(data[i].x) == FindRoot(data[i].y) ) //找到第一对无法避免的冲突
        {
            cout<<data[i].c;
            break;
        }

        if(enemy[data[i].x]==0) //输入第一个敌人
            enemy[data[i].x] = data[i].y;
        else  //已经有第一个敌人
            root[FindRoot(enemy[data[i].x])] = root[FindRoot(data[i].y)];

        if(enemy[data[i].y]==0)
            enemy[data[i].y] = data[i].x;
        else
            root[FindRoot(enemy[data[i].y])] = root[FindRoot(data[i].x)];
    }

ST 表

概述

ST 表可以实现离线查询区间最值的功能

代码逻辑

ST 表把区间划分为长度为 2 的幂次的子区间，stij表示原数组从 i 到 i+$$2^j-1$$的最值
求任意区间最值时，只需把区间划分为两个长度为 2 的幂次的子区间，查 st 表得最值
任意区间划分原则：长度对半分，断点 k=$$log_2{(R-L+1)}$$

核心代码_生成 ST 表

for(int j=1;j<=maxj;j++)  //区间长度为2^j,区间长度大的st值由更小的区间得到
   {
       for(int i=n;i>=1;i--)  //区间起点为i，起点小的st值需要依赖起点大的st值获得
           st[i][j] = max( st[i][j-1], st[i+(1<<(j-1))][j-1] );
   }

核心代码_任意区间查值

int query(int L,int R)
   {
       int k = log(R-L+1) / log(2);
       //确保区间被划分为两个长为2^k的区间，所以后一个区间的左端点不是L+(1<<k)
       //又为了确保后一个区间的左端点小于等于前一个区间的右端点，计算求得k的值log(R-L+1) / log(2)
       return max(st[L][k],st[R-(1<<k)+1][k]);
   }

树状数组

概述

树状数组是对原数组更快速的管理方式，普通树状数组可用于单点修改和区间查询，如果引入差分数组就可以实现区间修改、单点查询、区间和查询，这里所有的修改和查询都指对原数组的操作。
普通树状数组是管理原数组的工具
差分树状数组是管理差分数组从而管理原数组的工具
树状数组大小和原数组一样

前置知识

lowbit(x)：x 二进制表示中最低位 1 代表的数字，lowbit(x) = x&(~x+1)
差分数组：差分数组 data_diffi = datai-data~~i-1~~

代码逻辑

树状数组中下标为 x 的节点的父节点为下标为 x+lowbit(x)的节点
每一个节点存的数据是本身数据以及本身的子节点数据的和
求原数组下标 1-x 的和是从树状数组下标为 x 的节点开始加，每次下标减去 lowbit(x)

核心代码_创建树状数组/单点修改

//创建树状数组的过程相当于做单点修改,原数组下标为i的值从0修改为输入的data[i]
	void add(int index,int value)
	{
		for(int i=index;i<=n;i+=lowbit(i)) //回溯每一个父节点
			data_tree[i] += value;
	}

核心代码_区间和查询

int query(int L,int R)
   {
       int ans = 0;
     	for(int i=R;i>=1;i-=lowbit(i))
           ans += data_tree[i];
       if(L==1)
           return ans;
      	for(int i=L-1;i>=1;i-=lowbit(i))
           ans -= data_tree[i];
      	return ans;
   }

核心代码_差分数组创建树状数组/单点修改

//创建树状数组的过程相当于做单点修改,原数组下标为i的值从0修改为输入的data[i]
	for(int i=1;i<=n;i++)
    {
        cin>>data[i];
        for(int j=i;j<=n;j+=lowbit(j))
            data_tree[j] = data[i] - data[i-1];
    }

核心代码_差分树状数组单点查询

//查询的是差分数组的1-index的和，也就是原数组的单点值
	int query(int index)
    {
        int ans = 0;
      	for(int i=index;i>=1;i-=lowbit(i))
            ans += data_tree[i];
       	return ans;
    }

核心代码_差分树状数组区间修改

//原数组在区间改值，相当于差分数组在left处+k，在right+1处-k，反映到树状数组就是做两次单点修改
	void change(int left,int right,int k)
    {
        for(int i=left;i<=n;i+=lowbit(i))
            data_tree[i] += k;
        for(int i=right+1;i<=n;i+=lowbit(i))
            data_tree[i] = -k;
    }

求和线段树

概述

求和线段树可完成区间修改（加法和乘法）和区间和查询的功能，需要的空间是原数组的 4 倍

代码逻辑

pos 表示树上结点，low-hight 表示 pos 结点树控制的原数组的位置
利用 tag 数组延迟完成改值操作，减少修改操作的次数，tag 的值只有 pos 的子结点才会用到
x、y、k 是输入的参数，分别表示操作的区间[x,y]以及操作数 k
每次调用 add 或者 mul 时，最终终止的地方，其父结点全都会被及时处理，其子结点会延迟处理，而每一次调用 add、mul、query 都是从 pos=1 开始的，所以 tree[1]的值总是正确的。如果一进 query 就返回了，那么输出的结果是 tree[pos]，不然就会先 pushdown 把子结点的值修改正确再调用 query 查询子结点，因此查询值总是正确的。

核心代码_建树

void build(int pos, int low , int hight)  //递归建树
{
	if(low == hight)
	{
		tree[pos] = data[low];
		return ;
	}
	int mid = low + ( (hight - low) >> 1);
	build(pos<<1, low, mid);
	build( (pos<<1)+1, mid+1, hight);
	tree[pos] = tree[pos<<1] + tree[(pos<<1)+1];
}

核心代码_向下传标记（tag）

void pushdown(int pos, int low, int hight)  //向下改值
{
	int mid = low + ( ( hight - low) >> 1 );
	//修改子结点的值,乘法优先
	tree[pos<<1] =  tree[pos<<1] * tag_mul[pos]  + ( mid - low + 1 ) * tag_add[pos];
	tree[(pos<<1)+1] =  tree[(pos<<1)+1] * tag_mul[pos] + ( hight - mid ) * tag_add[pos];
	//修改子结点的tag,乘法优先
	tag_mul[pos<<1] = tag_mul[pos<<1] * tag_mul[pos];
	tag_mul[(pos<<1)+1] = tag_mul[(pos<<1)+1] * tag_mul[pos];
	tag_add[pos<<1] = tag_add[pos<<1] * tag_mul[pos] + tag_add[pos];
	tag_add[(pos<<1)+1] = tag_add[(pos<<1)+1] * tag_mul[pos] + tag_add[pos];
	//复原当下结点的tag
	tag_mul[pos] = 1;
	tag_add[pos] = 0;
}

核心代码_区间改值（加法）

void add(int pos, int low, int hight)
{
	if(x<=low && y>=hight) //这个结点控制的区间已经被完全覆盖
	{
		//修改当下位置树的值并设置tag
		tree[pos] = tree[pos] +  ( hight - low + 1) * k;
		tag_add[pos] = tag_add[pos] + k;
		return ;
	}
	pushdown(pos, low, hight); //递归结束后做回溯的时候及时传递tag标记
	int mid = low +  ( ( hight - low ) >> 1 );
	//如果左右子结点控制的区间有被影响到，那么就对它们调用add函数
	if(x<=mid)
		add(pos<<1, low, mid);
	if(y>=mid+1)
		add( (pos<<1)+1, mid+1, hight);
	//改完左右结点后，给当下结点重新赋值
	tree[pos] = tree[pos<<1] + tree[(pos<<1)+1];
}

核心代码_区间改值（乘法）

void mul(int pos, int low, int hight)
{
	if(x<=low && y>=hight)
	{
		tree[pos] = tree[pos] * k;
		tag_mul[pos] = tag_mul[pos] * k;
		tag_add[pos] = tag_add[pos] * k; //注意：做乘法操作的时候会影响前面遗留的加法
		return	;
	}
	pushdown(pos, low, hight);
	int mid = low + ( ( hight - low ) >> 1 );
	if(x<=mid)
		mul( pos<<1, low, mid);
	if(y>=mid+1)
		mul( (pos<<1)+1, mid+1, hight);
	tree[pos] = tree[pos<<1] + tree[(pos<<1)+1];
}

核心代码_区间和查询

int query(int pos, int low, int hight)
{
	if(x<=low && y>=hight)
		return tree[pos];
	pushdown(pos,low,hight);
	int ans = 0, mid = low + ( ( hight - low ) >> 1 );
	if(x<=mid)
		ans += query(pos<<1, low, mid);
	if(y>=mid+1)
		ans += query( (pos<<1)+1, mid+1, hight );
	return ans;
}

字典树

概述

字典树对前缀进行复用，查找时可以省时间

代码逻辑

二维数组存三个信息，第一维存起始结点，数据存终止结点，第二维存这两个结点之间的值

例题

1、字符串前缀

问题描述

有 n 个文本串和 m 个模式串，求出各匹配串在文本串的前缀中出现的次数

核心代码_插入字符串

void Insert(string s)
   {
       int x = 1;  //从字典树起点开始
      	for(int i=0;i<s.length();i++)
       {
           if(!trie[x][s[i]-'a'])
               trie[x][s[i]-'a'] = ind++; //字典树数组的栈顶指针
           x = trie[x][s[i]-'a'];
       }
   }

核心代码_查询字符串

bool check(string s)
   {
       int x = 1;
       for(int i=0;i<s.length();i++)
       {
           x = trie[x][s[i]-'a'];
           if(x==0) //匹配到某个字符时，字典树中无对应的边，说明失配
               break;
       }
       return x;
   }

2、异或最大值

问题描述

有 n 个数字，可以任意两两组合做异或，求出可得的最大值

代码逻辑

对每个数字，找到和它和其他数字异或的最大结果，再利用各自的最大值求得总最大值即可
字典树寻找异或结果最大值：利用二进制编码构造 01 字典树，利用贪心思想，每一步都选择和自己对应数位相反的结点
字典树建立：为了统一，所有 int 数都看成 31 位二进制，只忽略了符号位的 0

核心代码_建树

void Insert(int data)
   {
       int x = 1;
       for(int j=30;j>=0;j--)
       {
    		if(!trie[x][ (data>>j)&1 ])
               trie[x][ (data>>j)&1 ] = ind++; //字典树数组的栈顶指针
          	x = trie[x][ (data>>j)&1 ]
       }
       val[x] = data;  //十进制值与字典树终点建立映射关系，方便查询
   }

核心代码_寻找异或最大值

int maxEXOR(int data)
   {
       int x = 1;
       for(int j=30;j>=0;j--)
       {
           //优先选择和自己对应数位数字不同的路径
           if(trie[x][ !( (data>>j)&1 ) ])
               x = trie[x][ !( (data>>j)&1 ) ];
           else
               x = trie[x][ (data>>j)&1 ];
       }
       return data ^ val[x];
   }