C++【STL】改造红黑树简单模拟实现set map（带你了解set map的底层实现结构）

目录

一、学前铺垫（泛型编程）

二、改造红黑树

1.红黑树节点的改造

2.insert的改造

3.迭代器的实现

4.完整改造代码

三、set的模拟实现封装

四、map的模拟实现封装

五、完结撒❀

前言：

下面为了简单模拟实现set map所出现的代码是以C++中STL源码库中的代码逻辑基础进行的简化代码，本片博客目的是带你简单深入底层，了解set map底层的实现逻辑，对泛型编程有更加深刻的认识。

一、学前铺垫（泛型编程）

本篇博客我们通过对一个红黑树进行改造，使其可以让set和map的模拟实现都使用这一个红黑树结构，因为set map所存储的数据类型不一样,set底层存储的是pair<key,key>,map底层存储的是pair<key,value>,所以这里就一定会用上多个模板对红黑树进行改造，形成泛型编程，之后再对set map使用改造后的红黑树进行封装，达到模拟STL库中set map的效果。（有能力的可以直接去看STL中set map所实现的源码，逻辑与我所讲述的相同）

二、改造红黑树

1.红黑树节点的改造

这里节点的构造基本与二叉搜索树的节点构造相同，但是因为要同时兼顾set map两中类型，所以存储数据的类型不可以写死，要用到模板，节点代码如下：

template <class T>
struct RBTreeNode
{
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;

	Color _col;
	T _data;

	RBTreeNode(const T& data)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _data(data)
		, _col(RED)
	{}
};

2.insert的改造

需要改造的地方：

1) 根据STL库中的set和map的insert的功能，插入成功返回插入位置所在的迭代器以及true，插入失败说明树中已存在改值，返回该值所在的位置的迭代器以及false，所以返回类型应为pair<iterator,bool>，所以返回类型需要进行改造。

2) 在insert中大小值的比较，因为要兼容set和map，而在set中的模板类型只需要一个就可以进行初始化，因为set中底层数据类型是一样的，而map不同，map底层类型其实是pair<key,pair<key,value>>实现，因为在实现find函数时需要用到key的值并且与set保持一致，所以将value类型定义为pair<key,value>，那么在后续的比较大小中就不能那么随意了，因为set直接拿其节点指向的_data进行比较即可，而map中的_data为pair<key,pair<key,value>>,不可以直接拿来进行比较,所以我们将代码进行改造。

下面是模拟实现set，map的简单封装。SetKeyOFT，MapKeyOFT就是解决大小比较所定义的内部类。
Mymap.h:

template <class K,class V>
class map
{
public:

	struct MapKeyOFT
	{
		const K& operator()(const pair<K, V>& kv)
		{
			return kv.first;
		}
	};
private:
	RBTree<K, pair<K,V>, MapKeyOFT> _t;
};

Myset.h:

template <class K>
class set
{
public:
	struct SetKeyOFT
	{
		const K& operator()(const K& key)
		{
			return key;
		}
	};
private:
	RBTree<K,K, SetKeyOFT> _t;
};

