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

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]

从今天起&#xff0c;我们的算法开始研究搜索&#xff0c;首先就是DFS深度优先搜索&#xff08;depth-first seach&#xff0c;DFS&#xff09;在搜索到一个新的节点时&#xff0c;立即对该新节点进行遍 历&#xff1b;因此遍历需要用先入后出的栈来实现&#xff0c;也可以通过…...

关于宏任务的说法已经过时

关于宏任务w3c的最新解释&#xff0c;&#xff08;mdn已经搜不到宏任务队列&#xff09; ● 每个任务都有一个任务类型&#xff0c;用一个类型的任务必须在一个队列&#xff0c;不同类型的任务可以分属不同的队列。在一次事件循环当中&#xff0c;浏览器可以根据实际情况从不同…...

Java箱与泛型

大O的渐进表示法 大 O 的渐进表示法 去掉了那些对结果影响不大的项 &#xff0c;简洁明了的表示出了执行次数。 void func1(int N){ int count 0; for (int i 0; i < N ; i) { for (int j 0; j < N ; j) { count; } } for (int k 0; k < 2 * N ; k) { count; } in…...

QT如何判断一个文件是否存在

在Qt中&#xff0c;判断一个文件是否存在是一个常见的操作&#xff0c;可以通过QFile类和QDir类来实现。不过&#xff0c;对于简单的文件存在性检查&#xff0c;QFile类提供的接口更为直接。下面是一个使用QFile类来判断文件是否存在的例子&#xff1a; #include <QFile>…...

Vim笔记

【指尖飞舞&#xff1a;vscode vim 高效开发&#xff08;系列视频&#xff09;】https://www.bilibili.com/video/BV1z541177Jyp16&vd_source23e4761174881d73295e362ffd706749 Vscode vim插件配置-CSDN博客 g_跳到行尾最后一个非空字符 gd :go to definition ctrl (o): …...

宝塔部署Vue项目解决跨域问题

一、前言 使用宝塔面板部署前端后端项目相比用命令行进行部署要简单许多&#xff0c;宝塔的可视化操作对那些对Linux不熟悉的人很友好。使用宝塔部署SpringBoot后端项目和Vue前端项目的方法如下&#xff1a; 1、视频教程 2、文字教程1 3、文字教程2 以上的教程完全可以按照步骤…...

C++智能指针简述

auto_ptr 设计目的&#xff1a;超出作用域&#xff0c;自动释放内存。所有权传递&#xff1a;拷贝auto_ptr时&#xff0c;原指针失效&#xff0c;释放所有权&#xff1b;新指针获得所有权。总而言之&#xff0c;允许通过拷贝转移所有权&#xff0c;独占所有权。缺陷&#xff1…...

龙芯+FreeRTOS+LVGL实战笔记(新)——05部署主按钮

本专栏是笔者另一个专栏《龙芯+RT-Thread+LVGL实战笔记》的姊妹篇,主要的区别在于实时操作系统的不同,章节的安排和任务的推进保持一致,并对源码做了改进和优化,各位可以先到本人主页下去浏览另一专栏的博客列表(目前已撰写36篇,图1所示),再决定是否订阅。此外,也可以…...

Android Camera系列(二):TextureView+Camera

两岸猿声啼不住&#xff0c;轻舟已过万重山—李白 Android Camera系列&#xff08;一&#xff09;&#xff1a;SurfaceViewCamera Android Camera系列&#xff08;二&#xff09;&#xff1a;TextureViewCamera Android Camera系列&#xff08;三&#xff09;&#xff1a;GLS…...

DFS算法专题(一)——二叉树中的深搜【回溯与剪枝的初步注入】

目录 1、DFS算法简介 2、算法实战应用【leetcode】 2.1 计算布尔二叉树的值 2.1.1 算法原理 2.1.2 算法代码 2.2 求根节点到叶节点数字之和 2.2.1 算法原理 ​2.2.2 算法代码 2.3 二叉树剪枝 2.3.1 算法原理 2.3.2 算法代码 2.4 验证二叉搜索树 2.4.1 算法原理 …...

AWS SES服务 Golang接入教程(排坑版)

因为刚来看的时候 也迷迷糊糊的 所以 先讲概念 再上代码 一 基础设置 这里需要完成两个最基础的设置任务 1 是验证至少一个收件电子邮箱 2 【很关键】是验证发送域。即身份里的域类型的身份。&#xff08;可以理解为配置你的域名邮箱服务器&#xff08;SMPT&#xff09;为亚马…...

Vite + Vue3 +Vant4出现Toast is not a function

今天写前端的时候出现了这个问题搞了我一会 搜集原因: 1:是vant版本的问题&#xff0c;Toast()的方法是vant3版本的写法&#xff0c;而我用的是vant4&#xff0c;vant4中的写法改成了showToast()方法&#xff0c;改正过来 import {showToast} from "vant"; 发现还是…...

【MATLAB】模拟退火算法

模拟退火算法的MATLAB实现 模拟退火算法简介模拟退火算法应用实例关于计算结果 模拟退火算法简介 1982年&#xff0c;Kirkpatrick 将退火思想引入组合优化领域&#xff0c;提出了一种能够有效解决大规模组合优化问题的算法&#xff0c;尤其对 NP 完全问题表现出显著优势。模拟…...

什么是Kubernetes RBAC?

