将一个给定字符串s根据给定的行数numRows,以从上往下、从左到右进行Z字形排列。
比如输入字符串为 “PAYPALISHIRING” 行数为 3 时,排列如下:
1 | P A H N |
之后,你的输出需要从左往右逐行读取,产生出一个新的字符串,比如:”PAHNAPLSIIGYIR”。
请你实现这个将字符串进行指定行数变换的函数:
string convert(string s, int numRows);
示例 1:
1 | 输入:s = "PAYPALISHIRING", numRows = 3 |
示例 2:
1 | 输入:s = "PAYPALISHIRING", numRows = 4 |
示例 3:
1 | 输入:s = "A", numRows = 1 |
提示:
1 <= s.length <= 1000
s 由英文字母(小写和大写)、’,’ 和 ‘.’ 组成
1 <= numRows <= 1000
直接解法
我们可以先将重组后的字符分成n个子串,观察很好发现,若i为字符串下标(从0开始),j = i % (2 \* numRows - 2)
,当j小于numRows时,此字符将正好是第j个子串的字符;当j大于等于numRows时,此时反过来,是第(2 \* numRows - 2) - j
个字串的字符;顺序就正好按照原来的顺序即可,最后将字串按照顺序接上即可组成符合题意的字符串,详见代码。
code
1 | func convert(s string, numRows int) string { |
分析
- 时间复杂度:O(n)
- 空间复杂度:O(n)