Z字形变换 | 梧席

题目描述

将一个给定字符串 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);

示例 1：

输入：s = “PAYPALISHIRING”, numRows = 3
输出：”PAHNAPLSIIGYIR”

示例 2：

输入：s = “PAYPALISHIRING”, numRows = 4
输出：”PINALSIGYAHRPI”

解释：
P I N
A L S I G
Y A H R
P I

示例 3：

输入：s = “A”, numRows = 1
输出：”A”

提示：

1 <= s.length <= 1000
s 由英文字母（小写和大写）、’,’ 和 ‘.’ 组成
1 <= numRows <= 1000

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/zigzag-conversion
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

我的答案

func convert(s string, numRows int) string {
    // 通过一个numRows维数组存储
    if numRows == 1{
        return s
    }
    str := make([][]rune,numRows)
    h,flag := 0,1;
    for i,r := range s{
        str[h] = append(str[h],r)
        if i != 0 && i % (numRows-1) == 0{
            flag = -flag
        }
        h = h + flag
    }
    result := ""
    for _,i := range str{
        for _,j := range i{
            result += string(j)
        }
    }
    return result
}

思路：用 numRows 维数组 str 存储每一行的符文集，如 str[0] 就存储第一行的字符集， numRows 为0时直接返回原字符串，否则通过每次加 flag 来进行标记， flag 在 Z 的拐角处进行异号处理。最后将每一行的符文集串接起来返回一个字符串 result 。

解题思路

输入”ABCDEFGHIJKLMNOPQRSTUVWXYZ”和参数5后，得到答案”AGMSYBFHLNRTXZCEIKOQUWDJPV”，按照题目的摆放方法，可得：

A   I   Q   Y
B  HJ  PR  XZ
C G K O S W
DF  LN  TV
E   M   U

可以看到，各行字符在原字符串中的索引号为

0行，0, 8, 16, 24
1行，1, 7,9, 15,17, 23,25
2行，2, 6, 10, 14, 18, 22
3行，3,5, 11,13, 19,21
4行，4, 12, 20

令p=numRows×2-2，可以总结出以下规律

0行， 0×p，1×p，…
r行， r，1×p-r，1×p+r，2×p-r，2×p+r，…
最后一行， numRow-1, numRow-1+1×p，numRow-1+2×p，…

只需编程依次处理各行即可。

题解

import (
	"bytes"
)

func convert(s string, numRows int) string {
	if numRows == 1 || len(s) <= numRows {
		return s
	}

	res := bytes.Buffer{}
	// p pace 步距
	p := numRows*2 - 2

	// 处理第一行
	for i := 0; i < len(s); i += p {
		res.WriteByte(s[i])
	}

	// 处理中间的行
	for r := 1; r <= numRows-2; r++ {
		// 添加r行的第一个字符
		res.WriteByte(s[r])

		for k := p; k-r < len(s); k += p {
			res.WriteByte(s[k-r])
			if k+r < len(s) {
				res.WriteByte(s[k+r])
			}
		}
	}

	// 处理最后一行
	for i := numRows - 1; i < len(s); i += p {
		res.WriteByte(s[i])
	}

	return res.String()
}

注意第24-29行处理中间每一行的操作，它将两个字符同时处理，避免了 for 循环头部对终止条件的多情况判定。

总结

归纳法