莎娜琳官方网站做水,装修公司加盟好还是自己开,百度广告推广怎么收费了,桂林北站到两江机场有多远本文涉及知识点
树状数组 队列
LeetCode1505. 最多 K 次交换相邻数位后得到的最小整数
给你一个字符串 num 和一个整数 k 。其中#xff0c;num 表示一个很大的整数#xff0c;字符串中的每个字符依次对应整数上的各个 数位 。 你可以交换这个整数相邻数位的数字 最多 k 次…本文涉及知识点
树状数组 队列
LeetCode1505. 最多 K 次交换相邻数位后得到的最小整数
给你一个字符串 num 和一个整数 k 。其中num 表示一个很大的整数字符串中的每个字符依次对应整数上的各个 数位 。 你可以交换这个整数相邻数位的数字 最多 k 次。 请你返回你能得到的最小整数并以字符串形式返回。 示例 1 输入num “4321”, k 4 输出“1342”
解释4321 通过 4 次交换相邻数位得到最小整数的步骤如上图所示。 示例 2 输入num “100”, k 1 输出“010” 解释输出可以包含前导 0 但输入保证不会有前导 0 。 示例 3 输入num “36789”, k 1000 输出“36789” 解释不需要做任何交换。 示例 4 输入num “22”, k 22 输出“22” 示例 5 输入num “9438957234785635408”, k 23 输出“0345989723478563548” 提示 1 num.length 30000 num 只包含 数字 且不含有 前导 0 。 1 k 109
树状数组
第一种操作让s[i1]变小第二种操作让s[i11…n-1]都变小。显然第一种操作比第二种操作更小。故i从小到大处理s[i]。 处理s[i]时依次枚举下标最小的s[i]等于ch ,ch ‘0’ to ‘9’ 如果能交换则交换并处理下一个i。 这样做的时间复杂度是O(nn)超时。 令某字符的原始下标为i1其它字符交换后若干次后i1的变化规律。如果起始位置都小于i1或都大于i1则对i1无影响。 由于从小到大处理i所以起始位置i一定小于i1。只需要统计大于i1的交换次数。如果原始下标大于i1的交换次数为cnt1则i1当前的左边为i1cnt1。 i1cnt1需要交换i1cnt1- i 次。下标大于i1的交换次数总交换次数(i) - 下标小于等于i1的交换次数。 如果算上自己交换自己交换一定能成功。 队列数组 indexs[i]升序记录 i‘0’ 交换成功的队列出队。 时间复杂度 O(nlogn)
代码
核心代码
templateclass ELE int
class CTreeArr
{
public:CTreeArr(int iSize) :m_vData(iSize 1){}void Add(int index, ELE value){index;while (index m_vData.size()){m_vData[index] value;index index (-index);}}ELE Sum(int index){index;ELE ret 0;while (index){ret m_vData[index];index - index (-index);}return ret;}ELE Get(int index){return Sum(index) - Sum(index - 1);}
private:vectorELE m_vData;
};class Solution {
public:string minInteger(string num, int k) {queueint indexs[10];for (int i 0; i num.length(); i) {indexs[num[i] - 0].emplace(i);}string ret;CTreeArrint ta(num.length());for (int i 0; i num.length(); i) {for (int j 0; j 10; j) {if (indexs[j].empty()) { continue; }const int inx indexs[j].front();const int cnt1 i - ta.Sum(inx);const int need inx cnt1 - i;if (need k) {k - need;ta.Add(inx, 1);ret (0 j);indexs[j].pop();break;}}}return ret;}
};单元测试
templateclass T1,class T2
void AssertEx(const T1 t1, const T2 t2)
{Assert::AreEqual(t1 , t2);
}templateclass T
void AssertEx(const vectorT v1, const vectorT v2)
{Assert::AreEqual(v1.size(), v2.size()); for (int i 0; i v1.size(); i){Assert::AreEqual(v1[i], v2[i]);}
}templateclass T
void AssertV2(vectorvectorT vv1, vectorvectorT 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 num;int k;TEST_CLASS(UnitTest){public:TEST_METHOD(TestMethod0){num 4321, k 4;auto res Solution().minInteger(num, k);AssertEx(string(1342), res);}TEST_METHOD(TestMethod2){num 100, k 1;auto res Solution().minInteger(num, k);AssertEx(string(010), res);}TEST_METHOD(TestMethod3){num 36789, k 1000;auto res Solution().minInteger(num, k);AssertEx(string(36789), res);}TEST_METHOD(TestMethod4){num 22, k 22;auto res Solution().minInteger(num, k);AssertEx(string(22), res);}TEST_METHOD(TestMethod5){num 294984148179, k 11;auto res Solution().minInteger(num, k);AssertEx(string(124498948179), res);}};
}扩展阅读
视频课程
先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。 https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了为老板分忧请学习C#入职培训、C入职培训等课程 https://edu.csdn.net/lecturer/6176
相关推荐
我想对大家说的话《喜缺全书算法册》以原理、正确性证明、总结为主。按类别查阅鄙人的算法文章请点击《算法与数据汇总》。有效学习明确的目标 及时的反馈 拉伸区难度合适 专注闻缺陷则喜(喜缺)是一个美好的愿望早发现问题早修改问题给老板节约钱。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙那算法就是他的是睛
测试环境
操作系统win7 开发环境 VS2019 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用**C**实现。
