一起学Rust-实战leetcode（三）
- 2019 年 10 月 4 日
- 筆記
将一个给定字符串根据给定的行数，以从上往下、从左到右进行 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() 连续遍历一个数组，到达结尾后再从头开始遍历。
完
