2511. 最多可以摧毁的敌人城堡数目

文章目录

  • Tag
  • 题目来源
  • 题目解读
  • 解题思路
  • 复杂度分析
  • 写在最后

Tag

【数组】


题目来源

2511. 最多可以摧毁的敌人城堡数目
在这里插入图片描述


题目解读

在数组 forts 中,forts[i] 有三种数值:

  • -1: 表示第 i 个位置没有城堡,是空地;
  • 0: 表示第 i 个位置有一个敌人城堡;
  • 1: 表示第 i 个位置有一个你控制的城堡。

需要计算从你的城堡走到空地需要摧毁的敌人城堡的最大数量。


解题思路

我们只需要统计相邻的 -11 中间 0 的数量,最后返回最大的 0 的数量。

实现上,我们使用 pre 变量记录上一个 -1 或者 1 出现的位置,我们从左到右遍历 forts 数组:

  • 假设我们遇到了 1,而 forts[pre] = -1,那么更新答案 res = max(res, i - pre - 1),我们用 i - pre - 1 来计算相邻的 -11 中间 0 的数量;
  • 假设我们遇到了 -1,而 forts[pre] = 1,那么更新答案 res = max(res, i - pre - 1)
  • 最后要及时更新 pre = i

实现代码

class Solution {
public:int captureForts(vector<int>& forts) {int pre = 0, res = 0;for (int i = 0; i < forts.size(); ++i) {if ((forts[i] == -1 || forts[i] == 1)) {if (forts[i] == -forts[pre]) {res = max(res, i - pre - 1);}pre = i;}}return res;}
};

复杂度分析

时间复杂度: O ( n ) O(n) O(n) n n n 为数组 forts 的长度。

空间复杂度: O ( 1 ) O(1) O(1),因为仅使用了一个额外的变量 pre 记录上一个 -1 或者 1 出现的位置。


写在最后

以上就是本篇文章的内容了,感谢您的阅读。🍗🍗🍗

如果感到有所收获的话可以给博主点一个 👍 哦。

如果文章内容有任何错误或者您对文章有任何疑问,欢迎私信博主或者在评论区指出。💬💬💬

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/116917.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

从零开始,探索C语言中的字符串

字符串 1. 前言2. 预备知识2.1 字符2.2 字符数组 3. 什么是字符串4. \04.1 \0是什么4.2 \0的作用4.2.1 打印字符串4.2.2 求字符串长度 1. 前言 大家好&#xff0c;我是努力学习游泳的鱼。你已经学会了如何使用变量和常量&#xff0c;也知道了字符的概念。但是你可能还不了解由…

layui框架学习(40:数据表格_主要事件)

Layui数据表格模块主要通过各类事件响应工具栏操作、单元格编辑或点击等交互操作&#xff0c;本文学习table数据表格模块中的主要事件及处理方式。   头部工具栏事件。通过代码“table.on(‘toolbar(test)’, function(obj))”获取lay-filter属性为test的数据表格的头部工具栏…

蒲公英路由器如何设置远程打印?

现如今&#xff0c;打印机已经是企业日常办公中必不可少的设备&#xff0c;无论何时何地&#xff0c;总有需要用到打印的地方&#xff0c;包括资料文件、统计报表等等。 但若人在外地或分公司&#xff0c;有文件急需通过总部的打印机进行打印时&#xff0c;由于不在同一物理网络…

每日一题-动态规划(从不同类型的物品中各挑选一个,使得最后花费总和等于1000)

四种类型的物品&#xff0c;每一种类型物品数量都是n&#xff0c;先要从每种类型的物品中挑选一件&#xff0c;使得最后花费总和等于1000 暴力做法10000^4 看到花费总和是1000&#xff0c;很小且固定的数字&#xff0c;肯定有玄机&#xff0c;从这里想应该是用dp&#xff0c;不…

记一次反弹shell的操作【非常简单】

#什么是反弹shell 通常我们对一个开启了80端口的服务器进行访问时&#xff0c;就会建立起与服务器Web服务链接&#xff0c;从而获取到服务器相应的Web服务。而反弹shell是我们开启一个端口进行监听&#xff0c;转而让服务器主动反弹一个shell来连接我们的主机&#xff0c;我们再…

Git企业开发控制理论和实操-从入门到深入(四)|Git的远程操作|Gitee

前言 那么这里博主先安利一些干货满满的专栏了&#xff01; 首先是博主的高质量博客的汇总&#xff0c;这个专栏里面的博客&#xff0c;都是博主最最用心写的一部分&#xff0c;干货满满&#xff0c;希望对大家有帮助。 高质量博客汇总 然后就是博主最近最花时间的一个专栏…

无涯教程-Android - Broadcast Receivers

Broadcast Receivers 仅响应来自其他应用程序或系统本身的广播消息&#xff0c;这些消息有时称为events或intents。例如&#xff0c;应用程序还可以启动广播&#xff0c;以使其他应用程序知道某些数据已下载到设备并可供他们使用&#xff0c;因此广播接收器将拦截此通信并启动适…

网络中的问题2

距离-向量算法的具体实现 每个routerY的路由表表项 involve<目的网络N&#xff0c;距离d&#xff0c;下一跳X> 对邻居X发来的报文,先把下一跳改为X,再把距离1,if original route table doesn’t involve N,add this item&#xff1b; else if original table’s relate…

