Problem List
- [1] 装满杯子需要的最短总时长
- [2] 无限集中的最小数字
- [3] 移动片段得到字符串
1. 装满杯子需要的最短总时长
1.1 题目描述
现有一台饮水机，可以制备冷水、温水和热水。每秒钟，可以装满 2 杯 不同 类型的水或者 1 杯任意类型的水。
给你一个下标从 0 开始、长度为 3 的整数数组 amount ，其中 amount[0]、amount[1] 和 amount[2] 分别表示需要装满冷水、温水和热水的杯子数量。返回装满所有杯子所需的 最少 秒数。
示例1：
输入： amount = [1,4,2]
输出： 4
解释： 下面给出一种方案：
第 1 秒：装满一杯冷水和一杯温水。
第 2 秒：装满一杯温水和一杯热水。
第 3 秒：装满一杯温水和一杯热水。
第 4 秒：装满一杯温水。
可以证明最少需要 4 秒才能装满所有杯子。示例2：
输入： amount = [5,4,4]
输出： 7
解释： 下面给出一种方案：
第 1 秒：装满一杯冷水和一杯热水。
第 2 秒：装满一杯冷水和一杯温水。
第 3 秒：装满一杯冷水和一杯温水。
第 4 秒：装满一杯温水和一杯热水。
第 5 秒：装满一杯冷水和一杯热水。
第 6 秒：装满一杯冷水和一杯温水。
第 7 秒：装满一杯热水。示例2：
输入： amount = [5,0,0]
输出： 5
解释： 每秒装满一杯冷水。
1.2 思路
求最大值，如果另外两个值的加和小于最大值，则直接返回最大值；否则返回三者加和的一半(如果除2不尽的话要+1).
class Solution {
public:
int fillCups(vector<int>& amount) {
int maxVal = 0, sum = 0;
for(int i = 0; i < 3; ++i) {
sum += amount[i];
maxVal = max(maxVal, amount[i]);
}
if(maxVal >= sum - maxVal) return maxVal;
return sum % 2 == 1 ? sum / 2 + 1 : sum / 2;
}
}; 2. 无限集中的最小数字
2.1 题目描述
现有一个包含所有正整数的集合 [1, 2, 3, 4, 5, ...] 。
实现 SmallestInfiniteSet 类：
SmallestInfiniteSet() 初始化 SmallestInfiniteSet 对象以包含 所有 正整数。int popSmallest() 移除 并返回该无限集中的最小整数。void addBack(int num) 如果正整数 num 不 存在于无限集中，则将一个 num 添加 到该无限集中。
示例1：
输入： [“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 ，并将其从集合中移除。
2.2 思路
set插入1-1000的数字，popSmallest则存放set.begin()指向的值，并将该值从set中erase掉，addBack则对应insert.
class SmallestInfiniteSet {
set<int> s;
public:
SmallestInfiniteSet() {
for(int i = 1; i <= 1000; ++i) {
s.insert(i);
}
}
int popSmallest() {
int ret = *s.begin();
s.erase(ret);
return ret;
}
void addBack(int num) {
s.insert(num);
}
}; 3. 移动片段得到字符串
3.1 题目描述
给你两个字符串 start 和 target ，长度均为 n 。每个字符串 仅 由字符 'L'、'R' 和 '_' 组成，其中：
- 字符
'L'和'R'表示片段，其中片段'L'只有在其左侧直接存在一个 空位 时才能向 左 移动，而片段'R'只有在其右侧直接存在一个 空位 时才能向 右 移动。 - 字符
'_'表示可以被 任意'L'或'R'片段占据的空位。
如果在移动字符串 start 中的片段任意次之后可以得到字符串 target ，返回 true ；否则，返回 false。
示例1：
输入： start = “_LRR_”, target = “L__RR”
输出： true
解释： 可以从字符串 start 获得 target ，需要进行下面的移动：
- 将第一个片段向左移动一步，字符串现在变为 “L_RR_” 。
- 将最后一个片段向右移动一步，字符串现在变为 “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 。
3.2 思路
遍历start和target，去除空位_后如果两者不相等说明无法从start变到target：L和R的位置有相反的或者个数不一致。
记录两个字符串中L和R对应出现的索引，如果出现start的L索引小于target中对应的L的索引或start的R索引大于target中对应的R的索引时，说明存在L/R由于只能朝一个方向移动而导致无法移动到目标位置，返回false.
class Solution {
public:
bool canChange(string start, string target) {
vector<int> left1, left2, right1, right2;
string s = "", t = "";
for(int i = 0; i < start.length(); ++i) {
if(start[i] == 'R') {
right1.emplace_back(i);
s += start[i];
}else if(start[i] == 'L') {
left1.emplace_back(i);
s += start[i];
}
if(target[i] == 'R') {
right2.emplace_back(i);
t += target[i];
}else if(target[i] == 'L') {
left2.emplace_back(i);
t += target[i];
}
}
if(s != t) return false;
for(int i = 0; i < left1.size(); ++i) {
if(left1[i] < left2[i]) return false;
}
for(int i = 0; i < right1.size(); ++i) {
if(right1[i] > right2[i]) return false;
}
return true;
}
};
