> 文档中心 > 九日集训day6【刷题】【九日集训】

九日集训day6【刷题】【九日集训】


前言

在这里插入图片描述

今天是周六,也是九日集训第六天,加油!下午摆烂了,😔

🐱🐱🐱

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

九日集训day6【刷题】【九日集训】

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边,去插奇偶,最小一个大的数,和最大一个小的数就有可能出错。

九日集训day6【刷题】【九日集训】

正确写法

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. 分发饼干

​ 注意数据有可能不按递增顺序输入

九日集训day6【刷题】【九日集训】

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仓库链接