【分类讨论】899. 有序队列

本文涉及知识点

分类讨论

LeetCode899. 有序队列

给定一个字符串 s 和一个整数 k 。你可以从 s 的前 k 个字母中选择一个,并把它加到字符串的末尾。
返回 在应用上述步骤的任意数量的移动后,字典序最小的字符串 。
示例 1:
输入:s = “cba”, k = 1
输出:“acb”
解释:
在第一步中,我们将第一个字符(“c”)移动到最后,获得字符串 “bac”。
在第二步中,我们将第一个字符(“b”)移动到最后,获得最终结果 “acb”。
示例 2:
输入:s = “baaca”, k = 3
输出:“aaabc”
解释:
在第一步中,我们将第一个字符(“b”)移动到最后,获得字符串 “aacab”。
在第二步中,我们将第三个字符(“c”)移动到最后,获得最终结果 “aaabc”。
提示:
1 <= k <= S.length <= 1000
s 只由小写字母组成。

分类讨论

一,如果k为1,则只能循环n种可能。移动i次后,i ∈ \in [1,n-1]后,新串为:s.substr(i)+s.substr(0,i)。 移动i次和i+n次完全一样。
二,但k >1时,一定能旋转到最小序。s[0]存储未处理的最小字符,旋转到位置,则插入。对s 排序就可以了。

代码

核心代码

class Solution {
public:string orderlyQueue(string s, int k) {if (k > 1) {sort(s.begin(), s.end());return s;}string ret = s;for (int i = 1; i < s.length(); i++) {auto tmp = s.substr(i) + s.substr(0, i);ret = min(ret, tmp);}return ret;}
};

