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]
从今天起,我们的算法开始研究搜索,首先就是DFS深度优先搜索(depth-first seach,DFS)在搜索到一个新的节点时,立即对该新节点进行遍 历;因此遍历需要用先入后出的栈来实现,也可以通过…...
关于宏任务的说法已经过时
关于宏任务w3c的最新解释,(mdn已经搜不到宏任务队列) ● 每个任务都有一个任务类型,用一个类型的任务必须在一个队列,不同类型的任务可以分属不同的队列。在一次事件循环当中,浏览器可以根据实际情况从不同…...

Java箱与泛型
大O的渐进表示法 大 O 的渐进表示法 去掉了那些对结果影响不大的项 ,简洁明了的表示出了执行次数。 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中,判断一个文件是否存在是一个常见的操作,可以通过QFile类和QDir类来实现。不过,对于简单的文件存在性检查,QFile类提供的接口更为直接。下面是一个使用QFile类来判断文件是否存在的例子: #include <QFile>…...

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

宝塔部署Vue项目解决跨域问题
一、前言 使用宝塔面板部署前端后端项目相比用命令行进行部署要简单许多,宝塔的可视化操作对那些对Linux不熟悉的人很友好。使用宝塔部署SpringBoot后端项目和Vue前端项目的方法如下: 1、视频教程 2、文字教程1 3、文字教程2 以上的教程完全可以按照步骤…...
C++智能指针简述
auto_ptr 设计目的:超出作用域,自动释放内存。所有权传递:拷贝auto_ptr时,原指针失效,释放所有权;新指针获得所有权。总而言之,允许通过拷贝转移所有权,独占所有权。缺陷࿱…...

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

Android Camera系列(二):TextureView+Camera
两岸猿声啼不住,轻舟已过万重山—李白 Android Camera系列(一):SurfaceViewCamera Android Camera系列(二):TextureViewCamera Android Camera系列(三):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 【很关键】是验证发送域。即身份里的域类型的身份。(可以理解为配置你的域名邮箱服务器(SMPT)为亚马…...

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

【MATLAB】模拟退火算法
模拟退火算法的MATLAB实现 模拟退火算法简介模拟退火算法应用实例关于计算结果 模拟退火算法简介 1982年,Kirkpatrick 将退火思想引入组合优化领域,提出了一种能够有效解决大规模组合优化问题的算法,尤其对 NP 完全问题表现出显著优势。模拟…...
什么是Kubernetes RBAC?
什么是Kubernetes RBAC? 1、什么是RBAC?2、核心组件3、优势💖The Begin💖点点关注,收藏不迷路💖 在Kubernetes集群中,RBAC(基于角色的访问控制)是保障系统安全的关键。它通过角色和绑定管理不同实体对资源的访问权限,具有显著优势: 1、什么是RBAC? RBAC是Kube…...
在Spring Boot中通过自定义注解、反射以及AOP(面向切面编程)
在Spring Boot中,通过自定义注解、反射以及AOP(面向切面编程)来动态修改请求参数是一种高级且强大的技术组合,它允许开发者在不修改原始方法实现的情况下,对方法的执行过程进行干预和定制。这种技术通常用于日志记录、…...

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

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

Superset二次开发之新增复选框Checkbox筛选器
一. 背景 Superset目前支持的筛选类型:值、数值范围、时间列、时间粒度、时间范围 5种类型,显然无法满足业务需求。根据产品需要,需要支持复选框、单选框、级联选择等类型的筛选器。本文探讨复选框、单选框的技术实现方式。 二. 效果预览 三. 实现思路 复用 值 筛选器模块,…...
PromQL 语法
什么是 PromQL PromQL (Prometheus Query Language) 是 Prometheus 监控系统中用于查询时间序列数据的语言。它允许用户编写查询,以从 Prometheus 中检索并处理监控数据。 PromQL 的基础概念 1. 时间序列 Prometheus 中的时间序列由以下几个部分组成:…...
掌握Go语言中的时间与日期操作
Go语言中的时间与日期操作 在编写程序时,处理时间和日期看似是一项无关紧要的任务,但在需要同步多个任务或从文本文件中读取时间时,它的重要性便凸显出来。Go语言中的time包为我们提供了丰富的时间与日期操作功能。本文将详细介绍如何在Go语…...

云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地
借阿里云中企出海大会的东风,以**「云启出海,智联未来|打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办,现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...
【Linux】C语言执行shell指令
在C语言中执行Shell指令 在C语言中,有几种方法可以执行Shell指令: 1. 使用system()函数 这是最简单的方法,包含在stdlib.h头文件中: #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...
【位运算】消失的两个数字(hard)
消失的两个数字(hard) 题⽬描述:解法(位运算):Java 算法代码:更简便代码 题⽬链接:⾯试题 17.19. 消失的两个数字 题⽬描述: 给定⼀个数组,包含从 1 到 N 所有…...

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

微信小程序 - 手机震动
一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注:文档 https://developers.weixin.qq…...

ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放
简介 前面两期文章我们介绍了I2S的读取和写入,一个是通过INMP441麦克风模块采集音频,一个是通过PCM5102A模块播放音频,那如果我们将两者结合起来,将麦克风采集到的音频通过PCM5102A播放,是不是就可以做一个扩音器了呢…...

C# 求圆面积的程序(Program to find area of a circle)
给定半径r,求圆的面积。圆的面积应精确到小数点后5位。 例子: 输入:r 5 输出:78.53982 解释:由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982,因为我们只保留小数点后 5 位数字。 输…...
docker 部署发现spring.profiles.active 问题
报错: 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脚本】
大家好,我是java1234_小锋老师,看到一个不错的微信小程序问卷调查系统(SpringBoot后端Vue管理端)【论文源码SQL脚本】,分享下哈。 项目视频演示 【免费】微信小程序问卷调查系统(SpringBoot后端Vue管理端) Java毕业设计_哔哩哔哩_bilibili 项…...
从面试角度回答Android中ContentProvider启动原理
Android中ContentProvider原理的面试角度解析,分为已启动和未启动两种场景: 一、ContentProvider已启动的情况 1. 核心流程 触发条件:当其他组件(如Activity、Service)通过ContentR…...