拿捏AVL（C++）

文章目录

  • 前言
  • AVL树介绍
  • 模拟实现
    • 框架
    • 查找
    • 插入
    • 验证
    • 删除
    • 完整代码
  • 性能分析
  • 总结

前言

在本篇文章中我，我们将会介绍一下·有关AVL树的相关内容，并且对一些接口进行模拟实现。

AVL树介绍

为什么会有AVL树呢？？
我们在之前学习二叉树时，如果我们插入的顺序是有序或者接近有序，就会退化成单支，查找一个值的时间复杂度就是O（N）。

为了解决这个问题，因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年
发明了一种解决上述问题的方法：

插入每个节点时，保证左右子树的高度差的绝对值不超过1，从而降低高度，保证平衡。

为什么保证高度不超过1呢？？为0不是更平衡吗？？
我们的节点是一个个插入的，有些情况无法做到左右子树高度不超过1，比如只有两个节点，4个节点。

一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：
🌟 它的左右子树都是AVL树
🌟 左右子树高度之差(简称平衡因子)的绝对值不超过1

在这里插入图片描述
这里引入平衡因子并不是必须的，而只是一种实现方式，方便我们理解，我们在进行模拟实现的时候，也会采用平衡因子的方式。

如果一颗二叉搜索树是高度平衡的，就是AVL树。
如果有N个节点，高度可保持在logN,搜索时间复杂度O（logN）

模拟实现

框架

每个节点都要包含一个平衡因子，并且加入一个父亲节点，方便我们进行链接。
这是一个三叉链的结构。

template<class K,class V>
struct AVLTreeNode
{
	AVLTreeNode(const pair<K,V>kv)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		,_kv(kv)
		, _bf(0)
	{ }
	AVLTreeNode<K, V> *_left;
	AVLTreeNode<K, V>*_right;
	AVLTreeNode<K, V>*_parent;
	pair<K, V>_kv;
	int _bf;//平衡因子
};


template<class K,class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;
public:

private:
	Node* _root = nullptr;
};

查找

我们查找的逻辑和二叉树的逻辑类似，这里就不在过多叙述了。
我们这里采用的是KV结构，需要返回查找的节点。
如果找不到，就返回nullptr

	Node* Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_kv.first < key)
			{
				cur = cur->_right;
			}
			else if (cur->_kv.first > key)
			{
				cur = cur->_left;
			}
			else
			{
				return cur;
			}
		}
		return NULL;
	}

插入

我们如何进行插入呢？？？

🌟 按照搜索二叉树规则插入节点
🌟 更新平衡因子

寻找插入节点很容易解决，我们重点看一下平衡因子的更新。

我们这里规定平衡因子=右子树的高度–左子树高度

如果我们插入的节点在父节点的左边，父节点的平衡因子就减减
如果我们插入的节点在父节点的右边，父节点的平衡因子就加加

我们是否要继续向上更新呢？？
是否继续更新去接与树的高度是否发生变化，插入节点可能会影响这个节点的祖先节点

我们对父节点的平衡因子进行更新后，可能会遇到以下情况
🌟 父节点的平衡因子为0。此时说明树的高度已经平衡了，不需要继续调整。说明之前父节点的平衡因子为-1或者1，我们在矮的那边1进行了插入，这是树的高度达到平衡。

🌟 父节点的平衡因子为-1或者1。说明之前树的高度平衡，父节点的平衡因子为0。我们在一边进行插入。树的高度发生了变化，不确定是否继续影响爷爷节点，我们不能结束，需要继续判断。
cur=parent;
parent=parent->_parent

🌟 父节点的平衡因子为2或者-2，违反了我们的规则，需要进行调整，我们调整的策略就是旋转。旋转之后树的高度达到了平衡，无需继续更新。

🌟如果我们更新到了根节点也结束

