1.找规律
思路:
对原字符串进行分块处理,找到每块中数字在Z形变化后的对应关系。
例如:
通过观察发现可以以Z型的头和身为块进行分块。即 [L E E T C O] [D E I S H I] [R I N G]
每块的数量等于行数的二倍减去2。即 4 * 2 - 2 = 6
这里可以发现每块中的Z型头元素对应的位置相差 6 也即每块中元素的个数。
然后谈论如何将每块的Z型身子插进去,这里除了Z型头首尾元素外,我们发现其他元素位置右侧对应Z型身元素存在规律,即身元素位置=头元素位置+块的元素数量-2*头元素在块中的位置。例如:[ D E I S H I ] 中头元素 E 在原字符串中位置为7,在块中位置为1,则其对应身元素 I 的位置为 7+6-1*2 = 11。其他元素同理。
所以我们在新字符串中插入元素时,如果插入的是每块的头元素,其对应的身元素存在的话,一并插入进去。
代码:
class Solution: def convert(self, s: str, numRows: int) -> str: if numRows == 1: return s length = len(s) newStr = "" p = numRows*2-2 n = math.ceil(length/p) for i in range(numRows): for j in range(n): k = i + p*j q = k+p-i*2 if k < length: newStr += s[k] if i!=0 and i!=numRows-1 and q < length: newStr += s[q] return newStr
2.用数组上下遍历插入
思路:
创建一个数组,里面包含对应行数个数的字符串。从上往下遍历,向数组中对应行数字符串插入字符。遍历到最下面时,变方向,从下往上遍历。遍历到第一行时,再变方向,从上往下。最后将数组中每个元素合并到一个字符串中。
代码:
class Solution: def convert(self, s: str, numRows: int) -> str: if numRows == 1: return s arr = [""]*numRows curRow = 0 length = len(s) isdown = True for c in s: arr[curRow] += c if isdown: curRow +=1 else: curRow -=1 if curRow == 0 or curRow ==numRows-1: isdown = not isdown return "".join(arr)
原文:https://www.cnblogs.com/nilhxzcode/p/12733539.html