insert函数改造实现：

	pair<iterator,bool> Insert(const T& data)
	{
		//二叉树为空，插入第一个值
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_col = BLACK;
			return make_pair(iterator(_root),true);
		}

		KeyOfT kot;
		//后续插入
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (kot(cur->_data) > kot(data))
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (kot(cur->_data) < kot(data))
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				//不允许冗余
				return make_pair(iterator(cur),false);
			}
		}

		//找到对应位置
		cur = new Node(data);
		cur->_parent = parent;
		
		Node* newcur = cur;

		if (kot(parent->_data) > kot(data))
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}

		//父亲的颜色是黑色也就结束
		while (parent && parent->_col == RED)//红黑树出现错误需要改正
		{
			Node* grandfather = parent->_parent;
			if (grandfather->_left == parent)
			{
				//舅子树在右边
				Node* uncle = grandfather->_right;
				if (uncle && uncle->_col == RED)
				{
					//存在且颜色为红
					parent->_col = BLACK;
					uncle->_col = BLACK;
					/*if (grandfather == _root)
					{
						grandfather->_col = BLACK;
					}
					else
					{
						grandfather->_col = RED;
					}*/

					grandfather->_col = RED;

					cur = grandfather;
					parent = grandfather->_parent;
				}
				else
				{
					//舅子树不存在或颜色为黑
					if (parent->_left == cur)
					{
						//单旋
						parent->_col = BLACK;
						grandfather->_col = RED;
						RNode(grandfather);
					}
					else
					{
						//双旋 先左再右
						LNode(parent);
						cur->_col = BLACK;
						grandfather->_col = RED;
						RNode(grandfather);
					}
					break;
				}
			}
			else
			{
				//舅子树在左边
				Node* uncle = grandfather->_left;
				if (uncle && uncle->_col == RED)
				{
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfather->_col = RED;

					cur = grandfather;
					parent = grandfather->_parent;
				}
				else
				{
					if (parent->_right == cur)
					{
						//单旋
						parent->_col = BLACK;
						grandfather->_col = RED;
						LNode(grandfather);
					}
					else
					{
						//双旋
						RNode(parent);
						LNode(grandfather);
						grandfather->_col = RED;
						cur->_col = BLACK;
					}
					break;
				}
			}
		}

		_root->_col = BLACK;

		return make_pair(iterator(newcur),true);
	}

因为只在红黑树insert函数里面使用的都是模板，所以是不知道所传数据的具体类型，但是在模拟实现的set，map中知道其对应的类型，所以我们可以在set，map类里面定义一个类，在这个类里面定义一个仿函数用于提取所对应比较大小的值，再将这个类用模板参数传递给红黑树中，在需要比较大小时提前用这个类定义一个变量，在通过仿函数进行大小的比较，这样就可以实现set，map的兼容。

3.迭代器的实现

迭代器的好处是可以方便遍历，是数据结构的底层实现与用户透明。如果想要给红黑树增加迭代
器，需要考虑以前问题：
● begin() 与 end()
STL 明确规定， begin() 与 end() 代表的是一段前闭后开的区间，而对红黑树进行中序遍历后，
可以得到一个有序的序列，因此： begin() 可以放在红黑树中最小节点 ( 即最左侧节点 ) 的位
置 ， end() 放在最大节点 ( 最右侧节点 ) 的下一个位置 ，关键是最大节点的下一个位置在哪块？
能否给成 nullptr 呢？答案是行不通的，因为 对 end() 位置的迭代器进行 -- 操作，必须要能找最
后一个元素 ，此处就不行，因此最好的方式是 将 end() 放在头结点的位置 ：

● operator++()与operator--()

// 找迭代器的下一个节点，下一个节点肯定比其大
void Increasement()
{
	//分两种情况讨论:_pNode的右子树存在和不存在
	// 右子树存在
	if (_pNode->_pRight)
	{
		// 右子树中最小的节点，即右子树中最左侧节点
		_pNode = _pNode->_pRight;
		while (_pNode->_pLeft)
			_pNode = _pNode->_pLeft;
	}
	else
	{
		// 右子树不存在，向上查找，直到_pNode != pParent->right
		PNode pParent = _pNode->_pParent;
		while (pParent->_pRight == _pNode)
		{
			_pNode = pParent;
			pParent = _pNode->_pParent;
		}
		// 特殊情况：根节点没有右子树
		if (_pNode->_pRight != pParent)
			_pNode = pParent;
	}
}
// 获取迭代器指向节点的前一个节点
void Decreasement()
{
	//分三种情况讨论：_pNode 在head的位置，_pNode 左子树存在，_pNode 左子树不
	存在
		// 1. _pNode 在head的位置，--应该将_pNode放在红黑树中最大节点的位置
		if (_pNode->_pParent->_pParent == _pNode && _pNode->_color == RED)
			_pNode = _pNode->_pRight;
		else if (_pNode->_pLeft)
		{
			// 2. _pNode的左子树存在,在左子树中找最大的节点，即左子树中最右侧节点
			_pNode = _pNode->_pLeft;
			while (_pNode->_pRight)
				_pNode = _pNode->_pRight;
		}
		else
		{
			// _pNode的左子树不存在，只能向上找
			PNode pParent = _pNode->_pParent;
			while (_pNode == pParent->_pLeft)
			{
				_pNode = pParent;
				pParent = _pNode->_pParent;
			}
			_pNode = pParent;
		}
}