bool Insert(const pair<K, V>kv)
{
	//按照二叉搜索树规则插入
	if (_root == nullptr)
	{
		_root = new Node(kv);
		return true;
	}
	Node* cur = _root;
	Node* parent = nullptr;
	while (cur)
	{
		if (cur->_kv. first> kv.first)
		{
			parent = cur;
	    	cur = cur->_left;
		}
		else if (cur->_kv.first < kv.first)
		{
			parent = cur;
			cur = cur->_right;
		}
		else
		{
			return false;
		}
	}
	cur = new Node(kv);
	cur->_parent = parent;
	if (kv.first > parent->_kv.first)
	{
		parent->_right = cur;
	}
	else
	{
		parent->_left = cur;
	}

	//更新平衡因子
	//更新规则：右子树高度--左子树高度
	
	//更新到根节点结束
	while (parent)//cur在根结束
	{
		if (cur == parent->_left)
		{
			parent->_bf--;
		}
		else
		{
			parent->_bf++;
		}
		//分三种情况
		if (parent->_bf == 0)
		{
			break;
		}
		else if (parent->_bf == 1 || parent->_bf == -1)
		{
			cur = parent;
			parent = parent->_parent;
		}
		//进行旋转
		else if (parent->_bf == 2 || parent->_bf == -2)
		{
		    //旋转
			break;
		}
	}
	return true;
}

我们进行旋转
1.保持原来搜索树规则不变
2.降低树的高度
3.由不平衡变为平衡

左旋(cur->_bf = = 1 && parent->_bf = = 2)

什么情况下我们会进行左旋呢？？
如果右子树的右边高，我们就进行左旋

在这里插入图片描述
我们为什么要画一个这样的图？？？？

我们对h进行赋值，看一下

h==0
只有一种情况
在这里插入图片描述

h==1;
我们有两个位置可以进行插入，有两种情况。
在这里插入图片描述

h==2

h==2的树有三种情况
在这里插入图片描述

我们用长方形代替了a,b，c情况中的一种
两个长方形都有三种选择，插入位置有四种选择，331*4=36。
这就有36种情况了，如果我们一个个分析，是分析不完的。

在这里插入图片描述
我们可以发现这几个例子中都有共同点
在这里插入图片描述

所以我们把它划分为一类，就如下图所示
在这里插入图片描述
我们如何进行旋转呢？？
如图所示，将30的右子树连接到60的左子树上；60的左子树连接上30，让60做这棵树的根，更新平衡因子

在这里插入图片描述

我们看看刚才将情况下的旋转
在这里插入图片描述

看一下代码实现

void RotateL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;

	//连接
	parent->_right = subRL;
	//subRL不一定存在
	if (subRL)
		subRL->_parent = parent;

	subR->_left = parent;
	//记录原来父节点的父亲，需要连接
	Node* ppnode = parent->_parent;
	parent->_parent = subR;

	//处理subR(当前根节点)
	if (parent == _root)
	{
		_root = subR;
		subR->_parent = nullptr;
	}
	else
	{
		if (parent == ppnode->_left)
		{
			ppnode->_left = subR;
		}
		else
		{
			ppnode->_right= subR;
		}
		subR->_parent = ppnode;
	}
	//更新平衡因子
	parent->_bf = 0;
	subR->_bf = 0;
}

右旋(cur->_bf = = -1 && parent->_bf == -2)

我们就直接画描述图了，不再一个个分析了
如果左子树的左边高我们需要进行右旋
在这里插入图片描述

如何进行旋转呢？？

60的右子树作为30的左子树，30这棵树作为60的右子树，更新平衡因子
在这里插入图片描述

代码实现

void RotateR(Node* parent)
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
	
	parent->_left = subLR;
	if (subLR)
		subLR->_parent = parent;
	subL->_right = parent;
	//记录parent的父亲
	Node* ppnode = parent->_parent;
	parent->_parent = subL;

	if (parent == _root)
	{
		_root = subL;
		_root->_parent = nullptr;
	}
	else
	{
		if (parent == ppnode->_left)
		{
			ppnode->_left = subL;
		}
		else
		{
			ppnode->_right = subL;
		}
		subL->_parent = ppnode;
	}
	//更新平衡因子
	subL->_bf = 0;
	parent->_bf = 0;

}

