您好,欢迎访问代理记账网站
移动应用 微信公众号 联系我们

咨询热线 -

电话 15988168888

联系客服
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

leetcode刷题

leetcode刷题日记

<day 2021/10/20>

453. 最小操作次数使数组元素相等 简单

给你一个长度为 n 的整数数组,每次操作将会使 n - 1 个元素增加 1 。返回让数组所有元素相等的最小操作次数。

示例 1:

输入:nums = [1,2,3]
输出:3
解释:
只需要3次操作(注意每次操作会增加两个元素的值):
[1,2,3]  =>  [2,3,3]  =>  [3,4,3]  =>  [4,4,4]

示例 2:

输入:nums = [1,1,1]
输出:0

提示:

  • n == nums.length
  • 1 <= nums.length <= 105
  • -109 <= nums[i] <= 109
  • 答案保证符合 32-bit 整数
解题思路:

因为是n-1个元素加一,所以也可以理解为一个元素减一,那么只需要找到最小值,并且便利容器每个元素减去最小值的结果相加就可以了。

实现代码:
class Solution {
public:
    int minMoves(vector<int>& nums) {
        int num=nums[0];
        for(int i=0;i<nums.size();i++)
        {
            if(num>nums[i])
            {
                num=nums[i];
            }
        }
        int res=0;
        for(int i=0;i<nums.size();i++)
        {
            res+=nums[i]-num;
        }
        return res;
    }
};
官方解法:
class Solution {
public:
    int minMoves(vector<int>& nums) {
        int minNum = *min_element(nums.begin(),nums.end());
        int res = 0;
        for (int num : nums) {
            res += num - minNum;
        }
        return res;
    }
};

很简洁了,使用的min_element找的最小值,原谅我刚看了c++ primer的vector也不知道有这个函数。


454. 四数相加 II 中等

给你四个整数数组 nums1nums2nums3nums4 ,数组长度都是 n ,请你计算有多少个元组 (i, j, k, l) 能满足:

  • 0 <= i, j, k, l < n
  • nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

示例 1:

输入:nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
输出:2
解释:
两个元组如下:
1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0

示例 2:

输入:nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
输出:1

提示:

  • n == nums1.length
  • n == nums2.length
  • n == nums3.length
  • n == nums4.length
  • 1 <= n <= 200
  • -228 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 228
解题思路:

自己想了半天啥也没想出来,只好看了解题,大概思路就是将ab分为一组,cd分为另一组,并存入map容器中去,然后map中的key为a,b的两数之和,值为两数之和出现的次数,然后再求cd的两数之和,将其值的负数拿到ab储存的容器中查找,若存在说明符合题目条件。

实现代码:

class Solution {
public:
    int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
        int res=0;
        map<int,int>ab_map;
        for(auto a:A)
        {
            for(auto b:B)
            {
                ab_map[a+b]++;
            }
        }
        for(auto c:C)
        {
            for(auto d:D)
            {
                if(ab_map.find(0-(c+d))!=ab_map.end())
                {
                    res+=ab_map[0-(c+d)];
                }
            }
        }
        return res;
    }
};

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

不太行,再试试官方解法

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

看了看代码,官方解法判断cd和的负数在ab的map容器中是否存在的方法是count函数,而我使用的是find函数,可能会更耗时。改了一下代码,发现事与愿违。

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

仔细看,发现官方解法使用的是unordered_map,也就是无序map容器,仔细一想,元素是否排序对本题并无帮助,所以排序的话反而会执行时间。改掉再试试。

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

很不错,执行时间明显变快了。

大佬解法:
class Solution {
  public:
    int fourSumCount(vector<int> &A, vector<int> &B, vector<int> &C, vector<int> &D) {
        int res = 0;
        map<int, int> map;
        for (const auto &a : A) for (const auto &b : B) ++map[a + b];
        for (const auto &c : C) for (const auto &d : D) res += map[-(c + d)];
        return res;
    }
};

