Description
给你一个字符串
num
和一个整数k
。其中,num
表示一个很大的整数,字符串中的每个字符依次对应整数上的各个数位。你可以交换这个整数相邻数位的数字最多
k
次。请你返回你能得到的最小整数,并以字符串形式返回。
提示:
1 <= num.length <= 30000
num
只包含数字且不含有前导 0。1 <= k <= 10^9
示例:num = “4321”, k = 4
4321 -> 3421 -> 3412 -> 3142 -> 1342
Example Input
num = "9438957234785635408", k = 23
Example Output
0345989723478563548
思路
本质上是一个贪心题,每次只需要在当前位置以后的 k
个可观测位置中找一个最小值,若比当前位置小则提前,提前以后 k
相应的减少移动的步数;否则当前位置后移。
因为题目数据量比较大,直接 $O(n^2)$ 不可取,那么考虑用树状数组 / 线段树来维护观测区间,这样可以将时间复杂度降到 $O(n\log n)$。
在我的思路中,设定了 st
代表可观测的列表,其中每个元素是一个 pair <值,index>,且借用 STL 中的 set 来维护,这样可以很方便的得到观测区间的最小值。
设定 ids
代表 st
中所有的元素的 index,同样的它也是一个 set,仅仅借用一个自动排序的功能,这样可以很方便找到观测区间的最后一个元素以及第一个元素位置。进而使用树状数组可以得到 ids
中每个元素之前存在多少个元素,这有利于计算转移需要的步数。
设定 vis
代表已输出的元素的 index,防止被重复使用。
此外,观测列表会随着程序进行逐渐变化,当列表元素数目大于 k
时则自动从最后删除多余的;若小于 k
则尽可能的补齐。
具体的实现可以阅读代码,大部分都有注释。
AC 代码
int bit[31000];
int lowbit(int k) { return k & -k; }
void add(int k, int num, int n) {
k += 1;
while (k <= n + 1) {
bit[k] += num;
k += lowbit(k);
}
}
int query(int k) {
int res = 0;
k += 1;
while (k > 0) {
res += bit[k];
k -= lowbit(k);
}
return res;
}
class Solution {
public:
string minInteger(string num, int k) {
char ans[31000] = {0}; // 存储最终的答案
int top = 0;
memset(bit, 0, sizeof(bit)); // 初始化树状数组
int len = num.length(), last = -1; // last 代表待加入的第一个元素
set<pair<int, int>>
st; // 当前位置为 now,往后 k 个的观测列表,<值,index>
set<int> ids,
vis; // ids 为 st 所有观测列表的 index,vis 是已输出的元素的 index
for (int i = 1; i < len && i <= k;
i++) { // 考虑 now 为第 0 个元素,构造初始观测列表
st.insert(make_pair(num[i], i));
ids.insert(i);
add(i, 1, len); // 在树状数组的第 i 个位置
// +1,树状数组主要用来查询当前某个 index
// 转移到最前面需要多少步
last = i + 1;
}
pair<int, int> now = make_pair(num[0], 0); // now 代表当前位置
for (int i = 0; i < len; i++) {
auto minn = *st.begin(); // 观测列表中的最小值
if (!st.empty() &&
minn.first < now.first) { // 如果观测列表最小值小于当前值
k -= query(minn.second); // 执行转移,k 减小转移的花费
ids.erase(minn.second); // 从观测列表删除此最小值
add(minn.second, -1, len);
st.erase(minn);
ans[top++] = minn.first; // 输出
vis.insert(minn.second); // 记录已输出的值的 index
} else { // 如果当前值小于等于观测列表所有值
ans[top++] = now.first; // 输出
vis.insert(now.second); // 记录已输出的值的 index
now = make_pair(num[*ids.begin()],
*ids.begin()); // 当前位置后移,即选取观测列表
// index 最靠前的
if (ids.empty()) // 如果观测列表为空,说明 k 已经没有了
break;
add(*ids.begin(), -1, len); // 删除观测列表中原先记录的 now
ids.erase(*ids.begin());
st.erase(now);
}
int idssize = ids.size();
for (int j = 0; j < idssize - k;
j++) { // 如果观测列表长度大于 k,则从最后面一一删除
add(*ids.rbegin(), -1, len);
last = *ids.rbegin();
st.erase(make_pair(num[*ids.rbegin()], *ids.rbegin()));
ids.erase(--ids.end());
}
while (k > (int)ids.size() &&
last <
len) { // 如果观测列表长度小于 k,则从 last 位置一一增加
if (vis.count(last)) { // 当前 last 已被转移到前面并输出
last++;
continue;
}
ids.insert(last);
add(last, 1, len);
st.insert(make_pair(num[last], last));
last++;
}
}
for (int j = last; j < len; j++) { // 输出未转移的数
if (!vis.count(j)) {
ans[top++] = num[j];
}
}
ans[top] = '\0';
return string(ans);
}
};
千神咋开始刷leetcode了?预防自己算法水平退步么OωO
QAQ 是的呢
这个不错耶,我喜欢!
欢迎常来哦~