首页 > 编程语言 >部分算法总结

部分算法总结

时间：2023-10-21 11:12:06浏览次数：37  
标签：总结 结点 int next 链表 算法 数组 部分 节点

小部分算法总结

部分题目请见：
https://github.com/ZhangFirst1/Algorithm-problem-code

异或运算

a^= b相当于a=a^b，将十进制数字转化为二进制进行运算，相同为0，相异为1，0和任何数异或运算都是原来的那个数。

可以用来判断数组中哪个数字只出现过一次 （通过将所有数与0进行异或运算）

快慢指针

  1. 单链表中可任意用来寻找“中点”，快指针（fast）每一步走两个结点，慢指针（slow）每一步走一个结点。当快指针到达链表末尾时，慢指针应该指向链表最中间的结点.如果是单数恰好为中间，如果是双数则是中间的第二个节点
  2. 在查找链表倒数第k个节点时，可以通过先让fast先走k步，再与slow同时运动，让两个指针保持一个距离，当fast到达结尾时，那么slow的位置就是倒数第k的位置。
  3. 对于环形链表，把快慢指针想象成一个追及问题，当两个指针重合时，就代表链表中有环

动态规划

例题一：最大子数组和

image-20220822161641662

例题二: 买股票的最佳时机

动态转移方程：dp[i]=min{dp[i-1],prices[i]}, dp[i]这个数组存着i位置前最小的价格

例题三：[分割数组以求得最大和](1043. 分隔数组以得到最大和 - 力扣（LeetCode）)

无后效性：每一个子问题只求解一次，以后求解问题的过程不会修改以前求解的子问题的结果

背包问题（动态规划）

0/1背包： (物品只能选一次)

f[i][j] = max(f[i][j],f[i-1][j-v[i]]+w[i]);//二维

//滚动数组优化，当前行f[i]的状态只与上一行有关，所以可以用一维数组优化
//如果是从小到大,前一行的状态会被新一行的状态覆盖掉,这样使用前面已经求出来的状态就会出错
for(int j = m; j >= v[i]; j--)    //从大到小的重量
            f[j] = max(f[j], f[j - v[i]] + w[i]);//一维

完全背包:(物品可以选无数次)

f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i])//二维转移方程

//从小到大可以满足一件物品不止选一次,物品不选则是前一行的状态，选该物品，则是同一行前面的状态再加上当前的价值
for(int j = v[i] ; j<=m ;j++)//注意了，这里的j是从小到大枚举，和01背包不一样
    {
            f[j] = max(f[j],f[j-v[i]]+w[i]);//一维
    }

分组背包(同组的物品只能选一个)：

和01背包类似，但是最外层的循环是组的数量，对每个组中的物品都讨论选或不选的价值，取最大值

需要三层循环：第一层i循环组的数量，第二层j循环背包的容量，第三层k逐个判断每组物品的价值取最大值

for(int i=1;i<=Max;i++){
		for(int j=m;j>=0;j--){
			for(int k=1;k<=s[i];k++){
				if(j>=w[index[i][k]]){//index存的是第i组第k个数在原始数组中的下标，从而获得该物品的大小和价值
                    dp[j]=max(dp[j],dp[j-w[index[i][k]]]+v[index[i][k]]);
                }
			}
		}
		
	}

获得环形链表相交的节点

  1. 利用快慢指针求解：获得fast和slow相遇的节点meetNode
  2. 利用一个结论：两个节点，一个从头结点head出发，一个从meetNode节点出发，两个节点速度相同，最后会在环形链表的相交节点处（入环的第一个节点）相遇。
ListNode* fast=head,*slow=head;//定义快慢指针
 while(fast&&fast->next){
    fast=fast->next->next;
    slow=slow->next;
    if(slow==fast){
       ListNode* meetNode=fast;//获得快慢指针相遇的节点
       while(meetNode!=head){//利用结论获得相交的节点处（入环的第一个节点）
           meetNode=meetNode->next;
           head=head->next;
         }
        return meetNode;
    }
 }

以下是手写证明：

