曼哈顿距离的定义：两个单元格 (xi, yi) 和 (xj, yj) 之间的曼哈顿距离为 |xi - xj| + |yi - yj|。

题目分析

由曼哈顿距离的定义可知：若要使用其定义求两个点之间的曼哈顿距离，则要求的两个点的坐标必须是已知的。因此，根据题目要求，我们需要依次枚举（去除）每个点，然后再将剩下的点两两一组，使用定义式来求出它们的曼哈顿距离，然后在这些曼哈顿距离中取一个最小值。枚举完毕后，再在这些"对于每次枚举，求出的曼哈顿距离中的最小值"中再取一次它们的最小值。即可解决本问题。
但细心的你可能会发现，这么做会使得算法的时间复杂度过高，因此我们需要对算法进行优化。我们可以先对曼哈顿距离公式进行化简，化简过程如图所示：

由化简后的式子可知，对于任意两个点的曼哈顿距离，我们可以这样求解：
1.先分别求出每个点的横纵坐标之和 以及 横纵坐标之差
2.将这两个点的横纵坐标之和相减并求绝对值，记作a。将这两个点的横纵坐标之差相减并求绝对值，记作b。
3.求a和b中的最大值，记作c。c即为两点之间的曼哈顿距离。

根据这个原理，我们继续对其化简：

因此，我们可以维护两个数组Sxy1和Sxy2。Sxy1数组存储了所有点的横纵坐标之和，Sxy2数组存储了所有点的横纵坐标之差。如果我们要求曼哈顿距离的最大值，那么只需要 用每个数组的最大值减去最小值，求绝对值，并将求出的两个值取最大值 即可。但根据题目的要求，我们需要求的是移除某个点后的曼哈顿距离的最大值所形成的数组中的最小值。因此，我们需要按照以下步骤来解决问题：

1.枚举每个点，求出其 x+y ，并在Sxy1数组中删除。求出其 x-y，并在Sxy2数组中删除。
2.使用曼哈顿距离公式的推论，求出曼哈顿距离的最大值Q。
3.将Q与之前推出的数（即之前推出的Q）做比较，假设Q小于之前推出的数，则更新结果sum为Q，记作min(Q)。
4.将之前删除的 x+y 和 x-y 重新加入数组中，开始下一个数的枚举。
5.完成所有数的枚举遍历后，返回min(Q)。

值得一提的是，对于Sxy1和Sxy2，之前为了便于讲解，一直强调其为两个数组。实际上，该算法涉及到频繁地对Sxy1和Sxy2进行增删改查，这会降低算法的执行效率。对于C++实现，推荐使用multiset 来进行操作。这是一种基于红黑树的数据结构，在本问题中可以大幅降低算法的时间复杂度。

完整代码实现

#include <vector>
#include <set>
#include <math.h>
using namespace std;

class Solution {
public:
    int minimumDistance(vector<vector<int>>& points) {
        multiset<int> Sxy1,Sxy2;
        for(int cptime=1;cptime<=points.size();cptime++)
        {
            Sxy1.emplace(points[cptime-1][0]+points[cptime-1][1]);
            Sxy2.emplace(points[cptime-1][0]-points[cptime-1][1]);
        }
        int sum=INT_MAX;
        for(int cptime=1;cptime<=points.size();cptime++)
        {
            int j=points[cptime-1][0]+points[cptime-1][1];
            int k=points[cptime-1][0]-points[cptime-1][1];
            Sxy1.erase(Sxy1.find(j));
            Sxy2.erase(Sxy2.find(k));
            int temp_max=max(abs(*(Sxy1.rbegin())-*(Sxy1.begin())),abs(*(Sxy2.rbegin())-*(Sxy2.begin())));
            if(temp_max<=sum)
            {
                sum=temp_max;
            }
            Sxy1.emplace(j);
            Sxy2.emplace(k);
        }
        return sum;
    }
};

SignUp

适用于大学/中小学/职场的打卡签到系统

👋 特性

• 支持显示签到日期，签到时间，签到排名。
• 支持同日内签到后不能再次签到，防止重复签到。
• 支持历史记录功能，可以查看签到人员的历史签到记录。
• 支持设置开机自动启动，设备开机后自动启动签到系统，无需手动启动。
• 具有可视化编辑器功能，无需修改源码就可以修改签到人员名单以及在签到界面中的位置。
• 支持通过修改源码限制签到时间，防止签到人员提前签到，可以设置迟到后不可签到。
• 源码采用前后端分离设计，团队协作开发方便快捷。
• 自制仿VS界面皮肤，系统具有实用性的同时兼顾美观。

🧩 应用指南

• 中小学/大学将本程序安装在班班通上，每日早晨学生到校后直接点击自己的名字完成签到。
• 公司将本系统整合到门禁系统中，同时可加入人脸识别系统，员工每日可通过该系统打卡上班。若某陌生人员不在系统名单中，则拒绝该人员进入。

✔️ 使用方式

[quote color="info"]项目Github仓库地址：https://github.com/bertwaver/signup[/quote]

1.直接下载Releases页面中的发布。该页面提供了可供32位操作系统以及64位操作系统运行的版本。

• 本程序仅支持Windows操作系统。经测试，该程序可以在Windows 10及更新的操作系统上正常运行，更早的版本暂时没有测试。
• 如果程序无法启动，请确保你已经安装了 .NET Framework 4.7.2 框架。

2.克隆仓库的源代码并进行编译。

如果你在 Releases 下载的程序始终无法在你的操作系统中运行，那么你可以将本仓库的源代码克隆到要运行本程序的目标机器，并在目标机器上编译源代码来解决该问题。

对于本软件的具体使用问题，请参阅本项目的wiki页面。

🌄 软件截图(加载较慢)

💻 开发教程

请参阅本项目的wiki页面。https://github.com/bertwaver/signup/wiki

📓 关于开源

本项目基于协议 Apache License 2.0 开源。使用本项目源代码时请遵守协议的相关规定。

📧 软件著作权

题目简介

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

[tabs]
[item title="示例一"]
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。[/item]
[item title="示例二"]
输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。[/item]
[/tabs]
1 <= nums.length <= 100
0 <= nums[i] <= 400

代码模板

class Solution {
public:
    int rob(vector<int>& nums) {

    }
};

问题分析

递归

我们以示例一为例，这条街区一共有四个房屋，我们可以从最后一个房屋（即第四个房屋）开始看。如果我们偷第四个房屋，那么第三个房屋我们就不能偷。如果我们不偷第四个房屋，那么第三个房屋就可以偷或者不偷。依次类推，直到我们推到第一个房屋。示例图如图所示：

通过观察我们可以知道，我们从第四个房屋一直推导到第一个房屋的过程中形成了一种二叉树的结构。我们想要求出我们能偷到的最大的钱数，只需要通过深度优先搜索(dfs)的方法遍历整棵树即可。dfs遍历的过程是通过递归实现的。我们通过“递”的过程从根节点（第四个房屋）遍历到了叶子节点（第0个房屋）。然后通过“归”的过程进行回溯，逐渐遍历整棵树，然后对能偷到的钱就行统计，就可以得到我们想要的结果。
这种方法虽然可以得到正确的结果，但是它的时间复杂度却很高。原因在于随着数据量的提升，这棵树的规模将会逐渐增大，程序的执行效率也会逐渐下降。另外，当我们对树进行遍历的过程中，产生了一些重复计算，这些重复计算也会随着数据量的提升而越来越多，这也是导致程序的时间复杂度上升的一个重要原因。

以下是递归实现的一个示例代码，该算法无法通过力扣的全部检查点。

class Solution
{
public:
    int rob(vector<int> &nums)
    {
        return _rob(nums.size(),nums);
    }

private:
    int _rob(int k, vector<int> &_nums)
    {
        if(k<=0)
        {
            return 0;
        }

        int selected=_nums[k-1]+_rob(k-2,_nums); //不要忘记加上当前元素的值
        int unselected=_rob(k-1,_nums);
        return max(selected,unselected);
    }
};

记忆化搜索

正如上方所指出的那样，这个算法的时间复杂度较高的原因之一在于大量的重复计算。那么我们就需要对该算法进行优化，去除这些无效的运算。一个比较好的方法是我们可以引入一个数组"memo"，在每次进行运算时记录当前节点的结果。当我们之后遇到重复的计算时，只需要从"memo"数组中找出相应的结果就行了。

从算法的时间复杂度和空间复杂度的角度来看，这是一种用“空间”换“时间”的方法，我们之前通过使用一部分内存来对结果进行存储，这样CPU需要获得相应的结果的时候只需要从内存中取出之前计算的结果就行了，就不需要再浪费一部分时间来进行相应的计算了。

