942. 增减字符串匹配 - 力扣
1. 题目
由范围
[0,n]内所有整数组成的n + 1个整数的排列序列可以表示为长度为n的字符串s,其中:
- 如果
perm[i] < perm[i + 1],那么s[i] == 'I'- 如果
perm[i] > perm[i + 1],那么s[i] == 'D'给定一个字符串
s,重构排列perm并返回它。如果有多个有效排列perm,则返回其中 任何一个 。
2. 示例

3. 分析
这道题目的意思就是如果字符是 I ,则当前元素需小于后一个元素;若为 D ,则当前元素需大于后一个元素:
以下摘抄自 官方题解 :
考虑 perm[0] (返回数组) 的值,根据题意:
- 如果 s[0] = 'I',那么令 perm[0] = 0,则无论 perm[1] 为何值都满足 perm[0] < perm[1];
- 如果 s[0] = 'D',那么令 perm[0] = n,则无论 perm[1] 为何值都满足 perm[0] > perm[1];
确定好 perm[0] 后,剩余的 n−1 个字符和 n 个待确定的数就变成了一个和原问题相同,但规模为 n−1 的问题。因此我们可以继续按照上述方法确定 perm[1]:如果 s[1] = 'I',那么令 perm[1] 为剩余数字中的最小数;如果 s[1] = 'D',那么令 perm[1] 为剩余数字中的最大数。如此循环直至剩下一个数,填入 perm[n] 中。即 I 就放剩余数字中的最小数,D 就放剩余数字中的最大数。
我们可以定义两个指针,表示剩余待确定数字中的最小和最大值:
class Solution {
public:vector<int> diStringMatch(string s) {int n = s.size();vector<int> res(n+1);int min = 0, max = n;for(int i = 0; i < n; i++){if(s[i] == 'I') {res[i] = min;min++;} else {res[i] = max;max--;}}res[n] = max; // 还剩最后一个数,此时 min == maxreturn res;}
};相关文章:
942. 增减字符串匹配 - 力扣
1. 题目 由范围 [0,n] 内所有整数组成的 n 1 个整数的排列序列可以表示为长度为 n 的字符串 s ,其中: 如果 perm[i] < perm[i 1] ,那么 s[i] I 如果 perm[i] > perm[i 1] ,那么 s[i] D 给定一个字符串 s ,重构排列 pe…...
2024华为OD机试真题-机器人搬砖-C++(C卷D卷)
题目描述 机器人搬砖,一共有N堆砖存放在N个不同的仓库中,第i堆砖中有bricks[i]块砖头, 要求在8小时内搬完。机器人每小时能搬砖的数量取决于有多少能量格, 机器人一个小时中只能在一个仓库中搬砖,机器人的能量格每小时补充一次且能量格只在这一个小时有效,为使得机器人损…...
【DevOps】深入了解RabbitMQ:AMQP协议基础、消息队列工作原理和应用场景
目录 一、核心功能 二、优势 三、核心概念 四、工作原理 五、交换机类型 六、消息确认 七、持久性和可靠性 八、插件和扩展 九、集群和镜像队列 十、客户端库 十一、管理界面 十二、应用场景 RabbitMQ是一个基于AMQP协议的消息队列中间件,提供高可用、可…...
Mysql 技术实战篇
命令行 导出 - -h localhost:指定MySQL服务器的主机地址为本地主机。如果MySQL服务器在其他主机上,请将localhost替换为相应的主机地址。 - -u username:指定连接MySQL服务器的用户名。将username替换为您的有效用户名。 - -p:提…...
App自动化测试_Python+Appium使用手册
一、Appium的介绍 Appium是一款开源的自动化测试工具,支持模拟器和真机上的原生应用、混合应用、Web应用;基于Selenium二次开发,Appium支持Selenium WebDriver支持的所有语言(java、 Object-C 、 JavaScript 、p hp、 Python等&am…...
k8s-部署对象存储minio
环境信息 minio版本 :最新 k8s 版本1.22 使用nfs作为共享存储 一.单节点安装包部署 脚本部署,一键部署,单节点应用于数据量小,一些缓存存储,比如gitlab-runner的产物数据,maven的打包依赖数据 #!/bin/bash# 步骤…...
go常用命令
创建一个module(逻辑概念) #The go mod init command initializes and writes a new go.mod file in the current directory, in effect creating #a new module rooted at the current directory. #specify a module path that serves as the module’s name. go mod initclon…...
【中年危机】程序猿自救指南
中年危机,一个听起来就充满挑战的词汇,它不仅仅是一个年龄的标记,更是一个个人成长和职业发展的转折点。 构架个人品牌: 学会打造IP个人品牌是职业生涯中的重要资产。在中年时期,你已经积累了丰富的经验和知识&#x…...
vueRouter路由总结
https://blog.csdn.net/qq_24767091/article/details/119326884...
算法工程师需要学习C++的哪些知识?
在开始前刚好我有一些资料,是我根据网友给的问题精心整理了一份「C的资料从专业入门到高级教程」, 点个关注在评论区回复“888”之后私信回复“888”,全部无偿共享给大家!!!以下是算法工程师需要学习的一些…...
CTF网络安全大赛简单的web抓包题目:HEADache
题目来源于:bugku 题目难度:简单 题目 描 述: > Wanna learn about some types of headache? > Lets dig right into it! 下面是题目源代码: <!DOCTYPE html> <html> <head><meta charset"utf-8"&…...
Qt Creator创建Python界面工程并打包为可执行exe文件
Qt Creator创建Python界面工程并打包为可执行exe文件_qtcreator创建python工程-CSDN博客...
基于单片机的步进电机控制系统的研究
摘要: 步进电机控制作为一种电机控制系统的重要模式,属于现代数字化控制的重要手段,其应用已经相当广泛。步进电机属于感应电机类,利用电子电路将直流电分为分时供电、多相时序供电控制电流,利用这种电流为电机供电,驱使电机工作。步进电机不能够在常规模式下使用,必须通过双环…...
BioPorto胰高血糖素样肽-1抗体(GLP-1)
丹麦BioPorto Diadnostics公司致力于提供世界领先的GLP-1抗体。基于结合GLP-1位点的不同,他们筛选出了不同的抗GLP-1抗体。有的抗体可以同时结合GLP-1的活性形式和非活性形式,有的专门结合生物活性形式的GLP-1。在开发和检测GLP-1相关治疗的过程中&#…...
Go 语言字符串及 strings 和 strconv 包
在 Go 语言编程中,字符串是最基本、最常用的数据类型之一。无论是处理用户输入、读取文件内容,还是生成输出,字符串操作无处不在。为了方便开发者对字符串进行各种操作,Go 语言提供了强大的 strings 包和 strconv 包。strings 包包…...
政府窗口服务第三方评估报告如何写
撰写政府窗口服务第三方评估报告需要结构清晰、内容详实,并包含对评估过程和结果的详细描述以及改进建议。以下是第三方评估机构民安智库(第三方社会评估调研公司)给出的一个政府窗口服务第三方评估报告简单的示例: 一、封面 报…...
若依前后端分离Spring Security新增手机号登录
备忘贴 转自:【若依RuoYi短信验证码登录】汇总_数据库_z_xiao_qiang-RuoYi 若依 配置Security: 按照Security的流程图可知,实现多种方式登录,只需要重写三个主要的组件,第一个用户认证处理过滤器,第二个用户认证tok…...
Oracle操作扩可变字符长度交易影响分析-较小
使用AI帮助学习知识 以下知识来至AI oracle 一张大表,对可变字符串长度从10扩到20位,oracle底层存储是否会发生变化,先锁表,更新表字典信息,然后会不会重新整理表,在有交易的情况下导致大量交易失效&#…...
全栈工程师需要具备哪些技能?
概论: 全栈工程师是一位能够从头到尾构建 Web 应用程序的工程师,能独立完成产品。技术包括前端部分、后端部分和应用程序所在的基础架构。他们在整个技术栈中工作,并了解其中的每个部分。从需求分析开始,到概要设计,详…...
用java实现客服聊天+网络爬虫下载音乐(java网络编程,io,多线程)
一 灵感: 在2022年的暑假,也就是我即将迈进高三的那个暑假,我并没有察觉自己应该要学习了,还是和过往的暑假一样玩着王者荣耀,凌晨2点睡觉,中午12点起床。我依稀记得这种状态一直持续到8月19。然而离开学还…...
MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例
一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...
阿里云ACP云计算备考笔记 (5)——弹性伸缩
目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...
Python:操作 Excel 折叠
💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 Python 操作 Excel 系列 读取单元格数据按行写入设置行高和列宽自动调整行高和列宽水平…...
在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module
1、为什么要修改 CONNECT 报文? 多租户隔离:自动为接入设备追加租户前缀,后端按 ClientID 拆分队列。零代码鉴权:将入站用户名替换为 OAuth Access-Token,后端 Broker 统一校验。灰度发布:根据 IP/地理位写…...
Java入门学习详细版(一)
大家好,Java 学习是一个系统学习的过程,核心原则就是“理论 实践 坚持”,并且需循序渐进,不可过于着急,本篇文章推出的这份详细入门学习资料将带大家从零基础开始,逐步掌握 Java 的核心概念和编程技能。 …...
学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2
每日一言 今天的每一份坚持,都是在为未来积攒底气。 案例:OLED显示一个A 这边观察到一个点,怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 : 如果代码里信号切换太快(比如 SDA 刚变,SCL 立刻变&#…...
Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信
文章目录 Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信前言一、网络通信基础概念二、服务端与客户端的完整流程图解三、每一步的详细讲解和代码示例1. 创建Socket(服务端和客户端都要)2. 绑定本地地址和端口&#x…...
在QWebEngineView上实现鼠标、触摸等事件捕获的解决方案
这个问题我看其他博主也写了,要么要会员、要么写的乱七八糟。这里我整理一下,把问题说清楚并且给出代码,拿去用就行,照着葫芦画瓢。 问题 在继承QWebEngineView后,重写mousePressEvent或event函数无法捕获鼠标按下事…...
Go 语言并发编程基础:无缓冲与有缓冲通道
在上一章节中,我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道,它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好࿰…...
比较数据迁移后MySQL数据库和OceanBase数据仓库中的表
设计一个MySQL数据库和OceanBase数据仓库的表数据比较的详细程序流程,两张表是相同的结构,都有整型主键id字段,需要每次从数据库分批取得2000条数据,用于比较,比较操作的同时可以再取2000条数据,等上一次比较完成之后,开始比较,直到比较完所有的数据。比较操作需要比较…...
