Golang算法之Z字形变换

发表于 | 更新于 | 分类于 | 浏览数
| 字数统计 724

Z字形变换，中等难度，leetcode地址：https://leetcode-cn.com/problems/zigzag-conversion

1.描述

将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 “PAYPALISHIRING” 行数为 3 时，排列如下：

1
2
3
P   A   H   N 
A P L S I I G 
Y   I   R

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如：”PAHNAPLSIIGYIR”。

示例 1：

1
2
输入：s = "PAYPALISHIRING", numRows = 3
输出："PAHNAPLSIIGYIR"

示例 2：

1
2
3
4
5
6
7
输入：s = "PAYPALISHIRING", numRows = 4
输出："PINALSIGYAHRPI"
解释：
P     I    N
A   L S  I G
Y A   H R
P     I

2.题解

第一眼看到这个题我是懵逼的，什么Z字形，我怎么看也看不出是Z字形，这明明是N字形啊。。。这题的描述确实有点问题。

大家都知道，电脑显示器在刷新画面的时候都是一行行产生，并不是竖着，所以如果要打印出这种带图形的结构，我们就需要计算出哪些地方该显示空白，哪些地方显示字符。

这道题解题的关键在于总结规律，我们可以把这3行看作是一个数组前3个元素，前下标依次为为 0 1 2，每个元素都是一个数组，说白了，就是一个2维数组

然后依次把字符串的每个字符放进这个数组对应的位置，追加到对应下标位置的数组里面，但是每个字符放置的数组下标满足一定规律：

从 p = 0 开始，同时初始化flag = -1

  • 把字符串放到下标 p 位置的数组里面

  • 当 p 等于 0或者2 的时候，flag = -flag

  • p = p + flag

按照以上算法:

1
2
3
4
5
6
7
p = 0, flag =  1, p = 1
p = 1, flag =  1, p = 2
p = 2, flag = -1, p = 1
p = 1, flag = -1, p = 0
p = 0, flag =  1, p = 1
p = 1, flag =  1, p = 2
...

如此往复，我们会发现通过控制反转flag的值，就可以控制下标的位置，这里面值得一提的是为什么0或者2的时候才反转，这恰恰是数组的2头，假如数组长度是5，那就应该是0或者4。

参考代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func convert(s string, numRows int) string {
    if numRows < 2 {
        return s
    }
    var (
        arr  = make([][]string, numRows) // 二维数组
        i    = 0
        flag = -1
    )
    for _, v := range s {
        arr[i] = append(arr[i], string(v))
        if i == 0 || i == numRows-1 {
            flag = - flag
        }
        i += flag
    }

    // 按顺序拼接二维数组各个元素
    var result string
    for _, v := range arr {
        result += strings.Join(v, "")
    }
    return result
}

掌握了窍门之外编码就简单了，但是实测这种解法击败的人数不超过10%，毕竟开辟了新内存和循环了多次，复杂度N。