当前位置: 首页 > news >正文

【进阶数据结构】平衡搜索二叉树 —— AVL树

🌈感谢阅读East-sunrise学习分享——[进阶数据结构]AVL树
博主水平有限,如有差错,欢迎斧正🙏感谢有你 码字不易,若有收获,期待你的点赞关注💙我们一起进步🚀


🌈我们上一篇博客分享了搜索二叉树,在文中也铺垫了搜索二叉树的一些结构局限性
而今天分享的一种特殊的搜索二叉树——AVL树,便是一种结构优异的搜索二叉树🎄那么我们就开始吧🚀🚀🚀

目录

  • 一、AVL树的概念
  • 二、AVL树结点的定义
  • 三、AVL树的插入
  • 四、AVL树的旋转
    • 1.左单旋
    • 2.右单旋
    • 3.左右双旋
    • 4.右左双旋
  • 五、最终代码展示

一、AVL树的概念

二叉搜索树虽可以缩短查找的效率,但如果数据有序或接近有序二叉搜索树将退化为单支树,查找元素相当于在顺序表中搜索元素,效率低下

因此,两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法:当向二叉搜索树中插入新结点后,如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整),即可降低树的高度,从而减少平均搜索长度

🎄一棵AVL树可以是一棵空树,或者是一棵具有以下性质的二叉搜索树

  • 它的左右子树都是AVL树
  • 左右子树高度之差(简称平衡因子)的绝对值不超过1

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-hDG6AbRQ-1679390790392)(C:\Users\DongYu\AppData\Roaming\Typora\typora-user-images\image-20230320143958347.png)]

这里的平衡因子是指:右子树高度-左子树高度

注意:平衡因子只是博主分享的这种实现方法的一种自定义名字(不是必须的),除了使用平衡因子之外还有许多实现AVL树的方法

如果一棵二叉搜索树是高度平衡的,它就是AVL树。如果它有n个结点,其高度可保持在O(logN),搜索时间复杂度O(logN)


二、AVL树结点的定义

AVL树的结点我们定义了一个三叉链结构,便于后续的操作;并且在每个结点中都引入了平衡因子

template<class K, class V>
struct AVLTreeNode
{//存储键值对的pair类pair<K, V> _kv;//含有父节点的三叉链AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;//平衡因子int _bf;AVLTreeNode(const pair<K, V>& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}
};//AVL树
template<class K,class V>
struct AVLTree
{typedef AVLTreeNode<K, V> Node;
public://插入bool Insert(const pair<K, V>& kv){}private:Node* _root = nullptr;
};

三、AVL树的插入

AVL树就是在二叉搜索树的基础上引入了平衡因子,因此AVL树也可以看成是二叉搜索树。那么AVL树的插入过程可以分为两步:

  1. 按照二叉搜索树的方式插入新节点
  2. 调整平衡因子,若不平衡则需要旋转调整AVL树

⭕⭕当有新节点插入后我们就需要判断此时的树是否仍然平衡仍然是AVL树了


🚩插入后平衡因子的变化类型?

我们知道,假如平衡,则每个结点的平衡因子只有三种可能:-1,0,1

而插入新结点肯定会使得高度的变化,假如插入新节点后仍平衡,则父节点的平衡因子的变化有:

  • 0 --> 1
  • 0 --> -1
  • 1 --> 0
  • -1 --> 0

知道了平衡因子的变化情况后,又抛出了一个问题

🚩插入新节点影响父节点的平衡因子,那是否会影响祖先结点的平衡因子?

最简单的情况就是插入了新节点,只影响了其父结点,只需更新父节点的平衡因子

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-yGlce0wT-1679390790393)(C:\Users\DongYu\AppData\Roaming\Typora\typora-user-images\image-20230320151927976.png)]

插入新节点后,改变了其父结点(8)的子树高度,所以需要更新父节点的平衡因子,但是插入之后并不会改变其祖先结点的子树高度,所以不需要往上更新平衡因子

📌因此我们可以总结出:是否持续更新平衡因子,取决于其结点的子树高度是否变化

