題目
將一個給定字符串根據(jù)給定的行數(shù)，以從上往下、從左到右進行 Z 字形排列。比如輸入字符串為 "LEETCODEISHIRING" 行數(shù)為 3 時，排列如下：
L C I R
E T O E S I I G
E D H N
之后，你的輸出需要從左往右逐行讀取，產(chǎn)生出一個新的字符串，比如："LCIRETOESIIGEDHN"。請你實現(xiàn)這個將字符串進行指定行數(shù)變換的函數(shù)：
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
解答
這道題目是用來找規(guī)律的。我們不用在乎字符串是什么樣子，只需要把下標(biāo)整理好就夠了。如圖所示，這里設(shè)輸入為13個元素的字符串，行數(shù)為4，我們先把字符串的下標(biāo)羅列一下：
我們可以觀察到一些規(guī)律：
1.Z字形變換有重復(fù)結(jié)構(gòu)，暫且稱為“單元”，而且相鄰單元相同位置的差值相同，記為node_length，例如10和4之間的差值、7和1之間的差值都是6；
2.每個單元包含一個垂直列和斜線列，垂直列從上到下連續(xù)遞增；
3.第一行和最后一行在每個單元中只有一個元素，其他行在每個單元有兩個，一個垂直列中的元素verticle_elem（綠色）和一個斜線列中的元素oblique_elem（紅色），而且這兩個元素下標(biāo)存在關(guān)系：oblique_elem = verticle_elem + node_length - 2 * 當(dāng)前行號，例如2和4分是同一個單元內(nèi)的垂直列元素和斜線上元素，存在關(guān)系：4= 2 + 6 - 2 * 2 = 4，推導(dǎo)很簡單；
我們逐行遍歷，用row代表當(dāng)前行號，從左到右逐個單元獲得當(dāng)前行當(dāng)前單元的垂直列元素（綠色），如果不是第一行或最后一行，還要把當(dāng)前行當(dāng)前單元的斜線列元素（紅色）加入到結(jié)果中。具體實現(xiàn)如下：
class Solution:
def convert(self, s, numRows):
"""
:type s: str
:type numRows: int
:rtype: str
"""
str_length = len(s) # 輸入字符串長度
node_length = 2 * (numRows - 1) # 相鄰單元相同位置的差值
result = "" # 結(jié)果變量
if str_length == 0 or numRows == 0 or numRows == 1:
return s
for row in range(numRows): # 逐行遍歷
for verticle_elem in range(row, str_length, node_length): # 從左到右逐個單元遍歷
result += s[verticle_elem] # 添加當(dāng)前行中處在垂直列中的元素
oblique_elem = verticle_elem - 2 * row + node_length # 當(dāng)前行中處在斜線上的元素下標(biāo)
if row != 0 and row != numRows-1 and oblique_elem < str_length:
# 如果不是第一行和最后一行，在每個單元上一定存在斜線上元素inter_elem
result += s[oblique_elem] # 添加斜線上的元素
return result
如有疑問，歡迎評論區(qū)留言~
