【DS】红黑树

目录

  • 红黑树的介绍
  • 红黑树节点的定义
  • 红黑树的插入
  • 红黑树的调整
    • 情况一
    • 情况二
    • 情况三
  • 红黑树的验证
  • 红黑树与AVL树的比较

在上一篇AVL树的实现中，学习了平衡二叉树的一种——AVL树；由于AVL树极度追求平衡，因此它的查找效率十分高效；但也正是由于其极度追求平衡的旋转策略，导致其动不动就旋转，因此旋转消耗十分大。在实际中使用的不多。对此，今天学习另一个平衡二叉树——红黑树。

红黑树的介绍

概念

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。

红黑树是平衡二叉搜索树中的一种，红黑树性能优异，广泛用于实践中，比如 Linux 内核中的 CFS 调度器，C++ STL库中的map和set的底层就用到了红黑树，由此可见红黑树的重要性。

红黑树
性质

  1. 每个结点不是红色就是黑色
    • 红黑树特点
  2. 根节点是黑色的
  3. 如果一个节点是红色的，则它的两个孩子结点是黑色的
    • 不红红
  4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点
    • 黑路同
  5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点，也叫NIL节点)
    • 此处黑色仅用于路径判断，不具备其他含义
  • 需要十分了解这些性质，特别是性质2，3，4。

上面前四条性质特别重要。同时满足前四条性质，就能保证：

其最长路径中节点个数不会超过最短路径节点个数的两倍

理论下极端的红黑树
这就是极端情况下，理论上存在的红黑树，也就是红黑树最不平衡的时候。而且只要再插入节点，通过红黑树的调整策略就会尽量平衡树身，所以红黑树的效率还是有保障的。

性质4(黑路同)确保了从根到叶子节点的任何路径上的黑色节点数相同。这意味着所有路径在黑色节点级别上是“等长”的。现在，考虑由于性质3(不红红)的存在，即不允许连续的红色节点，那么任意两个黑色节点之间最多只能插入一个红色节点（如果有的话）。

  • 最短路径：最短路径只包含黑色节点，因为不存在连续的红色节点可以缩短路径。
  • 最长路径：最长路径包含交替的黑色和红色节点（尽管并非所有黑色节点之间都必须有红色节点）。
    • 由于任意两个黑色节点之间最多只能插入一个红色节点，因此在两个黑色节点之间最多可以插入一个红色节点，这使得红色节点的数量在任意两个黑色节点之间都是受限的。

考虑从一个黑色节点到下一个黑色节点（包含这两个黑色节点）的路径上，可能的最长情况就是有一个红色节点。由于性质4，我们知道从根到任意叶子节点的黑色节点数相同，设这个数量为 B。那么，最长路径的长度（节点数）就是 2 B − 1 2B−1 2B−1（每个黑色节点之间最多插入一个红色节点）。最短路径只包含黑色节点，因此长度为 B。

所以，最长路径与最短路径的节点数之比为 ( 2 B − 1 ) / B (2B−1)/B (2B−1)/B，简化后得到 2 − 1 / B 2−1/B 2−1/B。由于 B 总是大于0，因此这个比值总是小于2，且随着 B 的增大而趋近于2。

综上，红黑树确保了从根到叶子的最长路径不会超过最短路径的两倍长。但这只是在规则限定下的理论而言，实际上红黑树的最长，最短路径都不一定会存在。

根据此特性可以得出，红黑树是近似平衡的，因此在查找效率上就没有追求极度平衡的AVL树效率高。

红黑树节点的定义

红黑树可以看作是AVL树的改良版，增加了树节点的颜色。其余的还是保存kv的键值对pair，三叉链。

enum Color
{RED, BLACK
};template<class K, class V>
struct RBTreeNode
{pair<K, V> _kv;RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;Color _col;RBTreeNode(const pair<K, V>& kv):_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr),_col(RED)//默认为红色{}};

节点的颜色默认设置为红色，理由如下：

  • 当节点颜色为黑色时，完成一次插入后，会发现此时一定违反了红黑树性质中黑路同的原则，因为你只能在树的左右一侧插入，那么插入一个黑色节点后，左右子树的黑色节点数量必然不同，必然需要进行调整。
  • 当节点颜色为红色时，不需要关心插入在哪棵子树上，由于节点颜色不是红色就是黑色，当插入节点的父节点为红色时，违反了不红红的性质，需要调整；但当插入节点的父节点为黑色时，没有违反红黑树的任何一条性质，此时不需要进行调整。

