- 题目：
https://leetcode.cn/problems/zigzag-conversion/
将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：
P A H N
A P L S I I G
Y I R
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。
请你实现这个将字符串进行指定行数变换的函数：
string convert(string s, int numRows);
- 思路：
- 这道题的根本是计算Z字型的数组序列。
也就是当遍历一个字符串的时候，如何计算出它需要填充到的数组坐标。
这个坐标特征是:
(0,0), (1,0), (2,0), (1,1), (0,2), (1,2), (2,2), (1,3), (0,4), (1,4), (2,4), (1,5), (0,6), (1,6)
可以由此推算：y坐标一直不变，直到x自增到最后一排
然后x开始自减，y开始自增，直到x自减到第一排，由此循环。
也就是说x要从0下降至row行，再从row上升到0行，完成一次循环。则循环的步长是[0, 2(row-1)]。在x下降时，y坐标不变，在x上升时，y坐标自增。 - 源码中，我们定义来一个ZConvert 结构来记录row到初始值，并且维护后续的迭代序列。当然也可以将ZConvert构造成一个迭代器用impl Iterator的方式来更优雅的遍历这个坐标序列。
- 在源码中，我们使用map的方式，将String映射为一个Point序列:Vec<Point>.由此我们就完成了对字符的坐标标记工作。后续的points.sort_by是为了得到以多维数组顺序索引的序列。我们使用了自定义的compare函数的方式来比较他们的坐标。当然如果以空间换时间的方法，是可以预先定义好二维数组，并且将具体的每一个char直接填入的。这里的sort方法实际上是一个额外的负担。
提交结果：
执行用时：4 ms, 在所有 Rust 提交中击败了78.24%的用户
内存消耗：2.2 MB, 在所有 Rust 提交中击败了61.77%的用户
通过测试用例：
1157 / 1157
源码：
use std::cmp::Ordering::*;
#[derive(Debug)]
struct Point {
alph: char,
x: i32,
y: i32,
}
struct ZConvert {
mid: i32,
x: i32,
y: i32,
}
impl ZConvert {
fn new(row: i32) -> Self {
ZConvert {
mid: row - 1,
x: 0,
y: 0,
}
}
fn get_next_coordinate(&mut self) -> (i32, i32) {
if self.mid == 0 {
self.y += 1;
return (self.x,self.y)
}
let x: i32 = self.x % (2 * self.mid);
self.x += 1;
if x < self.mid {
return (x, self.y);
} else {
self.y += 1;
return (2 * self.mid - x, self.y - 1);
}
}
}
impl Solution {
pub fn convert(s: String, num_rows: i32) -> String {
let mut z = ZConvert::new(num_rows);
let mut points = s
.chars()
.map(move |alph| {
let (x, y) = z.get_next_coordinate();
Point {
alph: alph,
x: x,
y: y,
}
})
.collect::<Vec<Point>>();
points.sort_by(|p1, p2| {
if p1.x < p2.x {
return Less;
} else if p1.x > p2.x {
return Greater;
} else {
if p1.y > p2.y {
return Greater;
} else if p1.y < p2.y {
return Less;
} else {
return Equal;
}
}
});
return points.into_iter().map(|p| p.alph).collect::<String>();
}
}
