银川网站建设公司排名,域名对网站seo的影响吗,微信小程序怎么做广告推广,wordpress进行不此系列分三章来记录leetcode的有关贪心算法题解#xff0c;题目我都会给出具体实现代码#xff0c;如果看不懂的可以后台私信我。 本章目录 1.柠檬水找零2.将数组和减半的最少操作次数3.最大数4.摆动序列5.最长递增子序列6.递增的三元子序列7.最长连续递增序列8.买卖股票的最…此系列分三章来记录leetcode的有关贪心算法题解题目我都会给出具体实现代码如果看不懂的可以后台私信我。 本章目录 1.柠檬水找零2.将数组和减半的最少操作次数3.最大数4.摆动序列5.最长递增子序列6.递增的三元子序列7.最长连续递增序列8.买卖股票的最佳时机9.买卖股票的最佳时机II10.K次取反后最大化的数组和11.按身高排序12.优势洗牌 1.柠檬水找零
柠檬水找零
class Solution {
public:bool lemonadeChange(vectorint bills) {int five 0,ten 0;for(auto x:bills){if(x5) five;else if(x10){if(five 0) return false;five--;ten;}else{if(tenfive) //贪心{ten--;five--;}else if(five3){five - 3;}else return false;}}return true;}
};2.将数组和减半的最少操作次数
将数组和减半的最少操作次数
class Solution {
public:int halveArray(vectorint nums) {//贪心大根堆priority_queuedouble heap;double sum 0.0;for(auto x:nums){sum x;heap.push(x);}sum / 2.0;int count 0;while(sum0){auto t heap.top()/2.0;heap.pop();sum - t;count;heap.push(t);}return count;}
};3.最大数
最大数
class Solution {
public:string largestNumber(vectorint nums) {//优化将整型都转成字符串通过比较字符串的字典序来比大小vectorstring strs;for(auto x:nums) strs.push_back(to_string(x));sort(strs.begin(),strs.end(),[](const string s1,const string s2){return s1s2s2s1;});string ret;for(auto s: strs) rets;//处理前导零if(ret[0]0) return 0;return ret;}
};4.摆动序列
摆动序列
class Solution {
public:int wiggleMaxLength(vectorint nums) {//贪心:找极值点建议大家将nums画成折线图进行观察int n nums.size();if(n2) return n;int ret 0,left 0;for(int i0;in-1;i){int right nums[i1]-nums[i];if(right 0) continue;if(left*right0) ret; //两边异号left right;}return ret1;//最后一个点必要}
};5.最长递增子序列
最长递增子序列
class Solution {
public:int lengthOfLIS(vectorint nums) {//自己设计一个数组此数组的每个元素表示存储长度为x的子序列的最后一个元素的最小值int n nums.size();vectorint ret;ret.push_back(nums[0]);for(int i1;in;i){if(nums[i]ret.back()){ret.push_back(nums[i]);}else{int left 0,right ret.size()-1;while(leftright){int mid (leftright)1;if(ret[mid]nums[i]) left mid1;else right mid;}ret[left] nums[i];}}return ret.size();}
};6.递增的三元子序列
递增的三元子序列
class Solution {
public:bool increasingTriplet(vectorint nums) {int a nums[0],b INT_MAX;for(int i1;inums.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(vectorint nums) {//贪心双指针int ret 0,n nums.size();for(int i0;in;){int j i1;while(jn nums[j]nums[j-1]) j;ret max(ret,j-i);i j;//直接在循环中更新下一个起点的位置体现了贪心}return ret;}
};8.买卖股票的最佳时机
买卖股票的最佳时机
class Solution {
public:int maxProfit(vectorint prices) {int ret 0,minElem INT_MAX;int n prices.size();for(int i0;in;i){ret max(ret,prices[i]-minElem);//先更新结果minElem min(minElem,prices[i]);//再更新最小值}return ret;}
};
9.买卖股票的最佳时机II
买卖股票的最佳时机II述
class Solution {
public:int maxProfit(vectorint prices) {//法一双指针int ret 0,n prices.size();for(int i0;in;i){int j i;while(j1n prices[j1]prices[j]) j;ret prices[j]-prices[i];i j;}return ret;}
};class Solution {
public:int maxProfit(vectorint prices) {//法二一天一天进行计算int ret 0,n prices.size();for(int i1;in;i){if(prices[i]-prices[i-1]0) ret (prices[i]-prices[i-1]);}return ret;}
};10.K次取反后最大化的数组和
K次取反后最大化的数组和
class Solution {
public:int largestSumAfterKNegations(vectorint nums, int k) {int m 0,minElem INT_MAX,n nums.size();for(auto x:nums){if(x0) m;minElem min(minElem,abs(x));}int ret 0;if(mk){sort(nums.begin(),nums.end());for(int i0;ik;i){ret -nums[i];}for(int ik;in;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:vectorstring sortPeople(vectorstring names, vectorint heights) {//1.创建一个下标数组int n names.size();vectorint index(n);for(int i0;in;i) index[i] i;//2.对下标数组进行排序sort(index.begin(),index.end(),[](int i,int j){return heights[i]heights[j];});//3.输出结果vectorstring ret;for(auto x:index){ret.push_back(names[x]);}return ret;}
};12.优势洗牌
优势洗牌
class Solution {
public:vectorint advantageCount(vectorint nums1, vectorint nums2) {//此题可以学习对应的策略积累经验int n nums1.size();//1.排序sort(nums1.begin(),nums1.end());vectorint index2(n);for(int i0;in;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;vectorint ret(n);for(int i0;in;i){if(nums1[i]nums2[index2[left]]) ret[index2[left]] nums1[i];else ret[index2[right--]] nums1[i];}return ret;}
};