右左旋转 (cur->_bf = = -1 && parent->_bf == 2)

右子树的左边高

如果我们采用左旋的方式，不能完成要求

在这里插入图片描述

我们需要把这棵树进行拆分
在这里插入图片描述

我们会分为三种情况(我们把这一块拆开来看待了)

✨60的左边插入
90先进行右旋，30进行左旋，更新平衡因子

在这里插入图片描述

✨60的右边插入
90先进行右旋，30进行左旋，更新平衡因子
在这里插入图片描述

✨60就是插入节点
90先进行右旋，30进行左旋，更新平衡因子

在这里插入图片描述

我们这三种情况的最终的平衡因子都不相同，我们需要独立判断。
不同的根本原因就是插入位置的不同，也就是受60的影响。
在这里插入图片描述

我们不关注过程，从上帝视觉来看一下
我们把60的左子树给了30的右子树，60的右子树给了90的左子树。把60推上去做根
在这里插入图片描述

代码编写

void RotateRL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
	int usebf = subRL->_bf;
	//
	RotateR(subR);
	RotateL(parent);
	
	if (usebf == -1)
	{
		parent->_bf = 0;
		subR->_bf = 1;
		subRL->_bf = 0;
	}
	else if (usebf == 1)
	{
		parent->_bf = -1;
		subR->_bf = 0;
		subRL->_bf = 0;
	}
	else if (usebf == 0)
	{
		parent->_bf = 0;
		subR->_bf = 0;
		subRL->_bf = 0;
	}
	else
	{
		assert(false);

	}
}

左右旋转 (cur->_bf = = 1 && parent->_bf == -2)

左子树的右边高
在这里插入图片描述

我们同样会分为三种情况
✨60的左边插入
先对30进行左旋，对90进行右旋，更新平衡因子

在这里插入图片描述
✨60的右边插入
先对30进行左旋，对90进行右旋，更新平衡因子

在这里插入图片描述

✨60就是插入节点
先对30进行左旋，对90进行右旋，更新平衡因子
此情况需要更新的平衡因子都是0.

