leetcode贪心算法题总结(一)

此系列分三章来记录leetcode的有关贪心算法题解，题目我都会给出具体实现代码，如果看不懂的可以后台私信我。

1.柠檬水找零

柠檬水找零

class Solution {
public:bool lemonadeChange(vector<int>& bills) {int five = 0,ten = 0;for(auto x:bills){if(x==5) five++;else if(x==10){if(five == 0) return false;five--;ten++;}else{if(ten&&five) //贪心{ten--;five--;}else if(five>=3){five -= 3;}else return false;}}return true;}
};

2.将数组和减半的最少操作次数

将数组和减半的最少操作次数

class Solution {
public:int halveArray(vector<int>& nums) {//贪心+大根堆priority_queue<double> heap;double sum = 0.0;for(auto x:nums){sum += x;heap.push(x);}sum /= 2.0;int count =0;while(sum>0){auto t = heap.top()/2.0;heap.pop();sum -= t;count++;heap.push(t);}return count;}
};

3.最大数

最大数

class Solution {
public:string largestNumber(vector<int>& nums) {//优化：将整型都转成字符串，通过比较字符串的字典序来比大小vector<string> strs;for(auto x:nums) strs.push_back(to_string(x));sort(strs.begin(),strs.end(),[&](const string& s1,const string& s2){return s1+s2>s2+s1;});string ret;for(auto& s: strs) ret+=s;//处理前导零if(ret[0]=='0') return "0";return ret;}
};

4.摆动序列

摆动序列

class Solution {
public:int wiggleMaxLength(vector<int>& nums) {//贪心:找极值点，建议大家将nums画成折线图进行观察int n = nums.size();if(n<2) return n;int ret =0,left = 0;for(int i=0;i<n-1;i++){int right = nums[i+1]-nums[i];if(right == 0) continue;if(left*right<=0) ret++; //两边异号left = right;}return ret+1;//最后一个点必要}
};

5.最长递增子序列

最长递增子序列

class Solution {
public:int lengthOfLIS(vector<int>& nums) {//自己设计一个数组，此数组的每个元素表示存储长度为x的子序列的最后一个元素的最小值int n = nums.size();vector<int> ret;ret.push_back(nums[0]);for(int i=1;i<n;i++){if(nums[i]>ret.back()){ret.push_back(nums[i]);}else{int left = 0,right = ret.size()-1;while(left<right){int mid = (left+right)>>1;if(ret[mid]<nums[i]) left = mid+1;else right = mid;}ret[left] = nums[i];}}return ret.size();}
};

6.递增的三元子序列

递增的三元子序列

class Solution {
public:bool increasingTriplet(vector<int>& nums) {int a = nums[0],b = INT_MAX;for(int i=1;i<nums.size();i++){if(nums[i]>b) return true;if(nums[i]>a) b = nums[i];else a = nums[i];}return false;}
};

7.最长连续递增序列

最长连续递增序列

class Solution {
public:int findLengthOfLCIS(vector<int>& nums) {//贪心+双指针int ret = 0,n = nums.size();for(int i=0;i<n;){int j = i+1;while(j<n&& nums[j]>nums[j-1]) j++;ret = max(ret,j-i);i = j;//直接在循环中更新下一个起点的位置，体现了贪心}return ret;}
};

8.买卖股票的最佳时机

买卖股票的最佳时机

class Solution {
public:int maxProfit(vector<int>& prices) {int ret = 0,minElem = INT_MAX;int n = prices.size();for(int i=0;i<n;i++){ret = max(ret,prices[i]-minElem);//先更新结果minElem = min(minElem,prices[i]);//再更新最小值}return ret;}
};

9.买卖股票的最佳时机II

买卖股票的最佳时机II述

class Solution {
public:int maxProfit(vector<int>& prices) {//法一：双指针int ret = 0,n = prices.size();for(int i=0;i<n;i++){int j = i;while(j+1<n && prices[j+1]>prices[j]) j++;ret += prices[j]-prices[i];i = j;}return ret;}
};class Solution {
public:int maxProfit(vector<int>& prices) {//法二：一天一天进行计算int ret = 0,n = prices.size();for(int i=1;i<n;i++){if(prices[i]-prices[i-1]>0) ret += (prices[i]-prices[i-1]);}return ret;}
};

10.K次取反后最大化的数组和

K次取反后最大化的数组和

class Solution {
public:int largestSumAfterKNegations(vector<int>& nums, int k) {int m = 0,minElem = INT_MAX,n = nums.size();for(auto x:nums){if(x<0) m++;minElem = min(minElem,abs(x));}int ret = 0;if(m>k){sort(nums.begin(),nums.end());for(int i=0;i<k;i++){ret += -nums[i];}for(int i=k;i<n;i++){ret += nums[i];}}else{for(auto x:nums){ret += abs(x);}if((k-m)%2!=0){ret -= minElem*2;}}return ret;}
};

11.按身高排序

按身高排序

class Solution {
public:vector<string> sortPeople(vector<string>& names, vector<int>& heights) {//1.创建一个下标数组int n = names.size();vector<int> index(n);for(int i=0;i<n;i++) index[i] = i;//2.对下标数组进行排序sort(index.begin(),index.end(),[&](int i,int j){return heights[i]>heights[j];});//3.输出结果vector<string> ret;for(auto x:index){ret.push_back(names[x]);}return ret;}
};

12.优势洗牌

优势洗牌

class Solution {
public:vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {//此题可以学习对应的策略，积累经验int n = nums1.size();//1.排序sort(nums1.begin(),nums1.end());vector<int> index2(n);for(int i=0;i<n;i++) index2[i] = i;sort(index2.begin(),index2.end(),[&](int i,int j){return nums2[i]<nums2[j];});//2.田忌赛马int left = 0,right = n-1;vector<int> ret(n);for(int i=0;i<n;i++){if(nums1[i]>nums2[index2[left]]) ret[index2[left++]] = nums1[i];else ret[index2[right--]] = nums1[i];}return ret;}
};