![img](file:///D:\QQ\1826203343\Image\C2C\E331194655F113A5D88003F3C6DB446C.jpg)

复制带随机指针的链表

复制带随机指针的链表_leetcode

  1. 先将新拷贝的结点链接在原来结点的后边

  2. 通过原链表来改变拷贝链表的随机指针 (最关键的一步)

    copyNode->random=cur->random->next;//cur是原链表的结点，copyNode是拷贝的结点

  3. 将拷贝链表和原链表还原

串的模式匹配

  1. BF算法(暴力算法)

  2. KMP算法

    ​ 求next的算法(关键代码):

int* GetNext(string t) {
	int len = t.size();//获得模式串的长度
    int* next = new int[len];//开辟一段数组 
	int index = 0;//表示数组下标,每一次循环要求的是next[index+1]中的值
	int j = -1;//表示next数组中的值
	next[0] = -1;//next[0]赋初值
	while (index < len) {
		if (j == -1 || t[index] == t[j]) {
			j++;
			index++;
			next[index] = j;
		}
		else {
			j = next[j];
		}
	}
	return next;
} 

//KMP算法测试
int main() {
	string sstring;
	string t;
	getline(cin, sstring);//原串
	getline(cin, t);//模块串
	int i = 0,j=0,slen,tlen,*next;
	slen = sstring.size();//获得原串的长度
	tlen = t.size();//模块串的长度
	next=GetNext(t);//获得next数组
	while (i < slen && j < tlen) {
		while ((sstring[i] == t[j]) && (j < tlen)) {
			i++;
			j++;
		}
		if (j==tlen) {
			cout << "已经找到字串，位置为" << i - j << endl;
			break;
		}
		else {
			if (next[j] == -1) {//表示已经到达模块串的第一位，需要将原串的指针移动到下一位
				j=0;
				i++;
			}
			else {
				j = next[j];
			}
		}


	}
	return 0;
}

Huffman算法(哈夫曼算法)

通过生成哈夫曼树(最优二叉树)来进行哈夫曼编码

  1. 将有权值的叶子结点按照从小到大的顺序排列

  2. 取两个最小权值得结点作为新结点得左右孩子，小的为左孩子，大的为右孩子

  3. 将新结点加入有序排列，继续重复步骤二

Huffman编码的平均编码长度计算：

先通过哈夫曼算法构造出最优二叉树后，判断每一个字符的编码长度，最后将编码长度乘以每个字符出现的概率求和

​

高精度加法

  1. 因为输入的数大于long long了，所以就用string先存着；

  2. 将string里存的数逆序存入数字数组，这样模拟手工从右往左计算过程。

  3. 循环（长的那个数组有多少个数，就循环多少次），两数相加，如果数>10，那就保留各位，十位加到下一个数中。

  4. 因为数逆序存入所以要逆序输出。

    string s1,s2;
int a[250],b[250],c[500];
 
int main()
{
	cin>>s1>>s2;
	
	for(int i=0;i<s1.size();i++)  //将s1字符串逆序存入数组a,将s2字符串逆序存入数组b
	{
		a[s1.size()-i-1]=s1[i]-'0';  
	}
	
	for(int i=0;i<s2.size();i++)
	{
		b[s2.size()-i-1]=s2[i]-'0';
	}
	
	int len=s1.size();
	if(s2.size()>len)
	{
		len=s2.size();
	}
	
	for(int i=0;i<len;i++)
	{
		c[i]=a[i]+b[i];
	}
	
	for(int i=0;i<len;i++)   //对进位进行处理
	{
		if(c[i]>=10) c[i+1]=c[i+1]+c[i]/10;
		c[i]=c[i]%10;
	}
	
	if(c[len]!=0) len++;    .//如果最高位有进位，那么c[len]还会有值
	
	for(int i=len-1;i>=0;i--)
	{
		cout<<c[i];
	}
	cout<<endl;
	return 0;
}

st表(Sparse Table，稀疏表）

st表是一种数据结构，主要用于解决RMQ（区间最大值或最小值） 例如：给你一个数列，求解在一个范围内的数值的最大值或最小值。

主要利用了倍增的思想和动态规划的思想。

  1. 动态规划的预处理（以2为倍数增加长度）

    img

    //由上图得，将要求得一个区间分为两个区间
//f[j][i]存的是从 j 到 j+2^i-1 范围内的 最大值 ，中间包含2^i个数

for(int i=1;i<=log2(n);i++){    // <<是移位运算符，1<<i相当于2^i
		for(int j=1;j+(1<<i)-1<=n;j++){
			f[j][i]=max(f[j][i-1],f[j+(1<<(i-1))][i-1]); 
            												}
	}

  2. 进行区间查询

    img

    找到一个值s，使得l+2 ^ s-1，尽可能接近r，r-2 ^ s+1尽可能接近l，两个区间的长度都是2 ^ s

    最后比较两个区间的最大值，取较大的那个

    max(f[l][s],f[r-(1<<s)+1][s]);

归并排序 稳定排序

时间复杂度O(nlogn) 空间复杂度O(n)

就是给定两个有序数组，将两个数组合并在一起升序。

定义一个更大的数组，给定两个指针分别指向两个数组，每次取较小值放入新数组。

//1.分离函数
void mergesort(int x,int y)			//分离，x 和 y 分别代表要分离数列的开头和结尾
{
	if (x>=y) return;        //如果开头 ≥ 结尾，那么就说明数列分完了，分的只有一个数了，就返回
	int mid=(x+y)/2;            //将中间数求出来，用中间数把数列分成两段
	mergesort(x,mid);			//左右两端继续分离
	mergesort(mid+1,y);        
	merge(x,mid,y);        //分离玩之后就合并,升序排序，从最小段开始
}

//2.合并算法

void merge(int low,int mid,int high) //将两段的数据合并成一段，每一段数据都已经升序排序
{
	int i=low,j=mid+1,k=low;
    //i、j 分别标记第一和第二个数列的当前位置，k 是标记当前要放到整体的哪一个位置
	while (i<=mid && j<=high)    //如果两个数列的数都没放完，循环
	{
		if (a[i]<a[j])
			b[k++]=a[i++];     //a[n](原始数组)和b[n](临时存数据的数组)为全局函数
		else
			b[k++]=a[j++];   //将a[i] 和 a[j] 中小的那个放入 b[k]，然后将相应的标记变量增加
	}        // b[k++]=a[i++] 和 b[k++]=a[j++] 是先赋值，再增加
	while (i<=mid)
		b[k++]=a[i++];
	while (j<=high)
		b[k++]=a[j++];    //当有一个数列放完了，就将另一个数列剩下的数按顺序放好
	for (int i=low;i<=high;i++)
		a[i]=b[i];                //将 b 数组里的东西放入 a 数组，因为 b 数组还可能要继续使用
}

快速排序 不稳定排序

最差时间复杂度O(n^2) 和冒泡排序一样，平均时间复杂度O(n*log2n)

递归算法：

void sort(int* a,int l,int r){
	if(l>r)return;
	int i=l,j=r;
	int std=a[l]; //最左端作为标准值  因为标准值是最左端的数，所以要先从右边开始找
	while(i!=j){
		while(a[j]>=std&&i<j){//从右往左 找到比标准小的数 
			j--;             
		}
	
		while(a[i]<=std&&i<j){//从左往右 找到比标准大的数 
			i++;
		}
		if(j>i){  //交换找到的两个值
			int t=a[i];
			a[i]=a[j];
			a[j]=t;
		}
	}
	//退出循环表示i==j,将标准值换到i=j的地方，继续递归运行
	a[l]=a[i];   
	a[i]=std;
	sort(a,l,i-1);
	sort(a,i+1,r);
}

快速选择查找 (基于快速排序)

可以用来查找第k小(大)的数，在快速排序每一轮确定基准值位置的时候判断是否是要选择的数

平均时间复杂度为O(n)，最坏时间复杂度为O(n^2)

//快速选择排序算法
int quickChoose(int left,int right,int k){
	if(left>right)return -1;
	int i=left,j=right;
	int std=num[left];
	while(i!=j){
		while(i<j&&num[j]>=std)j--;
		while(i<j&&num[i]<=std)i++;
		if(i<j){
			int t=num[i];
			num[i]=num[j];
			num[j]=t;
		}
	}
	num[0]=num[j];
	num[j]=std;
	if(k-1>j)quickChoose(j+1,right,k);//表示要查找的数在基准值位置的右边
	if(k-1<j)quickChoose(left,j-1,k);//在基准值的左边
	if(k-1==j)return num[k-1];//返回第k小(大)的值
}

桶排序

不基于比较的排序算法

通过统计值域内每个数据的个数，然后根据个数排序

int count[1002];//存放数的个数 这里数的值域是[0,1000]
void bucketSort(int n){
    //统计每个数据的个数
	for(int i=0;i<n;i++){
		count[num[i]]++;
	}
	int cnt=0;
    //值域为[0,1000]
	for(int i=0;i<=1000;i++){
		while(count[i]!=0){
			num[cnt++]=i;//将数填回原数组
			count[i]--;
		}
	}
}

堆排序(升序) 不稳定排序

时间复杂度 O(nlogn)

空间复杂度 O(1)

//对某个根节点调整为大根堆
//从上往下进行调整
void adjust_down(int *a,int n,int i){//i是需要调整的根节点的下标
	int father=i;
	int child=i*2+1;
	while(child<n){
        //比较孩子结点的大小，选出较大的那个
		if((child+1)<=n-1&&a[child]<=a[child+1]) ++child;
        //交换父节点和孩子结点，并顺着孩子结点向下继续调整
		if(a[father]<a[child]){
			int temp;
			temp=a[child];
			a[child]=a[father];
			a[father]=temp;
			father=child;
			child=father*2+1;
		}else{
            //一旦不能继续调整就退出循环
			break;
		}
	}
	
}


void heap_sort(int *a,int n){
	//建立大根堆
    //(n-1)/2为从后往前，第一个有孩子的结点
	for(int i=(n-1)/2;i>=0;i--){
		adjust_down(a,n,i);
	} 
	//摘取大顶,与最后一个结点交换 
	for(int i=0;i<n-1;i++){
		int temp=a[0];
		a[0]=a[n-i-1];
		a[n-i-1]=temp;
		adjust_down(a,n-i-1,0);
	} 
}

并查集

一种树形的数据结构

主要构成 pre[]数组、find()、join()

作用：求图的连通分支数

//pre数组初始化
void Init(int n){
    //每个结点的祖先都是自己
    for(int i=0;i<n;i++){
        pre[i]=i;
    }
}

//pre[x]中存放的是x结点的父节点
//find()函数找到某个结点的根，结点的祖先
int find(int x)					//查找某个结点的父节点
{								
	while(pre[x] != x)			
		x = pre[x];				
	return x;					
}

find()函数优化：路径压缩。就是将所有结点的父节点都改为根结点，这样子查找某个结点的父节点只需要向上查找一次

int find(int x)     				//查找结点 x的根结点 
{
    if(pre[x] == x) return x;		//递归出口：x的上级为 x本身，即 x为根结点        
    return pre[x] = find(pre[x]);	//此代码相当于先找到根结点 rootx，然后pre[x]=rootx 
}

//将两个集合合并
void join(int x,int y)
{
    //找到各自的父节点
   	int fx=find(x);
    int fy=find(y);
    //将fy和fx其中任意一个作为根
    if(fy!=fx) 
        pre[fy]=fx;
}

Kruskal算法--最小生成树

//并查集中的查找父节点函数
int find(int x){
	if(pre[x] == x) return x;
	return pre[x]=find(pre[x]);//路径压缩
} 
struct edge{
	int u;
	int v;
	int w;
};
edge a[M];//定义边的数组
//n是结点的个数，m是边的个数
int kruskal(int n,int m){
	int cnt=0;//统计加入生成树的边的条数
	for(int i=1;i<=m;i++){
		//找到边的两个端点的父节点，判断是否会形成环 
		int father1=find(a[i].u);//find()函数，找到该节点对应的父节点(和哪些点连通)  具体见并查集
		int father2=find(a[i].v);
        //如果两个父节点相同，表示加入这条边会在图中形成环
		if(father1==father2){
			continue;
		}else{
            //表示可以加入图    
			pre[father1]=father2;//将两个结点的父节点相连(并查集中的合并操作)
			ans+=a[i].w;//ans统计最小生成树的权值和
			cnt++;
			if(cnt==n-1)break;
		}
	}
    //输出最小生成树的长度和
	if(cnt==n-1){
		cout<<ans;
	}else{
		cout<<"orz";//表示不是连通图，不能构成生成树
	}
	
}

//测试函数
#include<iostream>
#include<algorithm>
using namespace std;
const int N=5100;
const int M=200050;
int pre[N];//并查集
int ans; //统计最小生成树的长度和
bool compareEdge(edge a1,edge a2){//伪函数 
	return a1.w<a2.w;//升序 
}
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>e[i].u>>e[i].v>>e[i].w; 
	} 
	sort(e+1,e+m+1,compareEdge);//排序
	//初始化pre数组
	for(int i=1;i<=n;i++){
		pre[i]=i;
	} 
	kruscal(n,m);
	return 0;
}

