LEETCODE 6. Z 字形变换
题目描述
将一个给定字符串根据给定的行数,以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 “LEETCODEISHIRING” 行数为 3 时,排列如下:
L C I R
E T O E S I I G
E D H N
之后,你的输出需要从左往右逐行读取,产生出一个新的字符串,比如:"LCIRETOESIIGEDHN"
。
请你实现这个将字符串进行指定行数变换的函数:
string convert(string s, int numRows);
示例 1:
输入: s = "LEETCODEISHIRING"
, numRows = 3
输出: "LCIRETOESIIGEDHN"
示例 2:
输入: s = "LEETCODEISHIRING"
, numRows = 4
输出: "LDREOEIIECIHNTSG"
解释:
L D R
E O E I I
E C I H N
T S G
题目地址: https://leetcode-cn.com/problems/zigzag-conversion/
题解
以"1234567890abcdefg"
为例,先看下变换的动态图:
这就相当于我们创建了numRows
个数组,然后遍历字符串,并将遍历到的字符往数组里面放,第一个字符放到arr[0]
中,第二个放到arr[1]
中,第numRows-1个字符放到arr[numRows-1]
。
而到了arr[numRows-1]
之后,就要开始反向走了,arr[numRows-2]
,arr[numRows-3]
,一直到arr[0]
。
所以这个过程是不断的往下、往上、往下、往上如此反复。
但是第一行
和最后一行
特殊,当遍历到第一行时,整个顺序就要往下,而遍历到最后一行时,遍历顺序就要往上。
我们只需要一个特殊的标志位,根据是否是第一行
或者最后一行
来判断是否要向上或者向下。
当nunRows个数组都按顺序放好后,就挨个把他们拼接起来,最后返回。
19g
280f
37ae
46bd
5c
时间复杂度:O(N)
空间复杂度:O(N)
java代码:
class Solution { public String convert(String s, int numRows) { if(s==null || numRows<=1) { return s; } int n = s.length(); //取numRows,字符串s长度的较小值,用这个较小值来创建n个StringBuilder int rows = Math.min(n,numRows); StringBuilder[] arr = new StringBuilder[rows]; for(int i=0;i<arr.length;++i) { arr[i] = new StringBuilder(); } int j = 0; //向上还是向下的标志位 boolean isDown = false; StringBuilder res = arr[0]; //遍历字符串s,并将字符放到arr[j]中,之后根据标志位来判断是继续往下还是往上 for(int i=0;i<n;++i) { arr[j].append(s.charAt(i)); if(j==0 || j==numRows-1) { isDown = !isDown; } if(isDown) { ++j; } else { --j; } } //将数组中的字符串挨个合并最后返回 for(int i=1;i<arr.length;++i) { res.append(arr[i]); } return res.toString(); } }
python代码:
class Solution(object): def convert(self, s, numRows): if not s or numRows<=1: return s # 取numRows,字符串s长度的较小值,用这个较小值来创建n个StringBuilder res = [[] for _ in xrange(min(numRows,len(s)))] # 向上还是向下的标志位 is_going_down = False n = len(s) j = 0 string = "" # 遍历字符串s,并将字符放到arr[j]中,之后根据标志位来判断是继续往下还是往上 for i in xrange(n): res[j].append(s[i]) if j==0 or j==numRows-1: is_going_down = not is_going_down j = j+1 if is_going_down else j-1 # 将数组中的字符串挨个合并最后返回 for i in res: string += "".join(i) return string
(全文完)
11 次阅读