从上方构建本问题的二叉树的角度来看，这种方法实现了对二叉树的“剪枝”，从而减少了遍历所需要的时间，大大降低了算法的时间复杂度。这种方法叫做记忆化搜索，掌握记忆化搜索的基本思路有利于我们以后使用动态规划来解决问题，因为动态规划也是通过存储重叠子问题的解的方式来提升时间效率的。

本问题的记忆化搜索实现代码如下，该算法能通过力扣的所有检查点：

class Solution
{
public:
    int rob(vector<int> &nums)
    {
        vector<int> memo(nums.size(),-1);
        return _rob(nums.size(),nums,memo);
    }

private:
    int _rob(int k, vector<int> &_nums, vector<int> &_memo)
    {
        if(k<=0)
        {
            return 0;
        }
        if(_memo[k-1]!=-1)
        {
            return _memo[k-1];
        }

        int selected=_nums[k-1]+_rob(k-2,_nums,_memo);
        int unselected=_rob(k-1,_nums,_memo);
        _memo[k-1]=max(selected,unselected);
        return _memo[k-1];
    }
};

初识动态规划 —— 递推关系与状态转移方程

动态规划是一种将问题拆分成一系列小问题的一种解决问题的方法。利用动态规划解决问题时，除了对于动态规划的基本方法的理解以外，更多的还要针对具体问题进行具体分析，思考如何将一个大的问题拆分成几个互不重叠的小问题，列出它的状态转移方程，从而根据它的递推关系一步步地解决这个较大的问题。
针对本问题，我们可以进行下面的分析：

假设只有一个房子，那么想要偷到最大的钱数，我们只需要偷这一个房子就行了，那么 result=nums[0]; 。

假设有两个房子，我们想要偷到最大的钱数，就只能偷其中的钱数最多的那个房子，而另一个房子并不能偷。因为对于两个房子而言，它们一定是相邻的，如果两个房子都偷的话，则会触发警报，这并不满足问题的要求。那么本问题的结果就是 result=max(nums[0],nums[1]);。

假设有三个房子，对于第三个房子，如果我们偷的话，就不能偷第二个房子，只能偷第一个房子。如果不偷的话，我们就可以选择偷第二个房子或者不偷第二个房子，具体偷不偷取决于是否能让我们得到最大的钱数。（不一定非要偷第二个房子才能获得最大的钱数，因为偷了第二个房子就代表偷不了第一个房子，这也是我们需要考虑偷不偷第二个房子的原因）。

对于四个及以上的房子，也是和三个房子同理的。我们将上方的memo数组转换为dp数组。就可以得到以下的递推关系：result=dp[n-1]=max(dp[n-2],nums[n-1]+dp[n-1])；。

这个递推关系就叫做动态规划的状态转移方程。与之前的方法不同的是，这个从“偷一个房子”(小问题)逐步推导，直到推到我们想要的结果“偷n个房子”(大问题)的。因此我们可以通过写一个for循环，来从dp[0]逐步推导至dp[n-1]，从而得到我们想要的结果。
这种方法的优势一在于dp数组也像memo数组一样，通过存储之前已有的状态来避免对于重叠子问题的重复计算。二在于不同于递归的自顶而下，自根节点遍历到每个叶子结点的方法。这种方法是自底而上，自叶子节点向根节点来解决问题的，它去除了递归过程的“递”的过程，只保留了“归”的过程，这使得它并不需要遍历整棵树就可以得到我们想要的结果，从而大大提高了算法的时间效率。
本算法的一个实现代码如下，该算法能通过力扣的所有检查点：

class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.size()==1)
        {
            return(nums[0]);
        }
        else if(nums.size()==2)
        {
            return(max(nums[0],nums[1]));
        }
        else
        {
            vector<int> dp(nums.size());
            dp[0]=nums[0];
            dp[1]=max(nums[0],nums[1]);
            for(int cptime=3;cptime<=nums.size();cptime++)
            {
                dp[cptime-1]=max(dp[cptime-2],dp[cptime-3]+nums[cptime-1]);
            }
            return dp.back();
        }
    }
};

[card title="状态转移方程的边界条件" color="info"]通过观察上方的代码我们可以发现，当只有一个房子或者两个房子的时候，我们并没有使用dp数组进行求解。这是因为对于最初始的这两种情况，它们是可知的或者可以直接计算出来的，这为我们以后对于更多房子的情况下的推导提供了基础。本问题的边界条件如下：

dp[0]=nums[0]; //只有一个房子就只能偷这个房子
dp[1]=max(nums[0],nums[1]); //对于两个房子而言，偷钱数最多的那个房子

假设我们直接把dp[0]或者dp[1]代入状态转移方程中，数组的访问将会越界。而且，假如我们将dp[2]代入状态转移方程后，对于dp[2]=max(dp[1],dp[0]+nums[2])而言，如果没有dp[0]和dp[1]的具体的值，我们也无法得到dp[2]的值，从而无法得到dp[3]乃至dp[n-1]的值。这是我们在本问题中需要设定边界的原因。[/card]

打家劫舍 II

题目简介

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
[tabs]
[item title="示例一"]输入：nums = [2,3,2]输出：3

解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。[/item]
[item title="示例二"]输入：nums = [1,2,3,1]输出：4

解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
偷窃到的最高金额 = 1 + 3 = 4 。[/item]
[item title="示例三"]输入：nums = [1,2,3]输出：3[/item]
[/tabs]
1 <= nums.length <= 100
0 <= nums[i] <= 1000

问题分析

本问题与 打家劫舍I 唯一的不同在于房子连成了环。这导致第一个房子和最后一个房子从本来不紧挨的状态变成了紧挨的状态，进而导致偷了第一个房子后就不能偷最后一个房子，偷了最后一个房子就不能偷第一个房子。所以我们只需要对这两种情况进行分类讨论并列出不同的状态转移方程即可。

假设偷第一家：

边界条件：

stoleone_dp[0]=nums[0]; //只有一家就偷这一家
stoleone_dp[1]=nums[0]; //有两家就只能偷第一家

该情况下的状态转移方程：

if(cptime==number)
{
stoleone_dp[cptime-1]=stoleone_dp[cptime-2]; //不偷最后一家
}
else
{
stoleone_dp[cptime-1]=max(nums[cptime-1]+stoleone_dp[cptime-3],stoleone_dp[cptime-2]); //非最后一家的情况下的状态转移方程，和打家劫舍I类似
}

假设不偷第一家：

边界条件：

unstoleone_dp[0]=0; //只有一家就不偷
unstoleone_dp[1]=nums[1]; //对于两家而言，第一家不偷了，那么可以选择偷第二家或者不偷第二家。但是要使得偷到的钱数最多，只能偷第二家。

该情况下的状态转移方程：

unstoleone_dp[cptime-1]=max(nums[cptime-1]+unstoleone_dp[cptime-3],unstoleone_dp[cptime-2]); //对于非第一家和第二家的状态转移方程，和打家劫舍I类似

最终，我们只需要对这两种分类讨论的情况取最大值即可：

return max(stoleone_dp[number-1],unstoleone_dp[number-1]);

完整代码实现

class Solution {
public:
    int rob(vector<int>& nums) {
        int number=nums.size();
        if(number==1)
        {
            return nums[0];
        }
        else if(number==2)
        {
            return max(nums[0],nums[1]);
        }
        else
        {
            vector<int> stoleone_dp(number,0);
            //偷第一家
            stoleone_dp[0]=nums[0];
            stoleone_dp[1]=nums[0];
            for(int cptime=3;cptime<=number;cptime++)
            {
                if(cptime==number)
                {
                    stoleone_dp[cptime-1]=stoleone_dp[cptime-2];
                }
                else
                {
                    stoleone_dp[cptime-1]=max(nums[cptime-1]+stoleone_dp[cptime-3],stoleone_dp[cptime-2]);

                }
            }
            //不偷第一家
            vector<int>unstoleone_dp(number,0);
            unstoleone_dp[0]=0;
            unstoleone_dp[1]=nums[1];
            for(int cptime=3;cptime<=number;cptime++)
            {
                unstoleone_dp[cptime-1]=max(nums[cptime-1]+unstoleone_dp[cptime-3],unstoleone_dp[cptime-2]);
            }
            int sum=max(stoleone_dp[number-1],unstoleone_dp[number-1]);
            return sum;
        }
    }
}; 

打家劫舍 III —— 树形动态规划

题目简介

问题分析

本问题与之前的问题不同点在于各个房屋之间形成了一棵二叉树。但我们依然可以用动态规划的思想来解决本问题：

状态转移：我们可以用树的后序遍历来遍历整棵树，由于后序遍历是按照 左子树 —— 右子树 —— 根节点的顺序进行遍历的。如果我们在遍历树时引入dp数组进行记录的话，根节点则可以接受到来自其左子树和右子树所记录的信息，这样我们便达到了状态转移的目的。

同时，考虑到每个节点可能存在 选与不选 两种情况。因此，在记录能偷到的钱的最大值时也应该分为这两种情况进行分类讨论，从而保证状态转移的完成。

