2023-05-27：給你一個(gè)只包含小寫英文字母的字符串 s 。 每一次 操作 ，你可以選擇 s
2023-05-27：給你一個(gè)只包含小寫英文字母的字符串 s 。
每一次 操作 ，你可以選擇 s 中兩個(gè) 相鄰 的字符，并將它們交換。
請你返回將 s 變成回文串的 最少操作次數(shù) 。
注意 ，輸入數(shù)據(jù)會(huì)確保 s 一定能變成一個(gè)回文串。
輸入：s = "letelt"。
輸出：2。
答案2023-05-27：
大體過程如下：
1.定義結(jié)構(gòu)體?IndexTree，其中包含一個(gè)整型切片?tree?和整型變量?n，用于實(shí)現(xiàn)樹狀數(shù)組。
2.定義函數(shù)?createIndexTree(size int) *IndexTree，用于創(chuàng)建一個(gè)大小為?size?的樹狀數(shù)組并初始化，返回該數(shù)組的指針。
3.定義函數(shù)?sum(it *IndexTree, i int) int，用于求以?i?為結(jié)尾的前綴和。
4.定義函數(shù)?add(it *IndexTree, i int, v int)，用于將第?i?個(gè)位置上的值增加?v。
5.定義函數(shù)?merge(arr []int, help []int, l int, m int, r int) int，用于歸并排序并統(tǒng)計(jì)逆序?qū)?shù)量。
6.定義函數(shù)?number(arr []int, help []int, l int, r int) int，用于遞歸地求解整個(gè)序列中的逆序?qū)?shù)量。
7.定義函數(shù)?minMovesToMakePalindrome(s string) int，用于求解將字符串?s?變成回文串的最少操作次數(shù)。首先遍歷字符串，將每個(gè)字符第一次出現(xiàn)的下標(biāo)加入到對應(yīng)字符的索引列表中。然后定義一個(gè)整型切片?arr?用于記錄每個(gè)字符與其對稱位置之間的距離，以及一個(gè)?IndexTree?類型的變量?it?用于記錄每個(gè)字符在左半部分的逆序?qū)?shù)量。遍歷整個(gè)字符串，對于每個(gè)未處理的位置，找到它與其對稱位置之間的距離，并計(jì)算出在左半部分有多少個(gè)字符與該字符構(gòu)成了逆序?qū)?。最后調(diào)用?number?函數(shù)求解?arr?中的逆序?qū)?shù)量即可。
8.在?main?函數(shù)中定義字符串?s = "letelt"，并調(diào)用?minMovesToMakePalindrome?函數(shù)輸出結(jié)果。
時(shí)間復(fù)雜度為 $O(n\log n)$，空間復(fù)雜度為 $O(n)$。
其中，遍歷整個(gè)字符串的時(shí)間復(fù)雜度為 $O(n)$，建立字符索引列表的時(shí)間復(fù)雜度為 $O(n)$，建立樹狀數(shù)組的時(shí)間復(fù)雜度為 $O(n\log n)$，遞歸求解逆序?qū)?shù)量的時(shí)間復(fù)雜度為 $O(n\log n)$，歸并排序中合并兩個(gè)有序子序列的時(shí)間復(fù)雜度為 $O(n)$。
而空間復(fù)雜度中，建立字符索引列表占用的空間為 $O(26n)$，建立樹狀數(shù)組占用的空間為 $O(n\log n)$，遞歸求解逆序?qū)?shù)量時(shí)傳遞的輔助數(shù)組占用的空間為 $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?<?26;?i++?{
????????indies[i]?=?[]int{}
????}
????for?i?:=?0;?i?<?n;?i++?{
????????c?:=?int(s[i])?-?'a'
????????indies[c]?=?append(indies[c],?i+1)
????}
????arr?:=?make([]int,?n+1)
????it?:=?newIndexTree(n)
????for?i,?l?:=?0,?1;?i?<?n;?i,?l?=?i+1,?l+1?{
????????if?arr[l]?==?0?{
????????????c?:=?int(s[i])?-?'a'
????????????r?:=?indies[c][len(indies[c])-1]
????????????indies[c]?=?indies[c][:len(indies[c])-1]
????????????if?l?==?r?{
????????????????arr[l]?=?(1?+?n)?/?2
????????????????it.add(l,?-1)
????????????}?else?{
????????????????kth?:=?it.sum(l)
????????????????arr[l]?=?kth
????????????????arr[r]?=?n?-?kth?+?1
????????????????it.add(r,?-1)
????????????}
????????}
????}
????return?number(arr,?make([]int,?n+1),?1,?n)
}
type?indexTree?struct?{
????tree?[]int
????n????int
}
func?newIndexTree(size?int)?*indexTree?{
????tree?:=?make([]int,?size+1)
????ans?:=?&indexTree{tree:?tree,?n:?size}
????for?i?:=?1;?i?<=?size;?i++?{
????????ans.add(i,?1)
????}
????return?ans
}
func?(it?*indexTree)?sum(i?int)?int?{
????ans?:=?0
????for?i?>?0?{
????????ans?+=?it.tree[i]
????????i?-=?i?&?-i
????}
????return?ans
}
func?(it?*indexTree)?add(i?int,?v?int)?{
????for?i?<?len(it.tree)?{
????????it.tree[i]?+=?v
????????i?+=?i?&?-i
????}
}
func?number(arr?[]int,?help?[]int,?l?int,?r?int)?int?{
????if?l?>=?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?<=?r;?i++?{
????????arr[i]?=?help[i]
????}
????return?ans
}
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<i32>>?=?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<i32>?=?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?{
????????if?arr[l?as?usize]?==?0?{
????????????let?c_index?=?(s.chars().nth(i?as?usize).unwrap()?as?u8?-?b'a')?as?usize;
????????????let?a?=?indies[c_index].len()?-?1;
????????????let?r?=?indies[c_index][a];
????????????indies[c_index].remove(a);
????????????if?l?==?r?{
????????????????arr[l?as?usize]?=?(1?+?n?as?i32)?/?2;
????????????????it.add(l,?-1);
????????????}?else?{
????????????????let?kth?=?it.sum(l);
????????????????arr[l?as?usize]?=?kth;
????????????????arr[r?as?usize]?=?n?as?i32?-?kth?+?1;
????????????????it.add(r,?-1);
????????????}
????????}
????????i?+=?1;
????????l?+=?1;
????}
????number(&mut?arr,?&mut?vec![0;?n?as?usize?+?1],?1,?n?as?i32)
}
struct?IndexTree?{
????tree:?Vec<i32>,
????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?<?self.tree.len()?as?i32?{
????????????self.tree[i?as?usize]?+=?v;
????????????i?+=?i?&?-i;
????????}
????}
}
fn?number(arr:?&mut?Vec<i32>,?help:?&mut?Vec<i32>,?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<i32>,?help:?&mut?Vec<i32>,?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?<iostream>
#include?<vector>
using?namespace?std;
struct?IndexTree?{
????vector<int>?tree;
????int?n;
????IndexTree(int?size)?{
????????tree.resize(size?+?1);
????????n?=?size;
????????for?(int?i?=?1;?i?<=?n;?i++)?{
????????????add(i,?1);
????????}
????}
????int?sum(int?i)?{
????????int?ans?=?0;
????????while?(i?>?0)?{
????????????ans?+=?tree[i];
????????????i?-=?i?&?-i;
????????}
????????return?ans;
????}
????void?add(int?i,?int?v)?{
????????while?(i?<?tree.size())?{
????????????tree[i]?+=?v;
????????????i?+=?i?&?-i;
????????}
????}
};
int?merge(vector<int>&?arr,?vector<int>&?help,?int?l,?int?m,?int?r);
int?number(vector<int>&?arr,?vector<int>&?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<int>&?arr,?vector<int>&?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?<=?r;?i++)?{
????????arr[i]?=?help[i];
????}
????return?ans;
}
int?minMovesToMakePalindrome(char*?s)?{
????int?n?=?strlen(s);
????vector<vector<int>>?indies(26,?vector<int>());
????for?(int?i?=?0,?j?=?1;?i?<?n;?i++,?j++)?{
????????int?c?=?s[i]?-?'a';
????????indies[c].push_back(j);
????}
????vector<int>?arr(n?+?1,?0);
????IndexTree?it(n);
????for?(int?i?=?0,?l?=?1;?i?<?n;?i++,?l++)?{
????????if?(arr[l]?==?0)?{
????????????int?c?=?s[i]?-?'a';
????????????int?r?=?indies[c].back();
????????????indies[c].pop_back();
????????????if?(l?==?r)?{
????????????????arr[l]?=?(1?+?n)?/?2;
????????????????it.add(l,?-1);
????????????}
????????????else?{
????????????????int?kth?=?it.sum(l);
????????????????arr[l]?=?kth;
????????????????arr[r]?=?n?-?kth?+?1;
????????????????it.add(r,?-1);
????????????}
????????}
????}
????vector<int>?help(n?+?1,?0);
????int?ans?=?number(arr,?help,?1,?n);
????return?ans;
}
int?main()?{
????char?s[]?=?"letelt";
????int?result?=?minMovesToMakePalindrome(s);
????cout?<<?result?<<?endl;
????return?0;
}
福大大架構(gòu)師每日一題
java當(dāng)死，golang當(dāng)立。最新面試題，涉及golang，rust，mysql，redis，云原生，算法，分布式，網(wǎng)絡(luò)，操作系統(tǒng)。
公眾號(hào)
