[解题报告]力扣双周赛73D

lornd

发布于：2022年3月22日

次浏览

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

题目地址：2193. 得到回文串的最少操作次数 - 力扣（LeetCode）

题目大意

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

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

$|s| \le 2000$ 。

样例输入

1
2

aabb
letelt

样例输出

1
2

2
2

解题思路

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

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

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

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

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

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

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

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

更新于：2023年9月15日