九日集训day6【刷题】【九日集训】
前言
今天是周六,也是九日集训第六天,加油!下午摆烂了,😔
🐱🐱🐱
1913. 两个数对之间的最大乘积差
class Solution {public: int maxProductDifference(vector<int>& nums) { //给数组排序选出最大次打,最小次 sort(nums.begin(), nums.end()); int max = nums[nums.size()-1], secondMax = nums[nums.size()-2], min = nums[0], secondMin = nums[1]; return max*secondMax - min*secondMin; }};
976. 三角形的最大周长
class Solution {public: int largestPerimeter(vector<int>& nums) { //先排序,然后从最大的3条边开始判断,如果满足两边之和大于第三边,说明可以组成三角形 sort(nums.begin(), nums.end()); //注意i>=2 for(int i = nums.size()-1; i >= 2; --i) { if(nums[i-2] + nums[i-1] > nums[i]) return nums[i]+nums[i-1]+nums[i-2]; } return 0; }};
561. 数组拆分 I
class Solution {public: int arrayPairSum(vector<int>& nums) { //只要把数组排好序然后按顺序两两取min就好了 sort(nums.begin(), nums.end()); int sum = 0; //注意是每两个数选一次,所以i+=2 for(int i = 1; i < nums.size(); i+=2) { sum += min(nums[i-1], nums[i]); } return sum; }};
或者只需加偶数项的数
int cmp(const void* a, const void *b) { return *(int *)a - *(int *)b;}int arrayPairSum(int* nums, int numsSize){ int i, ans = 0; qsort(nums, numsSize, sizeof(int), cmp); for(i = 0; i < numsSize; i += 2) { ans += nums[i]; } return ans;}
881. 救生艇
class Solution {public: int numRescueBoats(vector<int>& people, int limit) { sort(people.begin(), people.end()); int count = 0; //看最重的人和最轻的人能否一起坐船,如果不能,最重的就要单独坐 int left = 0, right = people.size()-1; while(left <= right) { //只有1个人时只能单独坐船,然后退出循环。 if(left == right) { ++count; break; } if(people[left] + people[right] > limit) ++count, --right; else ++left, --right, ++count; } return count; }};
324. 摆动排序 II
如果分别把大的小的分2边,去插奇偶,最小一个大的数,和最大一个小的数就有可能出错。
正确写法
class Solution {public: void wiggleSort(vector<int>& nums) { sort(nums.begin(), nums.end()); //拷贝一份数组 int n = nums.size(); int arr[n]; for(int i = 0; i < nums.size(); ++i) arr[i] = nums[i]; //将最大的后半边的数穿插着排序就行 //1 1 1 4 5 6 //1 1 1 4 5 6 int right = nums.size()-1; for(int i = 1; i < nums.size(); i+=2) nums[i] = arr[right--]; for(int i = 0; i < nums.size(); i+=2) nums[i] = arr[right--]; }};
455. 分发饼干
注意数据有可能不按递增顺序输入
class Solution {public: int findContentChildren(vector<int>& g, vector<int>& s) { //注意数据有可能不按递增顺序输入 sort(g.begin(), g.end()); sort(s.begin(), s.end()); int count = 0; //让最大的饼干尺寸去比较最大的胃口,不能就继续比较次小的 int gRight = g.size()-1, sRight = s.size()-1; while(gRight >= 0 && sRight >= 0) { if(s[sRight] >= g[gRight]) { ++count; --gRight, --sRight; } else --gRight; } return count; }};
1827. 最少操作使数组递增
class Solution {public: int minOperations(vector<int>& nums) { //双指针,分别指向最小的和次小的 //1 5 2 4 1 //5 2差值为3 +4 --》 1 5 6 4 1 //6 4差值为2 +3 --》 1 5 6 7 1 //7 5差值为2 +7 --》 1 5 6 7 8 int count = 0; for(int i = 1; i < nums.size(); ++i) { if(nums [i] <= nums[i-1]) { int tmp = nums[i-1] - nums[i] + 1; count += tmp; nums[i] = nums[i-1] + 1; } } return count; }};
611. 有效三角形的个数
class Solution {public: int triangleNumber(vector<int>& nums) { //先排序 sort(nums.begin(), nums.end()); //固定最大的边,双指针移动 //2 3 4 4 //2 3 4 //2 3 4 //2 4 4 //3 4 4 int n1 = 0, n2 = 1, n3 = 2; int count = 0; //2个小边之和大于大的边,就可以组成三角形 for(int n3 = nums.size()-1; n3 >= 2; n3--) { int n1 = 0, n2 = n3-1; while(n1 < n2) { if(nums[n1] + nums[n2] > nums[n3]) { //最小的边+次大的边>最大的边 //那么次大到最小边的边也都满足条件 count = count + n2 - n1; --n2; } else ++n1; } } return count; }};
尾声
🌹🌹🌹
写文不易,如果有帮助烦请点个赞~ 👍👍👍
Thanks♪(・ω・)ノ🌹🌹🌹
😘😘😘
👀👀由于笔者水平有限,在今后的博文中难免会出现错误之处,本人非常希望您如果发现错误,恳请留言批评斧正,希望和大家一起学习,一起进步ヽ( ̄ω ̄( ̄ω ̄〃)ゝ,期待您的留言评论。
附GitHub仓库链接