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

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

来源:力扣(LeetCode)

描述:

给你一个长度为 n ,下标从 0 开始的整数数组 forts ,表示一些城堡。forts[i] 可以是 -10 或者 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 个敌人城堡,位置分别在 12- 将军队从位置 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. 最多可以摧毁的敌人城堡数目】

来源&#xff1a;力扣&#xff08;LeetCode&#xff09; 描述&#xff1a; 给你一个长度为 n &#xff0c;下标从 0 开始的整数数组 forts &#xff0c;表示一些城堡。forts[i] 可以是 -1 &#xff0c;0 或者 1 &#xff0c;其中&#xff1a; -1 表示第 i 个位置 没有 城堡。…...

stm32f1xx单片机拦截中断源代码

这个是实现后的效果&#xff0c;可以看到已经没有中断的效果了 这个是拦截前的效果可以看到电平是在变化的 实现原理非常简单&#xff1a;一句话搞定&#xff1a; if(TIM2->CNTTIM2->ARR-5)TIM2->CNT-5; 以下是完整的代码&#xff1a;是用来补充说明和筹字数的 /* …...

C++(21):特殊工具与技术

控制内存分配 某些应用程序对内存分配有特殊需求&#xff0c;无法直接应用标准内存管理机制。需要自定义内存分配的细节。 重载 new 和 delete void* operator new(std::size_t size) {// 自定义内存分配逻辑void* ptr std::malloc(size);if (!ptr) {throw std::bad_alloc(…...

go读取yaml,json,ini等配置文件

实际项目中&#xff0c;要读取一些json等配置文件。今天就来说一说&#xff0c;Golang 是如何读取YAML,JSON,INI等配置文件的。 一. go读取json配置文件 JSON 应该比较熟悉&#xff0c;它是一种轻量级的数据交换格式。层次结构简洁清晰 &#xff0c;易于阅读和编写&#xff0…...

一、安装GoLang环境和开发工具

一、安装GoLang环境 GoLang中国镜像站 下载后对应的环境包以后&#xff0c;一路下一步就好了&#xff0c;安装路径的话&#xff0c;尽量就安装到默认的文件目录下。 二、配置Go的环境变量 右击此电脑–>属性–>高级系统设置–>环境变量&#xff0c;打开环境变量设置…...

条款40:对并发使用std::atomic,对特种内存使用valatile