也就是说：当节点为黑色时一定会调整，当节点为红色时可能会调整。
综上所述，节点默认为红色的设计更优。

红黑树的插入

红黑树的插入分三步：

  1. 按搜索二叉树的性质插入

    • BST性质

  2. 通过颜色判断是否需要调整

    • 通过性质3(不红红)来判断是否需要进行调整

  3. 调整

    • 分三种状况

第二步为什么通过不红红这一性质判断是否需要调整。

与AVL树通过平衡因子(本质就是高度)来判断是否需要旋转调平衡不同；红黑树这里没有所谓高度一说，而是通过树节点的颜色来控制树身的近似平衡的；
通过不红红这一性质判断是否需要调整是因为：树节点的颜色默认为红色，所以插入节点后如果破坏了红黑树的性质，那么一定是不红红这一性质，此时就需要进行调整。

红黑树的调整

由于新插入的节点默认设为红色，所以红黑树在插入之后不一定需要调整，可分为以下三种情况进行调整。调整策略分为两种：

  • 单纯染色
  • 旋转加染色
    • 这里的旋转和AVL树的旋转是一样的，如果不了解如何进行旋转的话请参考——AVL树的旋转

前面说过，红黑树是AVL树的改良版；由于AVL树追求极度的平衡，所以其旋转次数肯定不会少，红黑树的目的就是达到近似平衡，效率上不会差太多，但是可以减少他的旋转消耗，所以红黑树调整时是不情愿旋转的，能不旋转尽量不旋转，必须的时候才旋转。

对于红黑树的调整，需要关注以下几个节点：

  • cur为当前节点
  • parent为父节点，以下称p
  • grandfather为祖父节点，以下称g
  • uncle为叔叔节点，以下称u

以下的三种情况我们以u节点的不同状况来区分。

情况一

红黑树调整一

cur为红，p为红，g为黑，u存在且为红

  • 以下示意图为抽象图；abcde不代表高度，代表从abcde开始的路径上有多少黑色节点。

情况一
此时cur与p都为红，违反了不红红的性质，需要进行调整；此时的p，u都为红色，所以为了既要解决不红红的问题，又需要保证黑路同的性质，此时可以将p，u都变为黑色，此时解决了不红红的问题；但是由此时的g开始的左右子树的黑色节点的数量都增加了1；这时候还得根据g是否为根节点继续判断:

  1. g为根节点，这种情况下由于根开始的左右子树都增加了黑色节点数量，所以不违反黑路同的性质。
  2. g不是根节点，是一颗子树，因为g不是根节点，只是根节点的左/右子树，这种情况增加黑色节点数量违反了黑路同原则，需要将g变红，保证当前子树的黑色节点数量不变。而这时又会出现情况一的问题，还得需要向上继续更新。
  • 情况一需要注意的就是当前的树是否是一颗完整的树还是一棵子树。
  • 在实现情况一解决办法时，代码的实现为解决上述第二种情况。
  • cur不一定是新插入的，也有可能是变色而来。

情况一解决
注意：情况一中，cur不管是p的左孩子还是右孩子都是一样的

情况二

红黑树调整2

cur为红，p为红，g为黑，u不存在

情况二
出现情况二这种状况说明此时的的树身已经不平衡了，有点单枝树的倾向了；而且此时的cur一定是新插入的节点，由于没有u，所以现在是一个单支的状况只能有g，p两个节点。

此时单独的染色已经无法解决这种极度不平衡的树型了，需要搬出旋转大法；此时按照AVL树的旋转策略旋转调平衡不了解旋转策略的请参考AVL树的旋转
完成旋转后，再进行染色维持红黑树的性质：此时的染色策略为交换两旋转点的颜色，这样操作还是从此时的g是否是整棵树还是子树进行考虑；染色就需要同时确保：根为黑，黑路同，不红红的性质。

  • 注意染色是不需要考虑cur是p的左孩子还是有孩子；但是旋转需要根据AVL树的旋转规则来，需要区分cur是p的左还是右孩子。

情况二

情况三

