LeetCode 6 Z字形变换

1 题目描述

给定字符串,以Z字形显示。如"PAYPALISHIRING"以给定行数为3的Z字形显示为:

然后从左到右一行一行拼起来为:“PAHNAPLSIIGYIR”。

现在,传入一个字符串及行数,请编写代码求该字符串的Z字形变换。

例子1:

输入:s = “PAYPALISHIRING”, numRows = 3

输出:“PAHNAPLSIIGYIR”

例子2:

输入:s = “PAYPALISHIRING”, numRows = 4

输出:“PINALSIGYAHRPI”

释义:

题目出处:

https://leetcode.com/problems/zigzag-conversion/

2 解决思路

如下图所示:

a)最顶部和最底部水平方向两字母之间最大间隔maxInterval为2 * (numRows-1);

b)i从0开始,第i行,自左向右,奇数序号水平方向两字母之间距离interval为2 * (numRows-1) - i*2,偶数序号水平方向两字母之间距离为maxInterval - interval;

c) 根据此规律,可以构造字符串的Z字形显示结果。

3 golang实现代码

https://github.com/olzhy/leetcode/blob/master/6_ZigZag_Conversion/test.go

func convert(s string, numRows int) string {
    if numRows < 2 {
        return s
    }
    maxInterval := (numRows - 1) << 1
    interval := maxInterval
    after := ""
    for i := 0; i < numRows; i++ {
        if numRows-1 == i {
            interval = maxInterval
        }
        for j, no := i, 0; j < len(s); no++ {
            after += string(s[j])
            if i > 0 && i < numRows-1 && 1 == no&1 {
                j += maxInterval - interval
                continue
            }
            j += interval
        }
        interval -= 2
    }
    return after
}
若觉得文章对您有所帮助,可以请我喝杯咖啡,Thanks!
微信 支付宝