《九日集训》第五天打卡
题目一:
链接:排序数组
解题思路:
采用C语言库里面的qsort(对象,大小,类型大小,排序函数)
排序函数 返回小于0,升序;
排序函数 返回大于0,降序。
C语言:
int cmp(const void*a,const void *b){return *(int *)a - *(int *)b;
}
int* sortArray(int* nums, int numsSize, int* returnSize){qsort(nums,numsSize,sizeof(int),cmp);*returnSize=numsSize;return nums;
}
**C++:**选择排序
class Solution {
public:vector<int> sortArray(vector<int>& nums) {for(int i=0;i<nums.size()-1;i++){int k=i;for(int j=i+1;j<nums.size();j++){if(nums[k]>=nums[j])k=j;}if(k!=i){int t=nums[i];nums[i]=nums[k];nums[k]=t;}} return nums; }
};
题目二:
链接:多数元素
解题思路:
采用sort排序
C++:
class Solution {
public:int majorityElement(vector<int>& nums) {sort(nums.begin(), nums.end());return nums[nums.size()/2];}
};
题目三:
链接:存在重复元素
解题思路:
C++:
class Solution {
public:bool containsDuplicate(vector<int>& nums) {sort(nums.begin(), nums.end());for(int i=1;i<nums.size();i++){if(nums[i]==nums[i-1]){return true;}}return false;}
};
第四题:
链接:最大间距
解题思路:
C++:
class Solution {
public:int maximumGap(vector<int>& nums) {if(nums.size()<2) return 0;sort(nums.begin(),nums.end());int ma=-1;for(int i=1;i<nums.size();i++){if(nums[i]-nums[i-1]>ma)ma=nums[i]-nums[i-1];}return ma;}
};
第五题:
**链接:按奇偶排序数组
解题思路:
C++:
class Solution {
public:vector<int> sortArrayByParity(vector<int>& nums) {vector<int>r;int l=0;for(int i=0;i<nums.size();i++){if(nums[i]%2!=0){r.push_back(nums[i]);}else{nums[l]=nums[i];l++;}}for(int i=0;i<r.size();i++){nums[l++]=r[i];}return nums;}
};
C语言:
int xx(int x){return x&1;//判断为偶数}int cmp(const void*a,const void *b){return xx(*(int *)a)-xx(*(int *)b);}int* sortArrayByParity(int* nums, int numsSize, int* returnSize){qsort(nums,numsSize,sizeof(int),cmp);*returnSize=numsSize;return nums;
}
第六题:
链接:
解题思路:
字符切割+排序
C++:
class Solution {
public:int findMinDifference(vector<string>& timePoints) {vector<int> l;for(auto time :timePoints){int hour=stoi(time.substr(0,2));int min=stoi(time.substr(3));l.push_back(24*60+hour*60+min);l.push_back(hour*60+min);}sort(l.begin(),l.end());int mi=INT_MAX;for(int i=1;i<l.size();i++){if(l[i]-l[i-1]<mi)mi=l[i]-l[i-1];}return mi;}
};
第七题:
链接:三角形周长最大
解题思路:
最大周长三角形对数据从大到小一一比较;
三角形原理:a+b>c
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-2]+nums[i-1]>nums[i])return nums[i]+nums[i-1]+nums[i-2];}return 0;}
};
第八题:
链接:救生艇
解题思路:
C++:
class Solution {
public:int numRescueBoats(vector<int>& people, int limit) {sort(people.begin(),people.end());int s=0;for(int i=0,j=people.size()-1;i<=j;){if(i==j){s++;j--;}elseif(people[i]+people[j]<limit){s++,i++,j--;}else if(people[i]+people[j]>limit){s++;j--;}}return s;}
};
《九日集训》第五天打卡
题目一:
链接:排序数组
解题思路:
采用C语言库里面的qsort(对象,大小,类型大小,排序函数)
排序函数 返回小于0,升序;
排序函数 返回大于0,降序。
C语言:
int cmp(const void*a,const void *b){return *(int *)a - *(int *)b;
}
int* sortArray(int* nums, int numsSize, int* returnSize){qsort(nums,numsSize,sizeof(int),cmp);*returnSize=numsSize;return nums;
}
**C++:**选择排序
class Solution {
public:vector<int> sortArray(vector<int>& nums) {for(int i=0;i<nums.size()-1;i++){int k=i;for(int j=i+1;j<nums.size();j++){if(nums[k]>=nums[j])k=j;}if(k!=i){int t=nums[i];nums[i]=nums[k];nums[k]=t;}} return nums; }
};
题目二:
链接:多数元素
解题思路:
采用sort排序
C++:
class Solution {
public:int majorityElement(vector<int>& nums) {sort(nums.begin(), nums.end());return nums[nums.size()/2];}
};
题目三:
链接:存在重复元素
解题思路:
C++:
class Solution {
public:bool containsDuplicate(vector<int>& nums) {sort(nums.begin(), nums.end());for(int i=1;i<nums.size();i++){if(nums[i]==nums[i-1]){return true;}}return false;}
};
第四题:
链接:最大间距
解题思路:
C++:
class Solution {
public:int maximumGap(vector<int>& nums) {if(nums.size()<2) return 0;sort(nums.begin(),nums.end());int ma=-1;for(int i=1;i<nums.size();i++){if(nums[i]-nums[i-1]>ma)ma=nums[i]-nums[i-1];}return ma;}
};
第五题:
**链接:按奇偶排序数组
解题思路:
C++:
class Solution {
public:vector<int> sortArrayByParity(vector<int>& nums) {vector<int>r;int l=0;for(int i=0;i<nums.size();i++){if(nums[i]%2!=0){r.push_back(nums[i]);}else{nums[l]=nums[i];l++;}}for(int i=0;i<r.size();i++){nums[l++]=r[i];}return nums;}
};
C语言:
int xx(int x){return x&1;//判断为偶数}int cmp(const void*a,const void *b){return xx(*(int *)a)-xx(*(int *)b);}int* sortArrayByParity(int* nums, int numsSize, int* returnSize){qsort(nums,numsSize,sizeof(int),cmp);*returnSize=numsSize;return nums;
}
第六题:
链接:
解题思路:
字符切割+排序
C++:
class Solution {
public:int findMinDifference(vector<string>& timePoints) {vector<int> l;for(auto time :timePoints){int hour=stoi(time.substr(0,2));int min=stoi(time.substr(3));l.push_back(24*60+hour*60+min);l.push_back(hour*60+min);}sort(l.begin(),l.end());int mi=INT_MAX;for(int i=1;i<l.size();i++){if(l[i]-l[i-1]<mi)mi=l[i]-l[i-1];}return mi;}
};
第七题:
链接:三角形周长最大
解题思路:
最大周长三角形对数据从大到小一一比较;
三角形原理:a+b>c
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-2]+nums[i-1]>nums[i])return nums[i]+nums[i-1]+nums[i-2];}return 0;}
};
第八题:
链接:救生艇
解题思路:
C++:
class Solution {
public:int numRescueBoats(vector<int>& people, int limit) {sort(people.begin(),people.end());int s=0;for(int i=0,j=people.size()-1;i<=j;){if(i==j){s++;j--;}elseif(people[i]+people[j]<limit){s++,i++,j--;}else if(people[i]+people[j]>limit){s++;j--;}}return s;}
};