6.Z字形变换

难度：中等
将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。

示例1：
输入：s = “PAYPALISHIRING”, numRows = 3
输出：“PAHNAPLSIIGYIR”

示例2：
输入：s = “PAYPALISHIRING”, numRows = 4
输出：“PINALSIGYAHRPI”

方法1（按行排序）：
从左到右迭代 $s$ ，将每个字符添加到合适的行。
时间复杂度： $O (n)$ ，空间复杂度： $O (n)$

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows == 1:
            return s
        convStr = ""
        result = ["" for _ in range(numRows)]
        for index, char in enumerate(s):
            subIndex = index % (2 * numRows - 2)
            if subIndex < numRows:
                result[subIndex] += char
            else:
                result[2 * (numRows - 1) - subIndex] += char
        for each in result:
            convStr += each
        return convStr

方法2（按行访问）：
首先访问行0中的所有字符，接着访问行1，然后行2，依此类推…
对于所有整数 $k$ ，

行0中的字符位于索引 $k (2 n u m R o w s ? 2)$ 处;
行 $n u m R o w s ? 1$ 中的字符位于索引 $k (2 n u m R o w s ? 2) + n u m R o w s ? 1$ 处;
内部的行 $i$ 中的字符位于索引 $k (2 n u m R o w s ? 2) + i$ 以及 $(k + 1) (2 n u m R o w s ? 2) ? i$ 处;

时间复杂度： $O (n)$ ，空间复杂度： $O (n)$

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows == 1:
            return s
        convStr = ""
        lens=len(s)
        cycleLen =2*numRows-2
        for i in range(numRows):
            for j in range(0,lens-i,cycleLen):
                convStr+=s[j+i]
                if (i!=0 and i!=numRows-1 and j+cycleLen-i<lens):
                    convStr+=s[j+cycleLen-i]
        return convStr

7.整数反转

难度：简单
给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。
如果反转后整数超过 32 位的有符号整数的范围 $2^{31}, 2^{31} ? 1]$ ，就返回 0。
假设环境不允许存储 64 位整数（有符号或无符号）。

示例1：
输入：x = 123
输出：321
示例2：
输入：x = -123
输出：-321
示例3：
输入：x = 120
输出：21
示例4：
输入：x = 1534236469
输出：0

方法1（转字符串）：
但用到了64位整数。
时间复杂度： $O (n)$ ，空间复杂度： $O (n)$

class Solution:
    def reverse(self, x: int) -> int:
        string=str(abs(x))
        string=string[::-1]
        revNum=int(string)
        if revNum>2**31:return 0
        return -revNum if x<0 else revNum

方法2（数学）：
记 $r e v$ 为翻转后的数字，为完成翻转，我们可以

// 弹出 x 的末尾数字 digit
digit = x % 10
x /= 10
// 将数字 digit 推入 rev 末尾
rev = rev * 10 + digit

我们需要在推入数字之前，判断是否满足
$-2^{31}\le rev\cdot10+digit\le2^{31}-1$ ，
若该不等式不成立则返回 $0$ 。
但是题目要求不允许使用64 位整数，上式改为
$\left\lceil\frac{-2^{31}}{10}\right\rceil \leq r e v \leq\left\lfloor\frac{2^{31}-1}{10}\right\rfloor。$ 证明
时间复杂度： $O (n)$ ，空间复杂度： $O (n)$

class Solution:
    def reverse(self, x: int) -> int:
        INT_MIN, INT_MAX = -2**31, 2**31 - 1
        rev = 0
        while x != 0:
            # INT_MIN 也是一个负数，不能写成 rev < INT_MIN // 10
            if rev < INT_MIN // 10 + 1 or rev > INT_MAX // 10:
                return 0
            digit = x % 10
            # Python3 的取模运算在 x 为负数时也会返回 [0, 9) 以内的结果，因此这里需要进行特殊判断
            if x < 0 and digit > 0:
                digit -= 10
            # 同理，Python3 的整数除法在 x 为负数时会向下（更小的负数）取整，因此不能写成 x //= 10
            x = (x - digit) // 10
            rev = rev * 10 + digit
        return rev