红黑树

特征：

1.根节点是黑色的

2.红色结点和黑色结点交替

3.任意节点到叶子结点的路径包含相同数目的黑色结点 (红黑树中的叶子结点是指最外部的空结点)

多重邻接表(存储无向图)

image-20230214104351092

十字链表(存储有向图)

image-20230214104512747

AOV网(解决拓扑排序问题)---活动赋予顶点

方式：每次选出入度为0的结点

用邻接矩阵 时间复杂度 O(o^2)

用邻接表 时间复杂度 O(n+e)

哈希表平均查找长度

成功时：ASL=(所有元素查找成功的比较次数)/元素的个数

哈希函数为 H(key)=key mod p （p一般来说是一个质数，除留余数法）

不成功时：ASL=(0到p-1向后查找直到遇到空的比较次数)/p (不是除以数组本身大小)

全排列问题

深度优先搜索思想DFS :

int arrange[N];//存全排列的数组 
int exist[N];//判断是否存在 
void createArrange(int k,int n){//k是数组的位置，n是数的个数
	if(k>n){
		showArrange(n);//如果k>n表示所有数组位置都已经赋值，一次全排列情况结束，打印数组
		return;
	}else{
		for(int i=1;i<=n;i++){
			if(!exist[i]){
				arrange[k]=i;//如果有没有被填入数组的数，就填入，然后标记已经选过
				exist[i]=1;
				createArrange(k+1,n);//进入递归
				exist[i]=0;//当递归退出表示一次全排列结束，会返回上一层递归的位置，执行下面的语句,将当前的数标为
                				//还没有选过
				arrange[k]=0;
			}
		}
	}
}

