本文涉及知识点
字符串 贪心 树状数组 分类讨论
LeetCode2193. 得到回文串的最少操作次数
给你一个只包含小写英文字母的字符串 s 。
每一次 操作 ，你可以选择 s 中两个 相邻 的字符，并将它们交换。
请你返回将 s 变成回文串的 最少操作次数 。
注意 ，输入数据会确保 s 一定能变成一个回文串。
示例 1：
输入：s = “aabb”
输出：2
解释：
我们可以将 s 变成 2 个回文串，“abba” 和 “baab” 。
- 我们可以通过 2 次操作得到 “abba” ：“aabb” -> “abab” -> “abba” 。
- 我们可以通过 2 次操作得到 “baab” ：“aabb” -> “abab” -> “baab” 。
因此，得到回文串的最少总操作次数为 2 。
示例 2：
输入：s = “letelt”
输出：2
解释：
通过 2 次操作从 s 能得到回文串 “lettel” 。
其中一种方法是：“letelt” -> “letetl” -> “lettel” 。
其他回文串比方说 “tleelt” 也可以通过 2 次操作得到。
可以证明少于 2 次操作，无法得到回文串。
提示：
1 <= s.length <= 2000
s 只包含小写英文字母。
s 可以通过有限次操作得到一个回文串。
贪心
s[0]和s[n-1]是第0对，s[1]和s[n-2]是第二对…
从大到小处理第i对，会让已经处理好的对，不在匹配。故只能从小到大处理。
分类讨论
任意两对x和y，有如下关系：
一,xxyy，两者相互无影响。
二，
先处理x，需要：a+e 在处理y，需要:a+b+d+e
先处理y:需要a+b+1+d+e+1,再处理x需要：a+e。
必须先处理x。
三，
先处理x: a+d+e+1，再处理y: a+b+e
线处理y: a+b+1+e 再处理x:a+d+e
结果一样：先处理谁都可以。
结果： 除非被另外一个字符包括，则可以先处理。
最左边的x，如果有多个可以匹配的x，选择最右边的x。
如果s[i] 是只有一个，按就是中心。从后面处理，将s转置。
以可以忽略，留到最后处理：
if (0 == index) { iRet += s.length()/2; s = s.substr(1); continue; }
代码
核心代码
class Solution { public: int minMovesToMakePalindrome(string s) { int iRet = 0; while (s.length() > 2) { int index = s.find_last_of(s[0]); if (0 == index) { std::reverse(s.begin(), s.end()); continue; } iRet += (s.length() - 1 - index); s = s.substr(1, index - 1) + s.substr(index + 1); } return iRet; } };
测试用例
template<class T,class T2> void Assert(const T& t1, const T2& t2) { assert(t1 == t2); } template<class T> void Assert(const vector<T>& v1, const vector<T>& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { Assert(v1[i], v2[i]); } } int main() { string s ; { Solution sln; s = "adabb"; auto res = sln.minMovesToMakePalindrome(s); Assert(3, res); } }
2023 年 3月版
class Solution { public: int minMovesToMakePalindrome(string s) { //统计各字符出行的次数 std::unordered_map<char, int> mFreq; for (const auto&ch : s) { mFreq[ch]++; } int iRet = 0; //记录组间移动后各字符的位置 std::unordered_map<char, vector> mLeft, mRight; int iLeftCnt = 0, iRightCnt = 0; for (int i = 0; i < s.length(); i++) { const char& ch = s[i]; if (mLeft[ch].size() < mFreq[ch] / 2) { iRet += i - iLeftCnt;//组间移动 mLeft[ch].emplace_back(iLeftCnt); iLeftCnt++; } else { mRight[ch].emplace_back(iRightCnt); iRightCnt++; } } //如果是奇数，左边末尾加上 for (auto& it : mLeft) { if (mFreq[it.first] & 1) { it.second.emplace_back(iLeftCnt++); } } //vMove[i]的值是b，表示目前在i位置的字符要移动到b位置 vector vMove(iRightCnt); for (auto it : mRight) { const auto& vLeft = mLeft[it.first]; for (int i = 0; i < it.second.size(); i++) { const int j = vLeft.size() - 1 - i; const int iNewPos = iRightCnt -1 - vLeft[j]; vMove[it.second[i]] = iNewPos; } }
//逆序对数就是组间移动数 CTreeArr<int> tree(iRightCnt); for (int i = iRightCnt - 1; i >= 0; i--) { iRet += tree.Sum(vMove[i]); tree.Add(vMove[i], 1); } return iRet; }
};
2023年7月版
class Solution { public: int minMovesToMakePalindrome(string s) { m_c = s.length(); int iRet = 0; for (int left = 0; left < m_c / 2; left++) { int right = s.length() - 1; for (; s[right] != s[left]; right–); if (left == right) { iRet += m_c / 2 - left; } else { iRet += s.length() - 1 - right; s.erase(right, 1); } } return iRet; } int m_c; };
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关
下载
想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 我想对大家说的话 |
| 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业 |
| 。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
