刷无尽 6 ～ 蛇形阵转换

基本信息

• 题号：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 时
• ……

总结

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