太简洁了!


66. 加一 简单

给定一个由 整数 组成的 非空 数组所表示的非负整数,在该数的基础上加一。

最高位数字存放在数组的首位, 数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外,这个整数不会以零开头。

示例 1:

输入:digits = [1,2,3]
输出:[1,2,4]
解释:输入数组表示数字 123。

示例 2:

输入:digits = [4,3,2,1]
输出:[4,3,2,2]
解释:输入数组表示数字 4321。

示例 3:

输入:digits = [0]
输出:[1]

提示:

  • 1 <= digits.length <= 100
  • 0 <= digits[i] <= 9
解题思路:

怎么解呢?第一个想到的方法是将数组转化为整数,本来以为这是个简单的方法,转化为整数十分容易,可是再将其转化为vector数组时才发现,自己还得把开头为9进位的情况单独列出一个if判断,好的,我加,可是还是提交失败了,看了报错信息与输入失败的样例,我…,还是直接修改数组吧。

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

太艰难了,先是在重新输入为数组的时候卡了半天,又在开头为9导致进位的情况卡了半天,最后系统给了个长度为10的数组样例,int型肯定放不下,我改成long long型,结果直接又来了个19位的数组,qaq。

实现代码:
class Solution {    //这是第一遍用的转换为整数的放大,对于10位数以内的还是很有效的(不考虑执行时间和内存占用的话)
public:
    vector<int> plusOne(vector<int>& digits) {
        int i;
        long long sum, n=1;
        for(i=0,sum=0;i<digits.size();i++)
        {
            n*=10;
            sum*=10;
            sum+=digits[i];
        }
        n/=10;
        sum++;
        if(sum/n==10)
        {
            n*=10;
            digits.push_back(0);
        }
        for(i=0;i<digits.size();i++)
        {
            digits[i]=(int)(sum/n);
            sum%=n;
            n/=10;
        }
        return digits;
    }
};
官方解法
class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int n = digits.size();
        for (int i = n - 1; i >= 0; --i) {
            if (digits[i] != 9) {
                ++digits[i];
                for (int j = i + 1; j < n; ++j) {
                    digits[j] = 0;
                }
                return digits;
            }
        }

        // digits 中所有的元素均为 9
        vector<int> ans(n + 1);
        ans[0] = 1;
        return ans;
    }
};

思路很简单,若最后一位不为9,加个一就完事了,为9的话,一直往前找到不为9的数,加一并把后面的数(也就是都为9的数)置0就可以了。

67. 二进制求和 简单

给你两个二进制字符串,返回它们的和(用二进制表示)。

输入为 非空 字符串且只包含数字 10

示例 1:

输入: a = "11", b = "1"
输出: "100"

示例 2:

输入: a = "1010", b = "1011"
输出: "10101"

提示:

  • 每个字符串仅由字符 '0''1' 组成。
  • 1 <= a.length, b.length <= 10^4
  • 字符串如果不是 "0" ,就都不含前导零。
解题思路:

首先想到的是找到最短的,然后将短的置为外层for循环,长的置为内层for循环,然后设置多个if条件,感觉很麻烦。实际做起来更麻烦,因为在实现的时候发现自己并不知道那个是长的,哪个是短的,那么就得把短的先用字符0给填充到与长的长度相等,然后继续算,又在第0位进位上卡了一会儿,要是没有vs的动态调试,今天一天估计都要被这道《简单的》题给搞混了,然后,不过最后好得是做出来了。

