【分类讨论】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

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