文章目录
485. 最大连续 1 的个数
线性枚举
没有任何复杂的思路，枚举整个数组，当前元素是0就看前面的连续长度是不是比答案大，并清零计数变量；是1的话就给计数变量加一
class Solution {
public:
int findMaxConsecutiveOnes(vector<int>& nums) {
int maxn=0;
int cnt=0;
for(int i=0;i<nums.size();i++){
if(nums[i]==1) cnt++;
else maxn=max(maxn,cnt),cnt=0;
}
maxn=max(maxn,cnt);
return maxn;
}
};
1464. 数组中两元素的最大乘积
题目链接
最大两数的乘积？不就是找出最大两数嘛。直接排序就好
排序
class Solution {
public:
int maxProduct(vector<int>& nums) {
sort(nums.begin(),nums.end());
return (nums[nums.size()-2]-1)*(nums[nums.size()-1]-1);
}
};
但是！这显然不是这道题放在这里的本意
线性枚举
我们可以定义两个变量first、second，分别用来保存数组中的最大值和次大值。最大值次大值的初始值分别是数组中第一第二个元素比较的结果。接下来从第三个元素开始枚举，如果当前元素比最大值还大，就把原来的最大值给次大值，当前元素给最大值；如果当前元素没有最大值大而比次大值要大的话就直接把当前元素给次大值就好
class Solution {
public:
int maxProduct(vector<int>& nums) {
int first=max(nums[0],nums[1]),second=min(nums[0],nums[1]);
for(int i=2;i<nums.size();i++)
{
if(nums[i]>first) second=first,first=nums[i];
else if(nums[i]>second) second=nums[i];
}
return (first-1)*(second-1);
}
};
153. 寻找旋转排序数组中的最小值
题目链接
说的花里胡哨的还不就是找最小值嘛，这活儿我熟~
线性枚举
class Solution {
public:
int findMin(vector<int>& nums) {
int minn=0x3f3f3f3f;
for(int i=0;i<nums.size();i++) minn=min(minn,nums[i]);
return minn;
}
};
但是！旋转两个字真的没用吗？你可不要忘了旋转前他是按照升序排列的。这么强的性质冥冥中注定不只是那么简单。
利用单调性
注意到旋转的过程就是把最后一个元素放到第一个，再加上他原来是一个升序排列的数组，我们可以得到他的基本结构
（纵坐标的大小表示数组中的元素大小）可以很明显的看到，他是由两部分组成的，两个单调上升的子序列，但是他们中间一定会有一个下降的过程（从最大值到最小值）所以我们只需要找出这个不一样的地方
class Solution {
public:
int findMin(vector<int>& nums) {
for(int i=1;i<nums.size();i++)
{
if(nums[i]<nums[i-1]) return nums[i];
}
return nums[0];
}
};
当然利用上面的性质二分也可以
二分
两个区间，再注意到上图的绿色线条，就很容易发现二段性：左边都比第一个元素大，右边都比第一个元素小。所以只需要寻找第一个小于第一个元素的数字就可以
class Solution {
public:
int findMin(vector<int>& nums) {
int l=0;
int r=nums.size()-1;
while(l<r)
{
int mid=l+r>>1;
if(nums[mid]<nums[0]) r=mid;
else l=mid+1;
}
if(nums[r]>nums[0]) return nums[0];
return nums[l];
}
};
154. 寻找旋转排序数组中的最小值 II
题目链接
这道题和上一道题的差异就在这道题数组中的元素允许重复。但是好在上一道题的前两种方法直接找“小”所以并不受这个条件的影响。所以只说一下受到影响的二分
二分
上一道题中我们的二段性使用与第一个元素的大小关系来分开的。这一题允许重复，所以就有可能最后的几个元素适合第一元素相等的，这样就不满足上面的二段性了。所以我们可以把用来二分的区间删除最后与第一个元素相等的部分，来使其恢复二段性
class Solution {
public:
int findMin(vector<int>& nums) {
int n = nums.size();
int l = 0,r = n - 1;
while(l < r && nums[r] == nums[0]){
r--;
}
while(l<r)
{
int mid=l+r>>1;
if(nums[mid]<nums[0]) r=mid;
else l=mid+1;
}
if(nums[r]>nums[0]) return nums[0];
return nums[l];
}
};
414. 第三大的数
错误的排序
找数？排序！
class Solution {
public:
int thirdMax(vector<int>& nums) {
sort(nums.begin(),nums.end());
if(nums.size()>=3) return nums[nums.size()-3];
return nums[nums.size()-1];
}
};
wa了。。一看才知道还要去重。。。
正确的排序
class Solution {
public:
int thirdMax(vector<int>& nums) {
sort(nums.begin(),nums.end());
nums.erase(unique(nums.begin(),nums.end()),nums.end());
sort(nums.begin(),nums.end());
if(nums.size()>=3) return nums[nums.size()-3];
return nums[nums.size()-1];
}
};
(上面的所有函数当然都是能用手动实现的，但在这里并不是重点，所以不做描述）
线性循环
类似于上面最大的乘积那个思路
class Solution {
public:
int thirdMax(vector<int> &nums) {
const long minn=-2147483650;
long a = minn, b = minn, c = minn;
for (long num : nums) {
if (num > a) {
c = b;
b = a;
a = num;
} else if (a > num && num > b) {
c = b;
b = num;
} else if (b > num && num > c) {
c = num;
}
}
if(c==minn) return a;
return c;
}
};
628. 三个数的最大乘积
排序
一样三个数的乘积那么就找最大的三个数呗。需要注意的是这个数组里面有负数，那么也需要考虑最小的两个数了。因为负数的绝对值可能很大，两个负数的乘积也是正数
class Solution {
public:
int maximumProduct(vector<int>& nums) {
sort(nums.begin(), nums.end());
int n = nums.size();
int a=nums[0] * nums[1] * nums[n - 1]
int b=nums[n - 3] * nums[n - 2] * nums[n - 1];
return max(a,b);
}
};
当然可以利用上面找两个数找三个数的方法去找五个数，可以自己试一下