公主坟网站建设a5站长网

题目一

测试链接：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;}
};