https://leetcode-cn.com/problems/zigzag-conversion

代码:

# -*- coding:utf-8 -*-

class Solution(object):
def convert(self, s, numRows):
"""
:type s: str
:type numRows: int
:rtype: str
"""
if numRows == 1 or numRows == len(s) or len(s) < numRows:
return s
s_len = len(s)
pre_jump_len = 2 * numRows
next_jump_len = -2
current_idx = 0
latest_idx = 0
result = ''
for i in range(numRows):
if pre_jump_len > 2:
pre_jump_len -= 2
else:
pre_jump_len = 2 * numRows - 2
if next_jump_len < 2 * numRows-2:
next_jump_len += 2
else:
next_jump_len = 0
result = result + s[current_idx]
latest_idx = current_idx
for j in range(s_len):
if current_idx + pre_jump_len < s_len:
result = result + s[current_idx + pre_jump_len]
current_idx = current_idx + pre_jump_len
else:
current_idx = latest_idx + 1
break
if next_jump_len == 0:
continue
if current_idx + next_jump_len < s_len:
result = result + s[current_idx + next_jump_len]
current_idx = current_idx + next_jump_len
else:
current_idx = latest_idx + 1
break
return result
pass


if __name__ == '__main__':
s = 'PAYPALISHIRING'
print(Solution().convert(s, 5))

思路:如下图可以轻松发现Z字抖动规律,首行间隔2*numRows-2个元素,次行间隔2*numRows-4个元素。但是要注意,除了首位行均有两中跳过长度(例如第二行E跳4个到O,O条2个到E,E再跳4个到I,I跳2个到I),他们的和为2*numRows。

依照这个思路,采用两个跳过长度标记,一个代表第一次跳的长度,一个代表第二次跳的长度。因此只有最后一行数据需要特殊处理,只要当首次跳过长度缩短为2时重新初始化长度到2*numRows-2即可。

同时注意特殊数据,例如s的长度比numRows小等特殊情况的处理。

分类: 算法

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注