再结合一开始的平衡因子变化情况我们可以得出插入新结点后:

  • parent -> _bf == 0 —— 说明之前parent -> _bf 是 1 或者 -1(一边高一边低)新节点刚好插入填上矮的那边,parent所在子树高度不变 —— 祖先的子树高度也不会变 —— 只需更新parent的平衡因子,不需要继续往上更新
  • parent -> _bf == 1 或 -1 —— 说明之前parent -> _bf == 0(两边一样高)新结点插入使得parent所在子树的高度变得一高一低 —— 祖先的子树高度也产生变化 —— 更新parent的平衡因子之外,还需要继续往上更新祖先结点的平衡因子
  • parent -> _bf == 2 或 -2 —— 说明本就一高一低的子树,插入新节点后造成更加不平衡,此时违反了AVL树的平衡规则 —— 就地处理 ——旋转调整

最坏的情况就是插入了新节点,直接影响到了root根结点,所以需要持续更新到root根结点的平衡因子

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-inVjVnIr-1679390790394)(C:\Users\DongYu\AppData\Roaming\Typora\typora-user-images\image-20230320154047198.png)]

💭更新结点的平衡因子时,假若我们需要持续向上更新平衡因子,一开始我们更新的是最下面的parent结点,更新后则可向上迭代,直到parent为空就停止

✏️代码实现

bool Insert(const pair<K, V>& kv){//空if (_root == nullptr){_root = new Node(kv);return true;}//非空Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}elsereturn false;}//插入cur = new Node(kv);if (parent->_kv.first < kv.first){parent->_right = cur;cur->_parent = parent;}else{parent->_left = cur;cur->_parent = parent;}//调整平衡因子while (parent){if (cur == parent->_right)parent->_bf++;elseparent->_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){//旋转调整}elseassert(false);}return true;}

四、AVL树的旋转

🌏如果在一棵原本是平衡的AVL树中插入一个新节点,可能造成不平衡,此时必须调整树的结构,使之平衡化。

因此旋转的要求即是:

  1. 旋转后仍保持二叉搜索树的结构
  2. 旋转后整棵树保持平衡,平衡因子不超过1

而根据节点插入位置的不同,AVL树的旋转分为四种:

1.左单旋

1️⃣新节点插入较高右子树的右侧 —— 左单旋

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ewTMX0mf-1679390790394)(C:\Users\DongYu\AppData\Roaming\Typora\typora-user-images\image-20230320191813189.png)]

此处我们给出左单旋过程的抽象图📌

我们发现,当parent的平衡因子是2,cur是1时,便进行左单旋 ——> 将cur的左子树给parent的右子树,然后将parent及其子树一整棵树变为cur的左子树

左单旋真就如此吗?不信我们可以画出具象图看看

当 h = 0

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-JOtMtrcS-1679390790394)(C:\Users\DongYu\AppData\Roaming\Typora\typora-user-images\image-20230320192229670.png)]

当 h = 1

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-TNDYGHPL-1679390790394)(C:\Users\DongYu\AppData\Roaming\Typora\typora-user-images\image-20230320192802162.png)]

当 h = 2

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-o56wtp0U-1679390790395)(C:\Users\DongYu\AppData\Roaming\Typora\typora-user-images\image-20230320193527342.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ndiplxh7-1679390790395)(C:\Users\DongYu\AppData\Roaming\Typora\typora-user-images\image-20230320194200461.png)]

💭有的兄弟看到这就有疑问,为什么h = 2时,子树c一定就得是z的模样呢?
因为假如子树c是x或y的模样,插入新节点时并不会引发节点30的旋转,那样最多只是变成以节点60为parent的树进行左单旋,那就和h = 1是同样的情况了💤因此以上的情况,其实是笼盖了所有需要进行左单旋的子情况了🚩然后以上的情况可能是某棵树的子树

最后我们发现,所有需要进行左单旋的情况,最后的操作都是如一开始所说

✏️代码实现(对照图更清晰易懂)

