- 题目:
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>();
}
}
网友评论