侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 675 篇文章
  • 累计创建 128 个标签
  • 累计收到 29 条评论

目 录CONTENT

文章目录

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

GabrielxD
2022-06-06 / 0 评论 / 0 点赞 / 277 阅读 / 741 字
温馨提示:
本文最后更新于 2022-07-26,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

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) 进行判断

  • kn1k \leq n-1 时:s[i] 属于第 k
  • k>n1k>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();
    }
}
0

评论区