力扣6:Z字变换

崩天的勾玉
崩天的勾玉
崩天的勾玉
65
文章
4
评论
2021年5月31日09:13:17
评论
5 1125字

其实是竖着的Z字,标题不是很清楚。https://leetcode-cn.com/problems/zigzag-conversion/

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

比如输入字符串为 "PAYPALISHIRING" 行数为 3 时,排列如下:

P A H N
A P L S I I G
Y I R

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

请你实现这个将字符串进行指定行数变换的函数。

class Solution {
    public String convert(String s, int numRows) {
    if (numRows == 1)
        return s;

    StringBuilder ret = new StringBuilder();
    int n = s.length();

    //竖z字形中一竖一斜设为一周期,字符数为2rows-2
    int cycleLen = 2 * numRows - 2;

    //i是行数,j是上端点,i+j是下标, j+cycleLen-i是↗部分的下标
    for (int i = 0; i < numRows; i++) {
        for (int j = 0; j + i < n; j += cycleLen) { //每次加一个周期
            ret.append(s.charAt(j + i)); //第0行和最后一行以及每个周期⇣的部分
            if (i != 0 && i != numRows - 1 && j + cycleLen - i < n) //除去第 0 行和最后一行的部分
                ret.append(s.charAt(j + cycleLen - i));//每个周期↗的部分
    }
    return ret.toString();
    }
}

其实就是找规律,找到规律就好写。

我们可以看到,图形其实是有周期的,0,1,2 ... 7 总过 8 个,然后就又开始重复相同的路径。周期的计算就是 cycleLen = 2 × numRows - 2 = 2 × 5 - 2 = 8 个。

我们发现第 0 行和最后一行一个周期内有一个字符,所以第一个字符下标是 0 ,第二个字符下标是 0 + cycleLen = 8,第三个字符下标是 8 + cycleLen = 16 。
相邻周期内竖着的部分都是相差一个周期,斜着的部分为当前周期第零行下标-行数。

其他行都是两个字符。

第 1 个字符和第 0 行的规律是一样的。

第 2 个字符其实就是下一个周期的第 0 行的下标减去当前行。什么意思呢?

我们求一下第 1 行第 1 个周期内的第 2 个字符,下一个周期的第 0 行的下标是 8 ,减去当前行 1 ,就是 7 了。

我们求一下第 1 行第 2 个而周期内的第 2 个字符,下一个周期的第 0 行的下标是 16 ,减去当前行 1 ,就是 15 了。

我们求一下第 2 行第 1 个周期内的第 2 个字符,下一个周期的第 0 行的下标是 8 ,减去当前行 2 ,就是 6 了。

当然期间一定要保证下标小于 n ,防止越界。

发表评论

匿名网友