算法leetcode

【贪心难题】力扣1505-最多K次交换相邻数位后得到的最小整数

字数统计: 1.2k字   |   阅读时长: 5分
, ,

摘要: 贪心+树状数组

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

本文我们看一个贪心的问题，这是第 196 场周赛 D 题。亮点是在执行贪心策略时需要一些预处理信息，这些预处理信息是通过树状数组计算的。

$1 题目

给你一个字符串 num 和一个整数 k 。其中，num 表示一个很大的整数，字符串中的每个字符依次对应整数上的各个 数位 。

你可以交换这个整数相邻数位的数字 最多 k 次。

请你返回你能得到的最小整数，并以字符串形式返回。

提示：

1
2
3
1 <= num.length <= 30000
num 只包含 数字 且不含有 前导 0 。
1 <= k <= 10^9

示例 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”

$2 题解

算法: 贪心

串 num 在进行数位交换的时候，长度不变，因此数值最小等价于字典序最小。

从高位往低位考虑, 枚举 i: 0,1,...,n-1。

对 i，问：num[i] 能否变得尽可能小，枚举 t: 0,1,...,9，找到 [i..n-1] 中最小的 j，满足 num[j] = t，若没有满足的，最后 j = n，需要 j-i 步，如果 j-i <= k，则当前可以满足，执行交换。

重复以上操作直至 i 推进到 n 或者 k 耗尽。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    string minInteger(string num, int k) {
        int n = num.size();
        int i = 0;
        while(i < n && k > 0)
        {
            for(char t = '0'; t <= '9'; ++t)
            {
                // 问：[i..n-1] 中最小的 j 是多少，num[j] == t，若不存在，j == n
                int j = i;
                while(j < n && num[j] != t)
                    ++j;
                if(j < n && j - i <= k)
                {
                    k -= j - i;
                    for(int k = j; k > i; --k)
                        num[k] = num[k - 1];
                    num[i] = t;
                    break;
                }
            }
            ++i;
        }
        return num;
    }
};

优化：树状数组

预处理 idx[0..9], idxs[t] 为一个 list<int> 保存 t 在 nums 中的所有位置：

1
2
3
4
5
枚举 i: 0,1,...,n-1
    枚举 t: 0,1,...,9
        int j = pos[t].front() 即为距离 i 最近的 j，满足原串中 nuns[j] = t
        但 num[j] = t 的意思是该 t 在原串中的位置是 j，但是现在不一定了，因为可能有一些之前的交换，使得 j 向后移动了。
        因此该 t 在当前的真实位置为 j + 该位置的历史交换次数

该位置的历史交换次数也就是在原串中，[j+1,..,n-1] 这些位置上发生交换的次数之和。(需要画图理解)。

这个该位置的历史交换次数可以用 BIT 维护，单点修改，区间和查询。

因此得到 j 后，查询 [j+1,..n-1] 上一共发生了几次交换 bit.query(n-1) - bit.query(j)，j 到 i 的真实距离为 d = j - i + bit.query(n-1) - bit.query(j)。

若 d <= k，则更新：

1
2
3
4
BIT 更新 j: bit.add(j, 1)
k -= d
pos[t].erase(pos[t].begin())
result += t

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
class BIT
{
public:
    BIT(){}
    BIT(int n)
    {
        vec = vector<int>(n + 1);
    }

    void add(int idx, int delta)
    {
        // idx 位置加 delta，BIT 中在 vec[idx + 1] 做改动
        for(int i = idx + 1; i < (int)vec.size(); i += lowbit(i))
            vec[i] += delta;
    }

    int query(int idx)
    {
        if(idx <= 0)
            return 0;
        // [0..idx] 的和
        // 返回 bit 中 [1..idx+1] 的和
        int ans = 0;
        for(int i = idx + 1; i > 0; i -= lowbit(i))
            ans += vec[i];
        return ans;
    }

private:
    vector<int> vec;

    int lowbit(int x)
    {
        return x & (-x);
    }
};

class Solution {
public:
    string minInteger(string num, int k) {
        int n = num.size();
        BIT bit(n);
        string result;
        vector<list<int>> pos(10);
        for(int i = 0; i < n; ++i)
            pos[num[i] - '0'].push_back(i);
        for(int i = 0; i < n; ++i)
        {
            for(char t = '0'; t <= '9'; ++t)
            {
                // [i..n-1] 中最小的满足 num[j]==t 的 j 或不存在
                if(!pos[t - '0'].empty())
                {
                    int j = pos[t - '0'].front();
                    // [j..n-1] 中交换的次数
                    int d = j - i + bit.query(n - 1) - bit.query(j);
                    if(d <= k)
                    {
                        k -= d;
                        pos[t - '0'].erase(pos[t - '0'].begin());
                        bit.add(j, 1);
                        result += t;
                        break;
                    }
                }
            }
        }
        return result;
    }
};
Share