void RotateL(Node* parent)
{Node* subR = parent->_right;//parent的右孩子Node* subRL = subR->_left;//parent的右孩子的左孩子//旋转后subR的左孩子作为parent的右孩子parent->_right = subRL;//subR的左孩子有可能为空也有可能存在//如果存在则需要更新父子关系if (subRL)subRL->_parent = parent;//subR的左孩子变为以parent为根的子树结构//同时更新父子关系subR->_left = parent;parent->_parent = subR;//parent也可能只是一棵子树的根,其pparent可能为空也可能存在Node* pparent = parent->_parent;if (pparent){//如果pparent不为空,则说明parent是一棵子树//可能是存在于其父节点的左子树or右子树if (parent == pparent->_left)pparent->_left = subR;elsepparent->_right = subR;subR->_parent = pparent;}else{//若pparent为空,则说明parent是整棵树的根节点//旋转后根节点已经换人了需要更新_root = subR;subR->_parent = nullptr;}//最后更新平衡因子parent->_bf = subR->_bf = 0;
}

📌看完以上的代码实现,发现旋转的代码实现起来也有许多细节需要注意啊…

因为旋转后也要保持一棵正常的树的结构,因此那些父子链接关系也需要正确更新

2.右单旋

2️⃣新节点插入较高左子树的左侧 - 右单旋

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-0rczBlb6-1679390790395)(C:\Users\DongYu\AppData\Roaming\Typora\typora-user-images\image-20230320224253056.png)]

✏️实现及情况考虑可参考左单旋

void RotateR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;Node* pparent = parent->_parent;subL->_right = parent;parent->_parent = subL;if (pparent){if (parent == pparent->_left)pparent->_left = subL;elsepparent->_right = subL;subL->_parent = pparent;}else{_root = subL;subL->_parent = nullptr;}subL->_bf = parent->_bf = 0;
}

3.左右双旋

3️⃣新节点插入较高左子树的右侧 - 先左单旋再右单旋

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-3Mn250NT-1679390790395)(C:\Users\DongYu\AppData\Roaming\Typora\typora-user-images\image-20230320225421511.png)]

左右双旋我们可以复用上面的左单旋和右单旋的代码🚩但是需要注意的是,左右双旋完各个节点的平衡因子有不同的情况,正是因为左右双旋会因为新节点插入的位置不同而影响不同的旋转结果,因此我们总结出了以下三种情况:

  1. h = 0 —— 节点60即是新插入节点
    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-fkFAFXcU-1679390790396)(C:\Users\DongYu\AppData\Roaming\Typora\typora-user-images\image-20230320230931222.png)]

  2. 新节点插入在b
    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-1pptemfj-1679390790396)(C:\Users\DongYu\AppData\Roaming\Typora\typora-user-images\image-20230320231609130.png)]

  3. 新节点插入在c
    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-JGZNUPir-1679390790396)(C:\Users\DongYu\AppData\Roaming\Typora\typora-user-images\image-20230320231628170.png)]

综上所述,当我们在实现左右双旋时的最后,可根据插入新节点后节点60的平衡因子大小,来确定不同的情况

void RotateLR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(parent->_left);RotateR(parent);//更新平衡因子if (bf == 1) //新增在sublr右子树{parent->_bf = 0;subL->_bf = -1;subLR->_bf = 0;}else if (bf == -1) //新增在sublr左子树{subL->_bf = 0;parent->_bf = 1;subLR->_bf = 0;}else //本身就是新增{parent->_bf = 0;subL->_bf = 0;subLR->_bf = 0;}
}

4.右左双旋

4️⃣新节点插入较高右子树的左侧——先右单旋再左单旋

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-RGitbiDD-1679390790396)(C:\Users\DongYu\AppData\Roaming\Typora\typora-user-images\image-20230320232205457.png)]

✏️实现及情况考虑可参考左右双旋

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

五、最终代码展示

template<class K, class V>
struct AVLTreeNode
{pair<K, V> _kv;AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;int _bf;AVLTreeNode(const pair<K, V>& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}
};template<class K,class V>
struct 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* parent = nullptr;Node* cur = _root;while (cur){if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}elsereturn false;}//插入cur = new Node(kv);if (parent->_kv.first < kv.first){parent->_right = cur;cur->_parent = parent;}else{parent->_left = cur;cur->_parent = parent;}//调整平衡因子while (parent){if (cur == parent->_right)parent->_bf++;elseparent->_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 (parent->_bf == 2 && cur->_bf == 1)RotateL(parent);else if (parent->_bf == -2 && cur->_bf == -1)RotateR(parent);else if (parent->_bf == -2 && cur->_bf == 1)RotateLR(parent);else if (parent->_bf == 2 && cur->_bf == -1)RotateRL(parent);elseassert(false);break;}elseassert(false);}return true;}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;Node* pparent = parent->_parent;subR->_left = parent;parent->_parent = subR;if (pparent){if (parent == pparent->_left)pparent->_left = subR;elsepparent->_right = subR;subR->_parent = pparent;}else{_root = subR;subR->_parent = nullptr;}parent->_bf = subR->_bf = 0;}void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;Node* pparent = parent->_parent;subL->_right = parent;parent->_parent = subL;if (pparent){if (parent == pparent->_left)pparent->_left = subL;elsepparent->_right = subL;subL->_parent = pparent;}else{_root = subL;subL->_parent = nullptr;}subL->_bf = parent->_bf = 0;}void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(parent->_left);RotateR(parent);if (bf == 1) //新增在sublr右子树{parent->_bf = 0;subL->_bf = -1;subLR->_bf = 0;}else if (bf == -1) //新增在sublr左子树{subL->_bf = 0;parent->_bf = 1;subLR->_bf = 0;}else if (bf == 0) //本身就是新增{parent->_bf = 0;subL->_bf = 0;subLR->_bf = 0;}else{assert(false);}}void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(parent->_right);RotateL(parent);if (bf == 1){subR->_bf = 0;parent->_bf = -1;subRL->_bf = 0;}else if (bf == -1){parent->_bf = 0;subR->_bf = 1;subRL->_bf = 0;}else if(bf == 0){parent->_bf = 0;subR->_bf = 0;subRL->_bf = 0;}else{assert(false);}}void Inorder(){_Inorder(_root);}void _Inorder(Node* root){if (root == nullptr)return;_Inorder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_Inorder(root->_right);}int Height(Node* root){if (root == nullptr)return 0;int hl = Height(root->_left);int hr = Height(root->_right);return hl > hr ? hl + 1 : hr + 1;}bool IsBalance(){return IsBalance(_root);}bool IsBalance(Node* root){if (root == nullptr)return true;int leftHeight = Height(root->_left);int rightHeight = Height(root->_right);if (rightHeight - leftHeight != root->_bf){cout << "平衡因子异常" << endl;return false;}return abs(rightHeight - leftHeight) < 2&& IsBalance(root->_left)&& IsBalance(root->_right);}private:Node* _root = nullptr;
};

🌈🌈写在最后 我们今天的学习分享之旅就到此结束了
🎈感谢能耐心地阅读到此
🎈码字不易,感谢三连
🎈关注博主,我们一起学习、一起进步

相关文章:

【进阶数据结构】平衡搜索二叉树 —— AVL树

&#x1f308;感谢阅读East-sunrise学习分享——[进阶数据结构]AVL树 博主水平有限&#xff0c;如有差错&#xff0c;欢迎斧正&#x1f64f;感谢有你 码字不易&#xff0c;若有收获&#xff0c;期待你的点赞关注&#x1f499;我们一起进步&#x1f680; &#x1f308;我们上一篇…...

ROS使用(5)action学习

action消息的构建 首先进行功能包的创建 mkdir -p ros2_ws/src cd ros2_ws/src ros2 pkg create action_tutorials_interfaces action消息的类型 # Request --- # Result --- # Feedback 动作定义由三个消息定义组成&#xff0c;以---分隔。 从动作客户机向动作服务器发送…...

2023前端面试题集(含答案)之HTML+CSS篇(一)

在又到了金三银四的招聘季&#xff0c;不管你是刚入行的小白&#xff0c;亦或是混迹职场的老鸟&#xff0c;还在为面试前端工程师时不知道面试官要问什么怎么回答而苦恼吗&#xff1f;为了帮助你获得面试官的青睐&#xff0c;顺利通过面试&#xff0c;跳槽进入大厂&#xff0c;…...

设计模式2 - 观察者模式

定义&#xff1a; 观察者模式又叫发布订阅模式&#xff0c;它定义了对象之间的一对多依赖&#xff0c;这样一来&#xff0c;当一个对象改变状态时&#xff0c;它的所有依赖者都会收到通知并自动更新。 组成&#xff1a; Subject&#xff08;通知者/被观察者&#xff09;&#…...