代码编写

	void RotateLR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		int usebf = subLR->_bf;
		//
		RotateL(subL);
		RotateR(parent);

		if (usebf == -1)
		{
			parent->_bf = 1;
			subL->_bf = 0;
			subLR->_bf = 0;
		}
		else if (usebf == 1)
		{
			parent->_bf = 0;
			subL->_bf = -1;
			subLR->_bf = 0;
		}
		else if (usebf == 0)
		{
			parent->_bf = 0;
			subL->_bf = 0;
			subLR->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

验证

我们如何验证这是一颗AVL树呢？？

AVL树同样具有二叉搜索树的特征，我们可以先中序遍历看看是否有序

	void Inorder()
	{
		_Inorder(_root);
	}
	
	void _Inorder(Node*root)
	{
		if (root == nullptr)
		{
			return;
		}
		_Inorder(root->_left);
		cout << root->_kv.first << " ";
		_Inorder(root->_right);
	}

但是我们仅仅通过中序遍历就能证明这是一颗AVL树吗？？？
这是句对不行的，AVL是一颗高度平衡二叉搜索树。
我们可以从高度入手，查看每一棵树高度是否满足为我们的需求。

	int Height()
	{
		return _Height(_root);
	}
	
	int _Height(Node* root)
	{
		if (root == nullptr)
		{
			return 0;
		}
		int LeftHeight = _Height(root->_left);
		int RightHeight = _Height(root->_right);
		return LeftHeight > RightHeight ? LeftHeight + 1 : RightHeight + 1;		
	}


	bool IsBalance()
	{
		return _IsBalance(_root);
	}
	
	bool _IsBalance(Node* root)
	{
		if (root == nullptr)
		{
			return true;
		}
		//左子树为真，右子树为真，根满足要求才能说明平衡
		if (_IsBalance(root->_left) == false)
		{
			return false;
		}
		if (_IsBalance(root->_right) == false)
		{
			return false;
		}
		int leftHeight = _Height(root->_left);
		int rightHeight= _Height(root->_right);
		if (abs(rightHeight - leftHeight)>2)
		{
			cout << "不平衡" << endl;
			return false;
		}
		if (rightHeight - leftHeight != root->_bf)
		{
			cout << "平衡因子异常" << endl;
			return false;
		}
		return true;
	}

我们通过验证，这个代码是没有任何问题的

我们来分析一下这段代码
以下面这棵树为例子进行分析。

我们写的是后序遍历，先判断0的左右子树，为true.
判断1时，需要重新求一下高度。
判断3时，需要重新求一下高度
判断5时，需要重新求一下高度

在这里插入图片描述

求高度就大量重复了，我们可不可以一边判断一边把高度带给上一层呢？？


	bool IsBalance()
	{
		int height = 0;
		return _IsBalance(_root,height);
	}

	bool _IsBalance(Node*root,int &height)
	{
		if (root == nullptr)
		{
			height = 0;
			return true;
		}
		int leftHeight = 0;
		int rightHeight = 0;
		//左子树
		if (_IsBalance(root->_left, leftHeight)==false)
		{
			return false;
		}
		//右子树
		if (_IsBalance(root->_right, rightHeight) == false)
		{
			return false;
		}
		//根
		if (abs(rightHeight - leftHeight) > 2)
		{
			cout << "不平衡" << endl;
		}
		if (rightHeight - leftHeight != root->_bf)
		{
			cout << "平衡因子异常" << endl;
		}
		height = leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;

		return true;
	}

我们这段代码1就通过返回值的方式，将高度带给了上一层

验证用例
🌟常规场景1
{16, 3, 7, 11, 9, 26, 18, 14, 15}
🌟特殊场景2
{4, 2, 6, 1, 3, 5, 15, 7, 16, 14}
在这里插入图片描述

删除

删除是十分复杂的，我们在这里了就简单的讲述一下，不在进行模拟实现了。

删除和插入的总体逻辑没有太大出别
🌟根据二叉搜索树删除规则，查找到需要删除的节点
🌟更改平衡因子
🌟进行旋转
有兴趣的可以参考《算法导论》或《数据结构-用面向对象方法与C++描述》殷人昆版。

完整代码

#include <assert.h>
template<class K,class V>
struct AVLTreeNode
{
	AVLTreeNode(const pair<K,V>kv)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		,_kv(kv)
		, _bf(0)
	{ }
	AVLTreeNode<K, V> *_left;
	AVLTreeNode<K, V>*_right;
	AVLTreeNode<K, V>*_parent;
	pair<K, V>_kv;
	int _bf;//平衡因子
};

template<class K,class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;
public:
	AVLTree()
		:_root(nullptr)
	{}
	bool Insert(const pair<K, V>kv)
	{
		//按照二叉搜索树规则插入
		if (_root == nullptr)
		{
			_root = new Node(kv);
			return true;
		}
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			if (cur->_kv. first> kv.first)
			{
				parent = cur;
		    	cur = cur->_left;
			}
			else if (cur->_kv.first < kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return false;
			}
		}
		cur = new Node(kv);
		cur->_parent = parent;
		if (kv.first > parent->_kv.first)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}

		//更新平衡因子
		//更新规则：右子树高度--左子树高度
		
		//更新到根节点结束
		while (parent)
		{
			if (cur == parent->_left)
			{
				parent->_bf--;
			}
			else
			{
				parent->_bf++;
			}
			//分三种情况
			if (parent->_bf == 0)
			{
				break;
			}
			else if (parent->_bf == 1 || parent->_bf == -1)
			{
				cur = parent;
				parent = parent->_parent;
			}
			//进行旋转
			else if (parent->_bf == 2 || parent->_bf == -2)
			{
				//左单旋
				if (cur->_bf == 1 && parent->_bf == 2)
				{
					RotateL(parent);
				}
				//右单旋
				else if (cur->_bf == -1 && parent->_bf == -2)
				{
					RotateR(parent);
				}
				//右左旋转
				else if (cur->_bf == -1 && parent->_bf == 2)
				{
					RotateRL(parent);
				}
				//左右旋转
				else if (cur->_bf == 1 && parent->_bf == -2)
				{
					RotateLR(parent);
				}
				else
				{
					assert(false);

				}
				//旋转之后结束
				break;
			}
		}
		return true;
	}
	void Inorder()
	{
		_Inorder(_root);
	}

	bool IsBalance()
	{
		int height = 0;
		return _IsBalance(_root,height);
	}
	Node* Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_kv.first < key)
			{
				cur = cur->_right;
			}
			else if (cur->_kv.first > key)
			{
				cur = cur->_left;
			}
			else
			{
				return cur;
			}
		}
		return NULL;
	}
	int Height()
	{
		return _Height(_root);
	}
	int Size()
	{
		return _Size(_root);
	}