实现代码:
class Solution {
public:
    string addBinary(string a, string b) {
        char jinwei = '0';
    string shortstr = "";
    string longstr = "";
    if (a.size() < b.size())
    {
        for (int i = 0; i < (b.size() - a.size()); i++)
            shortstr += '0';
        shortstr += a;
        longstr = b;
    }
    else if (a.size() > b.size())
    {
        for (int i = 0; i < (a.size() - b.size()); i++)
            shortstr += '0';
        shortstr += b;
        longstr = a;
    }
    else
    {
        shortstr = a;
        longstr = b;
    }
    string newstr=longstr;
    string str = "1";
    for (int i = shortstr.size() - 1; i >= 0; i--)
    {
        if ((longstr[i] + shortstr[i] + jinwei) == 147)
        {
            newstr[i] = '1';
            jinwei = '1';
            if (i == 0)
                newstr = str + newstr;
            continue;
        }
        if ((longstr[i] + shortstr[i] + jinwei) == 146)
        {
            newstr[i] = '0';
            jinwei = '1';
            if (i == 0)
                newstr = str + newstr;
            continue;
        }
        if ((longstr[i] + shortstr[i] + jinwei) == 145)
        {
            newstr[i] = '1';
            jinwei = '0';
            continue;
        }
        if ((longstr[i] + shortstr[i] + jinwei) == 144)
        {
            newstr[i] = '0';
            jinwei = '0';
            continue;
        }
    }
    return newstr;
    }
};

好的一个复杂无用的解法就出来了。

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

不过虽说代码长而无用,但效果好像还不错?

官方解法:
class Solution {
public:
    string addBinary(string a, string b) {
        string ans;
        reverse(a.begin(), a.end());   //首尾倒置
        reverse(b.begin(), b.end());

        int n = max(a.size(), b.size()), carry = 0;    //取得最长的值,通过carry的值保留a b内元素的运算结果,以及进位值。
        for (size_t i = 0; i < n; ++i) {
            carry += i < a.size() ? (a.at(i) == '1') : 0;   //通过三元表达式与间接接受运算解雇哦巧妙地解决了长度不同的问题,并且使用(a.at(i) == '1') : 0巧妙地解决了三元表达式在返回值上的限制
            carry += i < b.size() ? (b.at(i) == '1') : 0;
            ans.push_back((carry % 2) ? '1' : '0');   //在保存的时候判断此位的值,并巧妙地利用了三元表达式在不影响carry本身的值的情况下获得此位的值,使得carry技能求此位值,又能求进位值。
            carry /= 2;    //既清空了状态,又获得了进位值。
        }

        if (carry) {   //使用carry作为首元素是否进位条件,解决了0+0等非进位导致首元素为0的问题。
            ans.push_back('1');   //由于已经首尾倒置了,解决了无法头插的问题。
        }
        reverse(ans.begin(), ans.end());

        return ans;
    }
};

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

还有啥说的,太妙了。

优化代码

根据一位大佬的解法优化后的代码。

string addBinary(string a, string b) {
    char jinwei = '0';
    int al = a.size();
    int bl = b.size();
    while (al < bl) //补0更加简洁方便
    {
        a = '0' + a;
        ++al;
    }
    while (al > bl)
    {
        b = '0' + b;
        ++bl;
    }              //不再使用进位标志来记录进位,而是直接将前一位加一,并根据是否大于二判断是否产生了进位,与此位的值。
    for (int j = a.size() - 1; j > 0; --j) //从后到前遍历所有的位数,同位相加
    {
        a[j] = a[j] - '0' + b[j];
        if (a[j] >= '2') //若大于等于字符‘2’,需要进一
        {
            a[j] = (a[j] - '0') % 2 + '0';
            a[j - 1] = a[j - 1] + 1;
        }
    }
    a[0] = a[0] - '0' + b[0]; //将ab的第0位相加
    if (a[0] >= '2') //若大于等于2,需要进一
    {
        a[0] = (a[0] - '0') % 2 + '0';
        a = '1' + a;
    }
    return a;
}
1. 两数之和 简单

给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1:

输入:nums = [2,7,11,15], target = 9
输出:[0,1]
解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。

示例 2:

输入:nums = [3,2,4], target = 6
输出:[1,2]

示例 3:

输入:nums = [3,3], target = 6
输出:[0,1]

