2023-04-28：将一个给定字符串 s 根据给定的行数 numRows以从上往下、从左到右进行 Z 字形排列比如输入字符串为

福大大架构师每日一题

发布于 2023-06-09 02:06:10

28400

代码可运行

运行总次数：0

代码可运行

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;
}