leetcode周赛

一、301周赛

1.装满杯子需要的最短总时长

装满杯子需要的最短总时长https://leetcode.cn/problems/minimum-amount-of-time-to-fill-cups/

代码：

class Solution {
public:
    int fillCups(vector<int>& amount) {
        sort(amount.begin(),amount.end());
        if(amount[2]>=amount[0]+amount[1]){
            return amount[2];
        }
        else{
            return (amount[0]+amount[1]-amount[2]+1)/2+amount[2];
        }
    }
};

 解析：因为一台饮水机可以同时接两杯不同温度的水，所以尽可能的让其一直同时放两杯水用时最短。这就分为两种可能：1.排序后的amount[0]和amount[1]和小于等于amount[2]，这样0、1和2进行匹配接水，0、1接完后再单独接2，总用时就是2的个数；2.排序后amount[0]和amount[1]和大于amount[2]，同样的用0、1去匹配2，但是为了保证用时最短，剩下的0和1的个数应该是相等或者差一，因为同时接两杯水才是最省时的，所以最短用时是0和1减去2剩下的个数加一再除以2，最后再加上2的个数。

2.无限集中的最小数字

无限集中的最小数字https://leetcode.cn/problems/smallest-number-in-infinite-set/

 

现有一个包含所有正整数的集合 [1, 2, 3, 4, 5, ...] 。
 
实现 SmallestInfiniteSet 类：
 
SmallestInfiniteSet() 初始化 SmallestInfiniteSet 对象以包含 所有 正整数。
int popSmallest() 移除 并返回该无限集中的最小整数。
void addBack(int num) 如果正整数 num 不 存在于无限集中，则将一个 num 添加 到该无限集中。
 
 
示例：
 
输入
["SmallestInfiniteSet", "addBack", "popSmallest", "popSmallest", "popSmallest", "addBack", "popSmallest", "popSmallest", "popSmallest"]
[[], [2], [], [], [], [1], [], [], []]
输出
[null, null, 1, 2, 3, null, 1, 4, 5]
 
解释
SmallestInfiniteSet smallestInfiniteSet = new SmallestInfiniteSet();
smallestInfiniteSet.addBack(2);    // 2 已经在集合中，所以不做任何变更。
smallestInfiniteSet.popSmallest(); // 返回 1 ，因为 1 是最小的整数，并将其从集合中移除。
smallestInfiniteSet.popSmallest(); // 返回 2 ，并将其从集合中移除。
smallestInfiniteSet.popSmallest(); // 返回 3 ，并将其从集合中移除。
smallestInfiniteSet.addBack(1);    // 将 1 添加到该集合中。
smallestInfiniteSet.popSmallest(); // 返回 1 ，因为 1 在上一步中被添加到集合中，
                                   // 且 1 是最小的整数，并将其从集合中移除。
smallestInfiniteSet.popSmallest(); // 返回 4 ，并将其从集合中移除。
smallestInfiniteSet.popSmallest(); // 返回 5 ，并将其从集合中移除。

代码：

class SmallestInfiniteSet {
public:
    unordered_set<int>s;
    SmallestInfiniteSet() {
 
    }
    
    int popSmallest() {
        int i=1;
        for(;s.count(i);i++){
 
        }
        s.insert(i);
        return i;
    }
    
    void addBack(int num) {
        if(s.count(num))s.erase(num);
    }
};
 
/**
 * Your SmallestInfiniteSet object will be instantiated and called as such:
 * SmallestInfiniteSet* obj = new SmallestInfiniteSet();
 * int param_1 = obj->popSmallest();
 * obj->addBack(num);
 */

解析：本体的无限集数据太大不好维护，所以维护一个无限集中被删减的数据。无限集删除最小的数据，就相当于维护集中从1开始缺少的最小整数，添加到维护集合中。无限集添加数据就等价于从维护数据集中删除对应数据。

3.移动片段得到字符串

移动片段得到字符串https://leetcode.cn/problems/move-pieces-to-obtain-a-string/

给你两个字符串 start 和 target ，长度均为 n 。每个字符串 仅 由字符 'L'、'R' 和 '_' 组成，其中：
 
字符 'L' 和 'R' 表示片段，其中片段 'L' 只有在其左侧直接存在一个 空位 时才能向 左 移动，而片段 'R' 只有在其右侧直接存在一个 空位 时才能向 右 移动。
字符 '_' 表示可以被 任意 'L' 或 'R' 片段占据的空位。
如果在移动字符串 start 中的片段任意次之后可以得到字符串 target ，返回 true ；否则，返回 false 。
 
 
 
示例 1：
 
输入：start = "_L__R__R_", target = "L______RR"
输出：true
解释：可以从字符串 start 获得 target ，需要进行下面的移动：
- 将第一个片段向左移动一步，字符串现在变为 "L___R__R_" 。
- 将最后一个片段向右移动一步，字符串现在变为 "L___R___R" 。
- 将第二个片段向右移动散步，字符串现在变为 "L______RR" 。
可以从字符串 start 得到 target ，所以返回 true 。
示例 2：
 
输入：start = "R_L_", target = "__LR"
输出：false
解释：字符串 start 中的 'R' 片段可以向右移动一步得到 "_RL_" 。
但是，在这一步之后，不存在可以移动的片段，所以无法从字符串 start 得到 target 。
示例 3：
 
输入：start = "_R", target = "R_"
输出：false
解释：字符串 start 中的片段只能向右移动，所以无法从字符串 start 得到 target 。
 
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/move-pieces-to-obtain-a-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

 代码：

class Solution {
public:
    bool canChange(string start, string target) {
        if(start.size()!=target.size())return false;
        vector<pair<char,int>>s,t;
        for(int i=0;i<start.size();i++){
            if(start[i]!='_'){
                s.push_back(make_pair(start[i],i));
            }
            if(target[i]!='_'){
                t.push_back(make_pair(target[i],i));
            }
        }
        if(s.size()!=t.size())return false;
        for(int i=0;i<s.size();i++){
            if(s[i].first=='L' && s[i].second<t[i].second)return false;
            else if(s[i].first=='R' && s[i].second>t[i].second)return false;
            else if(s[i].first!=t[i].first)return false;
        }
        return true;
    }
};

解析：将start和target数组里面的非'_'元素全存到vector<pair<char,int>>容器中，然后比较这两个容器，如果相同位置内容不同，则返回false；如果start代表的容器的'L'的下标位置小于target的位置，由于L不能右移，故返回false；同理start的R的位置大于target的R的位置则返回false；其他情况都是返回true。