一起学Rust-实战leetcode(三)

将一个给定字符串根据给定的行数,以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时,

排列如下:

L   C   I   R
E T O E S I I G
E   D   H   N

之后,你的输出需要从左往右逐行读取,产生出一个新的字符串,比如:"LCIRETOESIIGEDHN"

示例 2:

输入: s = "LEETCODEISHIRING", numRows = 4

输出: "LDREOEIIECIHNTSG"

解释:

L     D     R
E   O E   I I
E C   I H   N
T     S     G

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/zigzag-conversion

这是来源于leetcode的一道题 “Z 字形变换”,我们使用Rust来实现。

本次实战的目的:

复习 Vec<T> 的使用, String 的方法使用, Range<T> 结构体及数学计算。

简单分析

这道题细看之下是存在一些数学规律的,如果从数据规律的方向去思考,细心观察可以发现,第一行和最后一行的字母是与numRows有着直接的关系的:

分析公式前定义两个未知数 i:行号从0开始,j:行内的字母下标,从0开始,n:numRows简写,总行数。

第一行(i=0)

下标值公式 idx = j * (n + (n - 1) - 1) { j=0,1,2... } ,取值char = str[idx]

所以当n=4时,第一行的第一个就应当对应原始字符串中下标是 0 * (4 + 3 - 1) = 0 , str[0]就是L,第二个就是 1 * (4 + 3 - 1) = 6 ,str[6]就是D,依次类推。

最后一行(i = n - 1):

偏移量: n - 1

下标值公式: j * (n + (n - 1) - 1) + n - 1 { j=0,1,2... } 。

所以当n=4时,最后一行的第一个就应该是 0 * (4 + 3 - 1) + 3 = 3,str[3]就是T,第二个就是 1 * (4+3 - 1 ) + 3 = 9,str[9]就是S,依次类推。

中间行(i>0且i < n - 1 {n > 2}):

中间的几行相对特别一点,我们这里引入一个区间的概念,例如n=4时,L和D形成一个区间,D和R形成第二个区间,这种的字母是以T为中心的对称序列。

由于对称便有了规律,中间的第 i 行(i=1,2..n-2; n > 2),行内的下标0和下标1的位置属于第一个区间,依次下标2和3是第二个区间,每个区间的起始和结束的字符位置通过上面的公式可确定,所以可以得出:

中间行的方法1:

公式: j * (n + (n - 1) - 1) + i 和 ( j + 1 )* (n + (n - 1) - 1) - i

i :这里i的意义发生变化,是属于区间的下标值。

一次循环中取得区间中的两个值

中间行的方法2(较复杂):

公式: (floor( j / 2 ) * (n + (n - 1) - 1) + n - 1) - ( n - i - 1) * (-1) ^ j

floor( j / 2 ):通过对行内字母下标取整数的商,来获取区间下标。

(floor( j / 2 ) * (n + (n - 1) - 1) + n - 1) 这一部分可以取出区间内的对称点。

( n - i - 1) * (-1) ^ j 获得区间内的正负偏移量,相减即得出实际的字符串下标。

下面实例为解释数字的幂运算,选择实现第二种方法:

fn convert(s: String, num_rows: i32) -> String {
    let mut result = String::new();
    let seq: Vec<char> = s.chars().collect();
    let length = s.len();
    if length < 3 || num_rows < 2{
        return s;
    }

    for i in 0..num_rows {
        let mut j:i32 = 0;
        loop {
            let mut idx:usize = 0;
            if i > 0 && i < num_rows - 1 {
                let k:i32 = j/2;
                let tail = k * (2 * num_rows - 2) + num_rows - 1;
                let offset = (num_rows - i - 1) * (-1_i32).pow(j as u32);
                idx = (tail - offset) as usize;
            } else {
                idx = (j * (num_rows + num_rows - 2) + i) as usize;
            }

            if idx >= length {
                break;
            }
            result.push(seq[idx]);

            j += 1;
        }
    }

    result
}

关注语法:

0..num_rows 这里实际是实现 Range<T> 结构体的一种语法,它生成等是从0开始,到4结束(不含)到一个可迭代的结构体,如果需要包含则可以使用 0..=num_rows 。而且Range<T>实现了迭代器,片段,排序等trait,所以可以在循环中使用。

(-1_i32).pow(j as u32) 有三点需要注意:

第一,如果是负数的幂运算,则需要加括号,否则负号会加到计算结果的前面。

第二,必须要标明数字的类型,或是标明数字变量的类型。

第三, ^ 在Rust中这个符号不是幂运算符号,而是异或。

最后分享一个别人的优秀案例,超级简洁明了:

fn convert1(s: String, num_rows: i32) -> String {
    if num_rows<=1 { return s; }
    let s = s.as_bytes();
    let mut ret = String::with_capacity(s.len());
    for n in 0..num_rows {
        let mut idx = 0;
        for &i in [n].iter().chain([(num_rows-n-1)*2, 2*n].iter().cycle()) {
            println!("{},{}", n, i);
            if idx+i != idx || idx==0 {
                idx += i;
                if idx as usize>=s.len() { break; }
                ret.push(s[idx as usize] as char);
            }
        }
    }
    ret
}

as_bytes() 将字符串转换为单字节数组。

with_capacity(len) 可以创建一个指定长度的空的字符串空间,在长度填满之前不会发生realloc。

iter() 获取迭代器

chain() 在尾部连接一个数组,

cycle() 连续遍历一个数组,到达结尾后再从头开始遍历。

原文发布于微信公众号 - 可回收BUG(way-of-full-stack)

原文发表时间:2019-09-15

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券