4.完整改造代码

#pragma once
#include <iostream>
using namespace::std;

enum Color
{
	RED,//(0)
	BLACK//(1)
};

template <class T>
struct RBTreeNode
{
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;

	Color _col;
	T _data;

	RBTreeNode(const T& data)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _data(data)
		, _col(RED)
	{}
};

template <class T,class Ref,class Ptr>
struct __RBTreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef __RBTreeIterator<T, Ref, Ptr> Self;

	Node* _node;

	__RBTreeIterator(Node* node)
		:_node(node)
	{}

	Ref operator*()
	{
		return _node->_data;
	}

	Ptr operator->()
	{
		return &_node->_data;
	}

	bool operator!=(const Self& s)
	{
		return _node != s._node;
	}

	Self& operator--()
	{
		if (_node->_left)
		{
			//存在左子树
			Node* cur = _node->_left;
			while (cur->_right)
			{
				cur = cur->_right;
			}
			_node = cur;
		}
		else
		{
			//不存在左子树
			Node* parent = _node->_parent;
			if (parent && parent->_left == _node)
			{
				//为父亲的左孩子
				while (parent && parent->_left == _node)
				{
					_node = parent;
					parent = parent->_parent;
				}
				_node = parent;
			}
			else
			{
				//为父亲的右孩子
				_node = parent;
			}
		}

		return *this;
	}

	Self& operator++()
	{
		if (_node->_right)
		{
			//存在右子树
			_node = _node->_right;
			while (_node && _node->_left)
			{
				_node = _node->_left;
			}
		}
		else
		{
			//不存在右子树
			Node* parent = _node->_parent;
			while (parent && _node == parent->_right)
			{
				_node = parent;
				parent = parent->_parent;
			}
			_node = parent;
		}
		return *this;
	}
};

template <class K, class T, class KeyOfT>
class RBTree
{
	typedef RBTreeNode<T> Node;
public:
	typedef __RBTreeIterator<T, T&, T*> iterator;
	typedef __RBTreeIterator<T,const T&,const T*> const_iterator;

	RBTree() = default;//强制编译器生成构造函数

	//拷贝构造
	RBTree(RBTree<K, const T, KeyOfT>& t)
	{
		_root = copy(t._root);
	}

	iterator begin()
	{
		Node* LeftMin = _root;
		while (LeftMin && LeftMin->_left)
		{
			LeftMin = LeftMin->_left;
		}
		return iterator(LeftMin);
	}

	iterator end()
	{
		return iterator(_root->_parent);
	}
	
	const_iterator begin() const
	{
		Node* LeftMin = _root;
		while (LeftMin && LeftMin->_left)
		{
			LeftMin = LeftMin->_left;
		}
		return const_iterator(LeftMin);
	}

	const_iterator end() const
	{
		return const_iterator(nullptr);
	}

	//右单旋，满足二叉树引发右单旋之后平衡因子一定为0
	void RNode(Node* parent)
	{
		Node* pparent = parent->_parent;

		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;

		subL->_right = parent;
		parent->_parent = subL;

		if (pparent)
		{
			subL->_parent = pparent;

			if (pparent->_left == parent)
			{
				pparent->_left = subL;
			}
			else
			{
				pparent->_right = subL;
			}
		}
		else
		{
			_root = subL;
			subL->_parent = nullptr;
		}
	}

