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

核心思路：

该题的模拟思路是比较简单的，但也有细节需要注意。
- 首先要清楚的是，当某一种水的数量（也就是数组中某个数值）为 0 的时候，需要的时长为剩余的两个数中更大的那一个。
- 假若三种水的数量都不为 0，则需要将此时数组中最大的数和最小的数减一。【这里也可以将最大的数和次大的数消耗掉，因为策略是尽快将最大的数耗掉】
- 因此可以从题解中知道需要用大根堆来维护实时排序的结果。【这里为了代码简洁我选择每次模拟完后将数组排序】
可以实现 O(1) 时间复杂度的解法，看了评论区才明白是如何实现。
- 一开始我也猜到要将最大的数量匀到第一小的数量和第二小的数量中，因此对数组进行排序。
- 当 amount[2] >= amount[0] + amount[1] 的时候，可以知道此时需要最大的数量次数来装满杯子，即直接返回 amount[2] 即可。
- 但关键是当 amount[2] < amount[0] + amount[1] 的时候，需要返回 ceil(sum(amount)/2)。【做题的时候就是这里卡了很久，我看了几个题解，每个题解的分析还不太一样，具体分析看后面参考内容的链接】

代码实现：

模拟解法代码实现如下：

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

分类讨论解法代码实现如下：

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

参考内容：

时间复杂度 O(1) 简洁代码

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

核心思路：

该题是设计题，题目也很直白，就是维护无限集合中的数值，每次会弹出最小数值，同时也可以插入数值。
- 根据题意可以维护无限集的起始位置，以及无限集前面零散的插入数据。

代码实现：

class SmallestInfiniteSet
{
private:
    int start;
    set<int> ss;
public:
    SmallestInfiniteSet() : start(1) {}
    
    int popSmallest()
    {
        int ans;
        if(ss.empty()) ans = start++;
        else
        {
            ans = min(*ss.begin(), start);
            ss.erase(ss.begin());
        }
        return ans;
    }
    
    void addBack(int num)
    {
        if(num >= start or ss.count(num)) return;
        ss.insert(num);
    }
};

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

核心思路：

该题做的时候一直没想明白究竟如何才算不可移动，其实直接观察 L 和 R 在 start 和 target 中的索引位置即可。
- 如 start = "L_" 和 target = "_L"，显然返回 false，因为 L 的索引分别为 i = 0 和 j = 1，i < j 所以该 L 无法通过左移操作从 i 到 j。

代码实现：

双指针解法代码实现如下：【代码来自参考内容链接】

class Solution {
public:
    bool canChange(string &start, string &target) {
        auto s = start, t = target;
        s.erase(remove(s.begin(), s.end(), '_'), s.end());
        t.erase(remove(t.begin(), t.end(), '_'), t.end());
        if (s != t) return false;
        for (int i = 0, j = 0; i < start.length(); ++i) {
            if (start[i] == '_') continue;
            while (target[j] == '_') ++j;
            if (i != j && (start[i] == 'L') == (i < j)) // if start[i] == 'L' and i < j, return false
              return false;
            ++j;
        }
        return true;
    }
};