LEETCODE 6. Z 字形变换

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
                                                                                            

(全文完)

7 次阅读

发表评论

电子邮件地址不会被公开。