【排序 队列】1585. 检查字符串是否可以通过排序子字符串得到另一个字符串

本文涉及知识点

排序 队列

LeetCode1585. 检查字符串是否可以通过排序子字符串得到另一个字符串

给你两个字符串 s 和 t ,请你通过若干次以下操作将字符串 s 转化成字符串 t :
选择 s 中一个 非空 子字符串并将它包含的字符就地 升序 排序。
比方说,对下划线所示的子字符串进行操作可以由 “14234” 得到 “12344” 。
如果可以将字符串 s 变成 t ,返回 true 。否则,返回 false 。
一个 子字符串 定义为一个字符串中连续的若干字符。
示例 1:
输入:s = “84532”, t = “34852”
输出:true
解释:你可以按以下操作将 s 转变为 t :
“84532” (从下标 2 到下标 3)-> “84352”
“84352” (从下标 0 到下标 2) -> “34852”
示例 2:

输入:s = “34521”, t = “23415”
输出:true
解释:你可以按以下操作将 s 转变为 t :
“34521” -> “23451”
“23451” -> “23415”
示例 3:

输入:s = “12345”, t = “12435”
输出:false
示例 4:

输入:s = “1”, t = “2”
输出:false

提示:
s.length == t.length
1 <= s.length <= 105
s 和 t 都只包含数字字符,即 ‘0’ 到 ‘9’ 。

冒泡排序

indexs[i] 是队列,升序记录i+'0’的所有下标。
根据冒泡排序的原理,选择m个字符排序能完成的效果,若干次选择2个元素排序也能完成。
从小到大枚举i,如果s[i] < t[i] 返回false
寻找 j > i ,且s[j]等于s[i] ,最小j
如果找不到j,返回false
s[i+1,j-1] 如果有字符小于s[j],则返回false。
indexs[t[i]-‘0’]] 出队。
** 注意**:除了顶替当前字符的字符,其它字符的相对位置不变。由于只需要相对顺序,所以除替换当前字符的字符出队外,其它字符都不需要变化。
时间复杂度: O(n)

代码

核心代码

class Solution {
public:
	bool isTransformable(string s, string t) {
		queue<int> indexs[10];
		for (int i = 0; i < s.length(); i++) {
			indexs[s[i] - '0'].emplace(i);
		}
		for (int i = 0; i < s.length(); i++) {
			auto& que = indexs[t[i] - '0'];
			if (que.empty()) { return false; }
			for (int j = 0; j < t[i] - '0'; j++) {
				if (indexs[j].size() && (indexs[j].front() < que.front())) { return false; }
			}
			que.pop();
		}
		return true;
	}
};

单元测试

template<class T1,class T2>
void AssertEx(const T1& t1, const T2& t2)
{
	Assert::AreEqual(t1 , t2);
}

template<class T>
void AssertEx(const vector<T>& v1, const vector<T>& v2)
{
	Assert::AreEqual(v1.size(), v2.size());	
	for (int i = 0; i < v1.size(); i++)
	{
		Assert::AreEqual(v1[i], v2[i]);
	}
}

template<class T>
void AssertV2(vector<vector<T>> vv1, vector<vector<T>> vv2)
{
	sort(vv1.begin(), vv1.end());
	sort(vv2.begin(), vv2.end());
	Assert::AreEqual(vv1.size(), vv2.size());
	for (int i = 0; i < vv1.size(); i++)
	{
		AssertEx(vv1[i], vv2[i]);
	}
}

namespace UnitTest
{
	string s,  t;
	TEST_CLASS(UnitTest)
	{
	public:
		TEST_METHOD(TestMethod0)
		{
			s = "84532", t = "34852";
			auto res = Solution().isTransformable(s, t);
			AssertEx(true, res);
		}
		TEST_METHOD(TestMethod1)
		{
			s = "34521", t = "23415";
			auto res = Solution().isTransformable(s, t);
			AssertEx(true, res);
		}
		TEST_METHOD(TestMethod2)
		{
			s = "12345", t = "12435";
			auto res = Solution().isTransformable(s, t);
			AssertEx(false, res);
		}
		TEST_METHOD(TestMethod3)
		{
			s = "1", t = "2";
			auto res = Solution().isTransformable(s, t);
			AssertEx(false, res);
		}
	};
}

