[LeetCode]题解（python）：006-ZigZag Conversion

题目来源：

https://leetcode.com/problems/zigzag-conversion/

题意分析：

这道题目是字符串处理的题目。输入一个字符串和一个数字，将字符串填入倒Z形输入字符串，然后按照列读取字符，得到一个新的字符，输出这个字符。例如：字符串"PAYPALISHIRING",3

P		A		H		N
A	P	L	S	I	I	G
Y		I		R

得到的新字符是”PAHNAPLSIIGYIR”。

题目思路：

这题只是简单的字符串处理。首先，我们可以对Z形字符串进行简单优化一下，将Z中的“折”合起来。比如：“ABCDEFGHIJKL”，4

A			G
B		F	H		L
C	E		I	K
D			J

优化后：

A		G
B	F	H	L
C	E	I	K
D		J

不难发现，得到的结果不变，而列表的列数减少了。在C和C++中可以直接定义一个二维数组，将字符读入，然后直接读取即可。但是用python初始化列表比较麻烦，我觉得直接通过下标规律可以直接得到，第一行和最后一行下一个下标是上一个+ 2*numRows – 2;而其他是先+ 2*（numRows - i） – 2 再+ 2*i，i是第几行。

代码（python）：

 1 class Solution(object):
 2     def convert(self, s, numRows):
 3         """
 4         :type s: str
 5         :type numRows: int
 6         :rtype: str
 7         """
 8         size = len(s)
 9         if size <= numRows or numRows == 1:
10             return s
11         ans = ''
12         i = 0
13         while i < numRows:
14             j = i
15             if i == 0 or i == numRows - 1:
16                 while j < size:
17                     ans += s[j]
18                     j += 2*numRows - 2
19                     if 2 * numRows - 2 == 0:
20                         break
21             else:
22                 while j < size:
23                     ans += s[j]
24                     j += 2*(numRows - i) - 2
25                     if j >= size:
26                         break
27                     ans += s[j]
28                     j += 2*i
29             i += 1
30         return ans

View Code

转载请注明出处：http://www.cnblogs.com/chruny/p/4798575.html