2023-04-28：将一个给定字符串 s 根据给定的行数 numRows 以从上往下、从左到右进行 Z...
source link: https://blog.51cto.com/u_14891145/6235470
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
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;
}
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK