6. Z 字形变换，7. 整数反转，8. 字符串转换整数 (atoi)，每题做详细思路梳理，配套Python&Java双语代码， 2024.03.08 可通过leetcode所有测试用例。
6. Z 字形变换
将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：
P A H N
A P L S I I G
Y I R
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。请你实现这个将字符串进行指定行数变换的函数：
string convert(string s, int numRows);
示例 1：
输入：s = "PAYPALISHIRING", numRows = 3
输出："PAHNAPLSIIGYIR"
示例 2：
输入：s = "PAYPALISHIRING", numRows = 4
输出："PINALSIGYAHRPI"
解释：
P I N
A L S I G
Y A H R
P I
示例 3：输入：s = "A", numRows = 1
输出："A"
提示：
1 <= s.length <= 1000
s 由英文字母（小写和大写）、',' 和 '.' 组成
1 <= numRows <= 1000
解题思路
这个问题可以通过模拟Z字形排列的过程来解决。具体思路如下：
-
初始化：创建一个列表（或者列表的列表），用于存储每一行的字符。行数由
numRows指定。 -
字符遍历：遍历字符串
s中的每个字符，并将其添加到正确的行中。 -
行的变化：使用一个变量来表示当前字符应该放在哪一行，以及一个方向变量，用于表示行的移动方向（向下或向上）。当我们向下移动到最底行时，改变方向向上移动；当向上移动到最顶行时，改变方向向下移动。
-
输出结果：遍历存储行的列表，将每行的字符连接起来形成最终的字符串。
边界条件
- 当
numRows为1时，不需要进行Z字形变换，直接返回原字符串。 - 当
numRows大于等于字符串长度时，同样不需要进行变换，直接返回原字符串。
完整代码
Python
class Solution:
def convert(self, s: str, numRows: int) -> str:
if numRows == 1 or numRows >= len(s):
return s
rows = [''] * min(numRows, len(s)) # 初始化行
curRow = 0 # 当前行
goingDown = False # 方向
# 遍历字符串，模拟Z字形排列
for c in s:
rows[curRow] += c
if curRow == 0 or curRow == numRows - 1:
goingDown = not goingDown
curRow += 1 if goingDown else -1
# 合并所有行，形成最终字符串
return ''.join(rows)Java
class Solution {
public String convert(String s, int numRows) {
if (numRows == 1 || numRows >= s.length()) {
return s;
}
StringBuilder[] rows = new StringBuilder[numRows];
for (int i = 0; i < numRows; i++) {
rows[i] = new StringBuilder();
}
int curRow = 0;
boolean goingDown = false;
for (char c : s.toCharArray()) {
rows[curRow].append(c);
if (curRow == 0 || curRow == numRows - 1) {
goingDown = !goingDown;
}
curRow += goingDown ? 1 : -1;
}
StringBuilder ret = new StringBuilder();
for (StringBuilder row : rows) {
ret.append(row);
}
return ret.toString();
}
}7. 整数反转
给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。
如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ，就返回 0。
假设环境不允许存储 64 位整数（有符号或无符号）。
示例 1：
输入：x = 123
输出：321
示例 2：输入：x = -123
输出：-321
示例 3：输入：x = 120
输出：21
示例 4：输入：x = 0
输出：0
解题思路
这个问题的关键在于如何反转一个整数的数字，并且在反转的过程中需要检查结果是否会超出32位有符号整数的范围（即是否会溢出）。
-
处理符号：首先，我们需要处理整数的符号。我们可以通过取绝对值的方式忽略掉整数的符号，然后在最后根据原始整数的符号来确定最终结果的符号。
-
数字反转：对于数字反转的部分，我们可以通过不断地取整数的最后一位数字，并将其添加到结果整数的末尾，同时将原整数除以10（向下取整）来去掉已经处理过的最后一位。
-
检查溢出：在每次添加新数字之前，我们需要检查结果是否会超出32位有符号整数的范围。对于正数，检查是否大于
Integer.MAX_VALUE/10；对于负数，检查是否小于Integer.MIN_VALUE/10。 -
返回结果：根据原始整数的符号返回最终的反转结果。
边界条件
- 如果整数为0，则直接返回0。
- 需要注意的是，整数反转后可能会出现前导0，但这对最终结果没有影响，因为在数学上，前导0被忽略。
完整代码
Python
class Solution:
def reverse(self, x: int) -> int:
INT_MAX, INT_MIN = 2**31 - 1, -2**31
rev = 0
sign = -1 if x < 0 else 1
x *= sign # 使x为正数，便于处理
while x != 0:
digit = x % 10
x = x // 10 # 更新x
# 检查反转后是否溢出
if rev > INT_MAX // 10 or (rev == INT_MAX // 10 and digit > INT_MAX % 10):
return 0
rev = rev * 10 + digit
return rev * sign
Java
class Solution {
public int reverse(int x) {
int res = 0;
while (x != 0) {
// 取最后一位
int digit = x % 10;
x /= 10;
// 检查溢出
if (res > Integer.MAX_VALUE / 10 || (res == Integer.MAX_VALUE / 10 && digit > 7)) return 0;
if (res < Integer.MIN_VALUE / 10 || (res == Integer.MIN_VALUE / 10 && digit < -8)) return 0;
res = res * 10 + digit;
}
return res;
}
}8. 字符串转换整数 (atoi)
请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。
函数 myAtoi(string s) 的算法如下：
读入字符串并丢弃无用的前导空格
检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。
读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
将前面步骤读入的这些数字转换为整数（即，"123" -> 123， "0032" -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。
如果整数数超过 32 位有符号整数范围 [−231, 231 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231 的整数应该被固定为 −231 ，大于 231 − 1 的整数应该被固定为 231 − 1 。
返回整数作为最终结果。
注意：本题中的空白字符只包括空格字符 ' ' 。
除前导空格或数字后的其余字符串外，请勿忽略 任何其他字符。
示例 1：
输入：s = "42"
输出：42
解释：加粗的字符串为已经读入的字符，插入符号是当前读取的字符。
第 1 步："42"（当前没有读入字符，因为没有前导空格）
^
第 2 步："42"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
^
第 3 步："42"（读入 "42"）
^
解析得到整数 42 。
由于 "42" 在范围 [-231, 231 - 1] 内，最终结果为 42 。
示例 2：输入：s = " -42"
输出：-42
解释：
第 1 步：" -42"（读入前导空格，但忽视掉）
^
第 2 步：" -42"（读入 '-' 字符，所以结果应该是负数）
^
第 3 步：" -42"（读入 "42"）
^
解析得到整数 -42 。
由于 "-42" 在范围 [-231, 231 - 1] 内，最终结果为 -42 。
示例 3：输入：s = "4193 with words"
输出：4193
解释：
第 1 步："4193 with words"（当前没有读入字符，因为没有前导空格）
^
第 2 步："4193 with words"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
^
第 3 步："4193 with words"（读入 "4193"；由于下一个字符不是一个数字，所以读入停止）
^
解析得到整数 4193 。
由于 "4193" 在范围 [-231, 231 - 1] 内，最终结果为 4193 。
解题思路
- 去除前导空格：遍历字符串，跳过所有前导空格。
- 处理正负号：如果遇到正号
+或负号-，记录下符号，并处理下一个字符。如果没有符号，默认为正数。 - 读取数字：继续遍历字符串，直到遇到非数字字符或字符串结束。将每个数字字符转换为数字，并加到结果中。在每次添加数字之前，检查是否会溢出。
- 溢出处理：如果在任何时候计算的结果超出32位有符号整数的范围，则根据正负号返回INT_MAX或INT_MIN。
- 返回结果：返回计算的结果，根据步骤2中记录的正负号调整正负。
边界条件
- 字符串为空或仅包含空白字符时，返回0。
- 读取的数字之后还有其他字符，忽略这些字符。
完整代码
Python
class Solution:
def myAtoi(self, s: str) -> int:
INT_MAX, INT_MIN = 2**31 - 1, -2**31
i, n, sign = 0, len(s), 1
result = 0
# 跳过前导空格
while i < n and s[i] == ' ':
i += 1
# 处理正负号
if i < n and (s[i] == '+' or s[i] == '-'):
sign = -1 if s[i] == '-' else 1
i += 1
# 读取数字
while i < n and s[i].isdigit():
digit = int(s[i])
# 检查溢出
if result > INT_MAX // 10 or (result == INT_MAX // 10 and digit > INT_MAX % 10):
return INT_MIN if sign == -1 else INT_MAX
result = result * 10 + digit
i += 1
return result * signJava
class Solution {
public int myAtoi(String s) {
int index = 0, sign = 1, total = 0;
// 1. Empty string
if(s.length() == 0) return 0;
// 2. Remove Spaces
while(index < s.length() && s.charAt(index) == ' ')
index++;
// 3. Handle signs
if(index < s.length() && (s.charAt(index) == '+' || s.charAt(index) == '-')){
sign = s.charAt(index) == '+' ? 1 : -1;
index++;
}
// 4. Convert number and avoid overflow
while(index < s.length()){
int digit = s.charAt(index) - '0';
if(digit < 0 || digit > 9) break;
// Check if total will be overflow after 10 times and add digit
if(Integer.MAX_VALUE/10 < total || Integer.MAX_VALUE/10 == total && Integer.MAX_VALUE %10 < digit)
return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
total = 10 * total + digit;
index ++;
}
return total * sign;
}
}
