基本信息

  • 题号：6
  • 题厂：谷歌
  • 难度系数：中


把一个字符串按蛇形路线转化后输出……

例如："PAYPALISHIRING" 以 3 行模式蛇形输出后长相如下：
P   A   H   N
A P L S I I G
Y   I   R

再行数从左往右输出，返回："PAHNAPLSIIGYIR"；


解题思路

  • 可以创建 1 个以行为单位的 hashmap，按行存入字符，最后按行 join 输出。于是解题关键为：如何找到每个字符转换为蛇形阵后的对应行数？？？
  • 很明显，需要运用一点数学思维寻找规律……
  • 每个轮回长度为 （行数 + 行数 - 2）；如果余数小于行数，蛇形阵对应行数就是当前行数；如果余数大于行数，蛇形阵对应行数为（循环长度 - 余数），即（行数 + 行数 - 2 - 余数）……


class Solution:
    def convert(self, s: str, numRows: int) -> str:
        # 如果行数为 1，该算法不成立；而蛇形阵和原字符串相等，提前返回即可……
        if numRows == 1:
            return s
        
        rows = [""] * numRows
        
        # put char to each row arrordingly
        fullRound = numRows + (numRows - 2)
        for i in range(len(s)):
            remainder = i % fullRound
            if remainder < numRows:
                rows[remainder] += s[i]
            else:
                rows[fullRound - remainder] += s[i]
        
        # join row by row
        return "".join([r for r in rows])



Constraints

  • 1 <= s.length <= 1000
  • s consists of English letters (lower-case and upper-case), ',' and '.'.
  • 1 <= numRows <= 1000

本题主要涉及行数为 1 时的边界处理问题🙈，比较容易被忽略……


Big O

  • Time：O（n + m）；n 字符串长度，m 为蛇形阵长度；
  • Space：O（m）—— 因为创建了一个以蛇形阵长度的数组


测试

  • 字符串为 1 时
  • 蛇形行数为 1 时
  • ……


总结

  • 看似挺唬人的，其实还好，正常中档题……
  • 小学奥数升级后的编程版🤪