本文涉及知识点
排序 队列
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++**实现。