扩展阅读

视频课程

先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关推荐

我想对大家说的话
《喜缺全书算法册》以原理、正确性证明、总结为主。
按类别查阅鄙人的算法文章,请点击《算法与数据汇总》。
有效学习:明确的目标 及时的反馈 拉伸区(难度合适) 专注
闻缺陷则喜(喜缺)是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙,那算法就是他的是睛

测试环境

操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Discourse 的 AI 内容分享

虽然 Discourse 的 AI 接口调用是需要比较高的用户权限或者管理员权限。 但是对已经生成的结果&#xff0c;Discourse 是可以保存并且分享的。 例如&#xff0c;我们搜索了一些美食的做法。 在页面的下面有一个分享 AI 对话的按钮。 在随后弹出的界面中&#xff0c;会又一个…

服务运营 | MS文章精选:线上点单,当真免排队?餐饮零售与医疗场景中的全渠道运营

编者按&#xff1a; 小A走进了一家奶茶店&#xff0c;准备向店员点单&#xff0c;但却在屏幕上看到还有98杯奶茶待制作&#xff08;因为线上订单突然暴增&#xff09;。因此&#xff0c;小A不满地嘟囔着离开了奶茶店。这个例子展示了线上渠道可能会对线下渠道造成一些负面影响…

链表数组遍历输出的辨析(二者都含指针的情况下)----PTA期末复习题

输入输出三位学生的学号和信息 一开始我认为是指针&#xff0c;直接背了指针输出的方式&#xff1b;p;p!NULL;pp->next 这个是错误的 下面这个输出是正确的方式 分析怎么区分这两个 举个例子来 数组遍历&#xff1a; 链表遍历&#xff1a; 输出的结果&#xff1a; 如果将…

第十次作业

1.登陆界面 2.导航页面 3.接口&#xff08;我负责的主要是管理员管理用户和密码的界面&#xff09; import request from /utils/request// 登录 export function login(data) {return request({url: /user/login,method: post,data}) }// 获取用户信息 export function getIn…

网关登录校验

如何在网关转发之前做登录校验&#xff1f; 网关请求处理流程 如何在网关转发之前做登录校验&#xff1f; 网关如何将用户信息传递给微服务&#xff1f; 如何在微服务之间传递用户信息&#xff1f; 自定义过滤器 网关过滤器有两种&#xff0c;分别是&#xff1a; GatewayFi…

春秋云境:CVE-2022-25411[漏洞复现]

根据题目提示和CNNVD优先寻找后台管理地址 靶机启动后&#xff0c;使用AWVS进行扫描查看网站结构 在这里可以看到后台管理的登录地址&#xff1a;/admin/&#xff0c;根据题目提示可知是弱口令 尝试admin、123456、admin666、admin123、admin888...等等常见弱口令 正确的账户…

论文导读 | Manufacturing Service Operations Management近期文章精选

编者按 在本系列文章中&#xff0c;我们梳理了顶刊Manufacturing & Service Operations Management5月份发布有关OR/OM以及相关应用的文章之基本信息&#xff0c;旨在帮助读者快速洞察行业/学界最新动态。 推荐文章1 ● 题目&#xff1a;Robust Drone Delivery with Weath…

KVM网络模式设置

一、KVM网络模式介绍 1、NAT ( 默认上网 ) 虚拟机利用host机器的ip进行上网,对外显示一个ip;virbr0是KVM 默认创建的一个 Bridge,其作用是为连接其上的虚机网卡提供NAT访问外网的功能,默认ip为192.168.122.1 2、自带的Bridge 将虚拟机桥接到host机器的网卡上,vm和ho…

【C++题解】1712. 输出满足条件的整数2

问题&#xff1a;1712. 输出满足条件的整数2 类型&#xff1a;简单循环 题目描述&#xff1a; 有这样的三位数&#xff0c;其百位、十位、个位的数字之和为偶数&#xff0c;且百位大于十位&#xff0c;十位大于个位&#xff0c;请输出满所有满足条件的整数。 输入&#xff1…

C++ | Leetcode C++题解之第191题位1的个数