完整代码实现

class Solution {
public:
    int rob(TreeNode* root) {
        auto result=dfs(root);
        return max(result.first,result.second);
    }
    pair<int,int> dfs(TreeNode* node)
    {
        if(node==nullptr)
        {
            return {0,0};
        }
        pair<int,int>left=dfs(node->left);
        pair<int,int>right=dfs(node->right);

        int stole=node->val+left.second+right.second;
        int unstole=max(left.first,left.second)+max(right.first,right.second);
        return {stole,unstole};
    }
};

算数基本定理又叫唯一分解定理，它说明任意大于1的自然数都可以唯一地分解成质数的幂的乘积。对于任意两个满足条件的数a,b，我们可以通过以下公式进行分解：

其中p1,p2,....，pk表示质数，而a1,a2,....ak以及b1,b2,...bk表示非负整数。如果一个数拆分成的质数中没有这个质数，可以将幂视作0，比如12=(2^2) (3^1) (5^0) (7^0) .....（后面的7,9,11的幂皆为0）。至于为什么不存在非质数，因为假如将其中的一个非质数视作a的一个因子，那它仍然可以继续拆分成几个质数的乘积（即表示a的式子可以继续化简），经过不断化简，最终得到的式子仍然是所有质数的幂相乘所形成的式子。

最大公约数的数学表示

我们以12和6为例，将这两个数用算数基本定理表示，可以得到以下公式(忽略幂为0的质数因子):

要找到最大公约数，我们就要找到一个共同的数，这个共同的数必须既能将6整除，又能将12整除，而且还必须是最大的。而6和12都可以表示为质数因子2和3的幂的乘积的形式，要找到这个最大的数，我们只需要找到其中 每个因子的最小幂的乘积 即可。寻找最小值是为了保证找到的公约数都能将6和12整除。而寻找每个因子是为了保证这个公约数是最大的（即最大公约数），因为一旦在寻找的过程中遗漏了某个因子，那么就相当于找到的是 用最大公约数除以了这个因子 所得到的数，所以导致找到的这个公约数不是最大的。
根据我们的方法，对于因子2，我们应该寻找的是2的1次方，而对于因子3，我们应该寻找的是3的一次方。将它们相乘，我们得到6和12的最大公约数为2x3=6。
综上所述，对于a,b两个数的最大公约数我们可以这样获得： 将a,b两个数用算数基本定理拆解后，对于相同底数的质数因子，取幂相对较小的那个数，然后将它们相乘，得到的即为a,b的最大公约数

最小公倍数的数学表示

我们仍然以6和12为例，要找到其最小公倍数，即要找到一个既可以被6整除，又可以被12整除的数，并且这个数还要是最小的。根据我们寻找最大公约数的方法，这次我们就应该寻找对于6和12的相同底数的两个因子中较大的那个。这样我们就可以保证了这个数都可以被两个数整除（因为这个数是由两个数的最大因子相乘而得来的，无论用哪个数整除，最终都会将共有的因子除掉，最终得到一个整数）。而且它一定是两个数的最小的公倍数，因为这个数不可以再拆分，如果继续拆分的话，相当于除掉了一个或多个质数，这会导致其无法成为6或者12的一个倍数。（想象一下，我们如果将12和6的最小公倍数12再除以一个2，得到了6，它并不是12的倍数。因为将12拆解后为2的二次方乘以3的一次方，而6拆解后为2的一次方乘以3的一次方，6比12少了一个2的一次方，因此无法成为12的倍数。）
综上所述，对于a,b两个数的最小公倍数我们可以这样获得：综上所述，对于a,b两个数的最大公约数我们可以这样获得： 将a,b两个数用算数基本定理拆解后，对于相同底数的质数因子，取幂相对较大的那个数，然后将它们相乘，得到的即为a,b的最小公倍数

最大公约数和最小公倍数的乘积

我们将a,b的最大公约数视作GCD(a,b)，将a,b的最小公倍数视作LCM（a,b）。则可以得到GCD(a,b) x LCM(a,b) = a x b。
推论如下：假设存在 6 和 12，我们将其用算数基本定理进行拆解
6= 2^1(q) x 3^1(t)
12= 2^2(s) x 3^1(d)
6 x 12= 72 = (q) x (t) x (s) x (d)

则GCD(6,12)=2^1(q) x 3^1(d)
LCM(6,12)=2^2(s) x 3^1(t)
则GCD(6,12) x LCM(6,12)= (q) x (t) x (s) x (d) =72=6 x 12

因此，对于a,b而言，GCD(a,b) x LCM(a,b) = a x b。

欧几里得算法

该算法基于以下事实：两个正整数的最大公约数（GCD）不变，即使其中一个数被它们的差替换。
假设存在两个非负正整数a,b且存在a>b而言。GCD(a,b)=GCD(b,a-b)。
证明过程如下：
如果d是a和b的最大公约数，则a=m x d，而b=n x d。（如果你不理解为什么可以这样表示，你需要重新理解前方所提到的知识）
a-b=（m-n）x d。
因此我们可以通过设计算法不断使其相减，最终使得a,b变量的其中一个值变为0，而另外一个值即为我们们要找到的最大公约数。
根据这个原理，我们可以设计两个或者两个以上的数的求最大公约数的算法：

// 最大公约数算法
int gcd(int a, int b)
{
    int tmin = min(a, b);
    int tmax = max(a, b);
    if (tmin != 0)
    {
        tmax = tmax - tmin;
        return gcd(tmin, tmax);
    }
    return tmax;
}
// 最大公约数算法扩展
int tgcd(int a, int b, int c)
{
    return gcd(gcd(a, b), c);
}

由于我们已经在上方得到了最大公约数和最小公倍数的乘积与两个数乘积之间的关系，因此我们可以这样设计求两个数最小公倍数的算法：

int lcm(int a,int b)
{
    return (a*b/gcd(a,b));
}

c++17计算最小公倍数和最大公约数

如果你的编译器支持c++17或更高标准，你可以分别使用lcm()函数和gcd()函数来计算最小公倍数和最大公约数。它包含在头文件numeric下。
详解如下:
https://zh.cppreference.com/w/cpp/numeric/gcd
https://zh.cppreference.com/w/cpp/numeric/lcm
演示代码：

#include <numeric>
using namespace std;

int main()
{
    int a=10,b=20;
    int j=lcm(10,20);
    int k=gcd(10,20);
    return 0;
}

结果为j=20 k=10。

求最大公约数的改良算法

假如有下面一个问题：

我们将公式S化简可以得到S=gcd(a,b,c)。因此，我们可以设计一个gcd算法进行暴力求解。代码如下：

#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
using namespace std;
// 最大公约数算法
int gcd(int a, int b)
{
    int tmin = min(a, b);
    int tmax = max(a, b);
    if (tmin != 0)
    {
        tmax = tmax - tmin;
        return gcd(tmin, tmax);
    }
    return tmax;
}
// 最大公约数算法扩展
int tgcd(int a, int b, int c)
{
    return gcd(gcd(a, b), c);
}

int main()
{
    // 获取并加入数组
    int n;
    cin >> n;
    vector<int> diamonds(n, -1);
    for (int cptime = 1; cptime <= n; cptime++)
    {
        cin >> diamonds[cptime - 1];
    }
    // 组合数学
    vector<vector<int>> combinations;
    for (int i = 1; i <= diamonds.size() - 2; i++)
    {
        for (int j = i + 1; j <= diamonds.size() - 1; j++)
        {
            for (int k = j + 1; k <= diamonds.size(); k++)
            {
                combinations.push_back({diamonds[i - 1], diamonds[j - 1], diamonds[k - 1]});
            }
        }
    }
    // 计算s
    vector<int> s;
    for (int cptime = 1; cptime <= combinations.size(); cptime++)
    {
        int a = combinations[cptime - 1][0];
        int b = combinations[cptime - 1][1];
        int c = combinations[cptime - 1][2];
        s.push_back(tgcd(a, b, c));
    }
    // 寻找最大元素
    vector<int>::iterator it;
    it = max_element(s.begin(), s.end());
    int dis = distance(s.begin(), it);
    // 输出
    vector<int> sum = {combinations[dis][0], combinations[dis][1], combinations[dis][2]};
    sort(sum.begin(), sum.end());
    cout << sum[0] << " " << sum[1] << " " << sum[2];
    return 0;
}

