本文涉及知识点
分类讨论
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++**实现。