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.对于每个字符 sj，将其填入字符数组 ans 中，并将 fill 指针向后移动一位。如果该字符所在的行不是第 0 行和最后一行，并且在下一个周期中对应的位置 nextColTop-i 小于字符串的长度 n，则将 snextColTop-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: Vecchar>
     = 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;

}
    

声明：本文内容由网友自发贡献，本站不承担相应法律责任。对本内容有异议或投诉，请联系2913721942#qq.com核实处理，我们将尽快回复您，谢谢合作！