力扣第 301 场周赛 题解

@TOC

题目

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

题目连接 ： 装满杯子需要的最短总时长

思路：贪心

每次可以选2个或一个，问最少次数，那么肯定每次能选2个就选两个啊，那么就有三种情况

先将三类水排个序，a[0] <= a[1] <= a[2] ，那么答案至少是a[2]

1. a[2] >= a[0] + a[1] ，那么答案就是a[2]
2. (a[2] + a[1] + a[0] ) % 2 == 0, 答案就是 (a[2] + a[1] + a[0] )/2 ，因为和是偶数的话一定可以每次选2个到选完，而且最优
3. (a[2] + a[1] + a[0] ) % 2 == 1，答案是 (a[2] + a[1] + a[0] )/2 + 1，因为最后一定剩下一杯水

代码

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

2.无限集中的最小数字

题目链接： 无限集中的最小数字

思路：数据结构

这道题就是考察数据结构的，用堆来存集合里的最小值，用map来记录集合中每个数是否在集合中

class SmallestInfiniteSet
{
public:
    int a[1010];
    priority_queue<int, vector<int>, greater<int>> q;
    SmallestInfiniteSet()
    {
        for (int i = 1; i < 1010; i++)
        {
            q.push(i);
            a[i] = 1;
        }
    }

    int popSmallest()
    {
        int t = q.top();
        a[t] = 0;
        q.pop();
        return t;
    }

    void addBack(int num)
    {
        if (a[num] == 0)
        {
            a[num] = 1;
            q.push(num);
        }
    }
};

3.移动片段得到字符串

题目链接： 移动片段得到字符串

思路：思维题

这题如果暴力的话一定会超时，所以不能暴力，我们可以去寻找一些性质

1. 字符串中的所有L和R的相对位置不能变化，也就是这俩字母可以移动，但不可以跳跃
2. 字符串中L在移动过程中下标会变小或不变
3. 字符串中R在移动过程中下标会变动或不变

根据这三条性质我们就可以想明白了，先把start和target中的L 和R提取出来，并且记录对应的下标，然后枚举每个字母即可

• 如果字母不同，直接返回false
• 如果字母是L，如果下标变大，直接false
• 如果字母是R，如果下标变小，直接false

代码

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

第四题现在还不会，以后在补上。

上分越来越艰难了，希望这个暑假能上Guardian

加油！