题目描述

将一个给定字符串根据给定的行数，以从上往下、从左到右进行 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
                                                                                            

(全文完)

8 次阅读