红黑树调整3

cur为红，p为红，g为黑，u存在且为黑

情况三

情况三的cur一定是由黑色节点变来的，不可能是新插入的节点；也就是说cur为红色是由于情况一的染色调整变来的；因为g的右子树u已经是黑色节点了，那么g的左子树也必须要有对应数量的黑色节点，那么子树abc就不可能是空，必须要有对应数量的黑色节点，才不会违反红黑树的原则。
情况三解释
调整策略与情况二一致，都是旋转加染色；

情况三
可以看到此时的树型会复杂一点，而且需要注意是谁要进行颜色交换，所以还是建议画图，对照着图来一步步实现。

以上的旋转加染色都是单旋加染色；颜色的调整无论左右，但是旋转不仅有单旋，还有双旋，需要知道树型是纯粹的一边高还是呈现出折线的样子。

单双旋
红黑树调整4

这里通过cur在较高左子树的右边这一例子展示双旋加染色的策略：这一情况需要进行两次旋转，第一次是为了将树型转化为情况二的树型，第二次旋转才是调平衡。之后将两旋转点进行换色处理。

  • 换色是在第二次旋转时才需要，而且双旋要换色的点为cur和g，所以一定要画图看仔细。

左右双旋

下图是我在红黑树学习时对插入操作的总结。

