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;}
};

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

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

相关文章

【LeetCode算法】第111题:二叉树的最小深度

目录 一、题目描述 二、初次解答 三、官方解法 四、总结 一、题目描述 二、初次解答 1. 思路&#xff1a;二叉树的先序遍历。求出左子树的最小高度&#xff0c;求出右子树的最小高度&#xff0c;最终返回左子树和右子树的最小高度1。关键&#xff1a;若左子树的高度为0&…

springboot发送短信验证码,结合redis 实现限制,验证码有效期2分钟,有效期内禁止再次发送,一天内发送超3次限制

springboot结合redis发送短信验证码,实现限制发送操作 前言(可忽略)实现思路正题效果图示例手机号不符合规则校验图成功发送验证码示例图redis中缓存随机数字验证码&#xff0c;2分钟后失效删除redis缓存图验证码有效期内 返回禁止重复发送图验证码24小时内发送达到3次&#xf…

[深度学习]使用python部署yolov10的onnx模型

测试环境&#xff1a; onnxruntime1.15.1 opencv-python4.8.0.76 部分实现代码&#xff1a; parser argparse.ArgumentParser()parser.add_argument("--model", typestr, default"yolov10n.onnx", help"Input your ONNX model.")parser.add_arg…

ChatGPT AI专题资料合集【65GB】

介绍 ChatGPT & AI专题资料合集【65GB】 &#x1f381;【七七云享】资源仓库&#xff0c;海量资源&#xff0c;无偿分享√

网络监听技术

网络监听技术 网络监听概述网络监听环境 流量劫持网络环境共享式网络监听原理交换式网络监听交换机的工作方式交换网络监听&#xff1a;交换机集线器交换网络监听&#xff1a;端口镜像交换网络监听&#xff1a;MAC洪泛交换网络监听&#xff1a;MAC洪泛交换网络监听&#xff1a;…

7-15 位模式(dump_bits)---PTA实验C++

一、题目描述 为方便调试位运算相关程序&#xff0c;先做个展现位模式的小工具。 建议参照以下接口实现&#xff1a; // 利用函数重载特性&#xff1a;string dump_bits(char x);string dump_bits(short x);string dump_bits(int x);string dump_bits(long long x);// 或用函…

Windows10系统中安装与配置PyTorch(无GPU版本)

文章目录 1. 什么是PyTorch2. PyTorch的安装与配置&#xff08;无GPU&#xff09;2.1 创建环境2.2 安装pytorch库&#xff08;无GPU&#xff09;2.3 验证安装结果 1. 什么是PyTorch PyTorch 是一种用于构建深度学习模型且功能完备的开源框架&#xff0c;通常用于处理图像识别和…

安装zookeeper

一、搭建前准备 192.168.1.99 sdw1 192.168.1.98 sdw2 192.168.1.97 sdw3 二、搭建 1、各主机修改/etc/hosts&#xff0c;/etc/hostname文件 /etc/hosts 127.0.0.1 localhost localhost.localdomain localhost4 localhost4.localdomain4 ::1 localhos…

【人工智能】第二部分:ChatGPT的架构设计和训练过程

人不走空 &#x1f308;个人主页&#xff1a;人不走空 &#x1f496;系列专栏&#xff1a;算法专题 ⏰诗词歌赋&#xff1a;斯是陋室&#xff0c;惟吾德馨 目录 &#x1f308;个人主页&#xff1a;人不走空 &#x1f496;系列专栏&#xff1a;算法专题 ⏰诗词歌…

考研数学考到110+分,到底有多难?

很难&#xff01; 大家平时在网上上看到很多人说自己考了130&#xff0c;其实这些人只占参加考研数学人数的极少部分&#xff0c;有个数据可以展示出来考研数学到底有多难&#xff1a; 在几百万考研大军中&#xff0c;能考到120分以上的考生只有2%。绝大多数人的分数集中在30…

通过非欧几何体改变 AI 嵌入

