文章目录
零、写在前面
一、主要知识点
快速排序
二、课后习题
539. 最小时间差
977. 有序数组的平方
870. 优势洗牌
881. 救生艇
写在最后
零、写在前面
今天是打卡的第37天，今天的难度一般般，赶紧写写写篇python爬虫试试水0.0 知识点在：
《算法零基础100讲》(第37讲) 排序进阶 - 快速排序
一、主要知识点
c语言中常见的排序方式
快速排序
基于分治的思想，利用哨兵作为比较的点，将大于哨兵点
void swap(int *a, int *b){//交换节点 if(a == b) return; //这是个大坑 如果a和b是同一个元素会变成0 *a = *a ^ *b; *b = *a ^ *b; *a = *a ^ *b; } int Partition(int *a, int l, int r){ int i = l + 1, j = l + 1, idx = l + (r - l) /2, pivox = a[idx]; //i 和j用于划分 idx选择中间元素进行分治 swap(&a[l], &a[idx]); //将idx暂存到l的位置 while(i <= r) //进行交换 使j前元素小于idx位置 if(a[i++] < pivox) swap(&a[i-1],&a[j++]); swap(&a[l],&a[j-1]);//将idx元素放回 return j - 1;//返回idx的位置 } void QuickSort(int *a,int l,int r){ if(l < r){ int mid = Partition(a,l,r); QuickSort(a,l,mid - 1);//排序左边 QuickSort(a,mid + 1,r);//排序右边 } }
二、课后习题
539. 最小时间差
539. 最小时间差
给定一个 24 小时制（小时:分钟 “HH:MM”）的时间列表，找出列表中任意两个时间的最小时间差并以分钟数表示。
解题思路
先全部转化为分钟，然后排序，从相邻元素的差值里面选一个最小的就好了，如果跨天的话一定是第一个减最后一个
int cmp(int *a,int*b){ return *a > *b; } 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; }
977. 有序数组的平方
977. 有序数组的平方
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
解题思路1
先全部平方，然后排序就好了？应该是英雄哥的本意吧？
void swap(int *a, int *b){ if(a == b) return; *a = *a ^ *b; *b = *a ^ *b; *a = *a ^ *b; } int Partition(int *a, int l, int r){ int i = l + 1, j = l + 1, idx = l + (r - l) /2, pivox = a[idx]; swap(&a[l], &a[idx]); while(i <= r) if(a[i++] < pivox) swap(&a[i-1],&a[j++]); swap(&a[l],&a[j-1]); return j - 1; } void QuickSort(int *a,int l,int r){ if(l < r){ int mid = Partition(a,l,r); QuickSort(a,l,mid - 1); QuickSort(a,mid + 1,r); } } int* sortedSquares(int* nums, int numsSize, int* returnSize){ int* ans = malloc(sizeof(int) * numsSize); for(int i = 0;i < numsSize;i++)//转化为平方 ans[i] = nums[i] * nums[i]; *returnSize = numsSize; QuickSort(ans,0,numsSize - 1);//快排不解释 return ans; }
解题思路2
上面太慢了，其实如果从后往前更新数组，那么最大值一定是最小值的平方或者最大值的平方，搜一遍就出来了。有点归并的意思
int* sortedSquares(int* nums, int numsSize, int* returnSize){ int* ans = malloc(sizeof(int) * numsSize); int l = 0, r = numsSize - 1,ansnum = numsSize; *returnSize = numsSize; while(ansnum){//当没有插入完 if(nums[l] < 0) //只有小的小于0 才可能比后面的平方大 if(-nums[l] > nums[r]) ans[--ansnum] = nums[l] * nums[l],l++; else ans[--ansnum] = nums[r] * nums[r],r--; else ans[--ansnum] = nums[r] * nums[r],r--; } return ans; }
870. 优势洗牌
870. 优势洗牌
给定两个大小相等的数组 A 和 B，A 相对于 B 的优势可以用满足 A[i] > B[i] 的索引 i 的数目来描述。
返回 A 的任意排列，使其相对于 B 的优势最大化。
解题思路
这就是田忌赛马啊，找到一个最小的可以赢的值插入，如果怎么都赢不了，就选一个最小的，保证牺牲最小？
int cmp(int *a,int *b){return *a > *b;} int* advantageCount(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize){ qsort(nums1,nums1Size,sizeof(int),cmp); int *ans = malloc(sizeof(int) * nums2Size); bool hash[nums1Size];//标记元素是否使用 memset(hash,0,sizeof(hash)); for(int i = 0;i < nums2Size;i++){ int low = 0, high = nums1Size; while(low < high){//找到最小的元素 int mid = low + (high - low )/2; if(nums1[mid] <= nums2[i]) low = mid + 1; else high = mid; } while(high < nums1Size && hash[high]) //未被使用的最小元素 high++; if(high == nums1Size){//如果没找到就找个最小的 int k = 0; while(hash[k]) k++; hash[k] = 1; ans[i] = nums1[k]; } else { //直接将找到的值当作解插入 hash[high] = 1; ans[i] = nums1[high]; } } *returnSize = nums2Size; return ans; }
881. 救生艇
881. 救生艇
第 i 个人的体重为 people[i]，每艘船可以承载的最大重量为 limit。
每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit。
返回载到每一个人所需的最小船数。(保证每个人都能被船载)。
解题思路
这也是田忌赛马，对于每个比较大的值如果能找到一个较小的值与之同船就一起，没有就自己。
int cmp(int *a,int *b){return *a > *b;} 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; }
