LeetCode第六题：锯齿形转换（Python）

一.题目要求及实例

将给定的字符串，转化为锯齿形。锯齿形的行数给定。按序输出转换后的字符串。

二.初始思路

（1）二维数组的大小

竖着写入二维数组较困难，所以想到了先横着写，再取转置。

首先需要知道二维数组的大小。参数中给的numRows即为行数，所以要考虑的就是二维数组的列数。

观察到实例中，字母的排列有一定的周期性。在每个周期中，第一列全部排满，后面倾斜的部分占据除上下两行之外的所有行，所以倾斜部分共有numRows-2个字母。所以一个周期的字母个数为numRows+numRows-2=2*numRows-2。也可知每个周期的列数即为1+numRows-2。

接下来就可以根据每个周期的字母个数和字符串长度（总字母个数）计算需要多少个周期。使用整除即可：(len(s)%(2*numRows-2))+1。+1是多给一个周期给剩下的字母。

根据以上分析，可知该二维数组的列数为每个周期的列数*周期数。

（2）填充的方式

可以每个周期每个周期的写，最后将它们拼接在一起。

转置后，每个周期的小矩阵列数为numRows，行数为1+numRows-2。

通过观察可以知道，倾斜部分字母的索引都是第一行最后一个字母索引的倍数。这就可以完成一个周期的字母填充。

import numpy as np
​
class Solution:
    def convert(self,s:str,numRows:int)->str:
        
        if numRows==1:
            return s
        else:
            len_str=len(s)
            
            #求关于周期的参数
            periods_num=(len_str//(2*numRows-2))+1#周期数
            num_str_in_p=2*numRows-2#每个周期的字符个数（除最后一个周期外）
            period_rowsnum=1+numRows-2##每个周期的行数
            
            #创建一个周期的二维数组
            periods=np.zeros((period_rowsnum*numRows))
            #将其中的数据类型改为str
            periods=periods.astype(str)
            
            #用于计算倾斜部分索引
            k=2
            
            #创建一个可以包含所有周期的数组
            p=np.zeros((0,))
            
            #对周期循环
            for period in range(periods_num):
                
                #取出该周期内的元素
                s_per=s[period*num_str_in_p:(period+1)*num_str_in_p]
                
                #如果是最后一个周期，该周期内元素个数通过取s_per的值求得
                if period==periods_num-1:
                    num_str_in_p=len(s_per)
                
                
                #对周期内的字符循环
                for idx in range(num_str_in_p):
                    if idx<numRows:#直线部分的字母
                        periods[idx]=s_per[idx]
                    else:#倾斜部分的字母
                        periods[k*(numRows-1)]=s_per[idx]
                        k+=1
                        
                #上面操作得到了一个周期的锯齿形矩阵
                #将其加入大数组中
                p=np.append(p,periods)
                
                #更新periods和k
                periods=np.zeros((period_rowsnum*numRows))
                periods=periods.astype(str)
                k=2
                
            #改变大数组的shape，并取转置，此时就是题目要求的形状
            p=p.reshape(periods_num*period_rowsnum,numRows)
            p=p.transpose()
            #再转化为一维的，便于提取
            p=p.reshape(periods_num*period_rowsnum*numRows)
            
            #按顺序输出字母即可
            zigzag_s=[]
            for element in p:
                if element!='0.0':
                    zigzag_s.append(str(element))
            zigzag_s=''.join(zigzag_s)
            
            return str(zigzag_s)
​
​
#测试
test=Solution()
​
test_str="PAYPALISHIRING"
numRows=3
result=test.convert(test_str,numRows)
​

一些语法上的注意：

1.取整除的商用的是//，取余数用的是%

2.字符串的.join()方法，其使用格式是separator.join(iterable)，其中separator是分隔符，iterable是要连接的可迭代对象。它可以把可迭代对象单独存在的元素放在一起，如将['H','e','l','l','o']组合为['Hello']。

可迭代对象和该方法的输出均为字符串，其他类型使用时需要转换。

三.更简单的方法

上面的想法中，最终目的是要将原始字符串按题目要求排列到一个二维数组中，导致复杂度过高。下面的方法通过改变读取的顺序来实现。

对于每一个周期来说，直线部分顺序索引读，倾斜部分倒序索引读。所以，我们只需要循环读取每个字符，并且在每一列的开始或结束的位置改变读取的顺序。

储存方式也可以更加简单，不需要二维数组，而是仅仅使用numRows个元素的列表表示。该列表中每个元素表示一行，将该行的字母按顺序存放在同一个位置。

​
class Solution:
    def convert(self,s:str,numRows:int)->str:
    
        #若只有一行或者一列，直接返回原字符串
        if numRows==1 or numRows>=len(s):
            return s
    
        #创建一个列表，每个元素表示每一行
        rows=['']*numRows
        #当前位置
        current_row=0
        #决定读取的方向
        going_down=False
    
        #遍历字符串，将每个字符放入相应的行
        for char in s: 
            #将该行字母按顺序放在同一个位置
            rows[current_row]+=char
            
            #到达顶部或底部时，改变方向
            if current_row==0 or current_row==numRows-1:
                going_down=not going_down   
            #为True时自增（直线部分），否则自减（倾斜部分）
            current_row+=1 if going_down else -1
    
        #将所有行连接起来
        return ''.join(rows)
​
#测试
test=Solution()
s="PAYPALISHIRING"
numRows=4
​
result=test.convert(s,numRows)
​