本次的周赛题目都很简单，但是参赛的时候还是没有完成，太菜。
leetcode第138场周赛赛题地址： https://leetcode-cn.com/contest/weekly-contest-138
学校在拍年度纪念照时，一般要求学生按照 非递减 的高度顺序排列。 请你返回至少有多少个学生没有站在正确位置数量。该人数指的是：能让所有学生以 非递减 高度排列的必要移动人数。
示例： 输入：[1,1,4,2,1,3] 输出：3 解释： 高度为 4、3 和最后一个 1 的学生，没有站在正确的位置。 提示： 1 <= heights.length <= 100 1 <= heights[i] <= 100
参赛的时候被“必要移动人数”给吓住了，其实只要排个序，看几个位置不对就可以了。
class Solution { public: int heightChecker(vector<int>& heights) { vector<int> heights_sort(heights); sort(heights_sort.begin(), heights_sort.end()); int ans = 0; for (int i = 0; i < heights.size(); i++) { ans += (heights[i] != heights_sort[i]); } return ans; } };今天，书店老板有一家店打算试营业 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 <= 20000 0 <= customers[i]<= 1000 0 <= grumpy[i] <= 1
我的想法比较简单粗暴，就是先遍历一遍，看X分钟用在哪一段能够收获最大效益，然后再把剩下的给计算了。
class Solution { public: int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int X) { int ans = 0, maxnum = 0, maxindex = 0; for (int i = 0; i < customers.size()-(X-1); ++i) { int sum = 0; for (int j = i; j < i+X; ++j) { sum += (customers[j] * grumpy[j]); } if (sum > maxnum) { maxnum = sum; maxindex = i; } } for (int i = 0; i < customers.size(); ) { if (i == maxindex) { for (; i < maxindex+X; ++i) { ans += customers[i]; } } else { ans += (customers[i] * (!grumpy[i])); ++i; } } return ans; } };给你一个正整数的数组 A（其中的元素不一定完全不同），请你返回可在 一次交换（交换两数字 A[i] 和 A[j] 的位置）后得到的、按字典序排列小于 A 的最大可能排列。
如果无法这么操作，就请返回原数组。
示例 1：
输入：[3,2,1] 输出：[3,1,2] 解释： 交换 2 和 1
示例 4：
输入：[3,1,1,3] 输出：[1,1,3,3]
提示：
1 <= A.length <= 10000 1 <= A[i] <= 10000
这题也是很简单的，从后往前，找后面比当前小的数中的最大值进行替换就好。
class Solution { public: vector<int> prevPermOpt1(vector<int>& A) { // 从倒数第二个开始，找后面比它小的里面最大的 int l = 0, r = 0; // 找到的两个要交换的位置 int less_max = -1; for (int i = A.size()-1; i >= 0; --i) { for (int j = i+1; j < A.size(); ++j) { if (A[j] < A[i] && A[j] > less_max) { less_max = A[j]; l = i; r = j; } } if(less_max != -1) { break; } } if (less_max != -1) { // 找到了 int temp = A[l]; A[l] = A[r]; A[r] = temp; } return A; } };但是WA了，不知道怎么回事，看了一下出错的和示例4，3113应该要得到1133？？？？这个示例让我很不解, 感觉好像不符合题意，是我题目理解错了吗？
改了一下判断条件，使得交换的那个数是靠个位的那个，然后就符合示例4了，也AC了。没懂题目意思。
if (A[j] < A[i] && A[j] >= less_max) { less_max = A[j]; l = i; r = j; }在一个仓库里，有一排条形码，其中第 i 个条形码为 barcodes[i]。
请你重新排列这些条形码，使其中两个相邻的条形码 不能 相等。 你可以返回任何满足该要求的答案，此题保证存在答案。
输入：[1,1,1,2,2,2] 输出：[2,1,2,1,2,1]
1 <= barcodes.length <= 10000 1 <= barcodes[i] <= 10000
参赛的时候想的是 先排个序，然后从前往后调整一百年，再从后往前调整一遍，结果超时了。
class Solution { public: vector<int> rearrangeBarcodes(vector<int>& barcodes) { sort(barcodes.begin(), barcodes.end()); for (int i = 0; i < barcodes.size()-1; i++) { if (barcodes[i] == barcodes[i+1]) { for (int j = i+2; j < barcodes.size(); j++) { if (barcodes[j] != barcodes[i]) { int temp = barcodes[j]; barcodes.erase(barcodes.begin()+j); barcodes.insert(barcodes.begin()+i+1, temp); ++i; break; } } } } for (int i = barcodes.size()-1; i >= 1; --i) { if (barcodes[i] == barcodes[i-1]) { for (int j = 0; j < barcodes.size(); ++j) { if (barcodes[j] != barcodes[i]) { int temp = barcodes[j]; barcodes.insert(barcodes.begin()+i, temp); barcodes.erase(barcodes.begin()+j); --i; break; } } } } return barcodes; } };其实思路也很简单，插空安排各数字即可。水平不够，码代码调bug用时太长，最后没时间了，理不清思路。
class Solution { public: vector<int> rearrangeBarcodes(vector<int>& B) { int N = B.size(); sort(B.begin(), B.end()); vector<int> cnt(10001); for (auto &b: B) cnt[b]++; int mB = max_element(cnt.begin(), cnt.end()) - cnt.begin(); B.erase(remove(B.begin(), B.end(), mB), B.end()); int L = 0; vector<int> tmp(N); for (int S = 0; S < 2; S++) { for (int i = S; i < N; i+=2) { if (cnt[mB]) tmp[i] = mB, cnt[mB]--; else tmp[i] = B[L++]; } } return tmp; } };