ini配置文件

ini配置文件 ini文件是initialization file的缩写&#xff0c;即初始化文件&#xff0c;是widows系统配置文件所采用的存储格式。 文件扩展名: .ini ini配置文件的后缀名也不一定必须是.ini, 也可以是.cfg, .conf或者是.txt ini文件格式 ini配置文件由参数, 节, 注解组成 参…...

蓝桥杯备赛经验 pythonA组(非科班选手)

个人2022 CA组江苏省一等奖&#xff0c;决赛成绩不理想&#xff0c;没有拿到一二等奖&#xff0c;但是因为自己是非科班的学生&#xff0c;所以能拿到这样的成绩自己其实也应该知足了 题外话&#xff1a; 很多ACMer嘲笑蓝桥杯非常水&#xff0c;但是据我观察CA组决赛一等奖获奖…...

C++实现通讯录管理系统

通讯录是一个可以记录亲人、好友信息的工具&#xff0c;本博客借助黑马程序员的项目进行修改&#xff0c;利用C实现一个通讯录管理系统&#xff0c;旨在复习C的语法。 一、系统需求 系统需要实现的功能如下&#xff1a; 添加联系人∶向通讯录中添加新人&#xff0c;信息包括…...

开关电源Y电容放置的位置

Y电容&#xff0c;是我们工程师做开关电源设计时都要接触到的一个非常关键的元器件&#xff0c;它对EMI的贡献是相当的大的&#xff0c;但是它是一个较难把控的元器件&#xff0c;原理上并没有那么直观易懂&#xff0c;在EMI传播路径中需要联系到很多的寄生参数才能够去分析。 …...

二叉树的最小深度——递归法、迭代法

1题目给定一个二叉树&#xff0c;找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。说明&#xff1a;叶子节点是指没有子节点的节点。示例 1&#xff1a;输入&#xff1a;root [3,9,20,null,null,15,7]输出&#xff1a;2示例 2&#xff1a;输入&…...

Vue中常使用的三种刷新页面的方式

一、通过js原始方法刷新 缺点&#xff1a; 出现闪白 目录 一、通过js原始方法刷新 二、通过Vue自带的路由进行跳转 三、通过在APP页面进行demo进行刷新(推荐) 1.vue2写法 2. vue3.2写法 <template><div><div class"header"><button clic…...

【Shell】脚本

Shell脚本脚本格式第一个Shell脚本&#xff1a;hello.sh脚本常用执行方式1. bash或sh脚本的相对路径或绝对路径2. 输入脚本的绝对路径或相对路径3. 在脚本的路径前加上.或者source脚本格式 脚本以#!/bin/bash开头&#xff08;指定解析器&#xff09; #! 是一个约定的标记&…...

Mybatis的多表操作

1.Mybatis多表查询 1.1一对一查询 1.一对一查询的模型 用户表和订单表的关系为&#xff0c;一个用户有多个订单&#xff0c;一个订单只从属于一个用户 一对一查询的需求&#xff1a;查询一个订单&#xff0c;与此同时查询出该订单所属的用户2.创建Order和User实体public class…...

【JVM】字节码指令全解

文章目录 入门案例原始 java 代码编译后的字节码文件常量池载入运行时常量池方法字节码载入方法区main 线程开始运行,分配栈帧内存执行引擎开始执行字节码bipush 10istore_1ldc #3istore_2iload_1iload_2iaddistore_3getstatic #4iload_3invokevirtual #5return条件判断指令循…...

【精品】华为认证数通HCIA+HCIP题库分享(含答案解析)

嗨~大家好久不见&#xff0c;我是薄荷学姐&#xff0c;随着华为业务也全球领域的迅猛发展&#xff0c;越来越多人开始重视华为认证的重要性。今天给大家分享一下去年8月份的题库&#xff0c;基本都是一样&#xff0c;希望可以帮助到大家哈想要通过华为认证&#xff0c;除了进行…...

Qt cmake 资源文件的加载

