九日集训第六天

目录

两个数对之间最大的乘积差

三角形的最大周长

数组拆分

救生艇

摆动排序||

分发饼干

最少操作使数组递增

使数组唯一的最小增量

有效三角形的个数

---

两个数对之间最大的乘积差

class Solution {
public:int maxProductDifference(vector<int>& nums) {sort(nums.begin(),nums.end());return nums[nums.size()-1]*nums[nums.size()-2]-nums[0]*nums[1];}
};

三角形的最大周长

class Solution {
public:int largestPerimeter(vector<int>& nums) {sort(nums.begin(),nums.end());int n=nums.size();for(int i=n-1;i>=2;i--){if(nums[i-2]+nums[i-1]>nums[i])return nums[i-2]+nums[i-1]+nums[i];}return 0;}
};

数组拆分

class Solution {
public:int arrayPairSum(vector<int>& nums) {int res=0;sort(nums.begin(),nums.end());for(int i=0;i<nums.size();i+=2){res+=nums[i];}return res;}
};

救生艇

class Solution {
public:int numRescueBoats(vector<int>& people, int limit) {int res=0;sort(people.begin(),people.end());int left=0;int right=people.size()-1;while(left<=right){if(people[left]+people[right]<=limit){res++;left++;right--;}else {res++;right--;}}return res;}
};

摆动排序||

class Solution {
public:void wiggleSort(vector<int>& nums) {sort(nums.begin(),nums.end());int left=(nums.size()-1)/2;int right=nums.size()-1;vector<int> s(nums.size());for(int i=0;i<nums.size();i++){if(i%2==0){s[i]=nums[left--];}else {s[i]=nums[right--];}}for(int i=0;i<nums.size();i++){nums[i]=s[i];}}
};

分发饼干

class Solution {
public:int findContentChildren(vector<int>& g, vector<int>& s) {sort(g.begin(),g.end());sort(s.begin(),s.end());int res=0;int pg=0;int ps=0;while(ps<s.size()&&pg<g.size()){if(s[ps]>=g[pg]){res++;pg++;ps++;}else {ps++;}}return res;}
};

最少操作使数组递增

class Solution {
public:int minOperations(vector<int>& nums) {if(nums.size()==1)return 0;int res=0;for(int i=1;i<nums.size();i++){if(nums[i]<=nums[i-1]){res+=nums[i-1]-nums[i]+1;nums[i]=nums[i-1]+1;}}return res;}
};

使数组唯一的最小增量

class Solution {
public:int minIncrementForUnique(vector<int>& nums) {if (nums.size() == 1)return 0;sort(nums.begin(), nums.end());int res = 0;for (int i = 1; i < nums.size(); i++) {if (nums[i] <= nums[i - 1]) {res += abs(nums[i] - nums[i - 1] )+ 1;nums[i] = nums[i - 1] + 1;}}return res;}
};

有效三角形的个数

class Solution {
public:int triangleNumber(vector<int>& nums) {if(nums.size()<=2)return 0;int res=0;sort(nums.begin(),nums.end());for(int i=0;i<nums.size();i++){for(int j=i+1;j<nums.size();j++){for(int k=j+1;k<nums.size();k++){if(nums[i]+nums[j]>nums[k]){res++;}}}}return res;}
};