private:
	int _Height(Node* root)
	{
		if (root == nullptr)
		{
			return 0;
		}
		int LeftHeight = _Height(root->_left);
		int RightHeight = _Height(root->_right);
		return LeftHeight > RightHeight ? LeftHeight + 1 : RightHeight + 1;
		
	}
	int _Size(Node* root)
	{
		if (root == nullptr)
		{
			return 0;
		}
		int LeftSize = _Size(root->_left);
		int RightSize = _Size(root->_right);
		return LeftSize + RightSize + 1;
	}

	bool _IsBalance(Node*root,int &height)
	{
		if (root == nullptr)
		{
			height = 0;
			return true;
		}
		int leftHeight = 0;
		int rightHeight = 0;
		//左子树
		if (_IsBalance(root->_left, leftHeight)==false)
		{
			return false;
		}
		//右子树
		if (_IsBalance(root->_right, rightHeight) == false)
		{
			return false;
		}
		//根
		if (abs(rightHeight - leftHeight) > 2)
		{
			cout << "不平衡" << endl;
		}
		if (rightHeight - leftHeight != root->_bf)
		{
			cout << "平衡因子异常" << endl;
		}
		height = leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;

		return true;
	}
	void _Inorder(Node*root)
	{
		if (root == nullptr)
		{
			return;
		}
		_Inorder(root->_left);
		cout << root->_kv.first << " ";
		_Inorder(root->_right);
	}


	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		//连接
		parent->_right = subRL;
		//subRL不一定存在
		if (subRL)
			subRL->_parent = parent;

		subR->_left = parent;
		//记录原来父节点的父亲，需要连接
		Node* ppnode = parent->_parent;
		parent->_parent = subR;

		//处理subR(当前根节点)
		if (parent == _root)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			if (parent == ppnode->_left)
			{
				ppnode->_left = subR;
			}
			else
			{
				ppnode->_right= subR;
			}
			subR->_parent = ppnode;
		}
		//更新平衡因子
		parent->_bf = 0;
		subR->_bf = 0;
	}

	//右单旋

	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		
		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;
		subL->_right = parent;
		//记录parent的父亲
		Node* ppnode = parent->_parent;
		parent->_parent = subL;

		if (parent == _root)
		{
			_root = subL;
			_root->_parent = nullptr;
		}
		else
		{
			if (parent == ppnode->_left)
			{
				ppnode->_left = subL;
			}
			else
			{
				ppnode->_right = subL;
			}
			subL->_parent = ppnode;
		}
		//更新平衡因子
		subL->_bf = 0;
		parent->_bf = 0;

	}

	void RotateRL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		int usebf = subRL->_bf;
		//
		RotateR(subR);
		RotateL(parent);
		
		if (usebf == -1)
		{
			parent->_bf = 0;
			subR->_bf = 1;
			subRL->_bf = 0;
		}
		else if (usebf == 1)
		{
			parent->_bf = -1;
			subR->_bf = 0;
			subRL->_bf = 0;
		}
		else if (usebf == 0)
		{
			parent->_bf = 0;
			subR->_bf = 0;
			subRL->_bf = 0;
		}
		else
		{
			assert(false);

		}
	}


	void RotateLR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		int usebf = subLR->_bf;
		//
		RotateL(subL);
		RotateR(parent);

		if (usebf == -1)
		{
			parent->_bf = 1;
			subL->_bf = 0;
			subLR->_bf = 0;
		}
		else if (usebf == 1)
		{
			parent->_bf = 0;
			subL->_bf = -1;
			subLR->_bf = 0;
		}
		else if (usebf == 0)
		{
			parent->_bf = 0;
			subL->_bf = 0;
			subLR->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}
	Node* _root = nullptr;
};