但这存在一个问题。由于我们需要获取到数组中所有可能存在的以三个为一组的组合，因此算法的时间复杂度是O(n^3)。这对于大数据是极其致命的，所以我们需要设计一种更高效的算法。这种算法需要去除获取所有可能的组合的步骤，这是一个三层嵌套循环，正是这个循环让算法的复杂度到了O(n^3)级别。
一种比较好的解决方法如下：我们将每一个数据求出其所有可以被整除的数，并将这个数出现的次数统计下来，哪个数出现的次数等于3，就代表这个数字可以同时整除数组中的三个的数。所有出现次数等于3的数对应的就是题目中的S，而最大的那个数就是S的最大值。有时候一个数字出现的次数也可以大于3，这代表这个数可以将数组中的多个数整除，这时候我们也只需要找出那个最小的组合即可（如题所见，它需要我们找到字典中的最小的那个组合）。这个数字出现的次数可能是4次，5次甚至是6次，但是对于暴力搜索一开始遍历并找出所有可能的组合而言，这种算法的时间复杂度开销要少得很多。
另外值得一提的是，我们在遍历一个数所有可能整除的数字时，我们只需要从1遍历到其二次方根即可，因为对于一个可以被b和c整除的数a而言，总有a=b(小) x c(大)。我们只要遍历出那个比较小的值，另一个比较大的值只需要用a除以这个比较小的值就可以得到了。b和c的分界线是a的平方根，原因在于假设b等于a的平方根时，c也等于a的平方根，当b和c之中的任意一个数再增大时，这个数会变成较大的那个数，所对应的另一个数必定会变成较小的那个数，而这两个数一定是我们在遍历1到a的平方根的过程中已经遍历过的。
综上所述，解决本问题的完整代码如下，本算法的时间复杂度在对数级别：

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <iterator>
#include <math.h>
using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> nums(n, 0);
    for (int cptime = 1; cptime <= n; cptime++)
    {

        cin >> nums[cptime - 1];
    }
    sort(nums.begin(), nums.end());

    // 存储公约数
    map<int,vector<int>> m;
    // 正式遍历
    for (int cptime = 1; cptime <= nums.size(); cptime++)
    {
        int cur_maxnumber = nums[cptime - 1];
        //平方根放缩优化
        for (int ncptime = 1; ncptime <= sqrt(cur_maxnumber); ncptime++)
        {
            if (nums[cptime - 1] % ncptime == 0)
            {
                m[ncptime].push_back(nums[cptime-1]);
                //求较大因数并加入map
                int bignumber=nums[cptime-1]/ncptime;
                //防止重复项
                if(bignumber!=ncptime)
                {
                    m[bignumber].push_back(nums[cptime-1]);
                }
            }
        }
    }
    // 寻找最大公约数及查找算法
    int sumindex = -1;
    vector<int> sums(3,-1);
    map<int, vector<int>>::iterator it;
    for (it=m.begin();it!=m.end();it++)
    {
        if(it->second.size()>=3)
        {
            if(it->first>=sumindex)
            {
                sumindex=it->first;
                sums[0]=it->second[0];
                sums[1]=it->second[1];
                sums[2]=it->second[2];
            }
        }
    }
    // 输出答案
    sort(sums.begin(),sums.end());
    cout<<sums[0]<<" "<<sums[1]<<" "<<sums[2];
    return 0;
}

二叉搜索树(binary search tree)是一种具有以下性质的二叉树(假设树不为空)：
1.若其左子树不为空，则其左子树的所有节点的值都小于其根节点的值
2.若其右子树不为空，则其右子树的所有节点的值都大于其根节点的值
3.若将其中的任意一个节点视为根节点的左右子树也都为二叉搜索树

因为二叉搜索树具有上述的特点，因此如果我们需要查找其中的一个值时，若该值小于当前节点的值则向左遍历，若该值大于当前节点的值则向右遍历，从而可以快速地查找到所需要的值。这种分治的方法类似于数组中的二分查找，而不是从头开始依次遍历，暴力查找所需的值，因此查找效率较高。另外，由于二叉搜索树是一种非线性的链式结构，因此也像链表一样，增加和删除效率也很高。

[card title="二叉搜索树的时间复杂度" color="success"]对于普通的二叉搜索树而言，无论是进行增删改查中的哪一种方式，时间复杂度最低都是 O(log n) ，最高都是 O(n)。理由如下：
假设该二叉树是一种平衡二叉树（即长度最长的叶子节点与长度最短的叶子节点的高度差小于或等于1），比如下方这种情况，那么增删改查的效率最高，为O(log n)。(见下方图1)
但假设该二叉树极度不平衡，那么左子树和右子树的高度相差就会很大，严重情况下甚至能退化成链表。这样的话增删改查的时间复杂度最高会降低至O(n)(类似于数组的暴力搜索)。(见下方图2)

[/card]

二叉搜索树的建树

二叉搜索树是二叉树的一种，因此我们首先先对树的节点进行定义。每个节点应该具有左节点的指针，右节点的指针，当前节点的值以及当前节点的构造函数。

struct TreeNode
{
    TreeNode* left;
    TreeNode* right;
    int val;
    TreeNode(int x):left(nullptr),right(nullptr),val(x){}
};

我们定义一个bst类并且新增一个init函数用于树的初始构建。这个函数接受一个vector数组，然后依次遍历完成树的构建。如果数组为空，那么返回空指针，否则依次调用add函数将数组中的每个元素添加到树中(add函数的实现会在下方写出)。构建完成后，返回指向根节点的指针。

    TreeNode* init(vector<int> &nums)
    {
        if(nums.empty()==true)
        {
            return nullptr;
        }
        //创建根节点
        TreeNode*root=new TreeNode(nums[0]);
        //循环遍历将数组中的数加入树中
        for(int cptime=2;cptime<=nums.size();cptime++)
        {
            add(root,nums[cptime-1]);
        }
        //存储根节点
        bst::root=root;
        //返回根节点
        return root;
    }

假设我们使用用例 63 39 97 29 86 99 5 61 建树，形成的结构如下图所示：
[acc status="close" title="可视化执行(加载较慢需等待片刻)"]

[/acc]
[card title="关于nullptr" color="danger"]nullptr是c++11中引入的新关键字，用于表示空指针。是一种相较于直接宏定义NULL更安全的一种表示空指针的方法。如果你的编译器报错，请检查你的编译器是否支持c++11标准。相关资料：https://zh.cppreference.com/w/cpp/language/nullptr[/card]

根节点的封装

我们在建树的过程中返回并存储了根节点的指针。并且我们将根节点的指针存储到了类中的root变量中，而root是一个私有成员变量，我们并不能在类外手动地去修改它，这样可以防止手动修改导致的一些问题。

private:
    //存储根节点
    TreeNode* root;

如果我们在后方进行增删改查时需要获取根节点，我们可以设计一个公共函数来获取它。

public:
    //获取根节点
    TreeNode* Getroot()
    {
        return bst::root;
    }

二叉搜索树的新增

我们声明一个add函数用于执行二叉树的新增操作，这个函数需要接受二叉树的根节点和需要插入二叉树的值。

    bool add(TreeNode* node,int value)
    {}

由于二叉搜索树中的各个节点的值各不相同，因此在设计函数时，如果插入的值在二叉树中已经存在，则直接返回，不进行新数据的插入。（返回值可以设计成一个bool函数，当进行这种操作时，返回false，使函数的调用者知晓新的值已存在于树中，因此不进行插入操作。其它正常插入的情况则返回true）。
我们在执行插入操作时，要保证插入完成后继续满足二叉搜索树的三种性质。因此，我们不能在二叉搜索树的中间位置或根节点（假设根节点已存在）执行插入操作，因为这样会破坏二叉搜索树原有的结构，这意味着我们只能在二叉搜索树的叶子节点插入元素。
要找到插入节点的合适位置，我们首先要将需要插入的值与根节点作比较，如果这个值小于根节点，则将这个值与根节点的左节点作比较，假设这个值又比根节点的左节点大，我们就继续往根节点的左节点的右节点遍历，以此类推，直到找到一个合适的空节点，我们将其放置在这个位置上，并且使其父节点的指针指向它，并且进行返回操作。

    //新增操作，手动调用请传入根节点，递归可传入其它节点
    bool add(TreeNode* node,int value)
    {
        if(value==node->val)
        {
            //传入相同值，不符合二叉搜索树定义
            return false;
        }
        else if(value<node->val)
        {
            if(node->left==nullptr)
            {
                TreeNode* tree=new TreeNode(value);
                node->left=tree;
                return true;
            }
            else
            {
                add(node->left,value);
                return true;
            }
        }
        else if(value>node->val)
        {
            if(node->right==nullptr)
            {
                TreeNode* tree=new TreeNode(value);
                node->right=tree;
                return true;
            }
            else
            {
                add(node->right,value);
                return true;
            }
        }
    }

