< 返回版块

eweca1992 发表于 2020-07-29 13:10

Tags:swap

假设:字符串在ASCII范围内。 我尝试过:

    let mut s = String::new("abc");
    let temp = &s[0..1];
    s[0..1] = s[1..2];
    s[1..2] = temp;

但是会提示s[1..2]在编译时size未知。或许需要分成三段来拼接字符串?


好吧,我自己找到了个办法:

    let mut s = String::from("abc");  
    let temp = &s[0..1].to_string();
    s.replace_range(0..1, &s[1..2].to_string());
    s.replace_range(1..2, temp);

但是我还想知道,比较主流的做法是啥呢?


这题实际上是力扣的全排列题目,最后代码如下 (400~430 ms):

fn main() {
    let mut s = "ABCDEFGHIJ".to_string();
    let ans = Solution::permutation(s);
}


struct Solution;

impl Solution {
    pub fn permutation(s: String) -> Vec<String> {
        let mut res = vec![];
        let mut s = s.chars().collect();
        dfs(&mut s, 0, &mut res);

        res
    }
}


fn dfs(s: &mut Vec<char>, left: usize, res: &mut Vec<String>) {
    if left == s.len() {
        res.push(s.iter().collect());
    }

    for i in left..s.len() {
        s.swap(i, left);
        dfs(s, left+1, res);
        s.swap(i, left);
    }
}

感谢各位大神的指导!

评论区

写评论
作者 eweca1992 2020-07-30 01:17

方法可行!速度跟第一位答主的差不多。都属于T1的效率行列。

--
👇
kkonghao: 可以这样实现 let c = "china".to_string(); let mut d = c.into_bytes();

unsafe {
    ptr::swap(&mut d[0], &mut d[1]);
}

let ss = String::from_utf8(d).unwrap();
println!("{:?}", ss);
作者 eweca1992 2020-07-30 01:07

学习到了!这次按照你的说法,递归的时候直接传 &mut Vec而不是&mut String,速度和unsafe下那个速度一致。稍稍略慢于C++使用了原生swap的递归(5%左右)。而且可以不用unsafe!

--
👇
gwy15: 如果你只是全排列,应该直接用 Vec<char> 或者 Vec<u8>,最后再 collect 一遍。

kkonghao 2020-07-29 18:11

可以这样实现 let c = "china".to_string(); let mut d = c.into_bytes();

unsafe {
    ptr::swap(&mut d[0], &mut d[1]);
}

let ss = String::from_utf8(d).unwrap();
println!("{:?}", ss);
gwy15 2020-07-29 16:12

如果你只是全排列,应该直接用 Vec<char> 或者 Vec<u8>,最后再 collect 一遍。

作者 eweca1992 2020-07-29 14:36

感谢你的思路!

--
👇
gwy15: 因为 String 是 utf8 变长储存的,所以直接 swap byte 肯定是 unsafe 的,只能 swap char; swap char 最坏是 O(n) 的。

目前 swap char 没有对应的 API(确实不常见),replace_range 应该是最接近的了。也可以这么写:

let s = String::from("wello, Horld!");
let mut chars: Vec<char> = s.chars().collect();
chars.swap(0, 7);
let s: String = chars.into_iter().collect();

O(n), safe

作者 eweca1992 2020-07-29 14:35

可用!但是会比replace_range慢了不少(在我的算例,递归式dfs全排列String,里慢了50%)。

--
👇
gwy15: 因为 String 是 utf8 变长储存的,所以直接 swap byte 肯定是 unsafe 的,只能 swap char; swap char 最坏是 O(n) 的。

目前 swap char 没有对应的 API(确实不常见),replace_range 应该是最接近的了。也可以这么写:

let s = String::from("wello, Horld!");
let mut chars: Vec<char> = s.chars().collect();
chars.swap(0, 7);
let s: String = chars.into_iter().collect();

O(n), safe

作者 eweca1992 2020-07-29 14:33

感谢,这个方式非常之快。比replace_range快一倍。

--
👇
cnwzhjs: ```rust fn main() { let mut s = String::from("abc"); unsafe { s.as_mut_vec().swap(0, 1); } println!("{}", s); }


这也是一个方法……

cnwzhjs 2020-07-29 14:00

要不要去发个pr,把 String::swapString::swap_range 加进去 :)

--
👇
gwy15: 因为 String 是 utf8 变长储存的,所以直接 swap byte 肯定是 unsafe 的,只能 swap char; swap char 最坏是 O(n) 的。

目前 swap char 没有对应的 API(确实不常见),replace_range 应该是最接近的了。也可以这么写:

let s = String::from("wello, Horld!");
let mut chars: Vec<char> = s.chars().collect();
chars.swap(0, 7);
let s: String = chars.into_iter().collect();

O(n), safe

gwy15 2020-07-29 13:55

因为 String 是 utf8 变长储存的,所以直接 swap byte 肯定是 unsafe 的,只能 swap char; swap char 最坏是 O(n) 的。

目前 swap char 没有对应的 API(确实不常见),replace_range 应该是最接近的了。也可以这么写:

let s = String::from("wello, Horld!");
let mut chars: Vec<char> = s.chars().collect();
chars.swap(0, 7);
let s: String = chars.into_iter().collect();

O(n), safe

cnwzhjs 2020-07-29 13:44
fn main() {
    let mut s = String::from("abc");
    unsafe { s.as_mut_vec().swap(0, 1); }
    println!("{}", s);
}

这也是一个方法……

1 共 10 条评论, 1 页