抱歉,您的浏览器无法访问本站

本页面需要浏览器支持(启用)JavaScript


了解详情 >

这道题目使用的贪心非常大胆(在做的时候没有想到),特此记录。

题目地址:2193. 得到回文串的最少操作次数 - 力扣(LeetCode)

题目大意

给定只包含小写英文字母的字符串 ss 。每一次操作,可以选择 ss 中两个相邻 的字符,并将它们交换。求将 ss 变成回文串的最少操作次数。

保证给定的字符串能够变成回文串。

s2000|s| \le 2000

样例输入

1
2
aabb
letelt

样例输出

1
2
2
2

解题思路

本题直接贪心即可。假设当前字符串长度为 nn ,对于左边的第一个字符,找到最右边第一个对应的字符,并且将该字符移到最右边。这样最外面已经满足回文串的条件,我们只需要让内部的长度为 n2n - 2 的字符串变成回文串即可,这样,我们就减小了问题的规模,不断套用这个算法即可逐渐将字符串全部变成回文。如果最后剩下一个单独的字符,将其移到最中间即可,时间复杂度 Θ(n2)\Theta (n^2)

接下来是贪心的简要证明:

考虑 s1s_1 以及它对应的右边的字符,不妨假设为 aa 。那么整个字符串看起来会像是这样:aaa\cdots a\cdots 。在我们将两个 aa 调整至回文对应的位置的时候,省略号部分的字符前后相对位置并不会发生改变,因此在不考虑这两个 aa 的情况下,无论我们就将 aa 放在哪里,省略号内部变成回文串的最少调整次数不会发生改变。

对于最终回文串中这两个 aa 所在的位置,在两边显然会比在中间要好一些,如果 aa 在中间,那么对省略号进行调整时,可能会出现越过 aa 的情况,从而增加调整的次数。如果将 aa 放在两边,那么调整省略号部分的时候,就不会出现越过 aa 的情况。

最后,我们再来考虑将这两个 aa 调整至两边的操作次数。左边的 aa 已经在字符串的最左边。假设字符串打得长度为 nn ,右边的 aa 下标为 rr ,那么显然会有 1+rn+11 + r \le n + 1。在最终的回文串中,这两个 aa 的下标之和肯定为 n+1n + 1 。因此,将这两个 aa 调整到对应位置,最小的操作次数为 (n+1)(1+r)=nr(n + 1) - (1 + r) = n - r 。这恰好就是把右边的 aa 调整至整个字符串最右边的操作次数。因此,我们将右边的 aa 放到最右边这一操作的最优性得到了保证。

调整完这两个 aa 之后,序列变成如下形式:aaa\cdots a 。现在对省略号进行调整时,我们一定不会将省略号内的字符与 aa 交换,因为这会浪费至少两次操作,而省略号内字符的相对位置不发生改变。所以我们可以继续对省略号套用我们的贪心策略。我们的字符串会变成三部分:左、中、右。其中中部就是我们需要求解的剩下的序列,而左部和右部已经回文对应,对我们的求解不会再造成影响。

最后,考虑 ss 的长度为奇数的情况,假设最后的回文串最中间的字符为 aa 。假设一开始 aa 不在最左边,那么我们的算法的最优性不会受到影响。对于 aa 在最左边的情况,ss 看起来则会像这样:aa\cdots ,其中 aa 最后要移到中间去。同理,移动 aa 并不会让省略号部分字符的相对位置发生改变,反而先移动 aa 可能导致在调整省略号部分时出现越过 aa 的情况(aa 会左移),因此我们把 aa 的移动放在最后会是最优的选择。

AC 代码

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
class Solution {
public int minMovesToMakePalindrome(String s) {
char[] ss = s.toCharArray ();
int r = ss.length - 1;
int ans = 0;
int flg = -1;
for (int i = 0; i < r; ++i) {
int cr = r;
while (ss [cr] != ss [i]) --cr;
if (cr == i && cr != r) {
flg = i;
continue;
}
while (cr < r) {
char tmp = ss [cr];
ss [cr] = ss [cr + 1];
ss [cr + 1] = tmp;
++cr;
++ans;
}
--r;
}
if (flg != -1) {
int mid = ss.length/ 2;
while (flg < mid) {
char tmp = ss [flg];
ss [flg] = ss [flg + 1];
ss [flg + 1] = tmp;
++flg;
++ans;
}
}
return ans;
}
}

评论