[quote color="primary"]我们在每次比较完成后调用函数本身再进行比较的方法叫做递归。因为无论将二叉搜索树的哪个节点再视为根节点，所形成的树也都是一颗二叉搜索树。因此当需要插入的值大于或小于当前节点的值时，我们可以将当前节点的左节点或右节点的指针传入add函数中，来继续向下寻找可插入该值的位置，找到后则通过return一层层地跳出这个嵌套结构。由于在递归过程中，我们调用add函数时都需要传入一个用于和所需要插入的值作比较的节点，因此在我们手动调用该函数时也需要传入树的根节点。如果我们需要在手动调用时不需要传入根节点，那我们可以设计一个在public:下的add函数用于手动调用，然后这个add函数再调用private:下的add_sort函数，这个函数的设计与上面的设计相同。在递归过程中让add_sort函数调用自己，完成插入操作后再逐步返回。这是一种更安全规范的方法。
[/quote]

二叉搜索树的查找

在查找算法的声明上，我们可以依旧参考新增函数的设计，接受一个根节点和一个需要查找的值，然后按照递归的方法来查找这个值。在返回值的类型方面，通常情况下设计成指向查找到的节点的指针。但为了提高函数的复用性，我们将其设计成从栈底到栈顶依次包含从根节点到该节点所有路径的节点的指针的栈。这样当我们在使用其它函数调用这个查找函数时，就可以很轻易地找到它的父节点来进行一些调整。

    //查询操作，返回查询到节点的指针的栈，手动调用请传入根节点
    //栈底:根节点 栈顶:子节点(如果根节点或子节点不存在则栈顶为nullptr)
    stack<TreeNode*> search(TreeNode* node,int value)
    {
        stack<TreeNode*> st;
        search_algo(node,value,st);
        return st;
    }
    //查询算法底层实现
    void search_algo(TreeNode* node,int value,stack<TreeNode*> &st)
    {
        st.push(node);
        if(node==nullptr)
        {
            return;
        }
        else if(node->val==value)
        {
            return;
        }
        else if(value<node->val)
        {
            search_algo(node->left,value,st);
            return;
        }
        else if(value>node->val)
        {
            search_algo(node->right,value,st);
            return;
        }
    }

[quote color="danger"]注意在函数的声明中将栈以引用的方式传入，否则在递归过程中栈将不能被正确构建。[/quote]

中序遍历的有序性

如果说建树是将含有树节点的数组转换为二叉搜索树的结构，那么遍历则是这种操作的反向操作。树的遍历有四种方法，分别是前序遍历，中序遍历，后序遍历，层序遍历，而中序遍历则是按照 左子树->根节点->右子树的顺序将树转换为数组。由于在建树过程中较小的数总是会向左子树构建，而较大的数总是会向右子树构建，因此在中序遍历的过程中，形成的数组也是一种从小到大升序排列的有序结构，示意图如下：

    //中序遍历
    void inorder(TreeNode*node,vector<int> &nums)
    {
        if(node==nullptr)
        {
            return;
        }
        inorder(node->left,nums);
        nums.push_back(node->val);
        inorder(node->right,nums);
    }

[card title="二叉树的遍历方法" color="success"]二叉树的四种遍历方法请见：https://www.hello-algo.com/chapter_tree/binary_tree_traversal/[/card]

删除度为0的节点

我们声明一个函数用于树的删除操作，并且分为度为0，1，2三种情况进行处理。（度指的是该节点拥有的子节点的数量，最小为0，最大为2，假设该节点的左右节点指针都为空，那么度就为0，如果该节点的左右节点指针都不为空，那么度就为2）
接下来我们对度为0的节点的情况进行处理:
度为0意味着该节点的左右指针都为空，那么这个节点必然是二叉搜索树的叶子节点或者单一的根节点。如果该节点是叶子节点，则删除该节点不会对其它节点造成任何影响，因此我们直接将这个节点删除并且将父节点指向这个节点的指针设为空指针即可。如果该节点是单一的根节点，那么我们就需要将该根节点设为nullptr，因为删除该节点后，这棵树将成为一个空树。
[quote color="danger"]在删除叶子节点时必须要将父节点指向这个节点的指针设为nullptr，否则删除该节点后，父节点的指针将继续指向原来该节点的所在的内存，在以后执行诸如查询操作时，强制地访问该内存将会导致程序崩溃。对于如何找到节点的父节点，因为我们在设计查询该节点的函数时使用了栈来存储路径，因此可以轻易地通过将该节点出栈的方式来找到父节点，否则就需要自行编写一套算法来找到父节点。[/quote]

        //传入不存在的根节点或者未找到相应元素执行的操作
        if(s_value.top()==nullptr)
        {
            return false;
        }
        //度为0的节点执行的操作
        else if(s_value.top()->left==nullptr && s_value.top()->right==nullptr)
        {
            if(is_root==true)
            {
                s_value.top()= nullptr;
            }
            else
            {
                TreeNode* tmp=s_value.top();
                s_value.pop();
                if(s_value.top()->left==tmp)
                {
                    delete tmp;
                    s_value.top()->left=nullptr;
                }
                else
                {
                    delete tmp;
                    s_value.top()->right=nullptr;
                }
            }
            return true;
        }

删除度为1的节点

对于度为1的节点，同样也要分为两种情况：要删除的节点是根节点或不为根节点。如果是根节点的话，我们需要在删除该节点后，将其子节点设为根节点。如果不是根节点，则直接将其父节点的指向该节点的指针指向其子节点并且删除该节点即可。因为如果其父节点的右指针指向该节点，代表该节点的数值大于其父节点的数值，而即使该节点的左指针指向了一个小于该节点的值，那么这个值也是一定大于其父节点的父节点的值的，否则拥有这个值的节点不会作为其父节点的父节点的右子树中的一个节点，而应该成为其父节点的父节点的左子树的一个节点。综上所述，直接将我们要删除的节点的父节点直接指向其子节点并且删除该节点是正确的。

        //度为1的节点执行的操作
        else if((s_value.top()->left==nullptr) != (s_value.top()->right==nullptr))
        {
            if(is_root==true)
            {
                if(s_value.top()->left!=nullptr)
                {
                    bst::root=s_value.top()->left;
                    delete s_value.top();
                }
                else
                {
                    bst::root=s_value.top()->right;
                    delete s_value.top();
                }
            }
            else
            {
                TreeNode* grandparent=nullptr;
                TreeNode* parent=nullptr;
                TreeNode* son=nullptr;
                parent=s_value.top();
                s_value.pop();
                grandparent=s_value.top();
                if(parent->left!=nullptr)
                {
                    son=parent->left;
                }
                else
                {
                    son=parent->right;
                }
                //非法操作，直接返回
                if(parent->val==grandparent->val)
                {
                    return false;
                }
                else if(parent->val<grandparent->val)
                {
                    grandparent->left=son;
                    delete parent;
                }
                else if(parent->val>grandparent->val)
                {
                    grandparent->right=son;
                    delete parent;
                }
            }
            return true;
        }

删除度为2的节点

删除方法简介

要删除度为2的节点，我们需要考虑删除对该节点的左子树和右子树的影响，不需要考虑对该节点的父节点以上的节点的影响，因为假设需要删除的节点是其父节点的右子树的根节点，我们将需要删除的节点的左右子树中的任意一个节点当作该节点，它的值都是比需要删除的节点的父节点的值要大的。基于这个特点，我们可以分为两种情况：将需要删除的节点的左子树中的最大值的节点移动到该位置并删除需要删除的节点或者将需要删除的节点右子树中的最小值的节点移动到该位置并删除需要删除的节点。

删除方法的随机获取

度为2的节点删除方法有两种，对于具体采用哪种方法，我们可以在每次要执行删除操作时通过生成一个0或1的随机数来实现，这样在经过多轮删除后，二叉搜索树可以尽可能地保持平衡，而不是逐渐向一个固定的方向倾斜并退化。

            //生成随机数，用于后方方法的选择
            mt19937 ge(random_device{}());
            bernoulli_distribution bd(0.5);
            bool way=bd(ge);

[quote color="danger"]这种生成随机数的方法利用了梅森旋转算法作为生成器的算法并且使用伯努利分布来限制生成随机数的范围，这是在c++11中新引入的一种方法。相比于直接使用时间戳来生成随机数的经典方法( srand(); rand(time (0)); )而言，虽然生成的也是一种伪随机数，但其随机性更强。如果你的编译器报错，请检查你的编译器是否支持c++11标准。相关资料：https://zh.cppreference.com/w/cpp/header/random[/quote]

获取所有节点的值

在选择完删除的方法后，我们需要找到可以替代这个待删除的节点的值。比如我们采用利用右子树中的最小值替代待删除的节点的方法，那我们就需要找到右子树的最小值。我们前面提到过二叉搜索树的中序遍历是有序的，因此我们可以通过中序遍历来获取到树中所有元素的值，然后找到待删除的值的下一个值即可。

            //获得中序遍历数组
vector<int> vec_search;
inorder(bst::root,vec_search);

删除元素