题目&#xff1a; 题解&#xff1a; class Solution { public:int hammingWeight(uint32_t n) {int ret 0;while (n) {n & n - 1;ret;}return ret;} };

SpringBoot控制反转和依赖注入

目录 一、内聚和耦合 二、分层解耦 三、具体实现 四、bean的组件扫描 五、bean注入 一、内聚和耦合 在了解分层解耦的概念之前我们我们要去先了解一下内聚和耦合。内聚&#xff1a;通常将的是软件中各个模块之间的功能联系。耦合衡量软件各个模块之间的依赖、关联的程度。一…

【ai】tx2 nx : fix pip升级警告

jetson 环境同样出现:【原创】pip3 使用报警问题在对 Ubuntu 18.04 上的 pip3 9.0.1 版本使用 pip install -U pip 的方式进行升级后,再使用 pip 就会出现一堆警告信息。这个警告信息目前不影响使用,但从警告信息来看,会在未来版本中出现失败风险。 当前系统中存在了两个不…

Android反编译之Apktool

文章目录 简述工具操作步骤 简述 可以从apk安装包中提取出res、AndroidManifest、xml等文件&#xff1b;也可以修改资源文件后rebuild一个apk。 工具 1.官方下载地址 https://apktool.org/ 2.操作指令 // 解析apk包 $ apktool d test.apk // 重新rebuid apk包 $ apktool …

vscode_cmake_stm32_lvgl移植及显示优化

1 LVGL移植 本文使用的环境如下&#xff1a; STM32H743FreeRTOSst7789 lcd(320*240) 下载 LVGL源码&#xff0c;本文使用Release v9.1.0&#xff1b; 将压缩包解压到工程目录&#xff0c;例如stm32h7xx_cmake_project/components/lvgl-9.1.0&#xff0c;如下所示&#xff1a; …

vue3封装表格嵌套表单问题汇总

1.插槽嵌套多层数据ui组件怎么使用 思路&#xff1a;插槽具名【区分】后暴露传递&#xff0c;这个为神魔要区分&#xff0c;因为封装组件表格列表项也有插槽 步骤一&#xff1a;表单插槽暴露 <ElFormclass"form-search":model"formParams"ref"form…

Linux 磁盘挂载与分区

Linux 磁盘挂载与分区 vda1: 其中vd表示虚拟磁盘&#xff0c;a表示第一块磁盘&#xff0c;b表示第二块磁盘&#xff0c;1表示第一块磁盘的第一分区&#xff08;显然两块磁盘都只有一个分区&#xff09;图中可以看到&#xff0c;vda1磁盘只有一个分区&#xff0c;且全部挂载到根…

期末复习题中的问题

一、编程中&#xff08;包括函数&#xff09;的问题 1. malloc 头文件是stdlib.h 二、第二次写复习题的不会的 三、程序填空 总结&#xff1a; 删除节点m >>>>要有一个指针来遍历找到这个m >>>> 用另一个指针指向这个指针的下一 个 >>&…

【数据结构与算法】堆排序算法 详解

堆排序算法 Status heapAdjust(ElemType *a, int s, int m) {ElemType t a[s];for (int j s * 2 1; j < m; j j * 2 1) {if (j < m && a[j] < a[j 1]) {j;}if (t > a[j]) {break;}a[s] a[j];s j;}a[s] t;return OK; }Status heapSort(ElemType *a…

[C#][opencvsharp]C#使用opencvsharp进行年龄和性别预测支持视频图片检测

使用 OpenCVSharp 来调用 age_net.caffemodel 和 gender_net.caffemodel 来进行性别和年龄预测涉及几个步骤。以下是一个简化的流程和示例文案&#xff1a; 1. 准备工作 确保你已经安装了 OpenCVSharp 和相关的依赖项。确保你有 age_net.prototxt、age_net.caffemodel、gende…

【redis】redis概述

1、定义 Redis&#xff08;Remote Dictionary Server&#xff09;&#xff0c;即远程字典服务&#xff0c;是一个开源的、内存中的数据结构存储系统。redis是一个key-value存储系统。和Memcached类似&#xff0c;它支持存储的value类型相对更多&#xff0c;包括string(字符串)…