Qt cmake 资源文件的加载概述qt_add_resourcesqt5_add_resourcesqt6_add_resources是否需要加载qrc文件需要加载qrc的情况不需要加载qrc的情况C 代码加载示例加载PNG加载CSS文件加载qrc文件Qt6相对于Qt5的一些变化Qt6和Qt5在加载资源文件方面的区别主要集中在两个方面&#xff…...

【链表OJ题(九)】环形链表延伸问题以及相关OJ题

环形链表OJ题 1. 环形链表 链接&#xff1a;141. 环形链表 描述&#xff1a; 给你一个链表的头节点 head &#xff0c;判断链表中是否有环。 如果链表中有某个节点&#xff0c;可以通过连续跟踪 next 指针再次到达&#xff0c;则链表中存在环。 为了表示给定链表中的环&…...

【C++初阶】四、类和对象(下)

文章目录一、再谈构造函数构造函数体赋值初始化列表explicit关键字二、Static成员引入- 计算类中创建了多少个类对象概念特性静态成员函数的访问三、友元友元函数友元类四、内部类五、匿名对象六、拷贝对象时的一些编译器优化一、再谈构造函数 构造函数体赋值 在创建对象时&a…...

IDEA maven没有Import Maven projects automatically解决办法

去年装了个 IDEA2022版本 配置maven时我才发现是个大坑 他没有import Maven projects automatically配置项 当时看到我人都麻了 然后项目呢 用了依赖 这东西还不会自动下依赖 整的我那是相当难受 还在最后还是找到了解决办法 我们在配置文件上点击右键 然后鼠标选择如下图选项…...

Java实习生------MySQL10道面试题打卡

今日语录&#xff1a;“没有执行力&#xff0c;就没有竞争力 ”&#x1f339; 参考资料&#xff1a;图解MySQL、MySQL面试题 1、事务有哪些特性&#xff1f; 原子性&#xff1a; 一个事务中的所有操作&#xff0c;要么全部完成&#xff0c;要么全部不完成&#xff0c;不会出现…...

帆软报表设计器 数据集之数据库查询

当点击数据库查询时,调用TableDataTreePane的 public void actionPerformed(ActionEvent var1) {TableDataTreePane.this.dgEdit(this.getTableDataInstance().creatTableDataPane(), TableDataTreePane.this.createDsName(this.getNamePrefix()), false);} 然后调用TableDat…...

在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能

下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能&#xff0c;包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...

Leetcode 3577. Count the Number of Computer Unlocking Permutations

Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接&#xff1a;3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯&#xff0c;要想要能够将所有的电脑解锁&#x…...

Linux简单的操作

ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...

MVC 数据库

MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...

土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等

&#x1f50d; 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术&#xff0c;可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势&#xff0c;还能有效评价重大生态工程…...

第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词

Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵&#xff0c;其中每行&#xff0c;每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid&#xff0c;其中有多少个 3 3 的 “幻方” 子矩阵&am…...

基于matlab策略迭代和值迭代法的动态规划

经典的基于策略迭代和值迭代法的动态规划matlab代码&#xff0c;实现机器人的最优运输 Dynamic-Programming-master/Environment.pdf , 104724 Dynamic-Programming-master/README.md , 506 Dynamic-Programming-master/generalizedPolicyIteration.m , 1970 Dynamic-Programm…...

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列&#xff0c;以便知晓哪些列包含有价值的数据&#xff0c;…...

【7色560页】职场可视化逻辑图高级数据分析PPT模版

7种色调职场工作汇报PPT&#xff0c;橙蓝、黑红、红蓝、蓝橙灰、浅蓝、浅绿、深蓝七种色调模版 【7色560页】职场可视化逻辑图高级数据分析PPT模版&#xff1a;职场可视化逻辑图分析PPT模版https://pan.quark.cn/s/78aeabbd92d1...

RabbitMQ入门4.1.0版本(基于java、SpringBoot操作)

RabbitMQ 一、RabbitMQ概述 RabbitMQ RabbitMQ最初由LShift和CohesiveFT于2007年开发&#xff0c;后来由Pivotal Software Inc.&#xff08;现为VMware子公司&#xff09;接管。RabbitMQ 是一个开源的消息代理和队列服务器&#xff0c;用 Erlang 语言编写。广泛应用于各种分布…...