VC++使用Microsoft Speech SDK进行文字TTS朗读

Microsoft Speech SDK下载地址 https://www.microsoft.com/en-us/download/details.aspx?id10121 需要msttss22L.exe、SpeechSDK51.exe、SpeechSDK51LangPack.exe三个&#xff0c;下载后全部安装 使用VS2005建立一个win32控制台项目 朗读"hello word"、中文“你好”…

[dasctf]misc3 chrchrchr.pcapng

webshell 流量分析 php代码部分没啥看的&#xff0c;主要在标黄的部分&#xff0c;裁剪掉前面的字符可base解码 能看到在向a.txt中写入数据 wp # tshark.exe -r chrchrchr.pcapng -T fields -e urlencoded-form.value -Y "urlencoded-form.keyzd2ebbfb26dd" >…

【Sql】把数据库字段用函数根据逗号分裂成列表,然后判断列表中是否包含目标值

【Sql】把数据库字段用函数根据逗号分裂成列表&#xff0c;然后判断列表中是否包含目标值 【1】问题描述【2】Oracle内置函数解决【3】mysql的内置函数INSTR()【4】mysql的内置函数FIND_IN_SET() 【1】问题描述 数据库中【库信息db】和【集群信息cluster】是一对多的关系&…

Remmina在ubuntu22.04中无法连接Windows

Remmina在ubuntu22.04中无法连接Windows 问题 提示为&#xff1a; 无法通过TLS到RDP服务器… 分析 原因是Remmina需要使用openssl通过RDP加密与Windows计算机连接&#xff0c;而ubuntu22.04系统中OpenSSL版本为3.0&#xff0c;Openssl3 将 tls<1.2 和 sha1 的默认安全级别…

管理类联考——逻辑——形式逻辑——汇总篇——知识点突破——形式逻辑——联言选言假言——矛盾

角度 角度——汇总——持续优化 性质 &#xff08;1&#xff09; 所有的 S 是 P 所有的S是P 所有的S是P 与 有的 S 不是 P 有的S不是P 有的S不是P矛盾 &#xff08;2&#xff09; 所有的 S 不是 P 所有的S不是P 所有的S不是P 与 有的 S 是 P 有的S是P 有的S是P 矛盾 &#xf…

Git——Windows平台创建gitee私有仓库详解

目录 1. 安装git 2. gitbash配置 2.1 设置 2.2 生成key 2.3 项目管理 2.3.1 本地新建 2.3.2 clone远程仓库的工程到本地改文件 1. 安装git 默认安装。 2. gitbash配置 2.1 设置 打开gitbash&#xff0c;设置用户名和邮箱&#xff1a; git config --global user.name …

excel功能区(ribbonx)编程笔记--2 button控件与checkbox控件

我们上一章简单先了解了ribbonx的基本内容,以及使用举例实现自己修改ribbox的内容,本章紧接上一章,先讲解一下ribbonx的button控件。 在功能区的按钮中,可以使用内置图像或提供自已的图像,可以指定大按钮或者更小的形式,添加少量的代码甚至可以同时提供标签。此外,可以利…

WPF基础入门-Class7-WPF-MVVN框架

WPF基础入门 Class7-MVVN框架 使用框架可以省掉如Class6中的ViewModelBase.cs的OnPropertyChanged&#xff0c;亦方便命令传参 1、NuGet安装CommunityToolkit.Mvvm&#xff08;原Mircrosoft.Toolkit.Mvvm&#xff09;也可以安装MVVMLight等其他集成库 2、显示页面&#xff1…

用Rust打印hello world!

步骤1 桌面新建1个名为 rustDemo 的文件夹&#xff08;文件夹名字随便取&#xff09; 步骤2 打开新建的文件夹&#xff0c;在地址输入栏输入 cmd 按回车键进入命令行窗口 步骤3 打开编译器&#xff0c;按 Ctrl S&#xff0c;保存文件到 rustDemo 文件夹中&#xff0c;保存的…

简述SpringMVC

一、典型的Servlet JSP JavaBean UserServlet看作业务逻辑处理&#xff08;Controller&#xff09;User看作模型&#xff08;Model&#xff09;user.jsp看作渲染&#xff08;View&#xff09; 二、高级MVC 由DispatcherServlet对请求统一处理 三、SpringMVC MVC与Spr…

MySQL8.0.22安装过程记录(个人笔记)

1.点击下载MySQL 2.解压到本地磁盘&#xff08;注意路径中不要有中文&#xff09; 3.在解压目录创建my.ini文件 文件内容为 [mysql] # 设置mysql客户端默认字符集 default-character-setutf8[mysqld] # 设置端口 port 3306 # 设计mysql的安装路径 basedirE:\01.app\05.Tool…

OpenCV(十四):ROI区域截取

在OpenCV中&#xff0c;你可以使用Rect对象或cv::Range来截取图像的感兴趣区域&#xff08;Region of Interest&#xff0c;ROI&#xff09;。 方法一&#xff1a;使用Rect对象截取图像 Rect_(_Tp _x&#xff0c; _Tp _y&#xff0c; _Tp _width,_Tp _height) Tp:数据类型&…