[数据结构与算法]【LeetCode】第 283 场周赛题解

LeetCode第 283 场周赛比赛地址

T1：2194. Excel 表中某个范围内的单元格

Excel 表中的一个单元格 (r, c)会以字符串"<col><row>" 的形式进行表示，其中：

• <col>即单元格的列号 c 。用英文字母表中的 字母 标识。
• 例如，第 1 列用A 表示，第 2 列用 B 表示，第 3 列用 C 表示，以此类推。
• <row>即单元格的行号 r 。第 r行就用 整数 r标识。
• 给你一个格式为 "<col1><row1>:<col2><row2>" 的字符串 s ，其中 <col1>表示 c1 列，<row1>表示 r1 行，<col2> 表示 c2 列，<row2> 表示 r2 行，并满足r1 <= r2 且 c1 <= c2。

找出所有满足 r1 <= x <= r2且 c1 <= y <= c2 的单元格，并以列表形式返回。单元格应该按前面描述的格式用 字符串 表示，并以 非递减 顺序排列（先按列排，再按行排）。

示例 1：

输入：s = "K1:L2"
输出：["K1","K2","L1","L2"]
解释：
上图显示了列表中应该出现的单元格。
红色箭头指示单元格的出现顺序。

示例 2：

输入：s = "A1:F1"
输出：["A1","B1","C1","D1","E1","F1"]
解释：
上图显示了列表中应该出现的单元格。 
红色箭头指示单元格的出现顺序。

提示：

• s.length == 5
• 'A' <= s[0] <= s[3] <= 'Z'
• '1' <= s[1] <= s[4] <= '9'
• s 由大写英文字母、数字、和 ':'组成

题目分析：

简单模拟题，按照题意顺序输出即可

class Solution {
public:
    vector<string> cellsInRange(string s) {
        string ss="";
        vector<string>ve;
        for(char c=s[0];c<=s[3];++c){
            for(char b=s[1];b<=s[4];b++){
                ss="";
                ss+=c;
                ss+=b;
                ve.push_back(ss);
            }
        }
        return ve;
    }
};

T2:向数组中追加 K 个整数

给你一个整数数组 nums 和一个整数 k 。请你向 nums 中追加 k个 未 出现在 nums 中的、互不相同 的 正 整数，并使结果数组的元素和 最小 。

返回追加到 nums 中的 k个整数之和。

示例 1：

输入：nums = [1,4,25,10,25], k = 2
输出：5
解释：在该解法中，向数组中追加的两个互不相同且未出现的正整数是 2 和 3 。
nums 最终元素和为 1 + 4 + 25 + 10 + 25 + 2 + 3 = 70 ，这是所有情况中的最小值。
所以追加到数组中的两个整数之和是 2 + 3 = 5 ，所以返回 5 。

示例 2：

输入：nums = [5,6], k = 6
输出：25
解释：在该解法中，向数组中追加的两个互不相同且未出现的正整数是 1 、2 、3 、4 、7 和 8 。
nums 最终元素和为 5 + 6 + 1 + 2 + 3 + 4 + 7 + 8 = 36 ，这是所有情况中的最小值。
所以追加到数组中的两个整数之和是 1 + 2 + 3 + 4 + 7 + 8 = 25 ，所以返回 25 。

提示：

• 1 <= nums.length <= 10⁵
• 1 <= nums[i], k <= 10⁹

题目分析：

思维题

• 首先看数据范围，这个范围是绝对不可能暴力的，暴力肯定会超时，所以必须要优化一下
• 然后我们先对数组排序，因为要使得加进去的元素和最小，那么肯定是从小的数字去加
• 紧接着我们去判断当前遍历的数是否小于等于k，如果小于等于k那么就不能在当前位置添加元素，然后k就要往后移一位，然后把这个数加起来，因为当我们按照题意添加完k个元素之后，一定形成了一个公差为1的等差数列，我们只要把没加进去的数字加起来，最后用前n项和减去没加进去的数字，就是答案
• 但是会有重复值，重复值要是没有考虑的话就会影响答案，所以我们用map去重，我们只加第一次出现的数字就解决问题了

实现代码

class Solution {
public:
typedef long long ll;
    long long minimalKSum(vector<int>& nums, int k) {
        int n=nums.size();
        map<int,int>mp;
        sort(nums.begin(),nums.end());
        ll ans=0;
        for(int i=0;i<n;++i){
            mp[nums[i]]++;
            if(nums[i]<=k&&mp[nums[i]]==1){
                ++k;
                ans+=nums[i];
            }
        }
        cout<<k<<endl;
        return (ll)(1+k)*k/2-ans;
    }
};

