1051. 高度检查器
学校在拍年度纪念照时，一般要求学生按照 非递减 的高度顺序排列。
请你返回至少有多少个学生没有站在正确位置数量。该人数指的是：能让所有学生以 非递减 高度排列的必要移动人数。
示例：
输入：[1,1,4,2,1,3]
输出：3
解释：
高度为 4、3 和最后一个 1 的学生，没有站在正确的位置。
提示：
1 <= heights.length <= 1001 <= heights[i] <= 100
思路：
这道题我是没做出来的，看了别人的解法我大概理解了意思。
题目要求返回能让所有学生以非递减高度排列的必要移动人数。在这里，我的理解是把学生两两交换，交换的人数就是要返回的结果。那么，什么时候交换呢？答案是，没有站在正确位置的时候就需要交换位置。那么，什么是所谓正确位置呢？答案就是排序过后该学生的位置。
所以答案显而易见了，对于原数组中的元素，如果该元素和数组排序后该元素的位置不同，那么说明该元素的位置发生了变化。
代码：
class Solution {
public:
int heightChecker(vector<int>& heights) {
int res = 0;
vector<int> sorted_heights(heights);
sort(sorted_heights.begin(), sorted_heights.end());
for (int i = 0; i < heights.size(); i++)
{
res += (sorted_heights[i] == heights[i] ? 0: 1);
}
return res;
}
};
1052. 爱生气的书店老板
今天，书店老板有一家店打算试营业 customers.length 分钟。每分钟都有一些顾客（customers[i]）会进入书店，所有这些顾客都会在那一分钟结束后离开。
在某些时候，书店老板会生气。 如果书店老板在第 i 分钟生气，那么 grumpy[i] = 1，否则 grumpy[i] = 0。 当书店老板生气时，那一分钟的顾客就会不满意，不生气则他们是满意的。
书店老板知道一个秘密技巧，能抑制自己的情绪，可以让自己连续 X 分钟不生气，但却只能使用一次。
请你返回这一天营业下来，最多有多少客户能够感到满意的数量。
示例：
输入：customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], X = 3
输出：16
解释：
书店老板在最后 3 分钟保持冷静。
感到满意的最大客户数量 = 1 + 1 + 1 + 1 + 7 + 5 = 16.
提示：
1 <= X <= customers.length == grumpy.length <= 200000 <= customers[i] <= 10000 <= grumpy[i] <= 1
思路：
计算步骤如下：
- 假设老板不抑制自己的情绪，则每分钟不满意的客户的数量为
unsatisfied_customers，类型为vector<int>，计算方式为unsatisfied_customers[i] = customers[i] * grumpy[i] - 当老板不抑制自己的情绪的时候，
customers的sum和unsatisfied_customers的sum都是固定的 - 当老板抑制自己的情绪
X分钟时，在这X分钟内的unsatisfied_customers变为0 - 显然
unsatisfied_customers的sum最小时，可以得到感到满意的最大客户数量 - 所以，现在要将
unsatisfied_customers中的长度为X的某一段变为0，使得unsatisfied_customers的和最小 - 问题转化为，求
unsatisfied_customers中长度为X的子数组的最大和
代码：
class Solution {
public:
int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int X) {
vector<int> unsatisfied_customers(customers.size());
for (int i = 0; i < unsatisfied_customers.size(); i++)
unsatisfied_customers[i] = customers[i] * grumpy[i];
// temp[i]: 在第i分钟开始，老板抑制自己的情绪，在此X分钟内，顾客从不满意变为满意的数量
vector<int> temp(unsatisfied_customers.size() - X + 1);
for (int i = 0; i < temp.size(); i++)
temp[i] = accumulate(unsatisfied_customers.begin() + i, unsatisfied_customers.begin() + i + X, 0);
auto max_it = max_element(temp.begin(), temp.end());
// 结果 = 顾客的总数 - 原本会不满意的数量 + 从不满意变为满意的最大顾客数量
return accumulate(customers.begin(), customers.end(), 0) - accumulate(unsatisfied_customers.begin(), unsatisfied_customers.end(), 0) + *max_it;
}
};
优化：
其中求temp每个元素的时候都要调用accumulate()，会把重复的数据反复相加，而且X越大，重复进行的计算次数就越大。
代替accumulate()的一个方法是使用如下的赋值语句
temp[i] = temp[i-1] - unsatisfied_customers[i-1] + unsatisfied_customers[i+X-1];
这样不管X有多大，只会进行两次加法。
1053. 交换一次的先前排列
给你一个正整数的数组 A（其中的元素不一定完全不同），请你返回可在 一次交换（交换两数字 A[i] 和 A[j] 的位置）后得到的、按字典序排列小于 A 的最大可能排列。
如果无法这么操作，就请返回原数组。
示例 1：
输入：[3,2,1]
输出：[3,1,2]
解释：
交换 2 和 1
示例 2：
输入：[1,1,5]
输出：[1,1,5]
解释：
这已经是最小排列
示例 3：
输入：[1,9,4,6,7]
输出：[1,7,4,6,9]
解释：
交换 9 和 7
示例 4：
输入：[3,1,1,3]
输出：[1,1,3,3]
提示：
1 <= A.length <= 100001 <= A[i] <= 10000
思路：
首先考虑什么情况下可以进行交换。
对于一个数字A，如果要在交换 A[i] 和 A[j] 之后得到一个小于A的数字B（假设i < j），则交换的两个数字必须满足 A[i] > A[j]。
也就是说，对于A[i]，如果在i之后的数字有小于A[i]的数字，就可以交换得到一个小于A的数字。
也就是说，对于一个数字A，如果可以得到一个小于A的最大排列，则A需要满足
\exist{j>i}, A[i]>A[j]
也就是说，只要A[i]不是一个非递减序列，就可以得到一个小于A的最大排列。
另外，对于A，为了得到一个小于A的最大排列，则优先交换低位的数字，也就是A[i]中i较大的位。
计算步骤如下：
- 从
A[i]的末尾往前搜索满足A[i-1]>A[i]的数字，如果没有搜索到，则无法找到小于A的最大排列，返回A。 - 如果搜索到，记录
i-1的位置，第i-1个数字就是要交换的高位数字。 - 从末尾往前搜索，遇到第一个小于
A[i-1]的数字A[j]，就将A[i-1]和A[j]交换，得到结果。
代码：
class Solution {
public:
vector<int> prevPermOpt1(vector<int>& A) {
int n = -1;
for (int i = A.size() - 1; i > 0; i--)
{
if (A[i - 1] > A[i])
{
n = i - 1;
break;
}
}
if (n == -1)
return A;
for (int i = A.size() - 1; i > n; i--)
{
if (A[i] < A[n])
{
swap(A[i], A[n]);
break;
}
}
return A;
}
};
1054. 距离相等的条形码
在一个仓库里，有一排条形码，其中第 i 个条形码为 barcodes[i]。
请你重新排列这些条形码，使其中两个相邻的条形码 不能 相等。 你可以返回任何满足该要求的答案，此题保证存在答案。
示例 1：
输入：[1,1,1,2,2,2]
输出：[2,1,2,1,2,1]
示例 2：
输入：[1,1,1,1,2,2,3,3]
输出：[1,3,1,3,2,1,2,1]
提示：
1 <= barcodes.length <= 100001 <= barcodes[i] <= 10000
思路：
首先建立一个unordered_map<int, int>对条形码和其出现的次数进行记录。
错误思路
这里一开始没想明白，直接按照条形码出现次数从高到低进行排序，保存在vector<pair<int, int>>中。然后对vector从头到尾进行遍历，将vector中的每个条形码push_back到结果中。
结果对于示例2，得到了错误的结果[1,2,3,1,2,3,1,1]。这给了我得到正确解法的思路。
正确思路的错误解法
从错误结果中来看，应该优先将出现次数高的条形码输出到结果中。否则，出现次数少的条形码输出完之后，只剩下了次数多的条形码，只能相邻排列，可以从错误解法结尾的两个1中看到。
还是使用vector<pair<int, int>>对条形码和出现次数进行保存，使用make_heap使其变成一个大顶堆，出现次数高的条形码在数组前端。用变量res保存条形码的输出结果。
对vector从头到尾进行遍历，如果vector[i]和res末尾的数字不同，则将vector[i]对应的条形码输出到res中，否则将vector[i+1]对应的条形码输出到res中。
输出后，将条形码出现的次数-1，对整个vector进行make_heap操作，使其保持大顶堆的性质，继续进行上述操作，直到res的长度和barcodes的长度相等。
但是这个方法每输出一个条形码都要进行一次make_heap操作，导致时间复杂度很高，对于较长的输入数据，直接就超时了。分析了一下，将每次输出的条形码次数-1之后，要使得vector继续保持大顶堆的性质，只需要改变这个输出的条形码的位置就可以，不需要对整个vector重新进行排序。
正确解法
因此考虑使用变量que（数据类型为priority_queue）保存条形码和出现次数，并且使出现次数最高的条形码在队列前端。
如果que.top()和res末尾的条形码不同，则直接将que.top()的条形码输出到res中，并且将该条形码pop之后，使其出现次数-1，再重新push到que中。
代码：
class Solution {
public:
struct cmp
{
bool operator()(pair<int, int> pair_a, pair<int, int> pair_b)
{
if (pair_a.second == pair_b.second)
return pair_a.first > pair_b.first;
return pair_a.second < pair_b.second;
}
};
vector<int> rearrangeBarcodes(vector<int>& barcodes) {
unordered_map<int, int> m;
vector<int> res;
priority_queue < pair<int, int>, vector<pair<int, int>>, cmp> que;
for (int barcode : barcodes)
{
if (m.find(barcode) == m.end())
m.insert(make_pair(barcode, 1));
else
m.at(barcode)++;
}
for (pair<int, int> each_pair : m)
{
que.push(each_pair);
}
while (res.size() != barcodes.size())
{
pair<int, int> top = que.top();
if (!res.empty() && top.first == res.back())
{
pair<int, int> temp1 = top;
que.pop();
pair<int, int> temp2 = que.top();
res.push_back(temp2.first);
temp2.second--;
que.pop();
que.push(temp1);
que.push(temp2);
}
else
{
res.push_back(top.first);
top.second--;
que.pop();
que.push(top);
}
}
return res;
}
};
若有收获，就点个赞吧
0 人点赞
