【2511. 最多可以摧毁的敌人城堡数目】
来源:力扣(LeetCode)
描述:
给你一个长度为 n
,下标从 0 开始的整数数组 forts
,表示一些城堡。forts[i]
可以是 -1
,0
或者 1
,其中:
-1
表示第i
个位置 没有 城堡。0
表示第i
个位置有一个 敌人 的城堡。1
表示第i
个位置有一个你控制的城堡。
现在,你需要决定,将你的军队从某个你控制的城堡位置 i 移动到一个空的位置 j ,满足:
0 <= i, j <= n - 1
- 军队经过的位置 只有 敌人的城堡。正式的,对于所有
min(i, j) < k < max(i, j)
的k
,都满足forts[k] == 0
。
当军队移动时,所有途中经过的敌人城堡都会被 摧毁 。
请你返回 最多 可以摧毁的敌人城堡数目。如果 无法 移动你的军队,或者没有你控制的城堡,请返回 0
。
示例 1:
输入:forts = [1,0,0,-1,0,0,0,0,1]
输出:4
解释:
- 将军队从位置 0 移动到位置 3 ,摧毁 2 个敌人城堡,位置分别在 1 和 2 。
- 将军队从位置 8 移动到位置 3 ,摧毁 4 个敌人城堡。
4 是最多可以摧毁的敌人城堡数目,所以我们返回 4 。
示例 2:
输入:forts = [0,0,1,-1]
输出:0
解释:由于无法摧毁敌人的城堡,所以返回 0 。
提示:
- 1 <= forts.length <= 1000
- -1 <= forts[i] <= 1
方法:直接模拟
思路与算法
根据题意可以知道军队从 i 处移动到 j 处时需要满足如下要求:
- 由于在 i 处的城堡为你方军队控制的城堡,则一定满足 forts[i] = 1;
- 由于在 j 处为空位置,则一定满足 forts[j] = −1;
- 在移动过程中如下,由于军队经过的位置只只能为敌人的城堡,因此当 k ∈ (min(i, j), max(i, j)) 时,需满足 forts[k] = 0。
- 当军队移动时,所有途中经过的敌人城堡都会被摧毁,题目要求找到一次移动后可以摧毁敌人城堡的最大数目。
根据以上分析可以知道由于军队只能在不同位置之间连续移动,军队移动的起点为 1,军队移动的终点为 −1,军队可以向左移动也可以向右移动,因此我们只需要找到相邻的 1 与 −1 之间的最大距离即可,此时 1 与 −1 之间所有的 0 都会被摧毁。查找过程如下:
- 依次遍历为数组 forts 中的每个元素,此时我们用 pre 记录数组中前一个为 1 或者 −1 的位置;
- 假设当前元素 forts[i] 为 1 或者 −1,即当前位置可能为军队的起点为终点,此时假设 forts[i] ≠ forts[pre],即此时可以在 i 与 pre 之间可以移动,此时可以摧毁的城堡数目为 i − pre − 1,更新当前的最大城堡数目,同时记录新的 pre;
按照上述方法找到最大可以摧毁的城堡数目即可。
代码:
class Solution {
public:int captureForts(vector<int>& forts) {int ans = 0, pre = -1;for (int i = 0; i < forts.size(); i++) {if (forts[i] == 1 || forts[i] == -1) {if (pre >= 0 && forts[i] != forts[pre]) {ans = max(ans, i - pre - 1);}pre = i;}}return ans;}
};
时间 4ms 击败 49.52%使用 C++ 的用户
内存 7.31MB 击败 79.65%使用 C++ 的用户
复杂度分析
- 时间复杂度:O(n),其中 n 表示数组 forts 的长度。在遍历 forts 时,每个元素只会遍历一次,因此时间复杂度为 O(n)。
- 空间复杂度:O(1)。
author:力扣官方题解
相关文章:
【2511. 最多可以摧毁的敌人城堡数目】
来源:力扣(LeetCode) 描述: 给你一个长度为 n ,下标从 0 开始的整数数组 forts ,表示一些城堡。forts[i] 可以是 -1 ,0 或者 1 ,其中: -1 表示第 i 个位置 没有 城堡。…...