可怜的volatile。被误解到如此地步。它甚至不应该出现在本章中,因为它与并发程序设计毫无关系。但是在其他程序设计语言中(Java和C#),它还是会对并发程序设计有些用处。甚至在C++中,一些编译器也已经把volatile投入到染缸,使得它的语义显得可以用于并发软件中(但是仅可用…...

Navicat使用HTTP通道服务器进行连接mysql数据库(超简单三分钟完成),centos安装nginx和php,docker安装nginx+php合并版

序言 因为数据库服务器在外网是不能直接连接访问的&#xff0c;但是可以访问网站&#xff0c;网站后台就能访问数据库&#xff0c;所以在此之前&#xff0c;访问数据库的数据是一件非常麻烦的事情&#xff0c;在平时和运维的交流中发现&#xff0c;他们会使用ssh通道进行连接访…...

图:有向无环图(DAG)

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

Python入门教程 - 基本语法 (一)

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

使用PAM保障开发运营安全

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

《Go 语言第一课》课程学习笔记(十二)

函数 Go 函数与函数声明 在 Go 语言中&#xff0c;函数是唯一一种基于特定输入&#xff0c;实现特定任务并可返回任务执行结果的代码块&#xff08;Go 语言中的方法本质上也是函数&#xff09;。在 Go 中&#xff0c;我们定义一个函数的最常用方式就是使用函数声明。 第一部…...

【深入浅出C#】章节10: 最佳实践和性能优化:编码规范和代码风格

编码规范和代码风格之所以重要&#xff0c;是因为它们直接影响到软件开发的质量、可维护性、可读性和协作效率。编码规范和代码风格是编程中的关键要素&#xff0c;它们有助于编写高质量、可维护和易读的代码&#xff0c;提高团队协作效率&#xff0c;减少错误&#xff0c;降低…...

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&#xff08;基于jupyter notebook&#xff09; 1.创建数组2.数据类型3.数组切片和索引4.Numpy的广播与数组操作5.数组合并与通用函数6.其他通用函数 1.创建数组 #引入numpy包&#xff0c;以后np就代表numpy import numpy as npanp.arange(10,30,2)#10为起点&#xf…...

nvm集合node版本,解决新版本jeecgboot3.5.3前端启动失败问题

jeecgboot前端3.5.3页面如下 使用之前的pnpm启动会报错&#xff0c;pnpm是node进行安装的&#xff0c;查询后发现&#xff0c;vue3版本的页面至少需要node16版本&#xff0c;我之前的版本只有15.5&#xff0c;适用于vue2 那么我将先前的node15.5版本删除&#xff0c;然后安装…...

Windows命令行初步:更改配色、提示符以及编码方式

文章目录 启动和退出窗口标题和提示符命令行颜色更改编码 启动和退出 按下winR&#xff0c;调出运行窗口&#xff0c;输入cmd就可以进入命令行了。在Win10以前的系统种&#xff0c;如果在命令行中再输入一个cmd&#xff0c;就会再打开一个命令行。但最近的Win11版本中&#xf…...

uniapp onLoad生命周期 uni.$on接受参数无法改变data数据解决办法

问题阐述&#xff1a; a: uni.$emit(name,data)uni.navigateTo({url:b})b:onload(){ uni.$on(name,(res)>{ this.nameres console.log(this.name) })}用以上写法来跨页面传参会发现在b页面&#xff0c;虽然能够接受到参数但是赋值到data时候没生效&#xff0c;虽然控制台能…...

Android Camera开发入门(4):USB/UVC Camera的使用

Android Camera开发入门(4):USB/UVC Camera的使用 本文基于开源项目https://github.com/saki4510t/UVCCamera之上进行二次封装和使用 在前几篇文章中,我们介绍了Camera到CameraX的基础功能应用,同时附上了相关代码,需要的源码的大佬们可以滑到最底部获取。 本篇我们一起…...

Java网络爬虫——jsoup快速上手,爬取京东数据。同时解决‘京东安全’防爬问题

文章目录 介绍jsoup使用1.解析url&#xff0c;获取前端代码2.解决京东安全界面跳转3.获取每一组的数据4.获取商品数据的具体信息4.最终代码 介绍 网络爬虫&#xff0c;就是在浏览器上&#xff0c;代替人类爬取数据&#xff0c;Java网络爬虫就是通过Java编写爬虫代码&#xff0…...

外观模式:简化复杂子系统的访问与使用

文章目录 1. 简介2. 外观模式的基本结构3. 外观模式的实现步骤4. 外观模式的应用与实例4.1 图形界面库的外观模式应用4.2 文件压缩与解压缩的外观模式应用4.3 订单处理系统的外观模式应用 5. 外观模式的优缺点5.1 优点5.2 缺点 6. 总结 1. 简介 外观模式是一种结构型设计模式&…...

[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?

&#x1f9e0; 智能合约中的数据是如何在区块链中保持一致的&#xff1f; 为什么所有区块链节点都能得出相同结果&#xff1f;合约调用这么复杂&#xff0c;状态真能保持一致吗&#xff1f;本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里&#xf…...

利用ngx_stream_return_module构建简易 TCP/UDP 响应网关

一、模块概述 ngx_stream_return_module 提供了一个极简的指令&#xff1a; return <value>;在收到客户端连接后&#xff0c;立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量&#xff08;如 $time_iso8601、$remote_addr 等&#xff09;&a…...

(二)TensorRT-LLM | 模型导出(v0.20.0rc3)

0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述&#xff0c;后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作&#xff0c;其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...

AI编程--插件对比分析:CodeRider、GitHub Copilot及其他

AI编程插件对比分析&#xff1a;CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展&#xff0c;AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者&#xff0c;分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...

Java毕业设计:WML信息查询与后端信息发布系统开发

JAVAWML信息查询与后端信息发布系统实现 一、系统概述 本系统基于Java和WML(无线标记语言)技术开发&#xff0c;实现了移动设备上的信息查询与后端信息发布功能。系统采用B/S架构&#xff0c;服务器端使用Java Servlet处理请求&#xff0c;数据库采用MySQL存储信息&#xff0…...

C语言中提供的第三方库之哈希表实现

一. 简介 前面一篇文章简单学习了C语言中第三方库&#xff08;uthash库&#xff09;提供对哈希表的操作&#xff0c;文章如下&#xff1a; C语言中提供的第三方库uthash常用接口-CSDN博客 本文简单学习一下第三方库 uthash库对哈希表的操作。 二. uthash库哈希表操作示例 u…...

Kubernetes 网络模型深度解析:Pod IP 与 Service 的负载均衡机制,Service到底是什么?

Pod IP 的本质与特性 Pod IP 的定位 纯端点地址&#xff1a;Pod IP 是分配给 Pod 网络命名空间的真实 IP 地址&#xff08;如 10.244.1.2&#xff09;无特殊名称&#xff1a;在 Kubernetes 中&#xff0c;它通常被称为 “Pod IP” 或 “容器 IP”生命周期&#xff1a;与 Pod …...

MyBatis中关于缓存的理解

MyBatis缓存 MyBatis系统当中默认定义两级缓存&#xff1a;一级缓存、二级缓存 默认情况下&#xff0c;只有一级缓存开启&#xff08;sqlSession级别的缓存&#xff09;二级缓存需要手动开启配置&#xff0c;需要局域namespace级别的缓存 一级缓存&#xff08;本地缓存&#…...

6个月Python学习计划 Day 16 - 面向对象编程(OOP)基础

第三周 Day 3 &#x1f3af; 今日目标 理解类&#xff08;class&#xff09;和对象&#xff08;object&#xff09;的关系学会定义类的属性、方法和构造函数&#xff08;init&#xff09;掌握对象的创建与使用初识封装、继承和多态的基本概念&#xff08;预告&#xff09; &a…...

数据库正常,但后端收不到数据原因及解决

从代码和日志来看&#xff0c;后端SQL查询确实返回了数据&#xff0c;但最终user对象却为null。这表明查询结果没有正确映射到User对象上。 在前后端分离&#xff0c;并且ai辅助开发的时候&#xff0c;很容易出现前后端变量名不一致情况&#xff0c;还不报错&#xff0c;只是单…...