提示:

  • 2 <= nums.length <= 104
  • -109 <= nums[i] <= 109
  • -109 <= target <= 109
  • 只会存在一个有效答案
解题思路:

想要尽可能地降低时间复杂度,就要让查找对应元素下标的方法尽可能简洁,而哈希表与此很匹配,所以就要使用哈希表,也就是无序map,一定要用无序。

实现代码:
class Solution {         //直接cv了官方的,因为都大差不差
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hashtable;
        for (int i = 0; i < nums.size(); ++i) {
            auto it = hashtable.find(target - nums[i]);
            if (it != hashtable.end()) {
                return {it->second, i};
            }
            hashtable[nums[i]] = i;      //这个一定要写在后面,假如是[3,2,4],目标为6的话,先插入了3,使得查找的时候直接查到了3,直接就给返回了。所以千万要写在后面。
        }
        return {};
    }
};
2. 两数相加 中等

难度中等6925收藏分享切换为英文接收动态反馈

给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。

请你将两个数相加,并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外,这两个数都不会以 0 开头。

示例 1:

img

输入:l1 = [2,4,3], l2 = [5,6,4]
输出:[7,0,8]
解释:342 + 465 = 807.

示例 2:

输入:l1 = [0], l2 = [0]
输出:[0]

示例 3:

输入:l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出:[8,9,9,9,0,0,0,1]

提示:

  • 每个链表中的节点数在范围 [1, 100]
  • 0 <= Node.val <= 9
  • 题目数据保证列表表示的数字不含前导零
解题思路:

这道题的买点就是链表了,把链表弄好就行了。

