贪心
1913. 两个数对之间的最大乘积差
两个最大的数减去最小的两个数就行了
class Solution { public: int maxProductDifference(vector<int>& nums) { int max1=0,max2=0,min1=INT_MAX,min2=INT_MAX; for(auto num:nums){ if(max1<num){ max2=max1; max1=num; }else if(max2<num){ max2=num; } if(min1>num){ min2=min1; min1=num; }else if(min2>num){ min2=num; } } return max2*max1-min1*min2; } };
976. 三角形的最大周长
昨天刷过了qwq
class Solution { public: int largestPerimeter(vector<int>& nums) { sort(nums.begin(),nums.end()); for(int i=nums.size()-1;i>=2;i--){ if(nums[i]<nums[i-1]+nums[i-2])return nums[i]+nums[i-1]+nums[i-2]; } return 0; } };
561. 数组拆分 I
把大的和大的取最小值,小的和小的取最小值总和才是最大。也就是先排序,然后两两分组取最小值相加
class Solution { public: int arrayPairSum(vector<int>& nums) { int sum=0; sort(nums.begin(),nums.end()); for(int i=0;i<nums.size();i+=2){ sum+=min(nums[i],nums[i+1]); } return sum; } };
881. 救生艇
昨天刷过了qwq
class Solution { public: int numRescueBoats(vector<int>& people, int limit) { int l=0,r=people.size()-1,res=0; sort(people.begin(),people.end()); while(l<=r){ if(people[l]+people[r]<=limit){ l++; r--; res++; }else if(people[l]>limit)return -1; else{ r--; res++; } } return res; } };
324. 摆动排序 II
把数组排序分为大数和小数部分,然后穿插。用 \(O(n)\) 时间复杂度和 / 或原地 \(O(1)\) 额外空间想不到qwq,以后补票
class Solution { public: void wiggleSort(vector<int>& nums) { vector<int>temp(nums.begin(),nums.end()); sort(temp.begin(),temp.end()); int r=nums.size()-1; for(int i=1;i<nums.size();i+=2){ nums[i]=temp[r--]; } for(int i=0;i<nums.size();i+=2) nums[i]=temp[r--]; } };
455. 分发饼干
先排序一下,尽量用小的饼干满足小的孩子,可以满足孩子数加一,因为饼干只能用一次,而且如果不满足只能往下找,所以不管满不满足饼干都要加一
class Solution { public: int findContentChildren(vector<int>& g, vector<int>& s) { sort(g.begin(),g.end()); sort(s.begin(),s.end()); int i=0,j=0;//i----小孩,j---饼干 while(i<g.size()&&j<s.size()){ if(s[j]>=g[i]){ i++; } j++; } return i; } };
1827. 最少操作使数组递增
如果\(nums[n]>=nums[n-1]\)的话
\[nums[n]=nums[n-1]+c \]次数为c+1的总和
class Solution { public: int minOperations(vector<int>& nums) { if(nums.size()==1)return 0; int res=0; for(int i=0;i<nums.size()-1;i++){ if(nums[i]>=nums[i+1]){ res+=nums[i]-nums[i+1]+1;//计算需要的次数 nums[i+1]=nums[i]+1;//改变nums[i+1]的值 } } return res; } };
945. 使数组唯一的最小增量
先排序一下,然后判断$nums[i]\leq nums[i-1] \(是否为真,如果为真的话,总和为他们相减加上1之和。要记得把\)nums[i]$变成改变后的样子,思路和1827. 最少操作使数组递增差不多qwq
class Solution { public: int minIncrementForUnique(vector<int>& nums) { sort(nums.begin(),nums.end()); int res=0; for(int i=1;i<nums.size();i++){ if(nums[i]<=nums[i-1]){ res+=nums[i-1]+1-nums[i]; nums[i]=nums[i-1]+1; } } return res; } };
611. 有效三角形的个数
固定第一个数,然后枚举第二和第三个数,第二和第三个数之间的距离总和就是结果
public: int triangleNumber(vector<int>& nums) { sort(nums.begin(), nums.end()); int res=0; for(int i=0;i<nums.size();i++){ for(int j=i-1,k=0;j>0&&k<j;j--){ while(k<j&&nums[k]<=nums[i]-nums[j])k++; res+=j-k; } } return res; } };
对贪心不熟练,还得多练一练qwq。写完碎觉( ̄▽ ̄)~*