	//左单旋
	void LNode(Node* parent)
	{
		Node* pparent = parent->_parent;

		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		parent->_right = subRL;
		if (subRL)
			subRL->_parent = parent;

		subR->_left = parent;
		parent->_parent = subR;

		if (pparent)
		{
			subR->_parent = pparent;

			if (pparent->_left == parent)
			{
				pparent->_left = subR;
			}
			else
			{
				pparent->_right = subR;
			}
		}
		else
		{
			_root = subR;
			subR->_parent = nullptr;
		}
	}

	pair<iterator,bool> Insert(const T& data)
	{
		//二叉树为空，插入第一个值
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_col = BLACK;
			return make_pair(iterator(_root),true);
		}

		KeyOfT kot;
		//后续插入
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (kot(cur->_data) > kot(data))
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (kot(cur->_data) < kot(data))
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				//不允许冗余
				return make_pair(iterator(cur),false);
			}
		}

		//找到对应位置
		cur = new Node(data);
		cur->_parent = parent;
		
		Node* newcur = cur;

		if (kot(parent->_data) > kot(data))
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}

		//父亲的颜色是黑色也就结束
		while (parent && parent->_col == RED)//红黑树出现错误需要改正
		{
			Node* grandfather = parent->_parent;
			if (grandfather->_left == parent)
			{
				//舅子树在右边
				Node* uncle = grandfather->_right;
				if (uncle && uncle->_col == RED)
				{
					//存在且颜色为红
					parent->_col = BLACK;
					uncle->_col = BLACK;

					grandfather->_col = RED;

					cur = grandfather;
					parent = grandfather->_parent;
				}
				else
				{
					//舅子树不存在或颜色为黑
					if (parent->_left == cur)
					{
						//单旋
						parent->_col = BLACK;
						grandfather->_col = RED;
						RNode(grandfather);
					}
					else
					{
						//双旋 先左再右
						LNode(parent);
						cur->_col = BLACK;
						grandfather->_col = RED;
						RNode(grandfather);
					}
					break;
				}
			}
			else
			{
				//舅子树在左边
				Node* uncle = grandfather->_left;
				if (uncle && uncle->_col == RED)
				{
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfather->_col = RED;

					cur = grandfather;
					parent = grandfather->_parent;
				}
				else
				{
					if (parent->_right == cur)
					{
						//单旋
						parent->_col = BLACK;
						grandfather->_col = RED;
						LNode(grandfather);
					}
					else
					{
						//双旋
						RNode(parent);
						LNode(grandfather);
						grandfather->_col = RED;
						cur->_col = BLACK;
					}
					break;
				}
			}
		}

		_root->_col = BLACK;

		return make_pair(iterator(newcur),true);
	}

	bool IsRBTree()
	{
		if (_root->_col == RED)
		{
			cout << "根节点为红节点" << endl;
			return false;
		}

		int DefNum = 0;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_col == BLACK)
			{
				DefNum++;
			}

			cur = cur->_left;
		}

		return _Check(_root, 0, DefNum);
	}

	~RBTree()
	{
		Destory(_root); 
		_root = nullptr;
	}

private:
	Node* copy(const Node* root)
	{
		if (root == nullptr)
		{
			return nullptr;
		}

		Node* newnode = new Node(root->_data);
		newnode->_col = root->_col;

		newnode->_left = copy(root->_left);
		if(newnode->_left)
			newnode->_left->_parent = newnode;
		newnode->_right = copy(root->_right);
		if (newnode->_left)
			newnode->_left->_parent = newnode;

		return newnode;
	}

	void Destory(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}

		Destory(root->_left);
		Destory(root->_right);

		delete root;
		root = nullptr;
	}

	bool _Check(Node* root, int BlackNum, int DefNum)
	{
		if (root == nullptr)
		{
			if (BlackNum != DefNum)
			{
				cout << BlackNum << "|" << DefNum << endl;
				cout << "存在黑色节点数量不相等的路径" << endl;
				return false;
			}
			return true;
		}

		if (root->_col == RED && root->_parent->_col == RED)
		{
			cout << root->_kv.first << "->存在连续的两个红节点" << endl;
			return false;
		}

		if (root->_col == BLACK)
		{
			BlackNum++;
		}

		return _Check(root->_left, BlackNum, DefNum)
			&& _Check(root->_right, BlackNum, DefNum);
	}


	Node* _root = nullptr;

};

