本文主要是介绍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 ~ ~
这篇关于LCP 485. 最大连续 1 的个数[lleetcode -11]的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!