將一個給定字符串 s 根據(jù)給定的行數(shù) numRows ，以從上往下、從左到右進(jìn)行 Z 字形排列。
比如輸入字符串為 "PAYPALISHIRING" 行數(shù)為 3 時，排列如下：
P A H N
A P L S I I G
Y I R
之后，你的輸出需要從左往右逐行讀取，產(chǎn)生出一個新的字符串，比如："PAHNAPLSIIGYIR"。
請你實現(xiàn)這個將字符串進(jìn)行指定行數(shù)變換的函數(shù)：
string convert(string s, int numRows);
第一種算法
自己沒看答案前，自己寫的，主要思路是：根據(jù)給定的字符串的長度和行數(shù)，算出一共多少列，然后將字符串再按照要求按列依次填入二維數(shù)組中，最后再按照行進(jìn)行讀取字符串。
代碼如下，附有詳細(xì)的注釋：
def convert1(s, numRows):
# 如果為1行，就直接返回原字符串
if numRows == 1:
return s
# 記錄字符串長度
n = len(s)
# 行數(shù)
row = numRows
# 計算列數(shù)
# 假設(shè)每row+(row-2)個字符為一組，這一個組的字符個數(shù)表示為：
g_nums = row + (row - 2)
# 那么這一組所占的列數(shù)為
g_column = 1 + (row - 2)
# 計算字符串中共有多少個組
gs = n // g_nums
# 余下的字符個數(shù)
rest_num = n % g_nums
# 計算剩下的不夠一組的字符占多少列，默認(rèn)為0
o_column = 0
# 余下的字符個數(shù)小于等于行數(shù)，剛好占一列
if 1 <= rest_num <= row:
o_column = 1
# 余下的字符個數(shù)大于行數(shù)，列數(shù)等于余下的個數(shù)減去行數(shù) +1
elif rest_num > row:
o_column = 1 + (rest_num - row)
# 計算總的列數(shù)
column = gs * g_column + o_column
# 創(chuàng)建二維數(shù)組，沒有字符的，用"*"占位
# 不能[["*"] * column] * row 這么創(chuàng)建，因為里面每個元素沒有自己的存儲空間
arr = [["*"] * column for _ in range(row)]
# 先是一列一列的按列遍歷，依次"Z"字形填入字符串
# 記錄遍歷到第幾組數(shù)據(jù)，默認(rèn)為0
for j in range(column):
for i in range(row):
# 當(dāng)在完整的一個組時
if j < gs * g_column:
# 第一個條件：當(dāng)整列都有數(shù)據(jù)的列時
# 第二個條件：當(dāng)一列只有一個數(shù)據(jù)時，找規(guī)律有如下關(guān)系
if j % g_column == 0 or i == (g_column - j % g_column):
arr[i][j] = s[0]
# 每次賦值后，將賦值的那個字符舍棄，這樣每次都是拿第一個字符
s = s[1:]
# 當(dāng)余下的不夠一個組時
else:
# 賦值時要保證字符串還有字符
# 余下的一組中的第一列或者其他列時
if len(s) > 0 and ((j - gs * g_column) == 0 or i == (g_column - j % g_column)):
arr[i][j] = s[0]
# 如果字符串為空了，就退出遍歷
s = s[1:]
if len(s) == 0:
break
# 按行讀取字符串
# 記錄讀取后的字符串
rs = ""
for i in range(row):
for j in range(column):
if arr[i][j] != "*":
rs += arr[i][j]
return rs
第二種方法
參考力扣官方答案和精選答案，我們可以從左到右迭代 s，將每個字符添加到合適的行?？梢允褂卯?dāng)前行和當(dāng)前方向這兩個變量對合適的行進(jìn)行跟蹤。只有當(dāng)我們向上移動到最上面的行或向下移動到最下面的行時，當(dāng)前方向才會發(fā)生改變。
代碼如下，附有詳細(xì)注釋：
def convert2(s, numRows):
# 如果行數(shù)等于1，就直接返回原字符串
if numRows == 1:
return s
# 可能存在字符串的長度比給的行數(shù)小，那么只需要字符串長度的行就可以了
row = min(numRows, len(s))
# 聲明一個字符串?dāng)?shù)組，用于記錄每行的字符串
row_strs = ["" for _ in range(row)]
# 默認(rèn)當(dāng)前行為0，即第一行
current_row = 0
# 記錄是不是方向向下，默認(rèn)為false
going_down = False
# 遍歷字符串，將每個字符加到合適的行
for c in s:
row_strs[current_row] += c
# 當(dāng)在第一行或者最后一行時，改變方向
if current_row == 0 or current_row == row - 1:
going_down = not going_down
# 如果going_down為true，當(dāng)前行+1，否則-1
current_row += 1 if going_down else -1
# 將數(shù)組拼接成字符串，即是要求的字符串
return "".join(row_strs)
復(fù)雜度分析
- 時間復(fù)雜度 O(N) ：遍歷一遍字符串 s；
- 空間復(fù)雜度 O(N) ：各行字符串共占用 O(N) 額外空間。
第三種方法
參考力扣精選答案，采用了數(shù)學(xué)規(guī)律法，即是找出數(shù)學(xué)規(guī)律，然后按行訪問直接拼接成最終需要的字符串。
規(guī)律如下：
我們先假定有 numRows=4 行來推導(dǎo)下，其中 2numRows-2 = 6 , 我們可以假定為 step=2numRows-2 ，我們先來推導(dǎo)下規(guī)則：
第0行： 0 - 6 - 12 - 18
==> 下標(biāo)間距 6 - 6 - 6 ==> 下標(biāo)間距 step —— step —— step
第1行： 1 - 5 - 7 - 11 - 13
==> 下標(biāo)間距 4 - 2 - 4 - 2 ==> 下標(biāo)間距step-2 * 1(行) ——2 * 1(行)——step-2 * 1(行)——2 * 1(行)
第2行： 2 - 4 - 8 - 10 - 14
==> 下標(biāo)間距 2 - 4 - 2 - 4 ==> 下標(biāo)間距step-2 * 2(行)——2 * 2(行)——step-2 * 2(行)——2 * 2(行)
第3行：3 - 9 - 15 - 21
==> 下標(biāo)間距間距 6 - 6 - 6 ==>下標(biāo)間距step - step - step
可以得出以下結(jié)論：
- 起始下標(biāo)都是行號
- 第0層和第numRows-1層的下標(biāo)間距總是step 。
- 中間層的下標(biāo)間距總是step-2行數(shù)，2行數(shù)交替。
- 下標(biāo)不能超過len(s)-1
代碼如下：
def convert3(s, numRows):
if numRows == 1: return s
res = "" # 聲明一個返回的字符串
step = numRows * 2 - 2 # 下標(biāo)間距
index = 0 # 記錄s的下標(biāo)，從0開始
n = len(s) # 字符串長度
add = 0 # 真實的下標(biāo)間距
for i in range(numRows): # i 表示行號
index = i
add = i * 2
while index < n: # 當(dāng)下標(biāo)超出字符串長度就計算下一層
res += s[index] # 當(dāng)前行的第一個字符
add = step - add # 第一次的間距是step - 2*i，第二次是2*i
# 第0行和最后一行使用step間距，其他行都使用add間距
if i == 0 or i == numRows - 1:
index += step
else:
index += add
return res # 返回結(jié)果字符串
