题目一
测试链接：581. 最短无序连续子数组 - 力扣（LeetCode）
分析：这道题只需要找到左边界和右边界即可，对于左边界代表左边界右边的最小值都比左边界大，右边界代表右边界左边的最大值都比右边界小。代码如下。
class Solution {
public:
int findUnsortedSubarray(vector<int>& nums) {
if(nums.size() == 1){
return 0;
}
int length = nums.size();
int left_max = nums[0];
int left = 0;
for(int i = 1;i < length;++i){
if(left_max > nums[i]){
left = i;
}
left_max = max(left_max, nums[i]);
}
int right_min = nums[length-1];
int right = length - 1;
for(int i = length-2;i >= 0;--i){
if(right_min < nums[i]){
right = i;
}
right_min = min(right_min, nums[i]);
}
return max(left - right + 1, 0);
}
};题目二
测试链接：https://leetcode.cn/problems/smallest-range-covering-elements-from-k-lists/
分析：将每一个列表的第一个数放入有序表中，即可得到这些数组成的区间，将最小的数弹出，然后将弹出的数字所属列表中的第二个数加入游戏表，得到一个新的区间，更新区间，直到其中一个列表遍历完即可得到答案。代码如下。
class Solution {
public:
int nums_index[3500] = {0};
vector<int> smallestRange(vector<vector<int>>& nums) {
multimap<int, int> table;
vector<int> ans;
ans.push_back(-100000);
ans.push_back(100000);
int len = 200001;
int length = nums.size();
for(int i = 0;i < length;++i){
table.insert(pair<int, int>(nums[i][0], i));
}
map<int, int>::iterator minValue, maxValue;
int from;
while (true)
{
minValue = table.begin();
maxValue = table.end();
--maxValue;
if((*maxValue).first - (*minValue).first + 1 < len){
len = (*maxValue).first - (*minValue).first + 1;
ans[0] = (*minValue).first;
ans[1] = (*maxValue).first;
}
from = (*minValue).second;
if(++nums_index[from] == nums[from].size()){
break;
}
table.erase(minValue);
table.insert(pair<int, int>(nums[from][nums_index[from]], from));
}
return ans;
}
};题目三
组团买票
景区里一共有m个项目，景区的第i个项目有如下两个参数：game[i] = { Ki, Bi }，Ki、Bi一定是正数。Ki代表折扣系数，Bi代表票价，举个例子 : Ki = 2, Bi = 10，如果只有1个人买票，单张门票的价格为 : Bi - Ki * 1 = 8，所以这1个人游玩该项目要花8元，如果有2个人买票，单张门票的价格为 : Bi - Ki * 2 = 6，所以这2个人游玩该项目要花6 * 2 = 12元，如果有5个人买票，单张门票的价格为 : Bi - Ki * 5 = 0，所以这5个人游玩该项目要花5 * 0 = 0元，如果有更多人买票，都认为花0元。于是可以认为，如果有x个人买票，单张门票的价格为 : Bi - Ki * x，x个人游玩这个项目的总花费是 : max { x * (Bi - Ki * x), 0 }。单位一共有n个人，每个人最多可以选1个项目来游玩，也可以不选任何项目，由你去按照上面的规则，统一花钱购票。你想知道自己需要准备多少钱，就可以应付所有可能的情况，返回这个最保险的钱数。
1 <= M、N、Ki、Bi <= 10^5
来自真实大厂笔试，没有在线测试。
分析：最保险的钱数就是让景区赚的钱最大，可以考虑对每一个来的人进行判断，如果这个人还可以让景区赚到钱，就将这个人分配到赚钱最多的项目；如果不能赚到钱，直接停止。代码如下。
class Solution {
public:
class Game{
public:
int ki;
int bi;
int people;
int earn(){
return bi - 2 * people * ki - ki;
}
Game(int a, int b, int c){
ki = a;
bi = b;
people = c;
}
};
int maxMoney(vector<vector<int>>& game, int n) {
int length = game.size();
auto cmp = [](Game& g1, Game& g2){
return g1.earn() < g2.earn();
};
priority_queue<Game, vector<Game>, decltype(cmp)> p(cmp);
for(int i = 0;i < length;++i){
Game temp(game[i][0], game[i][1], 0);
p.push(temp);
}
int ans = 0;
for(int i = 1;i <= n;++i){
Game temp = p.top();
p.pop();
if(temp.earn() <= 0){
break;
}
ans += temp.earn();
++temp.people;
p.push(temp);
}
return ans;
}
};题目四
平均值最小累加和
给定一个数组arr，长度为n，再给定一个数字k，表示一定要将arr划分成k个集合，每个数字只能进一个集合。返回每个集合的平均值都累加起来的最小值，平均值向下取整
1 <= n <= 10^5 0 <= arr[i] <= 10^5 1 <= k <= n
来自真实大厂笔试，没有在线测试。
分析：因为一个大的数和一个小的数进行求平均值会将小的数拉高，所以将前k-1个小的数单独成k-1个集合，剩下的数成一个集合，那样求出来就是每个集合的平均值累加最小。代码如下。
class Solution {
public:
int minAverage(vector<int>& arr, int k) {
int length = arr.size();
int sum = 0;
for(int i = 0;i < k-1;++i){
sum += arr[i];
}
int temp = 0;
for(int i = k-1;i < length;++i){
temp += arr[i];
}
temp /= (length - k + 1);
sum += temp;
return sum;
}
};题目五
执行所有任务的最少初始电量
每一个任务有两个参数，需要耗费的电量、至少多少电量才能开始这个任务。返回手机至少需要多少的初始电量，才能执行完所有的任务。
来自真实大厂笔试，没有在线测试。
分析：这道题的基本思路是从电量为0开始往回推且可以看出将任务耗费电量大的放前面、至少多少电量小的放前面，但是如果单一考虑这两个方向，总会找到反例，所以需要将这两个方向统一起来考虑。因为需要耗费电量越大越好，至少电量越小越好，所以构造变量耗费电量减至少电量，这个变量越大越好。进行排序后遍历回推即可得到答案。代码如下。
class Solution {
public:
int minPower(vector<vector<int>>& tasks) {
int length = tasks.size();
sort(tasks.begin(), tasks.end(), [](vector<int>& v1, vector<int>& v2){
return (v1[0] - v1[1]) > (v2[0] - v2[1]);
});
int power = 0;
for(int i = 0;i < length;++i){
power += tasks[i][0];
if(power < tasks[i][1]){
power = tasks[i][1];
}
}
return power;
}
};题目六
两个0和1数量相等区间的最大长度
给出一个长度为n的01串，现在请你找到两个区间使得这两个区间中，1的个数相等，0的个数也相等。这两个区间可以相交，但是不可以完全重叠，即两个区间的左右端点不可以完全一样。现在请你找到两个最长的区间，满足以上要求，返回区间最大长度
来自真实大厂笔试，没有在线测试。
分析：这道题只需找到从左开始第一个0的位置和第一个1的位置，从右边开始第一个0的位置和第一个1的位置，对同是0和同是1进行长度的计算取最大值即可。代码如下。
class Solution {
public:
int maxLen(vector<int>& arr) {
int left_zero = -1, left_one = -1;
int right_zero = -1, right_one = -1;
int length = arr.size();
for(int i = 0;i < length;++i){
if(left_zero >= 0 && left_one >= 0){
break;
}
if(arr[i] == 0 && left_zero < 0){
left_zero = i;
}
if(arr[i] == 1 && left_one < 0){
left_one = i;
}
}
for(int i = length-1;i >= 0;--i){
if(right_zero >= 0 && right_one >= 0){
break;
}
if(arr[i] == 0 && right_zero < 0){
right_zero = i;
}
if(arr[i] == 1 && right_one < 0){
right_one = i;
}
}
int ans = 0;
if(left_zero >= 0 && right_zero >= 0){
ans = max(ans, right_zero - left_zero);
}
if(left_one >= 0 && right_one >= 0){
ans = max(ans, right_one - left_one);
}
return ans;
}
};