🍗课后习题
912. 排序数组
912. 排序数组
题目描述
给你一个整数数组nums，请你将该数组升序排列。
思路
直接qsort就好了，直接用简化写法，因为数据的范围也才104
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; }
169. 多数元素
169. 多数元素
题目描述
给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
思路
因为是大于一半的元素，如果我们使用一个多数元素和一个非多数元素进行消除，最后剩下的肯定就是大于一半的元素对不对？
int majorityElement(int* nums, int numsSize){ int maxnum = 0,maxtime = 0; for(int i = 0;i < numsSize;i++){ if(maxtime == 0){ //未选定最大元素 maxnum = nums[i]; maxtime++; } else if(nums[i] == maxnum) maxtime++; //最大元素计数 else maxtime--; //最大元素计数-1 } return maxnum; }
217. 存在重复元素
217. 存在重复元素
题目描述
给定一个整数数组，判断是否存在重复元素。
如果存在一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回false。
思路
排序之后再进行查看是否有相等的就好了，我给了一种更简化的写法0.0
int cmp(int *a,int *b){ return *a > *b ? 1 : -1; } bool containsDuplicate(int* nums, int numsSize){ qsort(nums,numsSize,sizeof(int),cmp); for(int i = 1;i < numsSize;i++) if(nums[i] == nums[i-1]) return true; return false; }
164. 最大间距
164. 最大间距
题目描述
给定一个无序的数组，找出数组在排序之后，相邻元素之间最大的差值。
如果数组元素个数小于 2，则返回 0。
思路
直接排序之后进行最大值的查看就好了。
int cmp(int *a, int *b){return *b < *a ? 1 : -1;} int maximumGap(int* nums, int numsSize){ qsort(nums ,numsSize ,sizeof(int) ,cmp); int max = 0; for(int i = 1;i < numsSize;i++) if(max < nums[i] - nums[i - 1]) max = nums[i] - nums[i - 1]; return max; }
905. 按奇偶排序数组
905. 按奇偶排序数组
题目描述
给定一个非负整数数组A，返回一个数组，在该数组中，A的所有偶数元素之后跟着所有奇数元素。
你可以返回满足此条件的任何数组作为答案。
思路
我喜欢再cmp内直接写好排序规则，所以没用英雄哥的模板，就是根据a、b的奇偶来返回不同的值就好了。
int cmp(int *a, int *b){ if((*a)&1) if((*b)&1) return *a > *b ? 1 : -1; else return 1; else if((*b)&1) return -1; else return *a > *b ? 1 : -1; } int* sortArrayByParity(int* nums, int numsSize, int* returnSize){ *returnSize = numsSize; qsort(nums,numsSize,sizeof(int),cmp); return nums; }
539. 最小时间差
539. 最小时间差
题目描述
给定一个 24 小时制（小时:分钟 “HH:MM”）的时间列表，找出列表中任意两个时间的最小时间差并以分钟数表示。
思路
因为如果出现跨天的情况一定是在最大值和最小值之间，所以可以将min初始化为这个值。然后先转化为分钟再排序就好了？
int cmp(int *a,int*b){ return *a > *b ? 1 : -1; } int findMinDifference(char ** timePoints, int timePointsSize){ int hash[timePointsSize],hashSize = 0; for(int i = 0;i<timePointsSize;i++) //将字符串转化成分钟 hash[hashSize++] = (((timePoints[i][0] -'0') * 10) + timePoints[i][1] - '0') * 60 + (timePoints[i][3] - '0')*10 + timePoints[i][4]; qsort(hash,hashSize,sizeof(int),cmp); //排序 int min = 24*60+hash[0] - hash[hashSize - 1]; //将最小值记为最大和最小的距离 for(int i = 1;i < hashSize;i++) if(min>hash[i]-hash[i-1]) min = hash[i] - hash[i-1]; return min; }
976. 三角形的最大周长
976. 三角形的最大周长
题目描述
给定由一些正数（代表长度）组成的数组 A，返回由其中三个长度组成的、面积不为零的三角形的最大周长。
如果不能形成任何面积不为零的三角形，返回 0。
思路
满足三角形的定义要求，只需要最大边小于较小两个边的和就好了，先排序之后从后往前找就好了。
int cmp(int *a,int *b){return *a > *b ? 1 : -1;} int largestPerimeter(int* nums, int numsSize){ qsort(nums,numsSize,sizeof(int),cmp); int i; for(i = numsSize - 1;i > 1;i--){ if(nums[i] < nums[i-1] + nums[i - 2]) break; } if(i == 1) return 0; else return nums[i] + nums[i - 1] + nums[i-2]; }
881. 救生艇
881. 救生艇
题目描述
第 i 个人的体重为 people[i]，每艘船可以承载的最大重量为 limit。
每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit。
返回载到每一个人所需的最小船数。(保证每个人都能被船载)。
思路
先排序，如果最大值可以和最小值一条船就省一条，如果不能，最大值自己走0.0
int cmp(int *a,int *b){return *a > *b ? 1 : -1;} int numRescueBoats(int* people, int peopleSize, int limit){ qsort(people,peopleSize,sizeof(int),cmp); int low = 0, high = peopleSize - 1,ans = 0; while(low <= high){ //分配船 if(people[low] + people[high] > limit) --high;//不能一起走 最大值自己走 else ++low,--high; //最大最小一起走 ans++; } return ans; }
