首页 > 其他分享 >2023-05-27:给你一个只包含小写英文字母的字符串 s 。 每一次 操作 ,你可以选择 s 中两个 相邻 的字符,并将它们交换。 请你返回将 s 变成回文串的 最少操作次数 。 注意 ,输入数据

2023-05-27:给你一个只包含小写英文字母的字符串 s 。 每一次 操作 ,你可以选择 s 中两个 相邻 的字符,并将它们交换。 请你返回将 s 变成回文串的 最少操作次数 。 注意 ,输入数据

时间:2023-05-27 21:12:21浏览次数:46  
标签:p2 arr 27 help 05 int usize p1 2023

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
}

在这里插入图片描述

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;
}

在这里插入图片描述

标签:p2,arr,27,help,05,int,usize,p1,2023
From: https://www.cnblogs.com/moonfdd/p/17437351.html

相关文章

  • 2023-05-27:给你一个只包含小写英文字母的字符串 s 。 每一次 操作 ,你可以选择 s 中两
    2023-05-27:给你一个只包含小写英文字母的字符串s。每一次操作,你可以选择s中两个相邻的字符,并将它们交换。请你返回将s变成回文串的最少操作次数。注意,输入数据会确保s一定能变成一个回文串。输入:s="letelt"。输出:2。答案2023-05-27:大体过程如下:1.定义结构体Index......
  • 2023.21 linux下的文件打包tar
    “tar”是“tapearchive”的缩写,最初是为了在磁带上创建档案而设计的,Linux下常使用tar命令将多个文件或目录打包成一个文件,这样可以方便地将多个文件或目录打包成一个文件,以便于备份或传输。刚从Windows使用Linux的很多可能都没意识到打包和压缩两个不同的概念,打包就是将多......
  • 2023.5
    ARC157D绷不住了设行切了\(x\)刀,列切了\(y\)刀,Y的总数为\(A\),那么需要有\(2(x+1)(y+1)=A\)。进一步,如果确定了\(x,y\),那么行被分成的这\(x+1\)部分中一定每一部分都恰好有\(2(y+1)\)个Y。再进一步,对于每一种符合这个条件的行的分割方案,他们对应的列的分割方案数都......
  • 5. 27 日总结
    我今天复习了数据库相关的查询语句:1.理解了对查询结果进行分组统计的方法。2.学会了怎么样使用多表连接查询。(1.内连接2.自连接3.外连接)3.学会了如何使用TOP限制结果集。例如:查询年龄最大的三个学生的姓名,年龄及所在系。SELECTTOP3Sname,Sage,SdeptFROMStudent ORDE......
  • 230526 // 小数论复习
    裁决已至!称量,你的罪恶!以此身,肃正万象!人总是越活越抽象的,所以怎么还不考期末,我要考期末!A.Minhttp://222.180.160.110:1024/contest/3641/problem/1给出\(n\)个数\(A_{1\simn}\),现求一组整数序列\(X_{1\simn}\)使得\(S=A_1\timesX_1+A_2\timesX_2+\cdots......
  • C语言课程设计[2023-05-27]
    C语言课程设计[2023-05-27]C语言课程设计综合性设计实验说明设计要求:(1)功能完备,实现用户需求(2)用户界面友好易用(3)必须调试通过,能够正常运行(4)驼峰命名、合理注释、模块化程序功能实现等规范化编程(5)保证源程序可读性。对系统常量等数据要求规范处理,对于常用......
  • 2.27总结
    今天整个项目基本上全面的完成,并且成功打包成apk,而且软件应用商店发布的权限正在申请,由于代码太多和防止杯抄袭的原因,以图片形势展示一些,随后项目的代码会上传到github上。   ......
  • 5.27每日总结
    今天整个项目基本上全面的完成,并且成功打包成apk,而且软件应用商店发布的权限正在申请,由于代码太多和防止杯抄袭的原因,以图片形势展示一些,随后项目的代码会上传到github上。    ......
  • 2023华为伙伴大会:ISDP发布伙伴体验中心,邀伙伴探索数智化未来
    近日,2023年华为中国合作伙伴大会于深圳国际会展中心(宝安)圆满落幕。本次大会向来自全国各个领域的1.6万多名华为新老朋友,提供一个面对面开放交流、自我展示的舞台。此次大会煤亮子、软通动力、中软国际、易宝、全采智能等多家ISDP的新老伙伴出席,一起交流行业发展与下一步合作。其中......
  • 未授权访问漏洞检测工具(CVE-2023-29922)
    ===================================免责声明请勿利用文章内的相关技术从事非法测试,由于传播、利用此文所提供的信息而造成的任何直接或者间接的后果及损失,均由使用者本人负责,作者不为此承担任何责任。工具来自网络,安全性自测,如有侵权请联系删除。0x01工具介绍PowerJob<=4.3.2......