2023-05-27：给你一个只包含小写英文字母的字符串 s 。
每一次 操作 ，你可以选择 s 中两个 相邻 的字符，并将它们交换。
请你返回将 s 变成回文串的 最少操作次数 。
注意 ，输入数据会确保 s 一定能变成一个回文串。
输入：s = “letelt”。
输出：2。
答案2023-05-27：
大体过程如下：
1.定义结构体 IndexTree，其中包含一个整型切片 tree 和整型变量 n，用于实现树状数组。
2.定义函数 createIndexTree(size int) *IndexTree，用于创建一个大小为 size 的树状数组并初始化，返回该数组的指针。
3.定义函数 sum(it *IndexTree, i int) int，用于求以 i 为结尾的前缀和。
4.定义函数 add(it *IndexTree, i int, v int)，用于将第 i 个位置上的值增加 v。
5.定义函数 merge(arr []int, help []int, l int, m int, r int) int，用于归并排序并统计逆序对数量。
6.定义函数 number(arr []int, help []int, l int, r int) int，用于递归地求解整个序列中的逆序对数量。
7.定义函数 minMovesToMakePalindrome(s string) int，用于求解将字符串 s 变成回文串的最少操作次数。首先遍历字符串，将每个字符第一次出现的下标加入到对应字符的索引列表中。然后定义一个整型切片 arr 用于记录每个字符与其对称位置之间的距离，以及一个 IndexTree 类型的变量 it 用于记录每个字符在左半部分的逆序对数量。遍历整个字符串，对于每个未处理的位置，找到它与其对称位置之间的距离，并计算出在左半部分有多少个字符与该字符构成了逆序对。最后调用 number 函数求解 arr 中的逆序对数量即可。
8.在 main 函数中定义字符串 s = "letelt"，并调用 minMovesToMakePalindrome 函数输出结果。
时间复杂度为 $O(nlog n)$，空间复杂度为 $O(n)$。
其中，遍历整个字符串的时间复杂度为 $O(n)$，建立字符索引列表的时间复杂度为 $O(n)$，建立树状数组的时间复杂度为 $O(nlog n)$，递归求解逆序对数量的时间复杂度为 $O(nlog n)$，归并排序中合并两个有序子序列的时间复杂度为 $O(n)$。
而空间复杂度中，建立字符索引列表占用的空间为 $O(26n)$，建立树状数组占用的空间为 $O(nlog n)$，递归求解逆序对数量时传递的辅助数组占用的空间为 $O(n)$。
go语言完整代码如下：
package main
import "fmt"
func main() {
s := "letelt"
result := minMovesToMakePalindrome(s)
fmt.Println(result)
}
func minMovesToMakePalindrome(s string) int {
n := len(s)
indies := make([][]int, 26)
for i := 0; i 0 {
ans += it.tree[i]
i -= i & -i
}
return ans
}
func (it *indexTree) add(i int, v int) {
for i = r {
return 0
}
mid := l + ((r - l) >> 1)
return number(arr, help, l, mid) + number(arr, help, mid+1, r) + merge(arr, help, l, mid, r)
}
func merge(arr []int, help []int, l int, m int, r int) int {
i := r
p1 := m
p2 := r
ans := 0
for p1 >= l && p2 > m {
if arr[p1] > arr[p2] {
ans += p2 - m
help[i] = arr[p1]
i--
p1--
} else {
help[i] = arr[p2]
i--
p2--
}
}
for p1 >= l {
help[i] = arr[p1]
i--
p1--
}
for p2 > m {
help[i] = arr[p2]
i--
p2--
}
for i := l; i 
rust语言完整代码如下：
fn main() {
let s = String::from("letelt");
let result = min_moves_to_make_palindrome(s);
println!("{}", result);
}
fn min_moves_to_make_palindrome(s: String) -> i32 {
let n = s.len();
let mut indies: Vec> = vec![vec![]; 26];
for (i, c) in s.chars().enumerate() {
let index = (c as u8 - b'a') as usize;
indies[index].push((i + 1) as i32);
}
let mut arr: Vec = vec![0; n as usize + 1];
let mut it = IndexTree::new(n as i32);
let mut i = 0;
let mut l = 1;
while i ,
n: i32,
}
impl IndexTree {
fn new(size: i32) -> Self {
let tree = vec![0; size as usize + 1];
let mut ans = Self { tree, n: size };
for i in 1..=size {
ans.add(i, 1);
}
return ans;
}
fn sum(&self, mut i: i32) -> i32 {
let mut ans = 0;
while i > 0 {
ans += self.tree[i as usize];
i -= i & -i;
}
ans
}
fn add(&mut self, mut i: i32, v: i32) {
while i , help: &mut Vec, l: i32, r: i32) -> i32 {
if l >= r {
return 0;
}
let mid = l + ((r - l) >> 1);
return number(arr, help, l, mid) + number(arr, help, mid + 1, r) + merge(arr, help, l, mid, r);
}
fn merge(arr: &mut Vec, help: &mut Vec, l: i32, m: i32, r: i32) -> i32 {
let mut i = r;
let mut p1 = m;
let mut p2 = r;
let mut ans = 0;
while p1 >= l && p2 > m {
ans += if arr[p1 as usize] > arr[p2 as usize] {
p2 - m
} else {
0
};
if arr[p1 as usize] > arr[p2 as usize] {
help[i as usize] = arr[p1 as usize];
p1 -= 1;
} else {
help[i as usize] = arr[p2 as usize];
p2 -= 1;
};
i -= 1;
}
while p1 >= l {
help[i as usize] = arr[p1 as usize];
i -= 1;
p1 -= 1;
}
while p2 > m {
help[i as usize] = arr[p2 as usize];
i -= 1;
p2 -= 1;
}
for i in l..=r {
arr[i as usize] = help[i as usize];
}
ans
}
c++完整代码如下：
#include
#include
using namespace std;
struct IndexTree {
vector tree;
int n;
IndexTree(int size) {
tree.resize(size + 1);
n = size;
for (int i = 1; i 0) {
ans += tree[i];
i -= i & -i;
}
return ans;
}
void add(int i, int v) {
while (i & arr, vector& help, int l, int m, int r);
int number(vector& arr, vector& help, int l, int r) {
if (l >= r) {
return 0;
}
int mid = l + ((r - l) >> 1);
return number(arr, help, l, mid) + number(arr, help, mid + 1, r) + merge(arr, help, l, mid, r);
}
int merge(vector& arr, vector& help, int l, int m, int r) {
int i = r;
int p1 = m;
int p2 = r;
int ans = 0;
while (p1 >= l && p2 > m) {
if (arr[p1] > arr[p2]) {
ans += p2 - m;
help[i--] = arr[p1--];
}
else {
help[i--] = arr[p2--];
}
}
while (p1 >= l) {
help[i--] = arr[p1--];
}
while (p2 > m) {
help[i--] = arr[p2--];
}
for (i = l; i > indies(26, vector());
for (int i = 0, j = 1; i arr(n + 1, 0);
IndexTree it(n);
for (int i = 0, l = 1; i help(n + 1, 0);
int ans = number(arr, help, 1, n);
return ans;
}
int main() {
char s[] = "letelt";
int result = minMovesToMakePalindrome(s);
cout 
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.fwqtg.net
这里着重关注工具的收集，而不是使用的技巧，技术的原理 只记录一些我用过的。 目录 评测 播放器 分析视频流和码流 杂项 评测 https://codecwar.com/ 视频编解码器质量评估和相对性能比较的在线服务 播放器 PotPlayer VLC Play…
