最近正在學(xué)習(xí)Python片任，因為對語言的不熟練，所以打算刷題來使自己的語言掌握的更充分颅夺。在leetCode上看見了這么一道題

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 首先還是用圖來說一下原理吧
首先就用簡單的'0123456789012345678'來演示下

示意圖.png

就是將數(shù)字按上圖排放央串，以豎列形式拜訪

讀取示意圖.png

#這里是判斷如果特殊情況稚字，若給定行數(shù)過大或過下饲宿，直接做特殊處理
  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

列數(shù)為4時候快照.png

#首先根據(jù)上圖中方框部分算出，當(dāng)numRows = 4時候重復(fù)部分的數(shù)量為6胆描，當(dāng)numRows = 3時重復(fù)部分的字母數(shù)量為4瘫想，可以在紙上畫出當(dāng)numRows = 5時重復(fù)部分的字符數(shù)量為8，所以計算可得重復(fù)部分的數(shù)量隨numRows變化的數(shù)量就是numRows + numRows - 2
#count 為剩余部分有多少個字符
  count = len(s) % (numRows + numRows - 2)
#index為總共有多少個塊
  index = len(s) // (numRows + numRows - 2)
#i為這個塊中有多少列觀察可得昌讲，numRows 數(shù)量單獨(dú)占一列国夜，剩下的一個字符占一列，所以最終每個塊中有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 = []

接下來就該開始循環(huán)給對應(yīng)字符放入數(shù)組中了

  for real_i in range(0,total):
#創(chuàng)建每列的數(shù)組
      real_array = []
#這個判斷為判斷是否為該塊的第一列（第一列為字母數(shù)量為numRows短绸，其他列數(shù)字母數(shù)量為1）
      if real_i % (numRows - 1) == 0:
#計算該塊起始位置
        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:
#計算該列在該塊中的位置
        real_index_i = real_i % (numRows - 1)
#計算這個字符處于這個數(shù)組中的第幾個位置
        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(' ')
#將這個數(shù)組加入總數(shù)組
      array.append(real_array)

這步做完了后车吹，所有操作基本已經(jīng)算是完成筹裕，這個已經(jīng)算是完成一多半
最后就剩下拼湊字符串了

    str = ''
    i = 0
#取數(shù)組和平時遍歷數(shù)組方式不太一樣，外層的循環(huán)實際上是用來遍歷每個數(shù)組的角標(biāo)i的位置的
    while True:
      for sub_array in array:
        if len(sub_array) > i:
          real = sub_array[i]
#這個地方的判斷是為了防止數(shù)字崩潰窄驹，因為當(dāng)時用數(shù)字做的測試朝卒，將數(shù)字轉(zhuǎn)換成字符
          if isinstance(real,int):
            str += '%d '%(real)
          else:
            str += real
#下面部分是為了方便打印出對應(yīng)的格式的（真實提交測試時需要刪去）
            str += ' '
        str += '\n'
        i += 1
      if i == numRows:
        break
    return str

經(jīng)過測試提交，leetCode 給出的error是timeLimit乐埠，說明代碼是可以正確計算出結(jié)果了抗斤，但是耗時非常長，復(fù)雜度至少是O(n*numRows),太復(fù)雜了丈咐，耗時主要是在從數(shù)組中取出對應(yīng)字符的步驟瑞眼，所以需要優(yōu)化，最終決定優(yōu)化的方式是將數(shù)組轉(zhuǎn)化成字典棵逊，用key對應(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

接下來就剩讀取了，首先歹河，現(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

將修改后的代碼重新提交測試键菱，成功通過谬墙。應(yīng)該還有更好的方法，就是直接計算出對應(yīng)的角標(biāo)位置经备，但是礙于時間有限拭抬，就先用這個方法偷偷懶啦