三、set的模拟实现封装

set 的底层为红黑树，因此只需在 set 内部封装一棵红黑树，即可将该容器实现出来 ( 具体实现可参
考 map) 。 
template <class K>
class set
{
public:
	struct SetKeyOFT
	{
		const K& operator()(const K& key)
		{
			return key;
		}
	};

	typedef typename RBTree<K, K, SetKeyOFT>::iterator iterator;
	typedef typename RBTree<K, const K, SetKeyOFT>::iterator const_iterator;

	pair<iterator,bool> insert(const K& key)
	{ 
		return _t.Insert(key);
	}

	iterator begin()
	{
		return _t.begin();
	}

	iterator end()
	{
		return _t.end();
	}

	const_iterator begin() const
	{
		return _t.begin();
	}

	const_iterator end() const
	{
		return _t.end();
	}

private:
	RBTree<K, const K, SetKeyOFT> _t;
};

四、map的模拟实现封装

template <class K,class V>
class map
{
public:

	struct MapKeyOFT
	{
		const K& operator()(const pair<K, V>& kv)
		{
			return kv.first;
		}
	};

	typedef typename RBTree<K, pair<const K, V>, MapKeyOFT>::iterator iterator;
	typedef typename RBTree<K, pair<const K, V>, MapKeyOFT>::iterator const_iterator;

	V& operator[](const K& key)
	{
		pair<iterator,bool> ret = _t.Insert(make_pair(key,V()));
		return ret.first->second;
	}

	pair<iterator,bool> insert(const pair<K,V>& kv)
	{
		return _t.Insert(kv);
	}

	iterator begin()
	{
		return _t.begin();
	}

	iterator end()
	{
		return _t.end();
	}
	
	const_iterator begin() const
	{
		return _t.begin();
	}

	const_iterator end() const
	{
		return _t.end();
	}

private:
	RBTree<K, pair<const K,V>, MapKeyOFT> _t;
};

五、完结撒❀

如果以上内容对你有帮助不妨点赞支持一下，以后还会分享更多编程知识，我们一起进步。
最后我想讲的是，据说点赞的都能找到漂亮女朋友❤

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

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

相关文章

【诈骗离你我很近】中国同胞进来看看国外诈骗新套路。

【诈骗离你我很近】中国同胞进来看看国外诈骗新套路。

前几天一个老外经常在CSDN给我发消息&#xff0c;我最开始很警惕&#xff0c;不过聊了大概半个月&#xff0c;我就没怎么怀疑他了&#xff0c;而且还很高兴认识了一个外国朋友。这半个月聊天内容很正常&#xff0c;就聊些中国的小习惯&#xff0c;让我教他用筷子。还问我有哪些…
阅读更多...
算法家族之一——二分法

算法家族之一——二分法

目录 算法算法的打印效果如果算法里的整型“i”为1如果算法里的整型“i”为11 算法的流程图算法的实际应用总结 大家好&#xff0c;我叫 这是我58&#xff0c;现在&#xff0c;请看下面的算法。 算法 #define _CRT_SECURE_NO_WARNINGS 1//<--预处理指令 #include <stdi…
阅读更多...
实现手机空号过滤或手机号码有效性验证

实现手机空号过滤或手机号码有效性验证

手机空号过滤或手机号码有效性验证通常涉及使用专门的API接口来查询手机号码的状态。这些API接口通常由第三方服务提供商提供&#xff0c;它们会与电信运营商合作或利用自己的数据库来验证手机号码是否真实存在、是否已被分配、是否处于空号状态等。 以下是一些步骤和考虑因素…
阅读更多...
Java：111-SpringMVC的底层原理（中篇）

Java：111-SpringMVC的底层原理（中篇）

