題目描述
https://leetcode.cn/problems/zigzag-conversion/description/
將一個給定字符串 s 根據給定的行數 numRows ，以從上往下、從左到右進行 Z 字形排列。
比如輸入字符串為 “PAYPALISHIRING” 行數為 3 時，排列如下：
之后，你的輸出需要從左往右逐行讀取，產生出一個新的字符串，比如：“PAHNAPLSIIGYIR”。
請你實現這個將字符串進行指定行數變換的函數：
string convert(string s, int numRows);
示例 1：
輸入：s = “PAYPALISHIRING”, numRows = 3
輸出：“PAHNAPLSIIGYIR”
Tag: 字符串處理
class Solution:def convert(self, s: str, numRows: int) -> str:if numRows <= 1:return sl1 = numRowsl2 = numRows-2flag = 0slice1 = []slice2 = []length = len(s)while flag < length:if flag + l1 < length:slice1.append(s[flag:flag + l1])flag += l1else:slice1.append(s[flag:length])breakif flag + l2 < length:slice2.append(s[flag:flag + l2])flag += l2else:slice2.append(s[flag:length])breakflag1=len(slice1)flag2=len(slice2)flag = max(flag1, flag2)result = ""for i in range(numRows):for j in range(flag):if j<flag1:if i < len(slice1[j]):result += slice1[j][i]if i > 0 and i < numRows-1:if j<flag2:if len(slice2[j])- i >= 0:result += slice2[j][len(slice2[j])-i]return result
思路分析
- 構造場景模擬處理方法
- 尋找數學規律，推導下標變換公式
實際上我給出的方法類似于兩種結合，但是很遺憾沒能通過測試（解答錯誤 539 / 1157 個通過的測試用例）
通過畫圖+模擬，可以把這個過程拆分成：
- 新建兩個字符串隊列（一列的I 和斜著的 /)
- 根據不同的下標從隊列中按照題目要求順序進行字符提取
但是這樣做既沒能利用程序的自動化，也沒整明白數學公式，本來想結合兩種方法的長處，現在變成了結合兩種方法的短處了。經過多次調試也沒弄明白，證明此路不通。
所以要么構造矩陣，要么把數學規律整明白。
14點12分模擬法
看官方版本最直接
V字形變換法
參考這位的思路，把找循環規律做到了極致
class Solution:def convert(self, s: str, numRows: int) -> str:if numRows <= 1:return slength = 2*(numRows-1)str_length = len(s)loop = math.ceil(str_length/length)result = ""for j in range(0, numRows):for i in range(0, loop):tmp1 = i*length + jtmp2 = i*length + (length-j)# print(f"{length} {tmp1} {tmp2}")if j == 0 or j == numRows-1:if tmp1 < str_length:result += s[tmp1]else:if tmp1 < str_length:result += s[tmp1]if tmp2 < str_length:result += s[tmp2]return result
)
)
