目录
零、写在前面
一、主要知识点
1.n个数的最小值
2.qsort函数(补充知识点)
3.求次大值的扫描一遍的方式(补充知识点)
二、课后习题
485. 最大连续 1 的个数
主要思想
结果分析
1464. 数组中两元素的最大乘积
主要思想
结果分析
153. 寻找旋转排序数组中的最小值
主要思想
结果分析
153. 寻找旋转排序数组中的最小值
主要思想
结果分析
628. 三个数的最大乘积
主要思想
结果分析
三、今日总结
零、写在前面
这是打卡的第十七天，今天题目比较简单，我补充了两个知识点，主要知识点在
《算法零基础100讲》(第17讲) 线性枚举(一) - 最值算法_英雄哪里出来-CSDN博客
遇事不决就枚举
https://blog.csdn.net/WhereIsHeroFrom/article/details/121174370
一、主要知识点
1.n个数的最小值
主要利用到的思想就是两两比较，就可以得到最终的最小值。
int Min(int a, int b) { // 返回较小值 return a < b ? a : b; } int findMin(int* nums, int numsSize){ int i; int min = 100000001; // 初始化最大值为最小 for(i = 0; i < numsSize; ++i) min = Min(min, nums[i]); // 迭代求解 return min; }
2.qsort函数(补充知识点)
c语言自带的一个函数，叫做qsotr可以帮助我们完成排序，再求最大值就会很容易。 void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*)) 一共有四个参数，数组指针，数组大小，数组内变量大小，比较函数指针。看下面示例。 int cmp(int *a,int *b){ //比较函数 return *b > *a; //从大到小 } qsort(nums,numsSize,sizeof(int),&cmp);//排序算法
3.求次大值的扫描一遍的方式(补充知识点)
我们求最小值其实是通过扫描一遍数组不断比较得到的。假如我们在同时希望能得到次大值该怎么做的？其实最大值是不断更新的，如果我们把max上一次更新的值保存下来是不是就可以得到了？但是一开始就遇到最大值咋办呢？我们在剩下的元素找到最大值就行了不是么？看看代码理解一下
for(int i = 0;i < numsSize;i++){ if(nums[i] > max) max2 = max,max = nums[i]; else if(nums[i] > max2) max2 = nums[i]; }
二、课后习题
485. 最大连续 1 的个数
485. 最大连续 1 的个数
https://leetcode-cn.com/problems/max-consecutive-ones/
数数最多多少个1连续。
主要思想
从前到后扫描，用变量计数，更新结果就好了。。看代码
int findMaxConsecutiveOnes(int* nums, int numsSize){ int ans = 0,i = 0; while(i < numsSize){ int count = 0; //计数这次连续1的个数 while(i < numsSize && nums[i++] == 1 ) count++; if(count > ans) ans = count; //更新计数 } return ans; }
结果分析
还是可以的。满意了，下一个
1464. 数组中两元素的最大乘积
1464. 数组中两元素的最大乘积
https://leetcode-cn.com/problems/maximum-product-of-two-elements-in-an-array/
主要思想
这难道不是找到最大的两个数相乘不就完了？用我补充知识点。
int maxProduct(int* nums, int numsSize){ int ans = 0, max = 0,max2 = 0; for(int i = 0;i < numsSize;i++){ if(nums[i] > max) max2 = max,max = nums[i];//更新最大值和次大值 else if(nums[i] > max2) max2 = nums[i]; //如果一开始就是最大值，更新次大值 } return (max - 1) * (max2 - 1); }
结果分析
还有谁？？？
153. 寻找旋转排序数组中的最小值
153. 寻找旋转排序数组中的最小值
https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/
主要思想
看着复杂，，，从前到后扫一遍完事。。。
int findMin(int* nums, int numsSize){ int ans = 50000; for(int i = 0;i < numsSize;i++) if(ans >nums[i]) ans = nums[i]; return ans; }
结果分析
可以二分，但是感觉没必要。。。
153. 寻找旋转排序数组中的最小值
153. 寻找旋转排序数组中的最小值
https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/
主要思想
看着复杂，，，从前到后扫一遍完事。。。
int findMin(int* nums, int numsSize){ int ans = 50000; for(int i = 0;i < numsSize;i++)
if(ans >nums[i]) ans = nums[i];
return ans;
}
结果分析
可以了
414. 第三大的数
414. 第三大的数
https://leetcode-cn.com/problems/third-maximum-number/
主要思想
这道题其实直接进行排序再进行计算排名就好了。
int cmp(int *a,int *b){ return *b > *a; } int thirdMax(int* nums, int numsSize){ qsort(nums,numsSize,sizeof(int),&cmp); //排序 int i = 1,mingci = 1; while(i < numsSize) //计算排名 if(nums[i++] != nums[i - 2]){ mingci++; //不相等排名加 if(mingci == 3) break; //到第三名就退出 } return mingci == 3 ? nums[i - 1]:nums[0]; }
结果分析
凑合
628. 三个数的最大乘积
628. 三个数的最大乘积
https://leetcode-cn.com/problems/maximum-product-of-three-numbers/
主要思想
这道题把。。它有负数。。这就很难受。
最大值分为两种情况。一种是最大的三个数乘积，另外就是最大和最小的两个乘积。看看结果比较输出就好了。
int maximumProduct(int* nums, int numsSize){ int max1 = -1000, max2 = -1000,max3 = -1000,min = 1000, min2 = 1000; for(int i = 0;i < numsSize;i++){ if(nums[i] >= max1) max3 = max2,max2 = max1,max1 = nums[i];//最大值 else if(nums[i] > max2) max3 = max2 ,max2 = nums[i]; //次大值 else if(nums[i] > max3) max3 = nums[i]; //第三大 if(nums[i] <= min) min2 = min,min = nums[i]; //最小值 else if(nums[i] < min2) min2 = nums[i]; //第二最小？ } int a = max1 * max2 * max3; int b = max1 * min * min2; return a > b ? a : b; //返回两种情况中较大的 }
结果分析
凑合
三、今日总结
今天的难度不高，但是还挺好玩的。继续刷题去了。。。。
