leetcode6. Z 字形变换python_字符串

题目

将一个给定字符串 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

思路和代码

这题我曾经刷过，然后再刷想了很久才通过，看了之前提交的代码，原来是官方的代码。而且官方的代码和自己想出来的代码思路还不一样，这说明什么，说明自己进步了嘛。

自己思路

就是想得很繁琐复杂，就是找规律。

首先第一行和最后一行字母间隔都是相同的，为numRows-1（第一列剩下的个数） + numRows-2（z中间的个数） +1（索引要加一），也就是2*numRows-2。中间的行两个字符间隔的是周期性的一大一小，两种间隔，一种间隔是numRows-1-i （这个数下面的字符个数）+ numRows-1-1-i （z中间到该行下一个字符的个数）+1（下标），另一种间隔是i（这个数下面的字符个数）+i-1（z中间到该行下一个字符的个数）+1（下标）。两种间隔交替出现。最后把每行的结果进行拼接。

代码：

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        res = ""
        n = len(s)
        if numRows == 1:
            return s
        # 第一行两个字母之间的间隔 
        # 前面是第一列剩下的个数 后面是“z”中间的个数 索引加一
        # numRows-1 + numRows-2 +1
        count = 2*numRows - 2
        for i in range(0,n, count):
            res += s[i]
        for i in range(1,numRows-1):    
            jiange1 = numRows- i -1 + numRows-i -1 - 1+1
            jiange2 = i +i-1+1     
            c = 0
            j = i
            while j < n:
                if c%2 == 0:
                    res += s[j]         
                    j += jiange1       
                else:
                    res += s[j]        
                    j += jiange2
                c += 1 
        for i in range(numRows-1,n, count):
            res += s[i]
        return res
                    
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

我脑子可太聪明了，那么繁琐的代码都能被我想到（狗头）。

官方模拟思路

看了之前提交的官方写的代码，唉，有些代码看不懂了。其实思路也很好想，我也想到过这个思路。不过当时列数的计算感觉有点麻烦就没有细想。官方给的就是模拟，先计算z字形需要多少行（已知）多少列，然后一个个填充字母，最后拼接而成。

代码：

        n, r = len(s), numRows
        if r == 1 or r >= n:
            return s
        # 和我的count是一个意思么 第一行和最后一行两个字母间隔数
        t = r * 2 - 2
        # c是列数 计算公式怎么得来的？
        c = (n + t - 1) // t * (r - 1)
        mat = [[''] * c for _ in range(r)]
        x, y = 0, 0
        for i, ch in enumerate(s):
            mat[x][y] = ch
            #这个if判断句不是很懂
            if i % t < r - 1:
                x += 1  # 向下移动
            else:
                x -= 1
                y += 1  # 向右上移动
        return ''.join(ch for row in mat for ch in row if ch)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

接下来对我注释的部分进行解释说明。第一个t表示的是一个周期，其实感觉和我计算的第一行和最后一行两个字符的间隔计算方式一样，就是表达的意思不太一样。这个t是怎么计算得来的？numRows（第一列元素的个数） + numRows-2（z中间元素个数），也就是t= 2*numRows-2。

代码中的c是列数是怎么计算得到的？列数=周期的个数*（每个周期的列数）。周期的个数就是s的长度除以周期t，每个周期所用的列数是1 + numRows-2，也就是numRows-1。
所以c=n//t*（numRows-1），至于为什么n变成了（n+t-1）是因为整除//是向下取整，有的时候最后一个周期是填不完整的，如果直接用n除，计算结果就会少了最后一个周期的列数。

最后if i % t < r - 1:这个判断句是表示余数小于一列的个数就向下。

漂亮思路

学霸说的，就是排队，排到哪队加到哪队。例如题目中的第一个例子，P加到第一行，A加到第二行，Y加到第三行，P再加到第二行…

按着学霸的思路我今天早上又写了一遍，调试了一会又通过了，我真的是太聪明了。

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        # 是哪一行就加到哪一行 如第一个例子中
        # P加到第一行 A加到第二行 Y加到第三行 P再加到第二行...
        n = len(s)
        res = [[] for _ in range(numRows)]
        j = 0
        flag = -1
        for i in range(n):
            res[j].append(s[i])
            if j == 0 or j == numRows-1:
                flag = -flag
            j = min(max(0,j+flag),numRows-1)
        res = sum(res,[])
        ans = "".join(res)
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

不过不足以证明我聪明才智的是这个思路是学霸先和我说的，其次我昨晚看到有大佬用这个思路写的代码。如flag的设置我就是脑子里有这个印象，但一开始设置成1没通过就是。

这些代码三点说明吧。一就是flag的初始值，二是行数j的取值不能越界，三是拼接的时候用sum（res，[]）这是我之前学的，可以把二维的变成一维的。

然后我们再看看大佬的代码：

 if numRows < 2: return s
#不用列表 直接用字符串 这样后面就不用在将二维变成一维
 res = ["" for _ in range(numRows)]
 i, flag = 0, -1
 for c in s:
     res[i] += c
     if i == 0 or i == numRows - 1: flag = -flag
     i += flag
 return "".join(res)
1
2
3
4
5
6
7
8
9

与我的代码相比的话，就是res直接用字符串列表，然后在一开始的时候判断了一下。