标签：总结,结点,int,next,链表,算法,数组,部分,节点
From： https://www.cnblogs.com/zhangfirst1/p/17778648.html

相关文章

  • 10.21算法
    颠倒二进制位颠倒给定的32位无符号整数的二进制位。提示：请注意，在某些语言（如Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。在Java中，编译器使用二......
  • 前端常见问题总结（正在更新中）
    开发中我所遇到的前端问题1、按钮问题2、追加元素的问题3、AJAX发送的数据是数组或者对象时，会报错4、浮点数精度问题（7*0.8会等于5.6000000000000005）5、区分JS中的undefined,null,"",0和false5、误用ajax的complete1、按钮问题（1）、没有准确定位到按钮的选择器（这就不便多说，都知......
  • 1.基础知识(6) --Matlab 函数使用总结
    ✅作者简介：热爱科研的算法开发者，Python、Matlab项目可交流、沟通、学习。......
  • MySql Json字段部分查询语法
    模糊匹配jsonObject字段select*fromtableNamewherecolumnName->'$.xx'like'%xx%'精确匹配jsonObject类型字段select*fromtableNamewherecolumnName->'$.xx'='xx'模糊匹配jsonArray字段select*fromtableNamewh......
  • 常见密码学算法简介
    1.常见对称加解密算法对称加密算法是一种加密算法，使用相同的密钥来加密和解密数据。这些算法在保护数据安全性方面起着重要作用。下面是一些常用的对称加密算法的介绍：1.1AdvancedEncryptionStandard(AES)简介：AES是一种高级加密标准，用于保护敏感数据。它使用128、192或......
  • 智慧矿山AI算法极速解决皮带问题！
    近年来，随着智能技术的迅速发展与应用，智慧矿山逐渐成为提高生产能力和安全性的重要手段。其中，皮带运输系统作为矿山生产过程中的关键环节，其运行状态的准确判定和及时预警对矿山的安全和效率至关重要。为了实现对皮带运行状态的准确识别，智慧矿山AI算法应运而生。为什么需要皮带运行状......
  • 文心一言 VS 讯飞星火 VS chatgpt （117）-- 算法导论10.3 2题
    二、用go语言，对一组同构对象用单数组表示法实现，写出过程ALLOCATE-OBJECT和FREE-OBJECT。文心一言：在Go语言中，我们通常使用指针和结构体来表示和操作复杂的数据结构。对于一组同构对象，我们可以使用一个数组来存储它们的指针，每个指针指向一个对象。下面是使用Go语言实现ALLOCATE-OBJEC......
  • 文心一言 VS 讯飞星火 VS chatgpt （117）-- 算法导论10.3 2题
    二、用go语言，对一组同构对象用单数组表示法实现，写出过程ALLOCATE-OBJECT和FREE-OBJECT。文心一言：在Go语言中，我们通常使用指针和结构体来表示和操作复杂的数据结构。对于一组同构对象，我们可以使用一个数组来存储它们的指针，每个指针指向一个对象。下面是使用Go语言实现ALLOCATE-OB......
  • MVCC总结
    MVCC机制是什么MVCC，即**Multi-VersionConcurrencyControl**（多版本并发控制）。它是一种并发控制的方法，一般在数据库管理系统中，实现对数据库的并发访问，在编程语言中实现事务内存。个人理解MySQL的InnoDB存储引擎支持事务。事务的四大特性：A原子性、C一致性、I隔离性、D......
  • JAVA项目中的常用的异常处理情况总结
    在Java项目开发中，异常处理是至关重要的一部分。良好的异常处理能够提高程序的稳定性和可靠性，使得程序在面对意外情况时能够有所作为，而不至于因为一些小错误而导致整个系统崩溃。以下是Java项目中常见的异常处理情况及其处理方法的详细总结：1.空指针异常（NullPointerException）空指......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99