最近正在學(xué)習(xí)Python，因?yàn)閷?duì)語(yǔ)言的不熟練，所以打算刷題來(lái)使自己的語(yǔ)言掌握的更充分。在leetCode上看見(jiàn)了這么一道題
The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)
就是ZigZag 首先還是用圖來(lái)說(shuō)一下原理吧
首先就用簡(jiǎn)單的'0123456789012345678'來(lái)演示下
就是將數(shù)字按上圖排放，以豎列形式拜訪
讀取的時(shí)候從左向右讀所以最終讀取出來(lái)的文字是"0482613579135726048"
讀取方式也知道了，下面就該開(kāi)始代碼部分了。
首先我的思路就是按照?qǐng)D片方式，準(zhǔn)備一個(gè)二維數(shù)組。
#這里是判斷如果特殊情況，若給定行數(shù)過(guò)大或過(guò)下，直接做特殊處理
if numRows == 2:
array_1 = []
array_2 = []
for i in range(0,len(s)):
if i % 2 == 0:
array_1.append(s[i])
else:
array_2.append(s[i])
str = ''.join(array_1)
str += ''.join(array_2)
return str
elif numRows <= 1:
return s
elif numRows >= len(s):return s
#首先根據(jù)上圖中方框部分算出，當(dāng)numRows = 4時(shí)候重復(fù)部分的數(shù)量為6，當(dāng)numRows = 3時(shí)重復(fù)部分的字母數(shù)量為4，可以在紙上畫(huà)出當(dāng)numRows = 5時(shí)重復(fù)部分的字符數(shù)量為8，所以計(jì)算可得重復(fù)部分的數(shù)量隨numRows變化的數(shù)量就是numRows + numRows - 2
#count 為剩余部分有多少個(gè)字符
count = len(s) % (numRows + numRows - 2)
#index為總共有多少個(gè)塊
index = len(s) // (numRows + numRows - 2)
#i為這個(gè)塊中有多少列觀察可得，numRows 數(shù)量單獨(dú)占一列，剩下的一個(gè)字符占一列，所以最終每個(gè)塊中有1 + numRows - 2列
i = index * (1 + numRows - 2)
#j為剩余部分字符減去列數(shù)后剩余數(shù)量+1列
j = (count - numRows + 1) if count > numRows else 1
#total為總列數(shù)
total = i + j
array = []
接下來(lái)就該開(kāi)始循環(huán)給對(duì)應(yīng)字符放入數(shù)組中了
for real_i in range(0,total):
#創(chuàng)建每列的數(shù)組
real_array = []
#這個(gè)判斷為判斷是否為該塊的第一列（第一列為字母數(shù)量為numRows，其他列數(shù)字母數(shù)量為1）
if real_i % (numRows - 1) == 0:
#計(jì)算該塊起始位置
g = 2 * real_i
#循環(huán)添加字符進(jìn)入數(shù)組
for letter in range(g, g + numRows if g + numRows < len(s) else len(s)):
real_array.append(s[letter])
else:
#計(jì)算該列在該塊中的位置
real_index_i = real_i % (numRows - 1)
#計(jì)算這個(gè)字符處于這個(gè)數(shù)組中的第幾個(gè)位置
real_index_j = 2 * (real_i - real_index_i) + numRows
#取出字母
letter = s[real_index_i + real_index_j - 1]
#循環(huán)向數(shù)組中加入字符
for x in range(0,numRows):
if x == (numRows - 1 - real_index_i):
real_array.append(letter)
else:
real_array.append(' ')
#將這個(gè)數(shù)組加入總數(shù)組
array.append(real_array)
這步做完了后，所有操作基本已經(jīng)算是完成，這個(gè)已經(jīng)算是完成一多半
最后就剩下拼湊字符串了
str = ''
i = 0
#取數(shù)組和平時(shí)遍歷數(shù)組方式不太一樣，外層的循環(huán)實(shí)際上是用來(lái)遍歷每個(gè)數(shù)組的角標(biāo)i的位置的
while True:
for sub_array in array:
if len(sub_array) > i:
real = sub_array[i]
#這個(gè)地方的判斷是為了防止數(shù)字崩潰，因?yàn)楫?dāng)時(shí)用數(shù)字做的測(cè)試，將數(shù)字轉(zhuǎn)換成字符
if isinstance(real,int):
str += '%d '%(real)
else:
str += real
#下面部分是為了方便打印出對(duì)應(yīng)的格式的（真實(shí)提交測(cè)試時(shí)需要?jiǎng)h去）
str += ' '
str += '\n'
i += 1
if i == numRows:
break
return str
經(jīng)過(guò)測(cè)試提交，leetCode 給出的error是timeLimit，說(shuō)明代碼是可以正確計(jì)算出結(jié)果了，但是耗時(shí)非常長(zhǎng)，復(fù)雜度至少是O(n*numRows),太復(fù)雜了，耗時(shí)主要是在從數(shù)組中取出對(duì)應(yīng)字符的步驟，所以需要優(yōu)化，最終決定優(yōu)化的方式是將數(shù)組轉(zhuǎn)化成字典，用key對(duì)應(yīng)所在位置，直接優(yōu)化復(fù)雜度為O(n3)
#首先是循環(huán)部分修改
dic = {}
#real_i直接為所在位置的橫坐標(biāo)
for real_i in range(0,total):
if real_i % (numRows - 1) == 0:
g = 2 * real_i
for n in range(g, g + numRows if g + numRows < len(s) else len(s)):
#y為縱坐標(biāo)
index_y = letter - g
index_x = real_i
dic[index_x + index_y * (total)] = s[n]
else:
real_index_i = real_i % (numRows - 1)
real_index_j = 2 * (real_i - real_index_i) + numRows
letter = s[real_index_i + real_index_j - 1]
index_y = numRows - 1 - real_index_i
index_x = real_i
dic[index_x + index_y * (total)] = letter
接下來(lái)就剩讀取了，首先，現(xiàn)在key不是連續(xù)的，但是，咱們的位置排序卻是從小到大排序的，所以，下一步的操作就是給key進(jìn)行排序了,python有很強(qiáng)大的排序方法，就是sort
str = ''
i = 0
array = list(dic.keys())
array.sort()
for key in array:
letter = dic[key]
if isinstance(letter, int):
str += '%d' % (letter)
else:
str += letter
return str
將修改后的代碼重新提交測(cè)試，成功通過(guò)。應(yīng)該還有更好的方法，就是直接計(jì)算出對(duì)應(yīng)的角標(biāo)位置，但是礙于時(shí)間有限，就先用這個(gè)方法偷偷懶啦
