当前位置: 首页 > article >正文

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       ~       ~

http://www.kler.cn/a/294461.html

相关文章:

  • 【SpringMVC】——Cookie和Session机制
  • Redis 高并发分布式锁实战
  • 【数据分享】1901-2023年我国省市县镇四级的逐年降水数据(免费获取/Shp/Excel格式)
  • Spark的学习-02
  • 如何在 Spring Boot 中实现多数据源的事务管理?
  • 自己生成的页面,保存为图片,并下载word
  • 通信工程学习:什么是PCM脉冲编码调制、DPCM差分脉冲编码调制、ADPCM自适应差分脉冲编码调制
  • Flask中实现上下文管理
  • ARM基础---编程模型---ARM汇编
  • 把设计模式用起来!(1)——楔
  • 算法复杂度 —— 数据结构前言、算法效率、时间复杂度、空间复杂度、常见复杂度对比、复杂度算法题(旋转数组)
  • 掌握Hive函数[2]:从基础到高级应用
  • 对比测评3款BI分析工具
  • es数组包含查询
  • 『功能项目』战士的A键连击【33】
  • Java项目: 基于SpringBoot+mybatis+maven+mysql图书馆管理系统(含源码+数据库+任务书+答辩PPT+毕业论文)
  • 2024 批量下载公众号渤海小吏1千篇文章导出pdf(带留言),抓取文章标题时间链接封面阅读数分享数留言数粉丝数导出excel
  • Python测试开发---什么是单例模式
  • tomato靶场攻略
  • 基于单片机的多功能数字闹钟设计
  • 【简单】 猿人学web第一届 第15题 备周则意怠,常见则不疑
  • javaWeb【day03】---(Vue-Element)
  • python | 字符串字母大小写转换方法
  • HalconDotNet中的图像特征与提取详解
  • MATLAB算法实战应用案例精讲-【人工智能】数据元(概念篇)
  • 力扣 739. 每日温度【经典单调栈题目】