LCP 485. 最大连续 1 的个数[lleetcode -11]
从今天起,我们的算法开始研究搜索,首先就是DFS深度优先搜索(depth-first seach,DFS)在搜索到一个新的节点时,立即对该新节点进行遍 历;因此遍历需要用先入后出的栈来实现,也可以通过与栈等价的递归来实现。对于树结构而言, 由于总是对新节点调用遍历,因此看起来是向着“深”的方向前进。
下面是一个一维的DFS算法
LCP 485. 最大连续 1 的个数
给定一个二进制数组 nums
, 计算其中最大连续 1
的个数。
示例 1:
输入:nums = [1,1,0,1,1,1]
输出:3
解释:开头的两位和最后的三位都是连续 1 ,所以最大连续 1 的个数是 3.
示例 2:
输入:nums = [1,0,1,1,0,1]
输出:2
解决方案
class Solution {
public:
int dfs(const vector<int>& vec, int index) {
if (index >= vec.size() || vec[index] == 0) {
return 0; // 结束递归,遇到0或者越界
}
// 否则,当前1的长度加上后续的连续1的长度
return 1 + dfs(vec, index + 1);
}
int findMaxConsecutiveOnes(vector<int>& vec) {
int maxLength = 0;
int i = 0;
while (i < vec.size()) {
if (vec[i] == 1) {
// 找到1时开始DFS计算连续1的长度
int currentLength = dfs(vec, i);
maxLength = max(maxLength, currentLength);
// 跳过这段连续的1
i += currentLength;
} else {
i++;
}
}
return maxLength;
}
};
虽然解决问题的效率不高(我没有把击败图填出来ヾ(•ω•`)o),但是这个问题作为引入是比较好的,因为1维的数组的递归我们还是比较好想象的,下面是一些标记,让你对这个程序的认识更深刻
#include <vector>
#include <iostream>
using namespace std;
//求最长的连续1
class Solution {
public:
vector<int> tag;
int dfs(const vector<int>& vec, int index) {
if (index >= vec.size() || vec[index] == 0) {
return 0; // 结束递归,遇到0或者越界
}
// 否则,当前1的长度加上后续的连续1的长度
return 1 + dfs(vec, index + 1);
}
int findMaxConsecutiveOnes(vector<int>& vec) {
int maxLength = 0;
int i = 0;
while (i < vec.size()) {
if (vec[i] == 1) {
// 找到1时开始DFS计算连续1的长度
int currentLength = dfs(vec, i);
tag.push_back(currentLength);
maxLength = max(maxLength, currentLength);
// 跳过这段连续的1
i += currentLength;
tag.resize(tag.size() + currentLength-1, -1);
}
else {
i++;
tag.push_back(0);
}
}
return maxLength;
}
};
ostream& operator<<(ostream& os, vector<int> vec)
{
for (auto elem : vec)
{
if (elem == -1)
{
os << "~" << "\t";
}else
os << elem << "\t";
}
os << endl;
return os;
}
int main()
{
vector<int> vec = { 1,1,0,1,1,1 };
Solution ans;
cout << ans.findMaxConsecutiveOnes(vec) << endl;
cout << vec;
cout << ans.tag;
return 0;
}
运行结果是
3
1 1 0 1 1 1
2 ~ 0 3 ~ ~