2023-04-28：将一个给定字符串 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)。
答案2023-04-28：
算法过程大体可以分为以下步骤：
1.计算给定字符串 s 的长度 n 和指定行数 numRows。
2.如果 numRows 等于 1 或者 numRows 大于等于 n，则返回原始字符串 s。
3.计算一个周期 t，其值为 2 * (numRows - 1)。
4.创建一个字符数组 ans，其长度与输入字符串 s 相同，并用空格符初始化。
5.根据 Z 字形排列的规律，按顺序遍历每一行 i（从第 0 行到第 numRows-1 行）及其对应的列 j（每一列长度为 t）。在遍历的过程中，根据当前所在行的位置 i 和周期 t，计算出对应列的顶部的行号 nextColTop。
6.对于每个字符 s[j]，将其填入字符数组 ans 中，并将 fill 指针向后移动一位。如果该字符所在的行不是第 0 行和最后一行，并且在下一个周期中对应的位置 nextColTop-i 小于字符串的长度 n，则将 s[nextColTop-i] 也填入 ans 数组中，并将 fill 指针再次向后移动一位。
7.遍历完所有行和列后，将字符数组 ans 转换为字符串并返回。
时间复杂度：O(n)，其中 n 是字符串 s 的长度。我们只需要遍历一次字符串 s。
空间复杂度：O(n)，我们需要使用一个字符数组 ans 存储变换后的字符串，数组的大小为输入字符串 s 的长度 n。另外，我们还使用了常数级别的额外空间存储变换时需要的一些变量。
go完整代码如下：
package main
import "fmt"
func convert(s string, row int) string {
n := len(s)
if row == 1 || row >= n {
return s
}
t := 2 * (row - 1)
ans := make([]byte, n)
fill := 0
for i := 0; i < row; i++ {
nextColTop := t
for j := i; j < n; j += t {
ans[fill] = s[j]
fill++
if i >= 1 && i <= row-2 && nextColTop-i < n {
ans[fill] = s[nextColTop-i]
fill++
}
nextColTop += t
}
}
return string(ans)
}
func main() {
s := "PAYPALISHIRING"
result := convert(s, 3)
fmt.Println(result)
}
rust完整代码如下：
fn convert(s: String, row: i32) -> String {
let n = s.chars().count();
if row == 1 || row >= n as i32 {
return s;
}
let t = 2 * (row - 1);
let mut ans: Vec<char> = vec![' '; n];
let mut fill = 0;
for i in 0..row {
let mut next_col_top = t;
for j in (i as usize..n).step_by(t as usize) {
ans[fill] = s.chars().nth(j).unwrap();
fill += 1;
if i >= 1 && i <= row - 2 && next_col_top - i < n as i32 {
ans[fill] = s.chars().nth((next_col_top - i) as usize).unwrap();
fill += 1;
}
next_col_top += t;
}
}
ans.iter().collect()
}
fn main() {
let s = "PAYPALISHIRING".to_string();
let result = convert(s, 3);
println!("{}", result);
}
c++完整代码如下：
#include <iostream>
#include <string>
using namespace std;
string convert(string s, int row) {
int n = s.length();
if (row == 1 || row >= n) {
return s;
}
int t = 2 * (row - 1);
string ans(n, ' ');
int fill = 0;
for (int i = 0; i < row; i++) {
int nextColTop = t;
for (int j = i; j < n; j += t, nextColTop += t) {
ans[fill++] = s[j];
if (i >= 1 && i <= row - 2 && nextColTop - i < n) {
ans[fill++] = s[nextColTop - i];
}
}
}
return ans;
}
int main() {
string s = "PAYPALISHIRING";
string result = convert(s, 3);
cout << result << endl;
return 0;
}
c完整代码如下：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char* convert(char* s, int row) {
int n = strlen(s);
if (row == 1 || row >= n) {
return s;
}
int t = 2 * (row - 1);
char* ans = (char*)malloc(sizeof(char) * (n + 1));
memset(ans, ' ', sizeof(char) * n);
int fill = 0;
for (int i = 0; i < row; i++) {
int nextColTop = t;
for (int j = i; j < n; j += t, nextColTop += t) {
ans[fill++] = s[j];
if (i >= 1 && i <= row - 2 && nextColTop - i < n) {
ans[fill++] = s[nextColTop - i];
}
}
}
ans[n] = '\0';
return ans;
}
int main() {
char s[] = "PAYPALISHIRING";
char* result = convert(s, 3);
printf("%s\n", result);
free(result);
return 0;
}
