Leetcode 1505 最多 K 次交换相邻数位后得到的最小整数(贪心)

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);
    }
};

  • 4 只已被捕捉
    • lsx Chrome | 83.0.4103.116 Windows 10

      千神咋开始刷leetcode了?预防自己算法水平退步么OωO

      • 千千 Chrome | 83.0.4103.61 Windows 10

        QAQ 是的呢

    • 择偶网 搜狗浏览器 Windows 7

      这个不错耶,我喜欢!

      • 千千 Chrome | 83.0.4103.61 Windows 10

        欢迎常来哦~