【字符串】【贪心】【树状数组】2193. 得到回文串的最少操作次数

作者推荐

视频算法专题

本文涉及知识点

字符串贪心树状数组分类讨论

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，两者相互无影响。
二， $^{a个字符}_{\cdots} x ^{b个字符}_{\cdots}y ^{c个字符}_{\cdots}y ^{d个字符}_{\cdots}x ^{e个字符}_{\cdots}$
先处理x，需要：a+e 在处理y，需要:a+b+d+e
先处理y:需要a+b+1+d+e+1,再处理x需要：a+e。
必须先处理x。
三， $^{a个字符}_{\cdots} x ^{b个字符}_{\cdots}y ^{c个字符}_{\cdots}x ^{d个字符}_{\cdots}y ^{e个字符}_{\cdots}$
先处理x: a+d+e+1，再处理y: a+b+e
线处理y: a+b+1+e 再处理x:a+d+e
结果一样：先处理谁都可以。
结果：除非被另外一个字符包括，则可以先处理。
最左边的x，如果有多个可以匹配的x，选择最右边的x。
$For\Large_{i:0}^{i < s.length/2}匹配s[i]$
如果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

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业
。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