在找到用于替代待删除的节点的值后，我们将那个用于替代的值的节点删除（同样递归调用删除函数来删除那个节点），然后将待删除的节点的值设为用于替代的节点的值。

        //度为2的节点执行的操作
        else if(s_value.top()->left!=nullptr && s_value.top()->right!=nullptr)
        {
            //生成随机数，用于后方方法的选择
            mt19937 ge(random_device{}());
            bernoulli_distribution bd(0.5);
            bool way=bd(ge);
            //获得中序遍历数组
            vector<int> vec_search;
            inorder(bst::root,vec_search);
            //将当前节点替换为左子树最大节点
            if(way==1)
            {
                int node_index= distance(vec_search.begin(),find(vec_search.begin(),vec_search.end(),s_value.top()->val));
                bst::remove(bst::root,vec_search[node_index-1]);
                s_value.top()->val=vec_search[node_index-1];
            }
            //将当前节点替换为右子树最小节点
            else
            {
                int node_index=distance(vec_search.begin(),find(vec_search.begin(),vec_search.end(),s_value.top()->val));
                bst::remove(bst::root,vec_search[node_index+1]);
                s_value.top()->val=vec_search[node_index+1];
            }
            return true;
        }

二叉搜索树的修改

要修改二叉搜索树的值，只需要调用删除函数删除旧的值，然后调用新增函数来增加新的值即可。

    //修改节点，手动调用请传入根节点
    bool edit(TreeNode*node,int old_val,int new_val)
    {
        if(bst::remove(node,old_val)==false)
        {
            return false;
        }
        if(bst::add(node,new_val)==false)
        {
            return false;
        }
        return true;
    }

完整代码

//二叉搜索树
#include <vector>
#include <stack>
#include <random>
#include <iterator>
#include <algorithm>
#include <iostream>
using namespace std;

struct TreeNode
{
    TreeNode* left;
    TreeNode* right;
    int val;
    TreeNode(int x):left(nullptr),right(nullptr),val(x){}
};

class bst{
public:
    //初始化返回根节点
    TreeNode* init(vector<int> &nums)
    {
        if(nums.empty()==true)
        {
            return nullptr;
        }
        //创建根节点
        TreeNode*root=new TreeNode(nums[0]);
        //循环遍历将数组中的数加入树中
        for(int cptime=2;cptime<=nums.size();cptime++)
        {
            add(root,nums[cptime-1]);
        }
        //存储根节点
        bst::root=root;
        //返回根节点
        return root;
    }

    //新增操作，手动调用请传入根节点，递归可传入其它节点
    bool add(TreeNode* node,int value)
    {
        if(value==node->val)
        {
            //传入相同值，不符合二叉搜索树定义
            return false;
        }
        else if(value<node->val)
        {
            if(node->left==nullptr)
            {
                TreeNode* tree=new TreeNode(value);
                node->left=tree;
                return true;
            }
            else
            {
                add(node->left,value);
                return true;
            }
        }
        else if(value>node->val)
        {
            if(node->right==nullptr)
            {
                TreeNode* tree=new TreeNode(value);
                node->right=tree;
                return true;
            }
            else
            {
                add(node->right,value);
                return true;
            }
        }
    }

    //查询操作，返回查询到节点的指针的栈，手动调用请传入根节点
    //栈底:根节点 栈顶:子节点(如果根节点或子节点不存在则栈顶为nullptr)
    stack<TreeNode*> search(TreeNode* node,int value)
    {
        stack<TreeNode*> st;
        search_algo(node,value,st);
        return st;
    }

    //删除操作，手动调用请传入根节点
    bool remove(TreeNode*node,int value)
    {
        stack<TreeNode*> s_value = search(node,value);
        bool is_root=s_value.size()==1? true:false;
        //传入不存在的根节点或者未找到相应元素执行的操作
        if(s_value.top()==nullptr)
        {
            return false;
        }
        //度为0的节点执行的操作
        else if(s_value.top()->left==nullptr && s_value.top()->right==nullptr)
        {
            if(is_root==true)
            {
                s_value.top()= nullptr;
            }
            else
            {
                TreeNode* tmp=s_value.top();
                s_value.pop();
                if(s_value.top()->left==tmp)
                {
                    delete tmp;
                    s_value.top()->left=nullptr;
                }
                else
                {
                    delete tmp;
                    s_value.top()->right=nullptr;
                }
            }
            return true;
        }
        //度为1的节点执行的操作
        else if((s_value.top()->left==nullptr) != (s_value.top()->right==nullptr))
        {
            if(is_root==true)
            {
                if(s_value.top()->left!=nullptr)
                {
                    bst::root=s_value.top()->left;
                    delete s_value.top();
                }
                else
                {
                    bst::root=s_value.top()->right;
                    delete s_value.top();
                }
            }
            else
            {
                TreeNode* grandparent=nullptr;
                TreeNode* parent=nullptr;
                TreeNode* son=nullptr;
                parent=s_value.top();
                s_value.pop();
                grandparent=s_value.top();
                if(parent->left!=nullptr)
                {
                    son=parent->left;
                }
                else
                {
                    son=parent->right;
                }
                //非法操作，直接返回
                if(parent->val==grandparent->val)
                {
                    return false;
                }
                else if(parent->val<grandparent->val)
                {
                    grandparent->left=son;
                    delete parent;
                }
                else if(parent->val>grandparent->val)
                {
                    grandparent->right=son;
                    delete parent;
                }
            }
            return true;
        }
        //度为2的节点执行的操作
        else if(s_value.top()->left!=nullptr && s_value.top()->right!=nullptr)
        {
            //生成随机数，用于后方方法的选择
            mt19937 ge(random_device{}());
            bernoulli_distribution bd(0.5);
            bool way=bd(ge);
            //获得中序遍历数组
            vector<int> vec_search;
            inorder(bst::root,vec_search);
            //将当前节点替换为左子树最大节点
            if(way==1)
            {
                int node_index= distance(vec_search.begin(),find(vec_search.begin(),vec_search.end(),s_value.top()->val));
                bst::remove(bst::root,vec_search[node_index-1]);
                s_value.top()->val=vec_search[node_index-1];
            }
            //将当前节点替换为右子树最小节点
            else
            {
                int node_index=distance(vec_search.begin(),find(vec_search.begin(),vec_search.end(),s_value.top()->val));
                bst::remove(bst::root,vec_search[node_index+1]);
                s_value.top()->val=vec_search[node_index+1];
            }
            return true;
        }
    }

    //修改节点，手动调用请传入根节点
    bool edit(TreeNode*node,int old_val,int new_val)
    {
        if(bst::remove(node,old_val)==false)
        {
            return false;
        }
        if(bst::add(node,new_val)==false)
        {
            return false;
        }
        return true;
    }

    //获取根节点
    TreeNode* Getroot()
    {
        return bst::root;
    }

    //中序遍历
    void inorder(TreeNode*node,vector<int> &nums)
    {
        if(node==nullptr)
        {
            return;
        }
        inorder(node->left,nums);
        nums.push_back(node->val);
        inorder(node->right,nums);
    }

private:
    //存储根节点
    TreeNode* root;

    //查询算法底层实现
    void search_algo(TreeNode* node,int value,stack<TreeNode*> &st)
    {
        st.push(node);
        if(node==nullptr)
        {
            return;
        }
        else if(node->val==value)
        {
            return;
        }
        else if(value<node->val)
        {
            search_algo(node->left,value,st);
            return;
        }
        else if(value>node->val)
        {
            search_algo(node->right,value,st);
            return;
        }
    }
};

给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:

1.创建一个根节点，其值为 nums 中的最大值。
2.递归地在最大值 左边 的 子数组前缀上 构建左子树。
3.递归地在最大值 右边 的 子数组后缀上 构建右子树。

返回 nums 构建的 最大二叉树 。

[tabs]
[item title="示例一"]

输入：nums = [3,2,1,6,0,5]
输出：[6,3,5,null,2,0,null,null,1]
解释：递归调用如下所示：