单元测试

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;int k;TEST_CLASS(UnitTest){public:TEST_METHOD(TestMethod1){s = "cba", k = 1;auto res = Solution().orderlyQueue(s, k);AssertEx(string("acb"), res);}TEST_METHOD(TestMethod2){s = "baaca", k = 3;auto res = Solution().orderlyQueue(s,k);AssertEx(string("aaabc"), 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++**实现。

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

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

相关文章

数据库设计文档编写

方法1&#xff1a;使用 Navicat 生成数据库设计文档 效果 先看简单的效果图&#xff0c;如果效果合适&#xff0c;大家在进行测试使用&#xff0c;不合适直接撤退&#xff0c;也不浪费时间。 随后在docx文档中生成目标字段的表格&#xff0c;选中全部(ctrla)进行复制(ctrlc)…

《Cloud Native Data Center Networking》(云原生数据中心网络设计)读书笔记 -- 02 Clos拓扑

本章回答以下问题&#xff1a; 什么是 Clos 拓扑&#xff0c;它与“接入 - 汇聚 - 核心”拓扑有何不同?Clos 拓扑的特征是什么?Clos 拓扑对数据中心网络的影响是什么? Clos拓扑 云原生数据中心基础设施的先行者们想要构建一种支持大规模水平扩展网络。 基本的Clos拓扑如图…

AI日报|我国人工智能核心产业规模已达5784亿元!阿里通义Qwen2成斯坦福大模型榜单最强开源模型!

⭐️搜索“可信AI进展“关注公众号&#xff0c;动手做AI Agent书籍&#xff0c;限量免费赠送&#xff01;快来参与吧&#xff5e; 文章链接&#xff1a; 福利来啦&#xff01;动手做AI Agent书籍&#xff0c;限量免费赠送&#xff01; 今日热点&#xff1a; 我国人工智能企业…

【2024亲测无坑】在Centos.7虚拟机上安装Oracle 19C

目录 一、安装环境准备 1、linux虚拟机安装 2、虚拟机快照 3、空间检查&软件上传 二、Oracle软件安装 1.preinstall安装及其他配置准备 2.oracle安装 三、数据库实例的安装 1.netca——网络配置助手 2.dbca——数据库配置助手 四、ORACLE 19C 在linux centos 7上…

Windows环境部署MySQL_8.4.0 LTS的部署安装、验证连接以及卸载全过程实操手册

前言&#xff1a; 什么是 MySQL MySQL 是一个关系型数据库管理系统&#xff0c;由瑞典 MySQL AB 公司开发&#xff0c;目前属于Oracle 公司。MySQL 是一种关系型数据库管理系统&#xff0c;关系型数据库将数据保存在不同的表中&#xff0c;而不是将所有数据放在一个大仓库内&am…

【html】如何利用hbuilderX 开发一个自己的app并安装在手机上运行

引言&#xff1a; 相信大家都非常想开发一款自己的apk&#xff0c;手机应用程序&#xff0c;今天就教大家&#xff0c;如何用hbuilderX 开发一个自己的app并安装在手机上运行。 步骤讲解&#xff1a; 打开hbuilderX &#xff0c;选择新建项目 2.选择5app,想一个名字&#x…

双写一致性

双写一致性 当修改了数据库的数据也要同时更新缓存的数据&#xff0c;缓存和数据库的数据要保持一致。 注意这里是对数据库进行写操作而不是读操作&#xff0c;通常我们有两种方式完成这个写操作&#xff0c;分别是&#xff1a;先删除缓存再修改数据库 和 先修改数据库再删除…

SAP FICO 下载文件报错【调用数据提供商错误】

报错如下图所示&#xff1a; 解决办法&#xff1a; 当弹出保存文件的提示时&#xff0c;不要点击“记住我的决定”

qemu 安装ubuntu22.04虚拟机 -纯命令行-可ssh-带网络-编译安装 linux kernel-编译安装 kernel module

1&#xff0c;预备系统盘数据 1.1 下载光盘 注意需要 liver-server $ wget https://releases.ubuntu.com/22.04.4/ubuntu-22.04.4-live-server-amd64.iso 1.2 挂载并拷贝 $ sudo mkdir /mnt/iso_ubuntu-22.04.4-live-server-amd64 $ sudo mount ubuntu-22.04.4-live-ser…

蔚来汽车AI算法工程师,如何理解注意力?

大家好啊&#xff0c;我是董董灿。 今天分享一个上海蔚来汽车的AI算法岗位面试经验总结帖&#xff0c;面试岗位为算法工程师。 这次面试提到的问题&#xff0c;除了与实习相关内容和反问之外&#xff0c;面试官总共问了8个问题&#xff0c;主要集中在深度学习基础概念的理解上…

不见五陵高管墓,无花无酒锄做田

不见五陵高管墓&#xff0c;无花无酒锄做田 Golang 通用代码生成器仙童 2.4.0 电音仙女尝鲜版七已发布&#xff0c;此版本测试修复了 PostgreSQL 数据库自动反射功能。此版本更新修复了前端代码生成器&#xff0c;并修复了前端多对多界面的缺陷。PostgreSQL 的数据库反射功能刚…

ubuntu访问windows共享文件夹

方法: Ubuntu访问Windows共享文件夹的方法-CSDN博客 基于交换机的PC端网络通信_服务器交换机pc端-CSDN博客 补充说明&#xff1a; 在这里面输入&#xff1a; smb://192.168.0.30/WindowsShareToLinux

【Effective Web】常见的css布局方式--三栏布局

常见的css居中方式–三栏布局 第一种实现&#xff1a;table布局&#xff08;不推荐&#xff09; 缺点&#xff1a;在table加载前&#xff0c;整个table都是空白的&#xff0c;且修改布局排版都十分困难 <table class"container"><td class"left"…

Linux 软链接

# 语法 ln -s <文件夹or文件的真实路径> <自定义路径别名> # 例子 ln -s /etc/sysconfig/network-scripts/ifcfg-ens33 ~/ens33

Flutter 实现软鼠标

文章目录 前言一、如何实现&#xff1f;1、记录鼠标偏移2、MouseRegion获取偏移3、Transform移动图标 二、完整代码三、使用示例总结 前言 flutter在嵌入式系统中运行时&#xff0c;有可能遇到drm鼠标无法使用的情况&#xff0c;但鼠标事件却可以正常接收&#xff0c;此时如果…

基于SSM+Jsp的水果销售管理网站

开发语言&#xff1a;Java框架&#xff1a;ssm技术&#xff1a;JSPJDK版本&#xff1a;JDK1.8服务器&#xff1a;tomcat7数据库&#xff1a;mysql 5.7&#xff08;一定要5.7版本&#xff09;数据库工具&#xff1a;Navicat11开发软件&#xff1a;eclipse/myeclipse/ideaMaven包…

关于椭圆的方程(有Python画的动图)

关于椭圆的方程&#xff08;有Python画的动图&#xff09; flyfish 几何定义 椭圆是平面上所有到两个固定点&#xff08;焦点&#xff09;的距离之和为常数的点的集合。这两个固定点叫做焦点。 解析几何描述 设椭圆的两个焦点为 F 1 F_1 F1​ 和 F 2 F_2 F2​&#xff…

【论文笔记】The Power of Scale for Parameter-Effificient Prompt Tuning

题目: The Power of Scale for Parameter-Effificient Prompt Tuning 来源: EMNLP 2021 模型名称: Soft-Prompt 论文链接: https://aclanthology.org/2021.emnlp-main.243/ 项目链接: https://github.com/google-research/prompt-tuning 核心&#xff1a;针对不同的任务设计不同…

【笔记】打卡01 | 初学入门

初学入门:01-02 01 基本介绍02 快速入门库处理数据集网络构建模型训练保存模型加载模型打卡-时间 01 基本介绍 MindSpore Data&#xff08;数据处理层&#xff09; ModelZoo&#xff08;模型库&#xff09; MindSpore Science&#xff08;科学计算&#xff09;&#xff0c;包含…

视频融合共享平台LntonCVS视频监控安防系统运用多视频协议建设智慧园区方案

智慧园区&#xff0c;作为现代化城市发展的重要组成部分&#xff0c;不仅推动了产业的升级转型&#xff0c;也成为了智慧城市建设的核心力量。随着产业园区之间的竞争日益激烈&#xff0c;如何打造一个功能完善、智能化程度高的智慧园区&#xff0c;已经成为了业界广泛关注的焦…