什么是Kubernetes RBAC? 1、什么是RBAC?2、核心组件3、优势💖The Begin💖点点关注,收藏不迷路💖 在Kubernetes集群中,RBAC(基于角色的访问控制)是保障系统安全的关键。它通过角色和绑定管理不同实体对资源的访问权限,具有显著优势: 1、什么是RBAC? RBAC是Kube…...

在Spring Boot中通过自定义注解、反射以及AOP(面向切面编程)

在Spring Boot中&#xff0c;通过自定义注解、反射以及AOP&#xff08;面向切面编程&#xff09;来动态修改请求参数是一种高级且强大的技术组合&#xff0c;它允许开发者在不修改原始方法实现的情况下&#xff0c;对方法的执行过程进行干预和定制。这种技术通常用于日志记录、…...

安防监控视频平台LntonAIServer视频智能分析平台新增视频质量诊断功能

随着安防行业的快速发展&#xff0c;视频监控系统已经成为维护公共安全和个人隐私的重要工具。然而&#xff0c;由于各种因素的影响&#xff0c;视频流的质量可能会受到影响&#xff0c;从而导致监控效果不佳。为了解决这一问题&#xff0c;LntonAIServer推出了全新的视频质量诊…...

vscode从本地安装插件

1. 打开VSCode。 2. 点击左侧菜单中的“扩展”&#xff08;或按CtrlShiftX&#xff09;。 3. 点击“更多操作”&#xff08;三个点&#xff09;> “从VSIX安装”。 4. 选择下载的.vsix文件。 5. 点击“安装”即可安装插件。...

Superset二次开发之新增复选框Checkbox筛选器

一. 背景 Superset目前支持的筛选类型:值、数值范围、时间列、时间粒度、时间范围 5种类型,显然无法满足业务需求。根据产品需要,需要支持复选框、单选框、级联选择等类型的筛选器。本文探讨复选框、单选框的技术实现方式。 二. 效果预览 三. 实现思路 复用 值 筛选器模块,…...

PromQL 语法

什么是 PromQL PromQL (Prometheus Query Language) 是 Prometheus 监控系统中用于查询时间序列数据的语言。它允许用户编写查询&#xff0c;以从 Prometheus 中检索并处理监控数据。 PromQL 的基础概念 1. 时间序列 Prometheus 中的时间序列由以下几个部分组成&#xff1a;…...

掌握Go语言中的时间与日期操作

Go语言中的时间与日期操作 在编写程序时&#xff0c;处理时间和日期看似是一项无关紧要的任务&#xff0c;但在需要同步多个任务或从文本文件中读取时间时&#xff0c;它的重要性便凸显出来。Go语言中的time包为我们提供了丰富的时间与日期操作功能。本文将详细介绍如何在Go语…...

云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地

借阿里云中企出海大会的东风&#xff0c;以**「云启出海&#xff0c;智联未来&#xff5c;打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办&#xff0c;现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...

【Linux】C语言执行shell指令

在C语言中执行Shell指令 在C语言中&#xff0c;有几种方法可以执行Shell指令&#xff1a; 1. 使用system()函数 这是最简单的方法&#xff0c;包含在stdlib.h头文件中&#xff1a; #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...

【位运算】消失的两个数字(hard)

消失的两个数字&#xff08;hard&#xff09; 题⽬描述&#xff1a;解法&#xff08;位运算&#xff09;&#xff1a;Java 算法代码&#xff1a;更简便代码 题⽬链接&#xff1a;⾯试题 17.19. 消失的两个数字 题⽬描述&#xff1a; 给定⼀个数组&#xff0c;包含从 1 到 N 所有…...

CentOS下的分布式内存计算Spark环境部署

一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架&#xff0c;相比 MapReduce 具有以下核心优势&#xff1a; 内存计算&#xff1a;数据可常驻内存&#xff0c;迭代计算性能提升 10-100 倍&#xff08;文档段落&#xff1a;3-79…...

微信小程序 - 手机震动

一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注&#xff1a;文档 https://developers.weixin.qq…...

ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放

简介 前面两期文章我们介绍了I2S的读取和写入&#xff0c;一个是通过INMP441麦克风模块采集音频&#xff0c;一个是通过PCM5102A模块播放音频&#xff0c;那如果我们将两者结合起来&#xff0c;将麦克风采集到的音频通过PCM5102A播放&#xff0c;是不是就可以做一个扩音器了呢…...

C# 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

docker 部署发现spring.profiles.active 问题

报错&#xff1a; org.springframework.boot.context.config.InvalidConfigDataPropertyException: Property spring.profiles.active imported from location class path resource [application-test.yml] is invalid in a profile specific resource [origin: class path re…...

[免费]微信小程序问卷调查系统(SpringBoot后端+Vue管理端)【论文+源码+SQL脚本】

大家好&#xff0c;我是java1234_小锋老师&#xff0c;看到一个不错的微信小程序问卷调查系统(SpringBoot后端Vue管理端)【论文源码SQL脚本】&#xff0c;分享下哈。 项目视频演示 【免费】微信小程序问卷调查系统(SpringBoot后端Vue管理端) Java毕业设计_哔哩哔哩_bilibili 项…...

从面试角度回答Android中ContentProvider启动原理

Android中ContentProvider原理的面试角度解析&#xff0c;分为​​已启动​​和​​未启动​​两种场景&#xff1a; 一、ContentProvider已启动的情况 1. ​​核心流程​​ ​​触发条件​​&#xff1a;当其他组件&#xff08;如Activity、Service&#xff09;通过ContentR…...