• [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。

  • [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。

    • 空数组，无子节点。

    • [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。

      • 空数组，无子节点。
      • 只有一个元素，所以子节点是一个值为 1 的节点。

  • [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。

    • 只有一个元素，所以子节点是一个值为 0 的节点。
    • 空数组，无子节点。

  [/item]
  [item title="示例二"]

  

  输入：nums = [3,2,1]
  输出：[3,null,2,null,1]
  [/item]
  [/tabs]

提示：
1 <= nums.length <= 1000
0 <= nums[i] <= 1000
nums 中的所有整数 互不相同

代码模版

  struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
      };

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
    }
};

[card title="tips" color="info"]后文建树过程中提到的遍历数组指的是遍历此处传入的nums数组。[/card]

初步分析——建树

最大二叉树中的子节点的数值总是小于父节点的数值，并且要构建最大二叉树，我们需要找出其中的最大的那一个数作为根节点。这个根节点的左边的最大的数作为根的左子节点，这个根节点右边的最大的数作为根的右子节点作为根的右子节点，以此类推。因此，我们可以维护一个栈。从数组的第一个数开始遍历。如果栈为空，则直接将当前遍历的数直接入栈。如果栈不为空，则考虑下面的情况：
1.如果当前的数小于栈顶的数，则意味着这个数应该作为栈顶的数的右子节点（这个数作为栈顶的右子节点而不作为左子节点的原因在于这个数在数组中的位置一定是在栈顶的数的后方的，因此如果这个数小于栈顶的数，则只能作为栈顶的数的右子节点而不是左子节点），则我们将栈顶的数的右指针指向这个数并且将这个节点压栈。
2.如果当前的数大于栈顶的数，则意味着栈顶的数应该作为这个数的左子节点(也是从这两个数在数组中的位置进行考虑，这个数大于栈顶的数且在栈顶的数的右方，则栈顶的数肯定是这个数的左子节点或者这个数的左子节点的子节点)。因此我们需要将栈顶的数进行出栈，并且让这个数的左子节点指向它。通过不断的出栈并且设置这个数的左子节点，这个数将会指向原来栈中小于这个数但是相对于整个栈而言最大的那个数，也就是栈底的那个节点。完成操作后，原来栈中的元素则会作为这个数左节点，而这个数则作为整个树的根节点，我们将这个树压入栈中。
不断重复这个操作，如果再往后的数满足情况1，则后面的数会作为这棵具有左子节点但不具有右子节点的树的右子节点。如果满足情况2，则这颗树会作为新的树的左子节点。随着遍历的不断进行，最大二叉树就会被不断构建出来。下面是示例一的构建详情：

为什么栈底的元素总是栈中最大的元素

在上方建树过程中，一旦我们遍历到的数组中的元素（相对于栈中的元素是较新的数）小于栈顶的元素，则这个数将作为原来的栈顶的数的右节点并且被压入栈中。相反，如果新的数大于栈顶的元素，则这个栈顶的元素会被弹出栈并且作为这个新数的左子节点，然后这个带有原来栈顶元素的新数会被压入栈中。这样使得原来栈顶中小于这个数的元素被弹出了栈，取而代之的是一颗新数作为根节点的树，原来的栈顶元素虽然没有消失，变成了这个新树中的一个左子节点，但当我们后面进行比较时，比较的是在这个栈中的树的根节点的那个数的大小。而作为最大二叉树而言，根节点无疑是最大的那个数，这使得如果在后面继续遍历和比较操作时，比这个数小的数会不断被压入栈中并作为原来比较大的数的右节点，而如果后面一旦有比这个数大的数，原来栈底相对较大的那个数会被弹出栈并作为新的大的树的左子节点，新的大的树会再次入栈，成为栈底元素。通过这种操作，每次新数压栈完成后栈底的元素总是最大的，栈顶的元素总是最小的。这种类似于单增数列或单减数列的具有单调性的栈称为 单调栈 。通过单调栈的应用，我们可以快速地完成最大二叉树的构建过程。相关演示视频如下：
[BiliVideo]

[/BiliVideo]

回溯并找到树的根节点

完成数组的遍历操作后我们就完成了整棵树的构建。但我们需要通过回溯来找到整棵树的根节点。最大二叉树的特点在于根节点是整棵树中最大的那个数，而在我们构建的单调栈中，栈底的元素就是最大的那个数。因此我们只需要通过不断的出栈操作，来找到栈底的那个元素所对应的指针，就找到了整棵树的根节点。

最终代码

#include <vector>
#include <stack>
using namespace std;
struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
      };
class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        stack<TreeNode*> stk;
        for(int i=0;i<nums.size();i++)
        {
            TreeNode* cur=new TreeNode(nums[i]);
            while(stk.empty()==false && stk.top()->val<=nums[i])
            {
                cur->left=stk.top();
                stk.pop();
            }
            if(stk.empty()==false)
            {
                stk.top()->right=cur;
            }
            stk.push(cur);
        }
        TreeNode *root=nullptr;
        while(stk.empty()==false)
        {
            root=stk.top();
            stk.pop();
        }
        return root;
    }
};

奖品随机分布在3扇门后，客户随机选择其中一扇，主持人打开另外两扇中任意没有奖品的一扇，问客户选择以下哪种策略赢面更大：

1.坚持原来的选择

2.改选剩下的那扇未打开的门

测试代码及结果

[tabs]
[item title="测试代码"]

#include <iostream>
#include <random>
#include <vector>

using namespace std;

int get_random_number(int a, int b)
{
    random_device rd;
    mt19937 gen(rd());
    uniform_int_distribution<> distrib(a, b);
    int random_number = distrib(gen);
    return random_number;
}

int main()
{
    int test_time = 0, right_door = 0, right_time = 0, choose_door = 0, open_door = 0;
    double sum = 0;
    vector<int> wait_open_door;
    cout << "请输入测试次数" << endl;
    cin >> test_time;
    cout << "第一次测试：不更改门";
    for (int cptime = 1; cptime <= test_time; cptime++)
    {
        right_door = get_random_number(1, 3);
        choose_door = get_random_number(1, 3);
        if (right_door == choose_door)
        {
            wait_open_door.clear();
            for (int ncptime = 1; ncptime <= 3; ncptime++)
            {
                if (ncptime != choose_door)
                {
                    wait_open_door.push_back(ncptime);
                }
            }
            open_door = wait_open_door[get_random_number(0, wait_open_door.size() - 1)];
            right_time++;
        }
        else if (right_door != choose_door)
        {
            wait_open_door.clear();
            for (int ncptime = 1; ncptime <= 3; ncptime++)
            {
                if (ncptime != choose_door && ncptime != right_door)
                {
                    open_door = ncptime;
                }
            }
        }
    }
    sum = static_cast<double>(right_time) / static_cast<double>(test_time);
    cout << "测试完毕。" << endl << "测试次数：" << test_time << endl << "概率为：" << sum << endl;
    cout << "第二次测试：更改门";
    sum = 0, right_door = 0, right_time = 0, choose_door = 0, open_door = 0;
    wait_open_door.clear();
    for (int cptime = 1; cptime <= test_time; cptime++)
    {
        right_door = get_random_number(1, 3);
        choose_door = get_random_number(1, 3);
        if (right_door == choose_door)
        {
            wait_open_door.clear();
            for (int ncptime = 1; ncptime <= 3; ncptime++)
            {
                if (ncptime != choose_door)
                {
                    wait_open_door.push_back(ncptime);
                }
            }
            open_door = wait_open_door[get_random_number(0, wait_open_door.size() - 1)];
            int temp = 0;
            for (int ncptime = 1; ncptime <= 3; ncptime++)
            {
                if (ncptime != choose_door && ncptime != open_door)
                {
                    temp = ncptime;
                }
            }
            choose_door = temp;
        }
        else if (right_door != choose_door)
        {
            wait_open_door.clear();
            for (int ncptime = 1; ncptime <= 3; ncptime++)
            {
                if (ncptime != right_door && ncptime != choose_door)
                {
                    open_door = ncptime;
                }
            }
            int temp = 0;
            for (int ncptime = 1; ncptime <= 3; ncptime++)
            {
                if (ncptime != choose_door && ncptime != open_door)
                {
                    temp = ncptime;
                }
            }
            choose_door = temp;
        }
        if (choose_door == right_door)
        {
            right_time++;
        }
    }
    sum = static_cast<double>(right_time) / static_cast<double>(test_time);
    cout << "测试完毕。" << endl << "测试次数：" << test_time << endl << "概率为：" << sum << endl;
}

[/item]
[item title="100000次测试结果"]
请输入测试次数
100000
第一次测试：不更改门测试完毕。
测试次数：100000
概率为：0.33103
第二次测试：更改门测试完毕。
测试次数：100000
概率为：0.66814
[/item]
[item title="1000000次测试结果"]
请输入测试次数
1000000
第一次测试：不更改门测试完毕。
测试次数：1000000
概率为：0.333417
第二次测试：更改门测试完毕。
测试次数：1000000
概率为：0.666994
[/item]
[item title="一亿次测试结果"]
请输入测试次数
100000000
第一次测试：不更改门测试完毕。
测试次数：100000000
概率为：0.333328
第二次测试：更改门测试完毕。
测试次数：100000000
概率为：0.66656
剑客云提供云计算支持：https://cloud.swordsman.com.cn/
[/item]
[/tabs]

总结

如果每次不选择更改，那么概率将趋近于三分之一。如果每次都选择更改，那么概率将趋近于三分之二。

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

示例 1：
输入：head = [4,2,1,3]
输出：[1,2,3,4]

示例 2：
输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]

示例 3：
输入：head = []
输出：[]

提示：

链表中节点的数目在范围 [0, 5 * 104] 内
-105 <= Node.val <= 105

进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

模板

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {

    }
};

思路

