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);// 跳过这段连续的1i += currentLength;} else {i++;}}return maxLength;}
};

虽然解决问题的效率不高（我没有把击败图填出来ヾ(•ω•`)o），但是这个问题作为引入是比较好的，因为1维的数组的递归我们还是比较好想象的，下面是一些标记，让你对这个程序的认识更深刻

#include <vector>
#include <iostream>
using namespace std;//求最长的连续1class 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);// 跳过这段连续的1i += 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";}elseos << 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       ~       ~