这里续写上一章博客&#xff08;110章博客&#xff09;&#xff1a; 现在我们来学习一下高级的技术&#xff0c;前面的mvc知识&#xff0c;我们基本可以在67章博客及其后面相关的博客可以学习到&#xff0c;现在开始学习精髓&#xff1a; Spring MVC 高级技术&#xff1a; …
阅读更多...
黑马程序员——Spring框架——day07——SpringBoot高级

黑马程序员——Spring框架——day07——SpringBoot高级

目录&#xff1a; SpringBoot自动化配置原理 starter依赖管理机制自动化配置初体验Configuration配置注解Import注解使用1Import注解使用2Conditional衍生条件装配ConfigurationProperties配置绑定SpringBootApplication入口分析EnableAutoConfiguration自动配置注解按条件开启…
阅读更多...
指针（初阶2）“野指针以及指针运算”

指针（初阶2）“野指针以及指针运算”

目录 一.野指针 二.如何避免野指针 三.指针运算 1、指针&#xff08;-&#xff09;整数 2、指针 - 指针 3、指针关系运算 小编在这里声明一下&#xff0c;将某一块的知识点分为上中下或者1&#xff0c;2&#xff0c;3来编写不是为了增加小编的文章总量&#xff0c;也不是故意这…
阅读更多...
【大模型】Ollama+open-webui/Anything LLM部署本地大模型构建RAG个人知识库教程（Mac）

【大模型】Ollama+open-webui/Anything LLM部署本地大模型构建RAG个人知识库教程（Mac）

目录 一、Ollama是什么&#xff1f; 二、如何在Mac上安装Ollama 1. 准备工作 2. 下载并安装Ollama 3. 运行Ollama 4. 安装和配置大型语言模型 5. 使用Ollama 三、安装open-webui 1. 准备工作 2. Open WebUI ⭐的主要特点 3. Docker安装OpenWebUI&#xff0c;拉去太慢…
阅读更多...
quick4 - hackmyvm

quick4 - hackmyvm

简介 靶机名称&#xff1a;quick4 难度&#xff1a;简单 靶场地址&#xff1a;https://hackmyvm.eu/machines/machine.php?vmQuick4 本地环境 虚拟机&#xff1a;vitual box 靶场IP&#xff08;quick4&#xff09;&#xff1a;192.168.56.104 跳板机IP(windows 11)&…
阅读更多...
【OpenHarmony】ArkTS 语法基础 ⑤ ( ArkTS 状态管理 | @State 装饰器定义状态数据 | 使用状态数据渲染组件 )

【OpenHarmony】ArkTS 语法基础 ⑤ ( ArkTS 状态管理 | @State 装饰器定义状态数据 | 使用状态数据渲染组件 )

文章目录 一、ArkTS 状态管理 - State 装饰器1、State 装饰器定义状态数据2、State 装饰器定义状态数据 - 示例分析3、使用 State 装饰器定义的状态数据渲染组件 - 示例分析 二、完整代码示例1、完整自定义组件代码示例2、展示效果 参考文档 : <HarmonyOS第一课>ArkTS开发…
阅读更多...
2024年6月8日：极工度玩公司全球首发“竞技智慧，渔护海洋”竞渔棋，世界海洋日直播发布会圆满落幕

2024年6月8日：极工度玩公司全球首发“竞技智慧，渔护海洋”竞渔棋，世界海洋日直播发布会圆满落幕

在纪念2024年世界海洋日之际&#xff0c;极工度玩公司举办了一场别具一格的全球益智游戏首发发布会&#xff0c;向世界彰显了其对海洋生态保护的坚定承诺与热忱。这场以“竞技智慧&#xff0c;渔护海洋”为主题的盛会&#xff0c;旨在为参与者带来创新的游戏体验&#xff0c;同…
阅读更多...
归并排序法

归并排序法

归并排序法是典型的分治算法应用&#xff0c;1946年由冯.诺伊曼发明。 算法思路&#xff1a;归并排序算法有两个基本操作&#xff0c;一是分&#xff0c;也就是把原数组划分成两个子数组的过程&#xff0c;另一个是治&#xff0c;它将两个有序数组合并成一个更大的有序数组。 …
阅读更多...
【SpringCloud学习笔记】Docker（中篇）

