【字符串, 找规律】Z 字形变换

题目

6. 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

解题

方法一：找规律

思路

对于输入的字符串 s，其下标 i / (numRows-1) ：

• 如果为偶数或零，则代表该下标代表的字符在Z字型中属于竖列。
• 如果为奇数，则代表该下标代表的字符在Z字型中属于斜列（Z字型的中间倾斜部分）。
• 如果当前字符属于竖列，则按照正序依次保存在字符串数组 rows 中：rows[k].append(s[i])
• 如果属于斜列，则逆序保存：rows[numRows-k-1].append(s[i])

最后把 rows 数组中的字符串全部拼起来返回即可。

代码

class Solution {
    public String convert(String s, int numRows) {
        if (numRows == 1) return s;
        StringBuilder[] rows = new StringBuilder[numRows];
        for (int i = 0; i < numRows; i++) rows[i] = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            int k = i % (numRows - 1);
            if ((i / (numRows - 1) & 1) == 0) rows[k].append(ch);
            else rows[numRows - k - 1].append(ch);
        }
        StringBuilder ans = new StringBuilder();
        for (StringBuilder sb : rows) ans.append(sb);
        return ans.toString();
    }
}

找规律2：

例如对一个4行的：

0     6      12       18
1   5 7   11 13    17
2 4   8 10   14 16
3     9      15

对于 n 行的, s 中的第 i 个字符：

• i%(2n-2) == 0 ----> row 0
• i%(2n-2) == 1 or 2n-2-1 ----> row 1
• i%(2n-2) == 2 or 2n-2-2 ----> row 2
• …
• i%(2n-2) == n-1 ----> row n-1

结论：

对 k = i%(2n-2) 进行判断

• $k \leq n-1$ 时：s[i] 属于第 k 行
• $k>n-1$ 时：s[i] 属于 2n-2-k 行

最后将 rows 拼接起来就行了。

class Solution {
    public String convert(String s, int numRows) {
        if (numRows == 1) return s;
        StringBuilder[] rows = new StringBuilder[numRows];
        for (int i = 0; i < numRows; i++) rows[i] = new StringBuilder();
        final int C = 2 * numRows - 2;
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            int k = i % C;
            if (k <= numRows - 1) rows[k].append(ch);
            else rows[C - k].append(ch);
        }
        StringBuilder ans = new StringBuilder();
        for (StringBuilder sb : rows) ans.append(sb);
        return ans.toString();
    }
}