天天看點
傳回

2023-05-27：給你一個隻包含小寫英文字母的字元串 s 。 每一次 操作

作者：福大大架構師每日一題

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(n\log n)$，空間複雜度為 $O(n)$。

其中，周遊整個字元串的時間複雜度為 $O(n)$，建立字元索引清單的時間複雜度為 $O(n)$，建立樹狀數組的時間複雜度為 $O(n\log n)$，遞歸求解逆序對數量的時間複雜度為 $O(n\log n)$，歸并排序中合并兩個有序子序列的時間複雜度為 $O(n)$。

而空間複雜度中，建立字元索引清單占用的空間為 $O(26n)$，建立樹狀數組占用的空間為 $O(n\log 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 < 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
}
2023-05-27：給你一個隻包含小寫英文字母的字元串 s 。 每一次 操作

在這裡插入圖檔描述

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
}
2023-05-27：給你一個隻包含小寫英文字母的字元串 s 。 每一次 操作

在這裡插入圖檔描述

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;
}
2023-05-27：給你一個隻包含小寫英文字母的字元串 s 。 每一次 操作

在這裡插入圖檔描述

2023-05-27：給你一個隻包含小寫英文字母的字元串 s 。 每一次 操作

福大大架構師每日一題java當死，golang當立。最新面試題，涉及golang，rust，mysql，redis，雲原生，算法，分布式，網絡，作業系統。527篇原創内容

公衆号

英文字母
上一篇: #35萬家用MPV怎麼選#首先要搞清楚，什麼是家用MPV？MPV（multi-PurposeVehicles），多用途汽
下一篇: 華傲智能化子系統——智能3D可視監測系統

繼續閱讀