leetcode_rust/problems_cn/p000_0xx/p000_006.rs
1//! # 题目描述
2//!
3//! 将一个给定字符串 `s` 根据给定的行数 `numRows` ,以从上往下、从左到右进行 Z 字形排列。
4//!
5//! 比如输入字符串为 "PAYPALISHIRING" 行数为 3 时,排列如下:
6//!
7//! ```plain
8//! P A H N
9//! A P L S I I G
10//! Y I R
11//! ```
12//!
13//! 之后,你的输出需要从左往右逐行读取,产生出一个新的字符串,比如:"PAHNAPLSIIGYIR"。
14//!
15//! 请你实现这个将字符串进行指定行数变换的函数:
16//!
17//! `string convert(string s, int numRows);`
18//!
19//! | 示例 1 |
20//! | :-- |
21//! | 输入:s = "PAYPALISHIRING", numRows = 3 |
22//! | 输出:"PAHNAPLSIIGYIR" |
23//!
24//! | 示例 2 |
25//! | :-- |
26//! | 输入:s = "PAYPALISHIRING", numRows = 4 |
27//! | 输出:"PINALSIGYAHRPI" |
28//!
29//! 解释:
30//!
31//! ```plain
32//! P I N
33//! A L S I G
34//! Y A H R
35//! P I
36//! ```
37//!
38//! | 示例 3 |
39//! | :-- |
40//! | 输入: s = "A", numRows = 1 |
41//! | 输出:"A" |
42//!
43//! 提示:
44//!
45//! - `1 <= s.length <= 1000`
46//! - `s` 由英文字母(小写和大写)、',' 和 '.' 组成
47//! - `1 <= numRows <= 1000`
48//!
49//! 来源:<https://leetcode.cn/problems/zigzag-conversion>
50
51////////////////////////////////////////////////////////////////////////////////
52
53/// 用于选择要执行的算法的 Enum
54pub enum Algorithm {
55 /// 使用栈数组实现的字形变换
56 STACK = 0,
57
58 /// 使用二维数组实现的字形变换
59 MATRIX = 1,
60}
61
62/// Z 字形变换
63///
64/// 可以通过第三个参数选择要使用的算法
65///
66/// ### Arguments
67/// * `s` - 等待变换的字符串
68/// * `n_rows` - 变换后的行数
69///
70/// ```
71/// use leetcode_rust::problems_cn::p000_0xx::p000_006::zigzag_conversion;
72/// let mut result_value = zigzag_conversion(String::from("PAYPALISHIRING"), 1, None);
73/// assert_eq!(result_value, String::from("PAYPALISHIRING"));
74/// result_value = zigzag_conversion(String::from("PAYPALISHIRING"), 2, None);
75/// assert_eq!(result_value, String::from("PYAIHRNAPLSIIG"));
76/// result_value = zigzag_conversion(String::from("PAYPALISHIRING"), 3, None);
77/// assert_eq!(result_value, String::from("PAHNAPLSIIGYIR"));
78/// ```
79pub fn zigzag_conversion(s: String, n_rows: i32, alg: Option<Algorithm>) -> String {
80 match alg.unwrap_or(Algorithm::STACK) {
81 Algorithm::MATRIX => convert_s1(s, n_rows as usize),
82 Algorithm::STACK => convert_s2(s, n_rows),
83 }
84}
85
86#[cfg(test)]
87#[test]
88fn test_zigzag_conversion() {
89 assert!(zigzag_conversion(String::from("PAPAL"), 1, None) == String::from("PAPAL"));
90}
91
92/// Z 字形变换(解法一)
93///
94/// 使用二维矩阵设计的算法
95///
96/// ### Arguments
97/// * `s` - 等待变换的字符串
98/// * `n_cols` - 变换后的列数
99#[allow(unused_assignments)]
100fn convert_s1(s: String, n_cols: usize) -> String {
101 let mut cur_row = 0u16;
102 let mut cur_col = 0u16;
103 let mut n_rows = 1;
104
105 // Considering max string length 1_000 ASCII characters, minimum 1 column,
106 // max row count would be 1_000.
107 let mut arr = vec![0u8; n_cols * 1000];
108 let mut direction = 0; // 0 for GO, 1 for TURN
109 let mut conv_idx = 0usize;
110 while conv_idx < s.len() {
111 // Set value of current pos
112 arr[cur_row as usize * n_cols + cur_col as usize] = s.as_bytes()[conv_idx];
113 conv_idx += 1;
114 // Calculate next coordinate and direction
115 if cur_col == 0 {
116 if n_cols > 1 {
117 if direction == 1 {
118 direction = 0;
119 }
120 cur_col += 1;
121 } else {
122 // Move to next row directly because only 1 column needed.
123 cur_row += 1;
124 n_rows += 1;
125 }
126 } else {
127 if direction == 0 {
128 if cur_col < n_cols as u16 - 1 {
129 // Only move to the right
130 cur_col += 1;
131 } else {
132 // Last position, change direction and move to next row
133 direction = 1;
134 cur_col -= 1;
135 cur_row += 1;
136 n_rows += 1;
137 }
138 } else {
139 // Move to left and below
140 cur_col -= 1;
141 cur_row += 1;
142 n_rows += 1;
143 }
144 }
145 }
146
147 conv_idx = 0;
148 let mut output = vec![0u8; s.len()];
149 cur_row = 0;
150 cur_col = 0;
151 let mut str_idx = 0;
152 while conv_idx < s.len() {
153 // Update value if not 0u8
154 str_idx = cur_row as usize * n_cols + cur_col as usize;
155 if arr[str_idx] != 0u8 {
156 output[conv_idx] = arr[str_idx];
157 conv_idx += 1;
158 }
159 // Change position.
160 if cur_row < n_rows - 1 {
161 cur_row += 1;
162 } else {
163 cur_row = 0;
164 cur_col += 1;
165 }
166 }
167 String::from_utf8(output.to_vec()).unwrap()
168}
169
170#[cfg(test)]
171#[test]
172fn test_conversion_s1() {
173 assert!(convert_s1(String::from("PAPAL"), 1) == String::from("PAPAL"));
174}
175
176/// Z 字形变换(解法二)
177///
178/// 使用栈数组设计的算法
179///
180/// ### Arguments
181/// * `s` - 等待变换的字符串
182/// * `n_rows` - 变换后的行数
183fn convert_s2(s: String, num_rows: i32) -> String {
184 let mut rows = vec![String::new(); num_rows as usize];
185
186 let mut cur_row: i32 = 0;
187 let mut go_down: bool = true;
188 for val in s.bytes() {
189 rows[cur_row as usize].push(val as char);
190 if !go_down && cur_row == 0 {
191 go_down = true;
192 } else if go_down && cur_row == num_rows - 1 {
193 go_down = false;
194 }
195
196 if go_down {
197 cur_row += 1;
198 } else {
199 cur_row -= 1;
200 }
201
202 cur_row = i32::min(num_rows - 1, cur_row);
203 cur_row = i32::max(0, cur_row);
204 }
205
206 rows.join("").to_string()
207}
208
209#[cfg(test)]
210#[test]
211fn test_conversion_s2() {
212 assert!(convert_s2(String::from("PAPAL"), 2) == String::from("PPLAA"));
213}