將一個(gè)給定字符串 s 根據(jù)給定的行數(shù) numRows 签钩，以從上往下娜搂、從左到右進(jìn)行 Z 字形排列放典。
比如輸入字符串為 "PAYPALISHIRING" 行數(shù)為 3 時(shí)辽幌，排列如下：
P A H N
A P L S I I G
Y I R
之后忠蝗，你的輸出需要從左往右逐行讀取现横，產(chǎn)生出一個(gè)新的字符串，比如："PAHNAPLSIIGYIR"阁最。
請你實(shí)現(xiàn)這個(gè)將字符串進(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
# 計(jì)算列數(shù)
# 假設(shè)每row+(row-2)個(gè)字符為一組棋傍，這一個(gè)組的字符個(gè)數(shù)表示為：
g_nums = row + (row - 2)
# 那么這一組所占的列數(shù)為
g_column = 1 + (row - 2)
# 計(jì)算字符串中共有多少個(gè)組
gs = n // g_nums
# 余下的字符個(gè)數(shù)
rest_num = n % g_nums
# 計(jì)算剩下的不夠一組的字符占多少列救拉，默認(rèn)為0
o_column = 0
# 余下的字符個(gè)數(shù)小于等于行數(shù)，剛好占一列
if 1 <= rest_num <= row:
o_column = 1
# 余下的字符個(gè)數(shù)大于行數(shù)瘫拣，列數(shù)等于余下的個(gè)數(shù)減去行數(shù) +1
elif rest_num > row:
o_column = 1 + (rest_num - row)
# 計(jì)算總的列數(shù)
column = gs * g_column + o_column
# 創(chuàng)建二維數(shù)組亿絮，沒有字符的，用"*"占位
# 不能[["*"] * column] * row 這么創(chuàng)建，因?yàn)槔锩婷總€(gè)元素沒有自己的存儲空間
arr = [["*"] * column for _ in range(row)]
# 先是一列一列的按列遍歷派昧，依次"Z"字形填入字符串
# 記錄遍歷到第幾組數(shù)據(jù)黔姜，默認(rèn)為0
for j in range(column):
for i in range(row):
# 當(dāng)在完整的一個(gè)組時(shí)
if j < gs * g_column:
# 第一個(gè)條件：當(dāng)整列都有數(shù)據(jù)的列時(shí)
# 第二個(gè)條件：當(dāng)一列只有一個(gè)數(shù)據(jù)時(shí)，找規(guī)律有如下關(guān)系
if j % g_column == 0 or i == (g_column - j % g_column):
arr[i][j] = s[0]
# 每次賦值后蒂萎，將賦值的那個(gè)字符舍棄秆吵，這樣每次都是拿第一個(gè)字符
s = s[1:]
# 當(dāng)余下的不夠一個(gè)組時(shí)
else:
# 賦值時(shí)要保證字符串還有字符
# 余下的一組中的第一列或者其他列時(shí)
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纳寂，將每個(gè)字符添加到合適的行〔虺牛可以使用當(dāng)前行和當(dāng)前方向這兩個(gè)變量對合適的行進(jìn)行跟蹤烈疚。只有當(dāng)我們向上移動(dòng)到最上面的行或向下移動(dòng)到最下面的行時(shí)，當(dāng)前方向才會(huì)發(fā)生改變聪轿。
代碼如下爷肝，附有詳細(xì)注釋：
def convert2(s, numRows):
# 如果行數(shù)等于1，就直接返回原字符串
if numRows == 1:
return s
# 可能存在字符串的長度比給的行數(shù)小陆错，那么只需要字符串長度的行就可以了
row = min(numRows, len(s))
# 聲明一個(gè)字符串?dāng)?shù)組灯抛，用于記錄每行的字符串
row_strs = ["" for _ in range(row)]
# 默認(rèn)當(dāng)前行為0，即第一行
current_row = 0
# 記錄是不是方向向下音瓷，默認(rèn)為false
going_down = False
# 遍歷字符串对嚼，將每個(gè)字符加到合適的行
for c in s:
row_strs[current_row] += c
# 當(dāng)在第一行或者最后一行時(shí)，改變方向
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ù)雜度分析
- 時(shí)間復(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 = "" # 聲明一個(gè)返回的字符串
step = numRows * 2 - 2 # 下標(biāo)間距
index = 0 # 記錄s的下標(biāo)，從0開始
n = len(s) # 字符串長度
add = 0 # 真實(shí)的下標(biāo)間距
for i in range(numRows): # i 表示行號
index = i
add = i * 2
while index < n: # 當(dāng)下標(biāo)超出字符串長度就計(jì)算下一層
res += s[index] # 當(dāng)前行的第一個(gè)字符
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é)果字符串
