- 題目：
https://leetcode.cn/problems/zigzag-conversion/
將一個(gè)給定字符串 s 根據(jù)給定的行數(shù) numRows ，以從上往下靴患、從左到右進(jìn)行 Z 字形排列。
比如輸入字符串為 "PAYPALISHIRING" 行數(shù)為 3 時(shí)扰肌，排列如下：
P A H N
A P L S I I G
Y I R
之后默责，你的輸出需要從左往右逐行讀取，產(chǎn)生出一個(gè)新的字符串，比如："PAHNAPLSIIGYIR"纺铭。
請(qǐng)你實(shí)現(xiàn)這個(gè)將字符串進(jìn)行指定行數(shù)變換的函數(shù)：
string convert(string s, int numRows);
- 思路：
- 這道題的根本是計(jì)算Z字型的數(shù)組序列悴了。
也就是當(dāng)遍歷一個(gè)字符串的時(shí)候搏恤，如何計(jì)算出它需要填充到的數(shù)組坐標(biāo)违寿。
這個(gè)坐標(biāo)特征是:
(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坐標(biāo)一直不變，直到x自增到最后一排
然后x開(kāi)始自減熟空，y開(kāi)始自增藤巢，直到x自減到第一排，由此循環(huán)息罗。
也就是說(shuō)x要從0下降至row行掂咒，再?gòu)膔ow上升到0行，完成一次循環(huán)迈喉。則循環(huán)的步長(zhǎng)是[0, 2(row-1)]绍刮。在x下降時(shí)，y坐標(biāo)不變挨摸，在x上升時(shí)孩革，y坐標(biāo)自增。 - 源碼中得运，我們定義來(lái)一個(gè)ZConvert 結(jié)構(gòu)來(lái)記錄row到初始值膝蜈，并且維護(hù)后續(xù)的迭代序列。當(dāng)然也可以將ZConvert構(gòu)造成一個(gè)迭代器用impl Iterator的方式來(lái)更優(yōu)雅的遍歷這個(gè)坐標(biāo)序列熔掺。
- 在源碼中饱搏，我們使用map的方式，將String映射為一個(gè)Point序列:Vec<Point>.由此我們就完成了對(duì)字符的坐標(biāo)標(biāo)記工作置逻。后續(xù)的points.sort_by是為了得到以多維數(shù)組順序索引的序列推沸。我們使用了自定義的compare函數(shù)的方式來(lái)比較他們的坐標(biāo)。當(dāng)然如果以空間換時(shí)間的方法券坞，是可以預(yù)先定義好二維數(shù)組鬓催，并且將具體的每一個(gè)char直接填入的。這里的sort方法實(shí)際上是一個(gè)額外的負(fù)擔(dān)报慕。
提交結(jié)果：
執(zhí)行用時(shí)：4 ms, 在所有 Rust 提交中擊敗了78.24%的用戶
內(nèi)存消耗：2.2 MB, 在所有 Rust 提交中擊敗了61.77%的用戶
通過(guò)測(cè)試用例：
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>();
}
}