【SpringCloud学习笔记】Docker（中篇）

Docker 1. 自定义镜像 前面我们都是使用docker pull拉取仓库中现成的镜像&#xff0c;但是如果我们想要将一个Java应用程序构建成镜像然后部署应该怎么做呢&#xff1f;这个时候我们就需要自定义镜像了 **镜像&#xff1a;**本质上就是一堆文件的集合&#xff0c;包含了应用程…
阅读更多...
！力扣102. 二叉树的层序遍历

！力扣102. 二叉树的层序遍历

给你二叉树的根节点 root &#xff0c;返回其节点值的 层序遍历 。 &#xff08;即逐层地&#xff0c;从左到右访问所有节点&#xff09;。 示例 1&#xff1a; 输入&#xff1a;root [3,9,20,null,null,15,7] 输出&#xff1a;[[3],[9,20],[15,7]] /*** Definition for…
阅读更多...
PHP实现一个简单的接口签名方法以及思路分析

PHP实现一个简单的接口签名方法以及思路分析

文章目录 签名生成说明签名生成示例代码签名校验示例代码 签名生成说明 B项目需要调用A项目的接口&#xff0c;由A项目为B项目分配 AccessKey 和 SecretKey&#xff0c;用于接口加密&#xff0c;确保不易被穷举&#xff0c;生成算法不易被猜测。 最终需要确保包含签名的参数只…
阅读更多...
Letcode-Top 100二叉树专题

Letcode-Top 100二叉树专题

94. 二叉树的中序遍历 方法一&#xff1a;递归法 /*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeN…
阅读更多...
机器学习——卷积神经网络

机器学习——卷积神经网络

卷积神经网络CNN 多层感知机MLP的层数足够&#xff0c;理论上可以用其提取出二位特征&#xff0c;但是毕竟复杂&#xff0c;卷积神经网络就可以更合适的来提取高维的特征。 而卷积其实是一种运算 二维离散卷积的公式 可以看成g是一个图像的像素点&#xff0c;f是每个像素点对…
阅读更多...
312. 戳气球

312. 戳气球

题目 有 n 个气球&#xff0c;编号为 0 到 n - 1&#xff0c;每个气球上都标有一个数字&#xff0c;这些数字存在数组 nums 中。 现在要求你戳破所有的气球。戳破第 i 个气球&#xff0c;你可以获得 nums[i - 1] * nums[i] * nums[i 1] 枚硬币。 这里的 i - 1 和 i 1 代表和…
阅读更多...
Pytorch 实现目标检测一（Pytorch 23）

Pytorch 实现目标检测一（Pytorch 23）

一 目标检测和边界框 在图像分类任务中&#xff0c;我们假设图像中只有一个主要物体对象&#xff0c;我们只关注如何识别其类别。然而&#xff0c;很多时候图像里有多个我们感兴趣的目标&#xff0c;我们不仅想知 道它们的类别&#xff0c;还想得到它们在图像中的具体位置。在…
阅读更多...
【Python】数据处理：OS目录文件操作

【Python】数据处理：OS目录文件操作

Python的os模块是一个用于与操作系统进行交互的标准库模块。它提供了丰富的功能来处理文件和目录、执行系统命令、获取和设置环境变量等。 工作目录操作 获取当前工作目录 os.getcwd()参数&#xff1a;无返回值&#xff1a;一个字符串&#xff0c;表示当前工作目录的路径。这…
阅读更多...
算数运算符与表达式（打印被10整除的数）

算数运算符与表达式（打印被10整除的数）

打印100以内&#xff08;包含100&#xff09;能被10整除的正整数 #include <stdio.h>#define UPPER 100int main() {int i 1;while (i < UPPER)if (i % 10 0)printf("%d\n", i);return 0; } 自增运算符 i 用于递增变量 i 的值。在 while 循环中&#xf…
阅读更多...
最新文章

Copyright @ 2022~2023