2023-04-28：将一个给定字符串 s 根据给定的行数 numRows 以从上往下、从左到右进行 Z 字形排列比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下 P A H NA P L S I I GY 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;}
复制代码
评论