目录 一、说明 二、LLM嵌入的形势 三、了解一些背景信息 3.1 什么是嵌入&#xff1f; 3.2 为什么嵌入在 NLP 中很重要&#xff1f; 3.3 复数Complex 几何的角色 3.4 C主动学习 3.5 角度嵌入 &#xff08;AE&#xff09;&#xff1a;解锁稳健排序 3.6 RotatE&#xff1a;将关系…

浏览器运行原理:网页被解析过程、script元素和页面解析的关系、defer和async使用;V8引擎执行原理(执行js)

一、浏览器渲染页面的流程 1.如何找到服务器 2.找到服务器如何下载对应的静态资源 输入完服务器地址&#xff0c;下载下来的一般是html文件&#xff0c;在解析html文件过程中&#xff0c;遇到link引用了css文件&#xff0c;就下载对应的css文件&#xff0c;js文件同理 3.一个…

IDEA 学习之 命令行太长问题

现象 Error running App Command line is too long. In order to reduce its length classpath file can be used. Would you like to enable classpath file mode for all run configurations of your project?解决办法 办法一 .idea\workspace.xml ——> <compone…

关于IDEA创建Maven一直爆红无法下载的问题

你能看到这我就知道你肯定已经试过了网上的很多方法了&#xff0c;我之前也是&#xff0c;试过了很多一直无法正常下载&#xff0c;我也是找人给 线下看了看解决了&#xff0c;我总结一下从头到尾排除问题&#xff0c;试到最后要是还解决不了你直接私信我&#xff0c;我给你看看…

【并发程序设计】15.信号灯(信号量)

15.信号灯(信号量) Linux中的信号灯即信号量是一种用于进程间同步或互斥的机制&#xff0c;它主要用于控制对共享资源的访问。 在Linux系统中&#xff0c;信号灯作为一种进程间通信&#xff08;IPC&#xff09;的方式&#xff0c;与其他如管道、FIFO或共享内存等IPC方式不同&…

Python保存为json中文Unicode乱码解决json.dump()

保存为json中文Unicode乱码&#xff1a; 可以看到&#xff0c;中文字符没有乱码&#xff0c;只是出现了反斜杠&#xff0c;此时解决方法应考虑是否进行了二次序列化。 一、原因1 在dump时加入ensure_asciiFalse 即可解决&#xff0c;即json.dump(json_data, f, indent4, en…

【Spring-01】BeanFactory和ApplicationContext

【Spring-01】BeanFactory和ApplicationContext 1. 容器接口1.1 什么是 BeanFactory1.2 BeanFactory 能做什么&#xff1f; 1. 容器接口 以 SpringBoot 的启动类为例&#xff1a; /*** BeanFactory 与 ApplicationContext的区别*/ SpringBootApplication public class Spring…

【自动驾驶】针对低速无人车的线控底盘技术

目录 术语定义 一般要求 操纵装置 防护等级 识别代号 技术要求 通过性要求 直线行驶稳定性 环境适应性要求 功能安全要求 信息安全要求 故障处理要求 通信接口 在线升级(OTA) 线控驱动 动力性能 驱动控制响应能力 线控制动 行车制动 制动响应能力 线控转向 总体要求 线控…

STM32作业实现(五)温湿度传感器dht11

目录 STM32作业设计 STM32作业实现(一)串口通信 STM32作业实现(二)串口控制led STM32作业实现(三)串口控制有源蜂鸣器 STM32作业实现(四)光敏传感器 STM32作业实现(五)温湿度传感器dht11 STM32作业实现(六)闪存保存数据 STM32作业实现(七)OLED显示数据 STM32作业实现(八)触摸按…

UML静态图-类图

概述 静态图包含类图、对象图和包图的主要目的是在系统详细设计阶段&#xff0c;帮助系统设计人员以一种可视化的方式来理解系统的内部结构和代码结构&#xff0c;包括类的细节、类的属性和操作、类的依赖关系和调用关系、类的包和包的依赖关系。 一、类图的表示法 类图(Cla…