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

  |  

摘要: 贪心+树状数组

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的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