实现代码:
/*   也是官方代码,还是大差不差
  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* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *head = nullptr, *tail = nullptr;
        int carry = 0;
        while (l1 || l2) {
            int n1 = l1 ? l1->val: 0;      //使用三元表达式接受值可以不用再单独设置循环计算长的链表多出来的值。
            int n2 = l2 ? l2->val: 0;
            int sum = n1 + n2 + carry;
            if (!head) {
                head = tail = new ListNode(sum % 10);
            } else {
                tail->next = new ListNode(sum % 10);
                tail = tail->next;
            }
            carry = sum / 10;
            if (l1) {
                l1 = l1->next;
            }
            if (l2) {
                l2 = l2->next;
            }
        }
        if (carry > 0) {
            tail->next = new ListNode(carry);
        }
        return head;
    }
};

代码没什么好说的,就是链表的操作,但是对于链表的定义挺有意思的。可以看到是直接使用了构造函数,以前记得听说过结构体内是无法定义函数的,这么来看构造函数还是可以定义的,方便又省事。

总结一下:在没有什么特别清晰的思路的时候,最好不要想着生代码,扎扎实实的把每一个条件都做好,然后再慢慢的优化代码,就是因为老想着走捷径才会在交代码的时候有一直通不过的案例。唉~,老老实实比较好,对于我这种小白来讲。

229. 求众数 II 中等

给定一个大小为 n 的整数数组,找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。

示例 1:

输入:[3,2,3]
输出:[3]

示例 2:

输入:nums = [1]
输出:[1]

示例 3:

输入:[1,1,1,3,3,2,2,2]
输出:[1,2]

提示:

  • 1 <= nums.length <= 5 * 104
  • -109 <= nums[i] <= 109
解题思路:

很简单的题了,感觉似乎用到容器或链表这种结构体的题实现思路都不会太难的样子,直接创建一个unordered_map容器,然后值存放nums[i],键存放出现次数…就可以了。

实现代码:
class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        unordered_map<int,int> m;
        int n=nums.size();
        for(int i=0;i<n;i++)
        {
            if(m.find(nums[i])!=m.end()) m[nums[i]]++;     //没必要使用这个条件判断,map容器中与nums[i]的值对应的key不存在的话会自动添加并默认值为0
            else m.insert(pair(nums[i],1));
            //m[nums[i]]++;   优化代码
        }
        nums.resize(0);
        for(auto it:m)
        {
            if(it.second>(n/3))
                nums.push_back(it.first);
        }
        return nums;
    }
};
官方代码1:
class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans;
        unordered_map<int, int> cnt;

        for (auto & v : nums) {
            cnt[v]++;
        }
        for (auto & v : cnt) {
            if (v.second > n / 3) {
                ans.push_back(v.first);
            }
        }

        return ans;
    }
};

很简洁。

官方代码2:
class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        vector<int> ans;
        int element1 = 0;
        int element2 = 0;
        int vote1 = 0;
        int vote2 = 0;

        for (auto & num : nums) {
            if (vote1 > 0 && num == element1) { //如果该元素为第一个元素,则计数加1
                vote1++;
            } else if (vote2 > 0 && num == element2) { //如果该元素为第二个元素,则计数加1
                vote2++;
            } else if (vote1 == 0) { // 选择第一个元素
                element1 = num;
                vote1++;
            } else if (vote2 == 0) { // 选择第二个元素
                element2 = num;
                vote2++;
            } else { //如果三个元素均不相同,则相互抵消1次
                vote1--;
                vote2--;
            }
        }

        int cnt1 = 0;
        int cnt2 = 0;
        for (auto & num : nums) {
            if (vote1 > 0 && num == element1) {
                cnt1++;
            }
            if (vote2 > 0 && num == element2) {
                cnt2++;
            }
        }
        // 检测元素出现的次数是否满足要求
        if (vote1 > 0 && cnt1 > nums.size() / 3) {
            ans.push_back(element1);
        }
        if (vote2 > 0 && cnt2 > nums.size() / 3) {
            ans.push_back(element2);
        }

        return ans;
    }
};

将空间复杂度降低到了O(1),虽然更好,但感觉过于复杂了,贴上思路:

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

230. 二叉搜索树中第K小的元素 中等

给定一个二叉搜索树的根节点 root ,和一个整数 k ,请你设计一个算法查找其中第 k 个最小元素(从 1 开始计数)。

示例 1:

img

输入:root = [3,1,4,null,2], k = 1
输出:1

示例 2:

img

输入:root = [5,3,6,2,4,null,null,1], k = 3
输出:3

提示:

  • 树中的节点数为 n
  • 1 <= k <= n <= 104
  • 0 <= Node.val <= 104
解题思路:

好的,又是考数据结构,二叉树,现学一下,学完了,用vector封装一下再排个序直接交,美滋滋。说到这里突然想起来vector是可以插入重复元素的,而我并没有排除重复元素,啊这,我是怎么通过的?????总不能这道题的样例都不带重复元素的把。

实现代码
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
void preOrder(TreeNode* tree,vector<int> &v)
{
    if(tree)
    {
        v.push_back(tree->val);
        preOrder(tree->left,v);
        preOrder(tree->right,v);
    }
}

class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        vector<int> v;
        int res=0;
        preOrder(root,v);
        sort(v.begin(), v.end(), less<int>() );
        return v[k-1];
    }
};

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

虽然存在未排除重复元素的缺陷,但还是提交成功了?????

官方代码一:
class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        stack<TreeNode *> stack;
        while (root != nullptr || stack.size() > 0) {
            while (root != nullptr) {
                stack.push(root);
                root = root->left;
            }
            root = stack.top();
            stack.pop();
            --k;
            if (k == 0) {
                break;
            }
            root = root->right;
        }
        return root->val;
    }
};

这个就是把递归遍历改为了while循环遍历。写着麻烦点,但是省空间。

官方方法二

在这里插入图片描述

class MyBst {
public:
    MyBst(TreeNode *root) {
        this->root = root;
        countNodeNum(root);
    }

    // 返回二叉搜索树中第k小的元素
    int kthSmallest(int k) {
        TreeNode *node = root;
        while (node != nullptr) {
            int left = getNodeNum(node->left);
            if (left < k - 1) {
                node = node->right;
                k -= left + 1;
            } else if (left == k - 1) {
                break;
            } else {
                node = node->left;
            }
        }
        return node->val;
    }

private:
    TreeNode *root;
    unordered_map<TreeNode *, int> nodeNum;

    // 统计以node为根结点的子树的结点数
    int countNodeNum(TreeNode * node) {
        if (node == nullptr) {
            return 0;
        }
        nodeNum[node] = 1 + countNodeNum(node->left) + countNodeNum(node->right);
        return nodeNum[node];
    }

    // 获取以node为根结点的子树的结点数
    int getNodeNum(TreeNode * node) {
        if (node != nullptr && nodeNum.count(node)) {
            return nodeNum[node];
        }else{
            return 0;
        }
    }
};

class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        MyBst bst(root);
        return bst.kthSmallest(k);
    }
};

在这里插入图片描述

官方方法三

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

// 平衡二叉搜索树结点
struct Node {
    int val;
    Node * parent;
    Node * left;
    Node * right;
    int size;
    int height;

    Node(int val) {
        this->val = val;
        this->parent = nullptr;
        this->left = nullptr;
        this->right = nullptr;
        this->height = 0; // 结点高度:以node为根节点的子树的高度(高度定义:叶结点的高度是0)
        this->size = 1; // 结点元素数:以node为根节点的子树的节点总数
    }

    Node(int val, Node * parent) {
        this->val = val;
        this->parent = parent;
        this->left = nullptr;
        this->right = nullptr;
        this->height = 0; // 结点高度:以node为根节点的子树的高度(高度定义:叶结点的高度是0)
        this->size = 1; // 结点元素数:以node为根节点的子树的节点总数
    }

    Node(int val, Node * parent, Node * left, Node * right) {
        this->val = val;
        this->parent = parent;
        this->left = left;
        this->right = right;
        this->height = 0; // 结点高度:以node为根节点的子树的高度(高度定义:叶结点的高度是0)
        this->size = 1; // 结点元素数:以node为根节点的子树的节点总数
    }
};


// 平衡二叉搜索树(AVL树):允许重复值
class AVL {
public:
    AVL(vector<int> & vals) {
        if (!vals.empty()) {
            root = build(vals, 0, vals.size() - 1, nullptr);
        }
    }

    // 根据vals[l:r]构造平衡二叉搜索树 -> 返回根结点
    Node * build(vector<int> & vals, int l, int r, Node * parent) {
        int m = (l + r) >> 1;
        Node * node = new Node(vals[m], parent);
        if (l <= m - 1) {
            node->left = build(vals, l, m - 1, node);
        }
        if (m + 1 <= r) {
            node->right = build(vals, m + 1, r, node);
        }
        recompute(node);
        return node;
    }

    // 返回二叉搜索树中第k小的元素
    int kthSmallest(int k) {
        Node * node = root;
        while (node != nullptr) {
            int left = getSize(node->left);
            if (left < k - 1) {
                node = node->right;
                k -= left + 1;
            } else if (left == k - 1) {
                break;
            } else {
                node = node->left;
            }
        }
        return node->val;
    }

    void insert(int v) {
        if (root == nullptr) {
            root = new Node(v);
        } else {
            // 计算新结点的添加位置
            Node * node = subtreeSearch(root, v);
            bool isAddLeft = v <= node->val; // 是否将新结点添加到node的左子结点
            if (node->val == v) { // 如果值为v的结点已存在
                if (node->left != nullptr) { // 值为v的结点存在左子结点,则添加到其左子树的最右侧
                    node = subtreeLast(node->left);
                    isAddLeft = false;
                } else { // 值为v的结点不存在左子结点,则添加到其左子结点
                    isAddLeft = true;
                }
            }

            // 添加新结点
            Node * leaf = new Node(v, node);
            if (isAddLeft) {
                node->left = leaf;
            } else {
                node->right = leaf;
            }

            rebalance(leaf);
        }
    }

    // 删除值为v的结点 -> 返回是否成功删除结点
    bool Delete(int v) {
        if (root == nullptr) {
            return false;
        }

        Node * node = subtreeSearch(root, v);
        if (node->val != v) { // 没有找到需要删除的结点
            return false;
        }

        // 处理当前结点既有左子树也有右子树的情况
        // 若左子树比右子树高度低,则将当前结点替换为右子树最左侧的结点,并移除右子树最左侧的结点
        // 若右子树比左子树高度低,则将当前结点替换为左子树最右侧的结点,并移除左子树最右侧的结点
        if (node->left != nullptr && node->right != nullptr) {
            Node * replacement = nullptr;
            if (node->left->height <= node->right->height) {
                replacement = subtreeFirst(node->right);
            } else {
                replacement = subtreeLast(node->left);
            }
            node->val = replacement->val;
            node = replacement;
        }

        Node * parent = node->parent;
        Delete(node);
        rebalance(parent);
        return true;
    }

private:
    Node * root;

    // 删除结点p并用它的子结点代替它,结点p至多只能有1个子结点
    void Delete(Node * node) {
        if (node->left != nullptr && node->right != nullptr) {
            return;
            // throw new Exception("Node has two children");
        }
        Node * child = node->left != nullptr ? node->left : node->right;
        if (child != nullptr) {
            child->parent = node->parent;
        }
        if (node == root) {
            root = child;
        } else {
            Node * parent = node->parent;
            if (node == parent->left) {
                parent->left = child;
            } else {
                parent->right = child;
            }
        }
        node->parent = node;
    }

    // 在以node为根结点的子树中搜索值为v的结点,如果没有值为v的结点,则返回值为v的结点应该在的位置的父结点
    Node * subtreeSearch(Node * node, int v) {
        if (node->val < v && node->right != nullptr) {
            return subtreeSearch(node->right, v);
        } else if (node->val > v && node->left != nullptr) {
            return subtreeSearch(node->left, v);
        } else {
            return node;
        }
    }

    // 重新计算node结点的高度和元素数
    void recompute(Node * node) {
        node->height = 1 + max(getHeight(node->left), getHeight(node->right));
        node->size = 1 + getSize(node->left) + getSize(node->right);
    }

    // 从node结点开始(含node结点)逐个向上重新平衡二叉树,并更新结点高度和元素数
    void rebalance(Node * node) {
        while (node != nullptr) {
            int oldHeight = node->height, oldSize = node->size;
            if (!isBalanced(node)) {
                node = restructure(tallGrandchild(node));
                recompute(node->left);
                recompute(node->right);
            }
            recompute(node);
            if (node->height == oldHeight && node->size == oldSize) {
                node = nullptr; // 如果结点高度和元素数都没有变化则不需要再继续向上调整
            } else {
                node = node->parent;
            }
        }
    }

    // 判断node结点是否平衡
    bool isBalanced(Node * node) {
        return abs(getHeight(node->left) - getHeight(node->right)) <= 1;
    }

    // 获取node结点更高的子树
    Node * tallChild(Node * node) {
        if (getHeight(node->left) > getHeight(node->right)) {
            return node->left;
        } else {
            return node->right;
        }
    }

    // 获取node结点更高的子树中的更高的子树
    Node * tallGrandchild(Node * node) {
        Node * child = tallChild(node);
        return tallChild(child);
    }

    // 重新连接父结点和子结点(子结点允许为空)
    static void relink(Node * parent, Node * child, bool isLeft) {
        if (isLeft) {
            parent->left = child;
        } else {
            parent->right = child;
        }
        if (child != nullptr) {
            child->parent = parent;
        }
    }

    // 旋转操作
    void rotate(Node * node) {
        Node * parent = node->parent;
        Node * grandparent = parent->parent;
        if (grandparent == nullptr) {
            root = node;
            node->parent = nullptr;
        } else {
            relink(grandparent, node, parent == grandparent->left);
        }

        if (node == parent->left) {
            relink(parent, node->right, true);
            relink(node, parent, false);
        } else {
            relink(parent, node->left, false);
            relink(node, parent, true);
        }
    }

    // trinode操作
    Node * restructure(Node * node) {
        Node * parent = node->parent;
        Node * grandparent = parent->parent;

        if ((node == parent->right) == (parent == grandparent->right)) { // 处理需要一次旋转的情况
            rotate(parent);
            return parent;
        } else { // 处理需要两次旋转的情况:第1次旋转后即成为需要一次旋转的情况
            rotate(node);
            rotate(node);
            return node;
        }
    }

    // 返回以node为根结点的子树的第1个元素
    static Node * subtreeFirst(Node * node) {
        while (node->left != nullptr) {
            node = node->left;
        }
        return node;
    }

    // 返回以node为根结点的子树的最后1个元素
    static Node * subtreeLast(Node * node) {
        while (node->right != nullptr) {
            node = node->right;
        }
        return node;
    }

    // 获取以node为根结点的子树的高度
    static int getHeight(Node * node) {
        return node != nullptr ? node->height : 0;
    }

    // 获取以node为根结点的子树的结点数
    static int getSize(Node * node) {
        return node != nullptr ? node->size : 0;
    }
};

class Solution {
public:
    int kthSmallest(TreeNode * root, int k) {
        // 中序遍历生成数值列表
        vector<int> inorderList;
        inorder(root, inorderList);
        // 构造平衡二叉搜索树
        AVL avl(inorderList);

        // 模拟1000次插入和删除操作
        vector<int> randomNums(1000);
        std::random_device rd;
        for (int i = 0; i < 1000; ++i) {
            randomNums[i] = rd()%(10001);
            avl.insert(randomNums[i]);
        }
        shuffle(randomNums); // 列表乱序
        for (int i = 0; i < 1000; ++i) {
            avl.Delete(randomNums[i]);
        }

        return avl.kthSmallest(k);
    }

private:
    void inorder(TreeNode * node, vector<int> & inorderList) {
        if (node->left != nullptr) {
            inorder(node->left, inorderList);
        }
        inorderList.push_back(node->val);
        if (node->right != nullptr) {
            inorder(node->right, inorderList);
        }
    }

    void shuffle(vector<int> & arr) {
        std::random_device rd;
        int length = arr.size();
        for (int i = 0; i < length; i++) {
            int randIndex = rd()%length;
            swap(arr[i],arr[randIndex]);
        }
    }
};

在这里插入图片描述

啥也不说了,这方法太离谱了,看看得了。
{
public:
int kthSmallest(TreeNode * root, int k) {
// 中序遍历生成数值列表
vector inorderList;
inorder(root, inorderList);
// 构造平衡二叉搜索树
AVL avl(inorderList);

    // 模拟1000次插入和删除操作
    vector<int> randomNums(1000);
    std::random_device rd;
    for (int i = 0; i < 1000; ++i) {
        randomNums[i] = rd()%(10001);
        avl.insert(randomNums[i]);
    }
    shuffle(randomNums); // 列表乱序
    for (int i = 0; i < 1000; ++i) {
        avl.Delete(randomNums[i]);
    }

    return avl.kthSmallest(k);
}

private:
void inorder(TreeNode * node, vector & inorderList) {
if (node->left != nullptr) {
inorder(node->left, inorderList);
}
inorderList.push_back(node->val);
if (node->right != nullptr) {
inorder(node->right, inorderList);
}
}

void shuffle(vector<int> & arr) {
    std::random_device rd;
    int length = arr.size();
    for (int i = 0; i < length; i++) {
        int randIndex = rd()%length;
        swap(arr[i],arr[randIndex]);
    }
}

};


![在这里插入图片描述](https://img-blog.csdnimg.cn/7426762f6bdd41ceaf7d606428de22c1.png)

啥也不说了,这方法太离谱了,看看得了。

分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进