stm32f1xx单片机拦截中断源代码
这个是实现后的效果,可以看到已经没有中断的效果了 这个是拦截前的效果可以看到电平是在变化的 实现原理非常简单:一句话搞定: if(TIM2->CNTTIM2->ARR-5)TIM2->CNT-5; 以下是完整的代码:是用来补充说明和筹字数的 /* …...
C++(21):特殊工具与技术
控制内存分配 某些应用程序对内存分配有特殊需求,无法直接应用标准内存管理机制。需要自定义内存分配的细节。 重载 new 和 delete void* operator new(std::size_t size) {// 自定义内存分配逻辑void* ptr std::malloc(size);if (!ptr) {throw std::bad_alloc(…...
go读取yaml,json,ini等配置文件
实际项目中,要读取一些json等配置文件。今天就来说一说,Golang 是如何读取YAML,JSON,INI等配置文件的。 一. go读取json配置文件 JSON 应该比较熟悉,它是一种轻量级的数据交换格式。层次结构简洁清晰 ,易于阅读和编写࿰…...

一、安装GoLang环境和开发工具
一、安装GoLang环境 GoLang中国镜像站 下载后对应的环境包以后,一路下一步就好了,安装路径的话,尽量就安装到默认的文件目录下。 二、配置Go的环境变量 右击此电脑–>属性–>高级系统设置–>环境变量,打开环境变量设置…...
条款40:对并发使用std::atomic,对特种内存使用valatile
可怜的volatile。被误解到如此地步。它甚至不应该出现在本章中,因为它与并发程序设计毫无关系。但是在其他程序设计语言中(Java和C#),它还是会对并发程序设计有些用处。甚至在C++中,一些编译器也已经把volatile投入到染缸,使得它的语义显得可以用于并发软件中(但是仅可用…...

Navicat使用HTTP通道服务器进行连接mysql数据库(超简单三分钟完成),centos安装nginx和php,docker安装nginx+php合并版
序言 因为数据库服务器在外网是不能直接连接访问的,但是可以访问网站,网站后台就能访问数据库,所以在此之前,访问数据库的数据是一件非常麻烦的事情,在平时和运维的交流中发现,他们会使用ssh通道进行连接访…...

图:有向无环图(DAG)
1.有向无环图的定义 有向无环图:若一个有向图中不存在环,则称为有向无环图。 简称DAG图(Directed Acyclic Graph) 顶点中不可能出现重复的操作数。 2.有向无环图的应用 1.描述算数表达式 用有向无环图描述算术表达式。 解题步骤: 把各个操作数不重…...

Python入门教程 - 基本语法 (一)
目录 一、注释 二、Python的六种数据类型 三、字符串、数字 控制台输出练习 四、变量及基本运算 五、type()语句查看数据的类型 六、字符串的3种不同定义方式 七、数据类型之间的转换 八、标识符命名规则规范 九、算数运算符 十、赋值运算符 十一、字符串扩展 11.1…...

使用PAM保障开发运营安全
硬编码凭据和 DevOps 系统中缺乏凭据安全性是组织的巨大漏洞。以明文形式访问凭据的恶意内部人员可以在 IT 中建立和扩展其立足点 基础设施,构成巨大的数据被盗风险。 什么是PAM 特权访问管理 (PAM) 是指一组 IT 安全管理原则,可…...

《Go 语言第一课》课程学习笔记(十二)
函数 Go 函数与函数声明 在 Go 语言中,函数是唯一一种基于特定输入,实现特定任务并可返回任务执行结果的代码块(Go 语言中的方法本质上也是函数)。在 Go 中,我们定义一个函数的最常用方式就是使用函数声明。 第一部…...
【深入浅出C#】章节10: 最佳实践和性能优化:编码规范和代码风格
编码规范和代码风格之所以重要,是因为它们直接影响到软件开发的质量、可维护性、可读性和协作效率。编码规范和代码风格是编程中的关键要素,它们有助于编写高质量、可维护和易读的代码,提高团队协作效率,减少错误,降低…...

LNMP架构:搭建Discuz论坛
文章目录 1. 编译安装Nginx1.1 前置准备1.2 编译安装1.3 添加nginx系统服务 2.编译安装MySql2.1 前置准备2.2 编译安装2.3 修改mysql 配置文件2.4 设置路径环境变量2.5 初始化数据库2.6 添加musql系统服务2.7 修改MySql登录密码 3. 编译安装PHP3.1 前置准备3.2 编译安装3.3 复制…...
详解Numpy(基于jupyter notebook)
详解Numpy(基于jupyter notebook) 1.创建数组2.数据类型3.数组切片和索引4.Numpy的广播与数组操作5.数组合并与通用函数6.其他通用函数 1.创建数组 #引入numpy包,以后np就代表numpy import numpy as npanp.arange(10,30,2)#10为起点…...

nvm集合node版本,解决新版本jeecgboot3.5.3前端启动失败问题
jeecgboot前端3.5.3页面如下 使用之前的pnpm启动会报错,pnpm是node进行安装的,查询后发现,vue3版本的页面至少需要node16版本,我之前的版本只有15.5,适用于vue2 那么我将先前的node15.5版本删除,然后安装…...

Windows命令行初步:更改配色、提示符以及编码方式
文章目录 启动和退出窗口标题和提示符命令行颜色更改编码 启动和退出 按下winR,调出运行窗口,输入cmd就可以进入命令行了。在Win10以前的系统种,如果在命令行中再输入一个cmd,就会再打开一个命令行。但最近的Win11版本中…...
uniapp onLoad生命周期 uni.$on接受参数无法改变data数据解决办法
问题阐述: a: uni.$emit(name,data)uni.navigateTo({url:b})b:onload(){ uni.$on(name,(res)>{ this.nameres console.log(this.name) })}用以上写法来跨页面传参会发现在b页面,虽然能够接受到参数但是赋值到data时候没生效,虽然控制台能…...
Android Camera开发入门(4):USB/UVC Camera的使用
Android Camera开发入门(4):USB/UVC Camera的使用 本文基于开源项目https://github.com/saki4510t/UVCCamera之上进行二次封装和使用 在前几篇文章中,我们介绍了Camera到CameraX的基础功能应用,同时附上了相关代码,需要的源码的大佬们可以滑到最底部获取。 本篇我们一起…...

Java网络爬虫——jsoup快速上手,爬取京东数据。同时解决‘京东安全’防爬问题
文章目录 介绍jsoup使用1.解析url,获取前端代码2.解决京东安全界面跳转3.获取每一组的数据4.获取商品数据的具体信息4.最终代码 介绍 网络爬虫,就是在浏览器上,代替人类爬取数据,Java网络爬虫就是通过Java编写爬虫代码࿰…...

外观模式:简化复杂子系统的访问与使用
文章目录 1. 简介2. 外观模式的基本结构3. 外观模式的实现步骤4. 外观模式的应用与实例4.1 图形界面库的外观模式应用4.2 文件压缩与解压缩的外观模式应用4.3 订单处理系统的外观模式应用 5. 外观模式的优缺点5.1 优点5.2 缺点 6. 总结 1. 简介 外观模式是一种结构型设计模式&…...
vscode里如何用git
打开vs终端执行如下: 1 初始化 Git 仓库(如果尚未初始化) git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...

JavaScript 中的 ES|QL:利用 Apache Arrow 工具
作者:来自 Elastic Jeffrey Rengifo 学习如何将 ES|QL 与 JavaScript 的 Apache Arrow 客户端工具一起使用。 想获得 Elastic 认证吗?了解下一期 Elasticsearch Engineer 培训的时间吧! Elasticsearch 拥有众多新功能,助你为自己…...
Golang dig框架与GraphQL的完美结合
将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用,可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器,能够帮助开发者更好地管理复杂的依赖关系,而 GraphQL 则是一种用于 API 的查询语言,能够提…...
反射获取方法和属性
Java反射获取方法 在Java中,反射(Reflection)是一种强大的机制,允许程序在运行时访问和操作类的内部属性和方法。通过反射,可以动态地创建对象、调用方法、改变属性值,这在很多Java框架中如Spring和Hiberna…...

Java面试专项一-准备篇
一、企业简历筛选规则 一般企业的简历筛选流程:首先由HR先筛选一部分简历后,在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如:Boss直聘(招聘方平台) 直接按照条件进行筛选 例如:…...
今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存
文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...
LeetCode - 199. 二叉树的右视图
题目 199. 二叉树的右视图 - 力扣(LeetCode) 思路 右视图是指从树的右侧看,对于每一层,只能看到该层最右边的节点。实现思路是: 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...

C++使用 new 来创建动态数组
问题: 不能使用变量定义数组大小 原因: 这是因为数组在内存中是连续存储的,编译器需要在编译阶段就确定数组的大小,以便正确地分配内存空间。如果允许使用变量来定义数组的大小,那么编译器就无法在编译时确定数组的大…...
JS设计模式(4):观察者模式
JS设计模式(4):观察者模式 一、引入 在开发中,我们经常会遇到这样的场景:一个对象的状态变化需要自动通知其他对象,比如: 电商平台中,商品库存变化时需要通知所有订阅该商品的用户;新闻网站中࿰…...

处理vxe-table 表尾数据是单独一个接口,表格tableData数据更新后,需要点击两下,表尾才是正确的
修改bug思路: 分别把 tabledata 和 表尾相关数据 console.log() 发现 更新数据先后顺序不对 settimeout延迟查询表格接口 ——测试可行 升级↑:async await 等接口返回后再开始下一个接口查询 ________________________________________________________…...