转换为vector动态数组，使用排序算法进行排序，然后用排序后的结果替换掉原来的链表。（无需考虑链表空间的拓展，因为排序后的元素数量必和原链表中的元素数量相同）
[quote color="danger"]在转换的过程中要注意验证空指针。[/quote]

代码

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        vector<int> a;
        ListNode* b;
        b = head;
        while (b!=nullptr && b->next != nullptr)
        {
            a.push_back(b->val);
            b = b->next;
        }
        if (b != nullptr)
        {
            a.push_back(b->val);
        }
        sort(a.begin(), a.end());
        b = head;
        for (int cptime = 0; b!=nullptr && b->next != nullptr;cptime++ )
        {
            b->val = a[cptime];
            b = b->next;
        }
        if (b != nullptr)
        {
            b->val = a[a.size() - 1];
        }
        return head;
    }
};

blinker 是一个物联网接入方案，旨在让大家可以畅快 DIY 自己物联网设备。ios、android 都支持，本地、远程都支持，蓝牙、WiFi 都支持，可自己拖拽布局设备控制界面，轻松打造你的物联网设备。

但是目前blinker并没有windows版的客户端，在外使用计算机控制blinker设备不太方便，于是使用python做了一个简易版的pc客户端。

[quote color="info"]不过blinker也就是玩玩而已。专业单片机开发还是用keil吧......[/quote]

特性

支持自动填充登录。也就是说你不需要每次都登录你的blinker账号，在编辑实现自动登录相关js代码后就可以在不同的设备上无需登录随开随用了。
具体实现如下（更改前四行的username和password字段）：

var usernameInput = document.querySelector("input[name=\'username\']");
var passwordInput = document.querySelector("input[name=\'password\']");
var usernameValue = "usename";
var passwordValue = "password";
var usernameEvent = new Event("input", { bubbles: true });
var passwordEvent = new Event("input", { bubbles: true });
usernameInput.value = usernameValue;
usernameInput.dispatchEvent(usernameEvent);
passwordInput.value = passwordValue;
passwordInput.dispatchEvent(passwordEvent);

使用方法

1.将代码源文件保存到一个文件夹中
2.安装python3
3.安装pyside6

pip install pyside6 

4.安装pyinstaller

pip install pyinstaller 

5.编译并生成程序

pyinstaller main.py --noconsole --hidden-import pyside6.qtxml

代码开源链接

https://github.com/bertwaver/blinker_Win

设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

你的实现应该支持如下操作：

MyCircularQueue(k): 构造器，设置队列长度为 k 。
Front: 从队首获取元素。如果队列为空，返回 -1 。
Rear: 获取队尾元素。如果队列为空，返回 -1 。
enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
isEmpty(): 检查循环队列是否为空。
isFull(): 检查循环队列是否已满。

[acc status="close" title="示例一"]MyCircularQueue circularQueue = new MyCircularQueue(3); // 设置长度为 3
circularQueue.enQueue(1); // 返回 true
circularQueue.enQueue(2); // 返回 true
circularQueue.enQueue(3); // 返回 true
circularQueue.enQueue(4); // 返回 false，队列已满
circularQueue.Rear(); // 返回 3
circularQueue.isFull(); // 返回 true
circularQueue.deQueue(); // 返回 true
circularQueue.enQueue(4); // 返回 true
circularQueue.Rear(); // 返回 4[/acc]

提示：

所有的值都在 0 至 1000 的范围内；
操作数将在 1 至 1000 的范围内；
请不要使用内置的队列库。

动图演示

(动图来自 https://blog.csdn.net/qq_42996461/article/details/125674149)

实现容量为k的循环队列，可以定义一个大小为k的动态数组。同时，也可以通过链表实现。本文通过动态数组vector实现，并且在此过程中不使用指针。变量的定义与解释如下：

private:
    vector<int> queue; //循环队列
    int front; //队首
    int rear; //队尾
    int capacity; //队列的容量

[quote color="info"]对于使用指针实现容量为k的循环队列，需要定义(k+1)的空间，用于判空判满。但如果不使用指针实现，只需定义k的空间即可。[/quote]

验空与验满

由于存入队列的值的大小在0-1000之间，因此我们可以在队列初始化以及删除元素时用-1来代替数组中元素为空的情况。所以在验空和验满时，只需要判断数组中是否 全部元素为-1 或者 全部元素不为-1 来实现。

    bool isEmpty() {
        
        for (int cptime = 0; cptime < capacity; cptime++)
        {
            if (queue[cptime] != -1)
            {
                return false;
                
            }
        }
        return true;
    }

    bool isFull() {
        
        for (int cptime = 0; cptime < capacity; cptime++)
        {
            if (queue[cptime] == -1)
            {
                
                return false;
               
            }
        }
        return true;

    }

入队

在进行入队操作时，首先应该考虑队列是否已满，如果队列已满，那就无法进行入队操作，直接返回false即可。再考虑队尾是否处在数组的末尾，如果是这样的话，那就应该在数组的头部插入数据，并且将队尾指向数组的头部。如果不在数组的末尾，那么按顺序插入即可。

    bool enQueue(int value) {
        if (isFull() == true)
        {
            return false;
        } 
        if (rear == capacity - 1)
        {
            rear = 0;
            queue[rear] = value;
            return true;
        }
        queue[rear+1] = value;
        rear++;
        return true;
    }

[quote color="info"]由于队列遵循先入先出原则。因此在“再考虑队尾是否处在数组的末尾，如果是这样的话，那就应该在数组的头部插入数据，并且将队尾指向数组的头部。”的时候时，不需要考虑数组的头部是否有数据。因为对于队列来说，只会出现一种“队首和队尾都有数据，而队尾的指针指向数组的末尾”的情况，那就是队列已满。但由于在入队时我们优先考虑了队列是否已满的情况，所以在此步就不需要考虑了。[/quote]

出队

出队的逻辑与入队相似。

    bool deQueue() {
        if (isEmpty() == true)
        {
            return false;
        }
        if (front == capacity - 1)
        {
            front = 0;
            queue[capacity-1] = -1;
            return true;
        }
        queue[front] = -1;
        front++;
        return true;
    }

取出队首/队尾数据

只需要获取front或者rear指向的数据即可。（由于题目没有要求，因此本代码未考虑当队列为空的情况）

    int Front() {
        if (isEmpty() == true)
        {
            return -1;
        }
        return queue[front];

    }

    int Rear() {
        if (isEmpty() == true)
        {
            return -1;
        }
        return queue[rear];
    }

最终代码

class MyCircularQueue {
private:
    vector<int> queue;
    int front;
    int rear;
    int capacity;
public:
    MyCircularQueue(int k) {
        queue.resize(k);
        front = 0;
        rear = -1;
        capacity = k;
        for (int cptime = 0; cptime < k; cptime++)
        {
            queue[cptime] = -1;
        }
    }

    bool enQueue(int value) {
        if (isFull() == true)
        {
            return false;
        } 
        if (rear == capacity - 1)
        {
            rear = 0;
            queue[rear] = value;
            return true;
        }
        queue[rear+1] = value;
        rear++;
        return true;
    }

    bool deQueue() {
        if (isEmpty() == true)
        {
            return false;
        }
        if (front == capacity - 1)
        {
            front = 0;
            queue[capacity-1] = -1;
            return true;
        }
        queue[front] = -1;
        front++;
        return true;
    }

    int Front() {
        if (isEmpty() == true)
        {
            return -1;
        }
        return queue[front];

    }

    int Rear() {
        if (isEmpty() == true)
        {
            return -1;
        }
        return queue[rear];
    }

    bool isEmpty() {
        bool sum = true;
        for (int cptime = 0; cptime < capacity; cptime++)
        {
            if (queue[cptime] != -1)
            {
                sum = false;
                break;
            }
        }
        return sum;
    }

    bool isFull() {
        bool sum = true;
        for (int cptime = 0; cptime < capacity; cptime++)
        {
            if (queue[cptime] == -1)
            {
                sum = false;
                break;
            }
        }
        return sum;

    }
};

动态拓展队列空间与链表实现

详情见2019计算机考研408数据结构大题。

【2019统考真题】请设计一个队列，要求满足:①初始时队列为空;②入队时，允许增加队列占用空间;③出队后，出队元素所占用的空间可重复使用，即整个队列所占用的空间只增不减;④入队操作和出队操作的时间复杂度始终保持为O ( 1 ) O(1)O(1)。请回答下列问题:
1）该队列是应选择链式存储结构，还是应选择顺序存储结构?
2）画出队列的初始状态，并给出判断队空和队满的条件。
3 ) 画出第一个元素入队后的队列状态。
4）给出入队操作和出队操作的基本过程。

如果使用动态数组实现的话，可以使用 resize 方法拓展空间。但对于本题要求的链表实现，可以见 https://blog.csdn.net/qq_50710984/article/details/113946205