性能分析

AVL是一颗绝对平衡的二叉搜索树，要求每个节点的左右子树高度差的绝对值不超过1，这样可以保证查询时，时间复杂度为O（logN）.
如果要对AVL树做一些结构修改的操作，性能非常低下。比如：插入时要维护绝对平衡，旋转次数比较多；删除时候，可能一直要调整到根位置。
如果需要一个查询高效且有序的数据结构，数据的个数为静态的（不变），可以考虑AVL；但是一个结构要经常修改，就不太合适。

我们可以通过下面代码测试一下


void TestAVLTree2()
{
	const int N = 10000000;
	vector<int> v;
	v.reserve(N);
	srand(time(0));

	for (size_t i = 0; i < N; i++)
	{
		v.push_back(rand() + i);
		//cout << v.back() << endl;
	}

	size_t begin2 = clock();
	AVLTree<int, int> t;
	for (auto e : v)
	{
		t.Insert(make_pair(e, e));
		//cout << "Insert:" << e << "->" << t.IsBalance() << endl;
	}
	size_t end2 = clock();
	cout << "Insert:" << end2 - begin2 << endl;
	cout << t.IsBalance() << endl;
	cout << "Height:" << t.Height() << endl;
	cout << "Size:" << t.Size() << endl;

	size_t begin1 = clock();
	// 确定在的值
	for (auto e : v)
	{
		t.Find(e);
	}

	// 随机值
	//for (size_t i = 0; i < N; i++)
	//{
	//	t.Find((rand() + i));
	//}
	size_t end1 = clock();
	cout << "Find:" << end1 - begin1 << endl;
}

总结

以上就是今天要讲的内容，本文仅仅详细介绍了AVL树的一些特性，以及插入的左旋，右旋，双旋等操作，性能分析等等 。希望对大家的学习有所帮助，仅供参考 如有错误请大佬指点我会尽快去改正 欢迎大家来评论~~ 😘 😘 😘

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/671162.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

UI的学习（一）

UI的学习（一）

UI的学习(一) 文章目录 UI的学习(一)UIlabelUIButtonUIButton的两种形式UIButton的事件触发 UIView多个视图之间的关系 UIWindowUIViewController一个视图推出另一个视图 定时器和视图移动UISwitchUISlider和UIProgressSlid步进器与分栏控制器UITextFieldUIScrollView有关实现它…
阅读更多...
【Python打包成exe】

【Python打包成exe】

Python打包成exe 前言一、理论知识打底二、实操开始----pyinstaller【Base环境下】【这是一个失败案例】规规矩矩 总结 前言 先放点参考 这个字多&#xff0c;写得很详细⇨用 Pyinstaller 模块将 Python 程序打包成 exe 文件&#xff08;全网最全面最详细&#xff0c;万字详述…
阅读更多...
C语言王国——内存函数

C语言王国——内存函数

