【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. 简介 外观模式是一种结构型设计模式&…...
[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?
🧠 智能合约中的数据是如何在区块链中保持一致的? 为什么所有区块链节点都能得出相同结果?合约调用这么复杂,状态真能保持一致吗?本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里…...
利用ngx_stream_return_module构建简易 TCP/UDP 响应网关
一、模块概述 ngx_stream_return_module 提供了一个极简的指令: return <value>;在收到客户端连接后,立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量(如 $time_iso8601、$remote_addr 等)&a…...

(二)TensorRT-LLM | 模型导出(v0.20.0rc3)
0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述,后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作,其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...
AI编程--插件对比分析:CodeRider、GitHub Copilot及其他
AI编程插件对比分析:CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展,AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者,分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...
Java毕业设计:WML信息查询与后端信息发布系统开发
JAVAWML信息查询与后端信息发布系统实现 一、系统概述 本系统基于Java和WML(无线标记语言)技术开发,实现了移动设备上的信息查询与后端信息发布功能。系统采用B/S架构,服务器端使用Java Servlet处理请求,数据库采用MySQL存储信息࿰…...
C语言中提供的第三方库之哈希表实现
一. 简介 前面一篇文章简单学习了C语言中第三方库(uthash库)提供对哈希表的操作,文章如下: C语言中提供的第三方库uthash常用接口-CSDN博客 本文简单学习一下第三方库 uthash库对哈希表的操作。 二. uthash库哈希表操作示例 u…...
Kubernetes 网络模型深度解析:Pod IP 与 Service 的负载均衡机制,Service到底是什么?
Pod IP 的本质与特性 Pod IP 的定位 纯端点地址:Pod IP 是分配给 Pod 网络命名空间的真实 IP 地址(如 10.244.1.2)无特殊名称:在 Kubernetes 中,它通常被称为 “Pod IP” 或 “容器 IP”生命周期:与 Pod …...

MyBatis中关于缓存的理解
MyBatis缓存 MyBatis系统当中默认定义两级缓存:一级缓存、二级缓存 默认情况下,只有一级缓存开启(sqlSession级别的缓存)二级缓存需要手动开启配置,需要局域namespace级别的缓存 一级缓存(本地缓存&#…...
6个月Python学习计划 Day 16 - 面向对象编程(OOP)基础
第三周 Day 3 🎯 今日目标 理解类(class)和对象(object)的关系学会定义类的属性、方法和构造函数(init)掌握对象的创建与使用初识封装、继承和多态的基本概念(预告) &a…...
数据库正常,但后端收不到数据原因及解决
从代码和日志来看,后端SQL查询确实返回了数据,但最终user对象却为null。这表明查询结果没有正确映射到User对象上。 在前后端分离,并且ai辅助开发的时候,很容易出现前后端变量名不一致情况,还不报错,只是单…...