总结
以下时具体实现

	bool Insert(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;//根为黑色return true;}Node* cur = _root;Node* parent = nullptr;while (cur){if (kv.first > cur->_kv.first){parent = cur;cur = cur->_right;}else if (kv.first < cur->_kv.first){parent = cur;cur = cur->_left;}else{return false;}}//到在这里说明找到位置了，开始插入。//此时cur已经为nullptr，让其成为新节点cur = new Node(kv);if (kv.first > parent->_kv.first){parent->_right = cur;}else//不存在相等情况{parent->_left = cur;}//处理三叉链的最后一环cur->_parent = parent;//cur插在parent处且默认为红色while (parent && parent->_col == RED)//当cur为根节点时，parent为空，不会进{//p，c颜色为红Node* grandparent = parent->_parent;//      g//   p     u//  cif (parent == grandparent->_left)//单双旋需要借此区分{//两种调整策略//1：单纯染色//2：旋转加染色（分单双旋）Node* uncle = grandparent->_right;if (uncle && uncle->_col == RED)//策略1{parent->_col = BLACK;uncle->_col = BLACK;grandparent->_col = RED;//向上更新一整棵树cur = grandparent;parent = cur->_parent;}//策略二else//uncle不存在或者存在且为黑（由上面的情况变来）{//      g//   p     u//  c//先区分单旋还是双旋//单旋if (cur == parent->_left)//纯粹一边高{//看图RotateR(grandparent);parent->_col = BLACK;grandparent->_col = RED;}else//双旋   插入在较高左子树的右侧{//      g//   p     u//     cRotateL(parent);RotateR(grandparent);cur->_col = BLACK;grandparent->_col = RED;}break;//旋转完就可以退出}}else if(parent == grandparent->_right){//     g//  u     p//          cNode* uncle = grandparent->_left;if (uncle && uncle->_col == RED){parent->_col = BLACK;uncle->_col = BLACK;grandparent->_col = RED;cur = grandparent;parent = cur->_parent;}else//uncle不存在或者存在且为黑（由上面的情况变来）{//      g//   p     u//  c//单旋if (cur == parent->_right){RotateL(grandparent);parent->_col = BLACK;grandparent->_col = RED;}else//双旋{//      g//   p     u//     cRotateR(parent);RotateL(grandparent);cur->_col = BLACK;grandparent->_col = RED;}break;//旋转完就可以退出}}}_root->_col = BLACK;//暴力处理return true;}

红黑树的验证

红黑树的验证分为两步：

  1. 检测其是否满足二叉搜索树(中序遍历是否为有序序列)
  2. 检测其是否满足红黑树的性质
    • 根为黑
    • 不红红
    • 黑路同

是否满足二叉搜索树

介绍搜索二插树时详细介绍过了，这里就不介绍了。

public:void InOrder(){//嵌套一层，类外不能访问私有成员_InOrder(_root);cout << endl;}
private://嵌套一层void _InOrder(Node* root)//中序遍历搜索二叉树是有序的{if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);}

是否满足红黑树的性质

检查的点有三：根为黑，不红红，黑路通；采用两个函数来验证这三点：

IsBalanceTree：检测根是否为黑以及用refNum记录一条路径上有多少个黑色节点。

Check：三个参数，该函数验证不红红和黑路同这两个性质。

  • 第一个用来接受节点
  • 第二个用来接受从到上一层的的黑色节点数量
  • 第三个为先前在IsBalanceTree计算好的黑色节点数量refNum
public：bool IsBalanceTree(){if (_root == nullptr){return true;//空树也是红黑树}if (_root->_col == RED){cout << "err：根为红色" << endl;//根必须为黑色return false;}//验证黑路同原则int refNum = 0;//记录一条路的黑色节点数量Node* cur = _root;while (cur){if (cur->_col == BLACK)//黑色节点{refNum++;//记录黑色个数}cur = cur->_left;}return Check(_root, 0, refNum);//验证不红红，黑路同原则}
private:bool Check(Node* root, int blacknum, const int& refnum){if (root == nullptr){if (blacknum != refnum)//blacknum为遍历完一条路径后的黑色节点个数{cout << "相同路径黑色节点个数不同" << endl;return false;}return true;//到这里说明是一棵红黑树}//不红红原则：用当前节点与父节点比较if (root->_col == RED && root->_parent->_col == RED){cout << "连续的相同红色节点" << endl;return false;}if (root->_col == BLACK)//黑色节点{blacknum++;}return Check(root->_left, blacknum, refnum) && Check(root->_right, blacknum, refnum);//一条一条路径检查，全为真 Check函数才为真}

红黑树与AVL树的比较

红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是 O ( l o g 2 N ) O(log_2 N) O(log2​N) ，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。如C++ STL库中的map和set的底层就用到了红黑树。之后将进行map和set的模拟实现，学习map和set。

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

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

相关文章

虚拟机文件系统根目录上的磁盘空间不足？VMware虚拟机扩容磁盘步骤讲解

虚拟机文件系统根目录上的磁盘空间不足？VMware虚拟机扩容磁盘步骤讲解

VMware虚拟机扩容磁盘步骤讲解 今天使用vmware&#xff0c;想使用Ubuntu虚拟机&#xff0c;结果出现这种情况&#xff1a; 我的环境&#xff1a; Ubuntu20.04 VMWare workstation pro 17 VMware设置 参考链接&#xff1a; https://blog.csdn.net/hktkfly6/article/details…
阅读更多...
2024年9月26日 linux笔记

2024年9月26日 linux笔记

1、提示符 1.1 提示符 1.2 命令格式 1.3 路径 2、指令 2.1 pwd 显示当前路径 2.2 cd 切换路径、改变路径 2.3 mkdir 创建目录 [-p] 创建目录及子目录 mkdir -p dir1/dir2 2.4 rmdir 删除目录 &#xff08;注&#xff1a;不能删除空目录&#xff09; 2.5 ls 显示当前目录文…
阅读更多...
【行为树】06-重新映射树和子树之间的端口

【行为树】06-重新映射树和子树之间的端口

Remapping ports between Trees and SubTrees 重新映射树和子树之间的端口 在CrossDoor示例中&#xff0c;我们看到一个SubTree从其父节点&#xff08;示例中的MainTree&#xff09;的角度看起来像一个单独的叶子节点。 此外,为了避免在非常大的树中发生名称冲突,任何树和子…
阅读更多...
【cache】浅析四种常用的缓存淘汰算法 FIFO/LRU/LFU/W-TinyLFU

【cache】浅析四种常用的缓存淘汰算法 FIFO/LRU/LFU/W-TinyLFU

本文浅析淘汰策略与工作中结合使用、选取&#xff0c;并非针对算法本身如何实现的 文章目录 FIFOLFULRUW-TinyLFU实践与优化监控与调整 FIFO first input first output &#xff0c; 先进先出&#xff0c;即最早存入的元素最先取出&#xff0c; 典型数据结构代表&#xff1a;…
阅读更多...
当大模型成为新一代操作系统，我们如何转型AI产品经理？

当大模型成为新一代操作系统，我们如何转型AI产品经理？

大模型无疑是最近科技圈最炙手可热的时尚单品&#xff0c;跟AIGC能沾上边的工作岗位都成为行业香饽饽。许多产品经理朋友与斯年讨论如何转型AI产品经理&#xff0c;今天想通过用户体验五要素的逻辑框架&#xff0c;谈谈传统型产品经理 VS. AI型产品经理的差异。最后分享几点在转…
阅读更多...
【深度学习】（9）--调整学习率

【深度学习】（9）--调整学习率

文章目录 调整学习率一、学习率的定义二、学习率的作用三、实现调整学习率1. 使用库函数进行调整2. 手动调整学习率 总结 调整学习率 调整学习率的目的是&#xff1a;通过调整学习率&#xff0c;优化训练速度、提高训练稳定性、适应不同的训练阶段以及改善模型性能。那么&…
阅读更多...
不可错过的10款文件加密软件，企业电脑加密文件哪个软件好用

不可错过的10款文件加密软件，企业电脑加密文件哪个软件好用

在信息安全日益重要的今天&#xff0c;企业和个人都需要可靠的文件加密软件来保护敏感数据。以下是2024年不可错过的10款文件加密软件&#xff0c;它们以强大的加密功能和易用性而闻名。 1.安秉加密软件 安秉加密软件是一款专为企业设计的信息安全管理工具&#xff0c;采用驱动…
阅读更多...
Android系统应用安装完成后是如何通知其他应用的？

Android系统应用安装完成后是如何通知其他应用的？

文章目录 具体步骤如下&#xff1a;相关的系统广播&#xff08;Actions&#xff09;&#xff1a;总结&#xff1a; Android系统在应用安装完成后&#xff0c;会通过 广播&#xff08;Broadcast&#xff09;的方式通知其他应用。这个广播称为"应用安装完成广播"&…
阅读更多...
IBM开源新模型，可完美、快速转换PDF文档格式，附源码详细部署教程使用教程

IBM开源新模型，可完美、快速转换PDF文档格式，附源码详细部署教程使用教程

IBM开源新模型&#xff0c;可完美、快速转换PDF文档格式&#xff0c;附源码详细部署教程使用教程。 docling 是一个由 DS4SD&#xff08;Data Science for Social Development&#xff09;团队开发的开源项目&#xff0c;旨在帮助文档化软件项目。该项目提供了一个基于 Flask 的…
阅读更多...
在 OpenEuler 中配置 KVM 虚拟化环境指南

在 OpenEuler 中配置 KVM 虚拟化环境指南

本指南旨在为读者提供一个详细的步骤说明&#xff0c;帮助大家在 OpenEuler 系统中配置 KVM 虚拟化环境。无论您是初学者还是有一定经验的用户&#xff0c;这份指南都将涵盖从环境准备、安装到虚拟机管理的各个方面&#xff0c;确保您能够顺利地搭建并管理自己的虚拟化平台。 …
阅读更多...
写一个算法统计在输入字符串中各个不同字符出现的频度并将结果存入文件（字符串中的合法字符为A-Z这26个字母和0-9这十个数字）

写一个算法统计在输入字符串中各个不同字符出现的频度并将结果存入文件（字符串中的合法字符为A-Z这26个字母和0-9这十个数字）

题目分析&#xff0c;一共需要最多需要36个位置的数组&#xff0c;我们把前十个数组位置给0-9个数字字符存放空间&#xff0c;10-36的数组空间给到A-Z的存放 int main() {printf("请输入一串字符串内容,并且以#结束输入\n");char arr[36], ch;//26个大写字符10个数字…
阅读更多...
重磅！2025年国自然项目指南，发布时间确定！

重磅！2025年国自然项目指南，发布时间确定！

9月25日&#xff0c;基金委官网发布《《2025年度国家自然科学基金项目指南》征订通知》&#xff0c;据通知&#xff0c;《2025年度国家自然科学基金项目指南》预计于2025年1月中旬正式出版&#xff0c;届时将以电子和纸质两种形式同步刊出&#xff0c;纸质版48元\套&#xff0c…
阅读更多...
高校实训产品：教育AI人工智能实训与科研解决方案

高校实训产品：教育AI人工智能实训与科研解决方案

保持前沿、提升就业、低成本的教育AI实训全场景方案 产品概述 AIGC实训云图站解决方案为高校提供了灵活、高效的人工智能实训平台。通过弹性裸金属调度技术和GPU虚拟化&#xff0c;实现高性能与低成本的兼顾&#xff0c;为学生和教师提供不受时间和空间限制的实操机会。平台涵…
阅读更多...
SpringBoot使用validation进行自参数校验

SpringBoot使用validation进行自参数校验

一&#xff1a;介绍 在 SpringBoot 项目开发中&#xff0c;很多与数据库交互的参数需要校验数据正确性。很多小伙伴会把参数判断写进代码里&#xff0c;但是这种写法往往会有低可读性以及多处使用的时候&#xff0c;需要变更验证规则时&#xff0c;不易于维护等缺点。今天给大家…
阅读更多...
五秒Al绘画出图，全球最快的Stable Diffusion教程又来了！秋葉SD零基础入门到精通教程

五秒Al绘画出图，全球最快的Stable Diffusion教程又来了！秋葉SD零基础入门到精通教程

大家好&#xff0c;我是强哥 今年刷爆全网的Stable Diffution 最近出了无需安装的版本&#xff0c;还支持中文使用&#xff01; 但是很多小伙伴说不会用 所以给大家找来了中文教程 非常好上手哦&#xff01; AI绘画Stable Diffusion视频教程 帮助你更好的上手SD智能绘画 …
阅读更多...
基于Java+SQL Server2008开发的（CS界面）个人财物管理系统

基于Java+SQL Server2008开发的（CS界面）个人财物管理系统

一、需求分析 个人财务管理系统是智能化简单化个人管理的重要的组成部分。并且随着计算机技术的飞速发展&#xff0c;计算机在管理方面应用的旁及&#xff0c;利用计算机来实现个人财务管理势在必行。本文首先介绍了个人财务管理系统的开发目的&#xff0c;其次对个人财务管理…
阅读更多...
回归预测|基于蜣螂优化长短期记忆网络的数据回归预测Matlab程序DBO-LSTM 多特征输入单输出 含基础LSTM

回归预测|基于蜣螂优化长短期记忆网络的数据回归预测Matlab程序DBO-LSTM 多特征输入单输出 含基础LSTM

基于蜣螂优化长短期记忆网络的数据回归预测Matlab程序DBO-LSTM 多特征输入单输出 含基础LSTM 文章目录 一、基本原理DBO-LSTM 多特征输入单输出回归预测的原理和流程2.1 蜣螂优化&#xff08;DBO&#xff09;2.2 长短期记忆网络&#xff08;LSTM&#xff09;3.1 数据准备3.2 模…
阅读更多...
代码随想录算法训练营第45天 动态规划part12 |题目： 115.不同的子序列 583. 两个字符串的删除操作 72. 编辑距离 编辑距离总结篇

代码随想录算法训练营第45天 动态规划part12 |题目： 115.不同的子序列 583. 两个字符串的删除操作 72. 编辑距离 编辑距离总结篇

代码随想录算法训练营第45天 动态规划part12 |题目&#xff1a; 115.不同的子序列 583. 两个字符串的删除操作 72. 编辑距离 编辑距离总结篇 文章来源&#xff1a;代码随想录 题目名称&#xff1a;115.不同的子序列 给定一个字符串 s 和一个字符串 t &#xff0c;计算在 s 的子…
阅读更多...
源码-基于springBoot精准扶贫管理系统

源码-基于springBoot精准扶贫管理系统

注册 功能概述 提供帮扶干部自助注册功能&#xff0c;注册登记个人基本信息、所在单位等&#xff0c;管理组织审核和帮扶配对后&#xff0c;注册账号即可登录使用。 使用角色&#xff1a;帮扶人员 贫困户档案管理 功能概述 要是建立和查看贫困户档案&#xff0c;包括家庭信息、…
阅读更多...
Python(五)-函数

Python(五)-函数

目录 函数的定义与调用 特点 语法格式 函数的参数 函数的返回值 函数嵌套调用 变量的作用域 局部变量 全局变量 函数的多种参数 位置参数 关键字参数 默认参数 可变参数 函数的定义与调用 python函数需要使用def关键字来定义,需要先定义,后调用 特点: 先定义…
阅读更多...
最新文章

Copyright @ 2022~2023