目录 1 memcpy函数 1.1 函数表达式 1.2 函数模拟 2 memmove函数 2.1 函数的表达式 2.2 函数模拟 3 memset函数 3.1 函数的表达式 3.2 函数的运用 4 memcmp函数 4.1函数的表达式&#xff1a; 4.2 函数的运用 5 结论 接上回我们讲了C语言的字符和字符串函数&#…
阅读更多...
UI案例——登陆系统

UI案例——登陆系统

UI的登陆界面实例 在学习了UILabel&#xff0c;UIButton&#xff0c;UIView&#xff0c;UITextField的内容之后&#xff0c;我们就可以写一个简单的登陆界面 我们可以通过UILabel来编写我们显示在登陆界面上的文字比方说下面这两行字就是通过UILabel去实现的。 下面给出一下实现…
阅读更多...
6.2 休息日 背包问题总结

6.2 休息日 背包问题总结

就目前所遇到的01背包与完全背包作总结。 01背包 有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]&#xff0c;得到的价值是value[i] 。每件物品只能用一次&#xff0c;求解将哪些物品装入背包里物品价值总和最大。 二维dp数组01背包 动规五部曲 1.确定…
阅读更多...
【Linux】System V 信号量

【Linux】System V 信号量

一、信号量的概念理论渗透 1.1 基本概念 共享资源&#xff1a;多个执行流&#xff0c;可以看到的一份资源临界资源&#xff1a;被保护起来的资源 —— 保护的方式&#xff1a;同步和互斥互斥&#xff1a;任何时候只能有一个进程在访问共享资源资源&#xff0c;一定要被程序员…
阅读更多...
LeetCode刷题之HOT100之搜索旋转排序数组

LeetCode刷题之HOT100之搜索旋转排序数组

2024/6/2 雨一直下&#xff0c;一个上午都在床上趴着看完了《百年孤独》&#xff0c;撑伞去吃了个饭&#xff0c;又回到了宿舍。打开许久未开的老电脑&#xff0c;准备做题了。《百年孤独》讲了什么&#xff0c;想表达什么&#xff0c;想给读者留下什么&#xff0c;我不知道&am…
阅读更多...
每日一题《leetcode-- LCR 025.两数相加||》

每日一题《leetcode-- LCR 025.两数相加||》

https://leetcode.cn/problems/lMSNwu/ 分别把给定的两个链表翻转&#xff0c;然后从头开始相加。 /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/ //反转链表 struct ListNode* reverselist(struct ListNode*h…
阅读更多...
项目中统一异常处理

项目中统一异常处理

项目中统一异常处理 1.异常处理框架图2.实现 1.异常处理框架图 异常处理除了输出在日志中&#xff0c;还需要提示给用户&#xff0c;前端和后端需要作一些约定&#xff1a; 错误提示信息统一以json格式返回给前端。以HTTP状态码决定当前是否出错&#xff0c;非200为操作异常。…
阅读更多...
基于51单片机数控直流数控电源的设计

基于51单片机数控直流数控电源的设计

电源技术尤其是数控电源技术是一门实践性很强的工程技术，服务于各行各业。当今电源技术融合了电气、电子、系统集成、控制理论、材料等诸多学科领域。直流稳压电源是电子技术常用的仪器设备之一，广泛的应用于教学、科研等领域，是电子实验员、电子设计人员及电路开发部门进行…
阅读更多...
Win10 Edge提示兼容性问题打不开|解决浏览器兼容性问题

Win10 Edge提示兼容性问题打不开|解决浏览器兼容性问题

Edge有时候会与某些安全软件不兼容&#xff0c;导致报错 报错代码&#xff1a;STATUS_INVALID_IMAGE_HASH 解决Edge浏览器兼容性问题方法/步骤&#xff1a; 1、按 Win R 组合键&#xff0c;打开运行&#xff0c;并输入 regedit 命令&#xff0c;确定或回车&#xff0c;可以…
阅读更多...
大语言模型实战——最小化模型评测

大语言模型实战——最小化模型评测

