算法分析课程博客分享 14
949. 给定数字能组成的最大时间(Largest Time for Given Digits)
给定一个由 4 位数字组成的数组，返回可以设置的符合 24 小时制的最大时间。
最小的 24 小时制时间是 00:00，而最大的是 23:59。从 00:00 （午夜）开始算起，过得越久，时间越大。
以长度为 5 的字符串返回答案。如果不能确定有效时间，则返回空字符串。
示例 1：
输入：[1,2,3,4]
输出：”23:41”
示例 2：
输入：[5,5,5,5]
输出：””
提示：
- A.length == 4
- 0 <= A[i] <= 9
解题思路:
显然，在考虑这道题的时候，我们必须考虑 A 中元素的所有组合方式。因此，我们可以使用 std 的 next_permutation() 来完成这一任务。对于每一种组合方式，我们需要先判定当前时间是否合法，若合法，则需与记录中的最大时间进行比较，决定是否需要更新最大时间的值。我们把最大时间初始化为-1:-1，表示一个非法时间，在考虑完全部组合方式后，若记录中的最大时间等于-1:-1，我们返回空串，否则返回格式化后的时间。具体代码如下：
string largestTimeFromDigits(vector<int>& A) {
int hour = -1, minute = -1;
sort(A.begin(), A.end());
do {
int h = A[0]*10 + A[1], m = A[2]*10 + A[3];
if (h > 23 || m > 59)
continue;
if ((h > hour) || (h == hour && m > minute)) {
hour = h;
minute = m;
}
} while(next_permutation(A.begin(), A.end()));
string res = "";
if (hour != -1) {
char buf[4];
sprintf(buf, "%02d:%02d", hour, minute);
res = buf;
}
return res;
}
904. 水果成篮(Fruit Into Baskets)
在一排树中，第 i 棵树产生 tree[i] 型的水果。
你可以从你选择的任何树开始，然后重复执行以下步骤：
- 把这棵树上的水果放进你的篮子里。如果你做不到，就停下来。
- 移动到当前树右侧的下一棵树。如果右边没有树，就停下来。
- 请注意，在选择一颗树后，你没有任何选择：你必须执行步骤 1，然后执行步骤 2，然后返回步骤 1，然后执行步骤 2，依此类推，直至停止。
你有两个篮子，每个篮子可以携带任何数量的水果，但你希望每个篮子只携带一种类型的水果。
用这个程序你能收集的水果总量是多少？
示例 1：
输入：[1,2,1]
输出：3
解释：我们可以收集 [1,2,1]。
示例 2：
输入：[0,1,2,2]
输出：3
解释：我们可以收集 [1,2,2].
如果我们从第一棵树开始，我们将只能收集到 [0, 1]。
示例 3：
输入：[1,2,3,2,2]
输出：4
解释：我们可以收集 [2,3,2,2].
如果我们从第一棵树开始，我们将只能收集到 [1, 2]。
示例 4：
输入：[3,3,3,1,2,1,1,2,3,3,4]
输出：5
解释：我们可以收集 [1,2,1,1,2].
如果我们从第一棵树或第八棵树开始，我们将只能收集到 4 个水果。
提示：
- 1 <= tree.length <= 40000
- 0 <= tree[i] < tree.length
解题思路:
在面对这样的题目时，我们单从题设就可以估计到答案是 O(n) 时间复杂度的。在只允许扫描一遍数组的前提下，假设我们已经得到了一个子区间，在这个子区间内，我们有树 a 与树 b。假如我们扫描到的下一棵树为 a 或者 b，那么我们令当前子区间的长度加一；如果我们扫描到的下一棵树不为 a 或者 b，那么我们需要计算一个新的子区间。我们把扫描到的新的树记为 c，则新区间包含的另一棵树应为 c 的前一棵树。在这个逻辑下，我们设 res 为全局最优解；count 为其中一个子区间的长度。我们用 first 与 second 记录 a 与 b 的位置，这里的位置指 a 或 b 最后一个出现的连续区间的开头位置。借助例子来说明，考虑连续区间 abaab，开始时，first 的值为 0，second 的值为 1。当我们扫描到下标为 2 的 a 时，我们将 first 的值设为原来 second 的值，即 1，然后把 second 的值设为 2；当我们扫描到下标为 3 的 a 时，不更新 first 与 second 的值；当我们扫描到下标为 4 的 b 时，把 first 设成 second 的值，即 2，然后把 second 的值设成 4。我们可以把一个子区间看作若干个 a 或 b 的连续区间的组合，则 first 为倒数第二个连续区间的开头，second 为最后一个连续区间的开头。当我们扫描到 c 时，新的子区间就变成了旧子区间的最后一个连续区间加上当前的树 c，所以新子区间的长度应为旧子区间的最后一个连续区间的长度加一，而旧子区间的最后一个连续区间的长度等于当前下标 i 减去 second。我们只需要在每次获得新的子区间时，通过比较 res 与 count 来对 res 进行更新，即可获得题目所需的解。具体代码如下：
int totalFruit(vector<int>& tree) {
int res = 0, count = 0;
int first = 0, second = 0;
for (int i = 0; i < tree.size(); ++i) {
if (tree[i] == tree[second]) {
++count;
} else if (tree[i] == tree[first]) {
first = second;
second = i;
++count;
} else {
res = max(res, count);
first = second;
second = i;
count = second - first + 1;
}
}
return max(res, count);
}
950. 按递增顺序显示卡牌(Reveal Cards In Increasing Order)
牌组中的每张卡牌都对应有一个唯一的整数。你可以按你想要的顺序对这套卡片进行排序。
最初，这些卡牌在牌组里是正面朝下的（即，未显示状态）。
现在，重复执行以下步骤，直到显示所有卡牌为止：
- 从牌组顶部抽一张牌，显示它，然后将其从牌组中移出。
- 如果牌组中仍有牌，则将下一张处于牌组顶部的牌放在牌组的底部。
- 如果仍有未显示的牌，那么返回步骤 1。否则，停止行动。
返回能以递增顺序显示卡牌的牌组顺序。
答案中的第一张牌被认为处于牌堆顶部。
示例：
输入：[17,13,11,2,3,5,7]
输出：[2,13,3,11,5,17,7]
解释：
我们得到的牌组顺序为 [17,13,11,2,3,5,7]（这个顺序不重要），然后将其重新排序。
重新排序后，牌组以 [2,13,3,11,5,17,7] 开始，其中 2 位于牌组的顶部。
我们显示 2，然后将 13 移到底部。牌组现在是 [3,11,5,17,7,13]。
我们显示 3，并将 11 移到底部。牌组现在是 [5,17,7,13,11]。
我们显示 5，然后将 17 移到底部。牌组现在是 [7,13,11,17]。
我们显示 7，并将 13 移到底部。牌组现在是 [11,17,13]。
我们显示 11，然后将 17 移到底部。牌组现在是 [13,17]。
我们展示 13，然后将 17 移到底部。牌组现在是 [17]。
我们显示 17。
由于所有卡片都是按递增顺序排列显示的，所以答案是正确的。
提示：
- 1 <= A.length <= 1000
- 1 <= A[i] <= 10^6
- 对于所有的 i != j，A[i] != A[j]
解题思路:
对于这道题目，由于我们需要以递增顺序显示卡牌，我们必须先对 deck 进行排序，获得正确的显示序列，再根据显示序列获得所需的卡牌序列。我们使用一个 deque 来模拟翻牌的过程，通过逆推的形式求出卡牌序列。假设我们有一个卡组，当我们需要展示一张牌时，我们会展示牌组顶部的一张牌，然后将其下一张牌置于卡组底部。那么如果我们此时想还原到还未展示卡牌时的状态，我们需要把卡组底部的牌放置在卡组顶部，然后把刚才展示的牌放回卡组顶部。根据这个逻辑，我们只需要从后往前扫描排序过的 deck 即可获得所需的卡牌序列。具体代码如下：
vector<int> deckRevealedIncreasing(vector<int>& deck) {
sort(deck.begin(), deck.end());
deque<int> res;
for (int i = deck.size()-2; i >= 0; --i) {
res.push_front(res.back());
res.pop_back();
res.push_front(deck[i]);
}
return vector<int>(res.begin(), res.end());
}