Z 字形变换-python

leetCode第6题 Z 字形变换
链接：https://leetcode-cn.com/problems/zigzag-conversion

将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 “PAYPALISHIRING” 行数为 3 时，排列如下：

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

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如：“PAHNAPLSIIGYIR”。

请你实现这个将字符串进行指定行数变换的函数：

string convert(string s, int numRows);

示例 1：

输入：s = "PAYPALISHIRING", numRows = 3
输出："PAHNAPLSIIGYIR"

示例 2：

输入：s = "PAYPALISHIRING", numRows = 4
输出："PINALSIGYAHRPI"

解释：

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

示例 3：

输入：s = "A", numRows = 1
输出："A"

提示：

1 <= s.length <= 1000
s 由英文字母（小写和大写）、',' 和 '.' 组成
1 <= numRows <= 1000

很简单的一道题，我们来分析一下
题目要求我们需要根据给出的行数将字母进行一个Z字形的排列，然后逐行拼接成一个字符串。
首先考虑暴力算法怎么解决，然后进行优化。
首先我们需要摸清楚规律

不妨将Z字形进行一个拆分，将一竖到另一竖之间作为一组。
那么我们进行观察，一组中包含了row + (row-2)个元素，因为第一列占满，其余一列只放一个元素，那么一组就是 2(row-1)个元素。我们求出给定字符串的长度，然后除以一组的个数就能得出我们需要多少个组。
那么一组有多少列呢？显然时 1 + row -2 = row -1列，这样组数$\times$一组的列数 = 总共列数。
这样我们就可以得出我们用来排列的二维列表有多大。

接下来定义r,c两个坐标表明我们需要将元素排在列表的位置。
逐个取出字符串的元素填入对应的位置。
关键是r,c怎么变化。
当在每一组的第一列的时候，c时不变的，让r+1，将这一列填满。当这一竖填满后，要将r向上移动，c向右移动，知道下一竖。那么我们怎么定义到了Z字的那一竖呢？只要当前的列数c%(row -1)==0就意味着我们到了下一组。
然后不断重复直到字符串的所有元素被取完。

## python3
class Solution:def convert(self, s: str, numRows: int) -> str:num =int( len(s) / (2 * (numRows - 1)) ) + 1numColunms = (numRows - 1) * numres = [ [0 for i in range(numColunms)] for i in range(numRows)]r,c = 0,0for i in range(len(s)):x = s[i]res[r][c] = xif c % (numRows-1) == 0:r += 1if r == (numRows):c += 1r -= 2else:r -= 1c += 1res_str = ""for i in range(len(res)):for j in range(len(res[0])):if res[i][j] != 0:res_str += res[i][j]return  res_str

这样写的执行效率很低，效果很不理想，我们需要进行优化。

我们观察r,c的变化，发现，r增加到最底部时就要一格一格返回最顶部，而c只是在不同的时机一直向右移动。
在上一种写法中，我们定义的res列表用大量的0元素填充，这些零和指针c是不是可以去掉呢？
python提供了列表灵活的操作方式，c只会向右移，元素只会在右边添加，append()方法就能实现，而且我们也不需要知道列表到底应该有多少列。
我们通过r的变化，在合适的位置将元素append()进去就行了。
当r没到底部时就一直自增，触底了就反弹，通过r指针告诉我们在哪一行append就行了。

class Solution:def convert(self, s: str, numRows: int) -> str:res,row,i = [[] for i in range(numRows)],0,0while i < len(s):if row == numRows:row -= 1while row > 1 and i < len(s):row -= 1res[row].append(s[i])i += 1row -= 1continueres[row].append(s[i])row += 1i += 1str1 = ''for each in res:for each1 in each:str1 += str(each1)return str1

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！