1. 引言 现在国内外的主流模型&#xff0c;在新模型发布时都会给出很多评测数据&#xff0c;用以说明当前模型在不同数据集上的测评表现&#xff08;如下面llama3发布的评测数据&#xff09;。 这些评测数据是如何给出来的呢&#xff1f;这篇文章会用一个最小化的流程来还原下…
阅读更多...
【Android】手动下载gradle插件包，解决gradle插件包下载不全问题。

【Android】手动下载gradle插件包，解决gradle插件包下载不全问题。

问题描述 拉取别人的项目时&#xff0c;因为网络问题gradle插件包一直下载不全&#xff0c;一直build。 解决方案&#xff1a; 打开gradle>wrapper文件下gradle-wrapper.properties&#xff0c;查看需要下载gradle-7.2-bin.zip。 distributionBaseGRADLE_USER_HOME distr…
阅读更多...
kafka 发送文件二进制流及使用header发送附属信息

kafka 发送文件二进制流及使用header发送附属信息

文章目录 背景案例发送方接收方 背景 需要使用kafka发送文件二进制以及附属信息 案例 发送方 import org.apache.kafka.clients.producer.KafkaProducer; import org.apache.kafka.clients.producer.ProducerRecord;import java.io.InputStream; import java.nio.charset.S…
阅读更多...
Part 4.1 线性动态规划

Part 4.1 线性动态规划

线性动态规划&#xff0c;即具有线性阶段划分的动态规划。 [USACO1.5] [IOI1994]数字三角形 Number Triangles 题目描述 观察下面的数字金字塔。 写一个程序来查找从最高点到底部任意处结束的路径&#xff0c;使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右…
阅读更多...
统计信号处理基础 习题解答10-6

统计信号处理基础 习题解答10-6

题目 在例10.1中&#xff0c;把数据模型修正为&#xff1a; 其中是WGN&#xff0c;如果&#xff0c;那么方差&#xff0c;如果&#xff0c;那么方差。求PDF 。把它与经典情况PDF 进行比较&#xff0c;在经典的情况下A是确定性的&#xff0c;是WGN&#xff0c;它的方差为&#…
阅读更多...
数据库(17)——DCL数据控制语言

数据库(17)——DCL数据控制语言

DCL DCL是Data Control Language数据控制语言&#xff0c;用来管理数据库用户、控制数据库的访问权限。 DCL-管理用户 语法 1.查询用户 USE mysql; SELECT * FROM user; 也可以直接在datagrip找到user表 我们要操作用户要通过User和Host同时定位。Host表示当前用户只能在哪个…
阅读更多...
【深度学习实战—9】：基于MediaPipe的坐姿检测

【深度学习实战—9】：基于MediaPipe的坐姿检测

✨博客主页&#xff1a;王乐予&#x1f388; ✨年轻人要&#xff1a;Living for the moment&#xff08;活在当下&#xff09;&#xff01;&#x1f4aa; &#x1f3c6;推荐专栏&#xff1a;【图像处理】【千锤百炼Python】【深度学习】【排序算法】 目录 &#x1f63a;一、Med…
阅读更多...
前端Vue自定义滚动卡片组件设计与实现

前端Vue自定义滚动卡片组件设计与实现

摘要 随着技术的日新月异&#xff0c;前端开发的复杂度不断提升。传统的整块应用开发方式在面对小的改动或功能增加时&#xff0c;常常需要修改大量的整体逻辑&#xff0c;造成开发效率低下和维护成本高昂。为了应对这一挑战&#xff0c;组件化开发应运而生。本文将以Vue框架下…
阅读更多...
Day46 动态规划part06

Day46 动态规划part06

完全背包问题 完全背包和01背包问题唯一不同的地方就是&#xff0c;每种物品有无限件。先遍历物品还是先遍历背包以及遍历顺序 根据递推公式可知&#xff1a;每一个dp需要根据上方和左方的数据推出&#xff0c;只要保证数据左上方数据是递推出来的这种两个for循环的顺序就是可…
阅读更多...
最新文章

Copyright @ 2022~2023