算法【贪心经典题目专题3】

题目一

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

题目二

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