T3：2196. 根据描述创建二叉树

给你一个二维整数数组 descriptions ，其中 descriptions[i] = [parenti, childi, isLefti] 表示 parenti是 childi 在 二叉树 中的 父节点，二叉树中各节点的值 互不相同 。此外：

如果 isLefti == 1，那么 childi就是 parenti的左子节点。
如果 isLefti == 0 ，那么 childi就是 parenti的右子节点。
请你根据 descriptions的描述来构造二叉树并返回其 根节点 。

测试用例会保证可以构造出 有效 的二叉树。

示例 1：

输入：descriptions = [[20,15,1],[20,17,0],[50,20,1],[50,80,0],[80,19,1]]
输出：[50,20,80,15,17,19]
解释：根节点是值为 50 的节点，因为它没有父节点。
结果二叉树如上图所示。

示例 2：

输入：descriptions = [[1,2,1],[2,3,0],[3,4,1]]
输出：[1,2,null,null,3,4]
解释：根节点是值为 1 的节点，因为它没有父节点。 
结果二叉树如上图所示。 

提示：

• 1 <= descriptions.length <= 10⁴
• descriptions[i].length == 3
• 1 <= parenti, childi <= 10⁵
• 0 <= isLefti <= 1
• descriptions所描述的二叉树是一棵有效二叉树

题目分析：（哈希）

• 首先遍历整个数组，创建父节点和子节点，然后不断地更新节点
• 并且在遍历的过程中记下子节点的入度
• 最后再遍历map数组，找到入度为0的节点就是根节点

class Solution {
public:
    TreeNode* createBinaryTree(vector<vector<int>>& descriptions) {
        map<int,TreeNode*>mp;
        map<int,int>ans;
        for(auto & p:descriptions){
            int a=p[0],b=p[1],c=p[2];
            if(!mp.count(a))
            mp[a]=new TreeNode(a);//创建父节点
            if(!mp.count(b))
            mp[b]=new TreeNode(b);//创建子节点
            if(c==1)
            mp[a]->left=mp[b];//左节点
            else
            mp[a]->right=mp[b];//右节点
            ans[b]++;//子节点的入度加一
        }
    for(auto &[key,val]:mp){
        if(ans[key]==0)//如果节点的入度为0，就是根节点
        return  val;
    }
    return nullptr;
    }
};

高质量的生活从自律做起
生活
1.养成早睡早起的习惯，23：00~6：00，不为任何不值得的事熬夜
2.极简主义，对生活进行断舍离管理
3.培养至少一个爱好，有情调、有爱好过有仪式感的生活，做有价值的事
4.注重身体和精神的体面，注重每一件生活物品的
质量，穿有品质的服装，款式经典穿搭性强的
增值
1.每天都要读书，哪怕只读书一页，也要读
2.注重选择，看经典的电影，读经典语录，输入的知识越经典，输出的内容才越有价值
3.学一门技能，无论是烹饪、演讲、绘画还是其他，练习到拿的出手的程度
4.要有一个摘抄本，把你从书里、生活里、旅途中学到的东西记录在上面，定期翻看
健康
1.多吃蛋白质，多吃当季水果，多喝柠檬水，过八分饱的人生
2.保持健康的状态，找到喜欢的运动，一周最少3次30分钟以上的运动
存钱
1.每个月强制储蓄收入10%，如果做不到，就储存知识
2.想清楚自己想要的生活，为此写一份长短期财务计划或者写下100个愿望，放在每天可以看得到的地方
3.积极赚钱，理智消费，始终让钱服务于更好的生
活，给自己“独立”和“自由”
4.学习理财知识，很多事，你不知道，就赚不到
护肤
1.每天坚持涂防晒，可以有防晒指数的BB霜
2.不随意种草，买自己能承受的范围适合自己的护肤品，用完在买新的
3.补水补觉，健康作息，不为小事生气，用好的眼霜和精华
4.戒掉饮料和蛋糕，每天吃红枣保持好的气色，使用干净的床上用品
感情
1.永远记得，一段感情是两个人相互扶持一起成长，而不是消耗彼此的时间，
2.在感情中做个“有品”的人，拒绝暖昧，和合适的人在一起
3.不要相信“我养你”的这种话，男女关系中，免费的永远是最贵的
4.做个理智的女生，不作也不怂，可以撒娇，但不能无理取闹，给对方空间也有自己的底线
5.爱自己，不与人攀比也不低到尘埃，清楚自己的内心