LeetCode 246. 中心对称数
题目描述
题意分析
判断数字字符串整体旋转 180° 后是否仍与原来完全相同。旋转不仅改变数码的形状，也会把左右位置对调，因此不能只检查每个数码能否旋转。
解法：双指针对称映射
核心思路
[!blue]
合法的旋转关系只有
0 → 0、1 → 1、8 → 8、6 → 9和9 → 6。其余数码旋转后无法得到题目要求的有效数码，应直接判定失败。整体旋转会把左侧位置移到右侧对应位置，所以对称位置必须满足“左字符旋转后的结果等于右字符”。用两个指针分别从首尾向中间移动，每次检查这一对即可，无需构造旋转后的整个字符串。
这些映射互为逆操作：左字符能旋转成右字符，也就保证右字符能旋转回左字符。因此每对只验证一个方向就足够。只要有一对不满足，整体就不可能保持不变；所有对都通过，整个字符串就相同。
循环要包含
left == right。奇数长度的中心位旋转后仍在原位置，只能使用能映射成自身的0、1、8，不能使用需要与另一种数码配对的6、9。
解题步骤
- 将左右指针分别放在字符串首尾。
- 当左指针不超过右指针时，计算左字符的旋转结果。
- 若不存在合法映射，或者映射结果不等于右字符，立即返回
false。- 两端同时向内移动一位，直到所有字符对和可能存在的中心位都通过，返回
true。
代码实现
class Solution {
public boolean isStrobogrammatic(String num) {
int left = 0;
int right = num.length() - 1;
// 包含中心位置，奇数长度的中心也必须旋转后保持不变。
while (left <= right) {
char rotated = rotate(num.charAt(left));
// 无效标记与数字字符零不同，同时检查旋转后的对称字符。
if (rotated == 0 || rotated != num.charAt(right)) {
return false;
}
left++;
right--;
}
return true;
}
private char rotate(char digit) {
switch (digit) {
case '0':
case '1':
case '8':
return digit;
case '6':
return '9';
case '9':
return '6';
default:
return 0;
}
}
}
func isStrobogrammatic(num string) bool {
left, right := 0, len(num)-1
// 包含中心位置，奇数长度的中心也必须旋转后保持不变。
for left <= right {
rotated, valid := rotateDigit(num[left])
// 无效标记与数字字符零不同，同时检查旋转后的对称字符。
if !valid || rotated != num[right] {
return false
}
left++
right--
}
return true
}
func rotateDigit(digit byte) (byte, bool) {
switch digit {
case '0', '1', '8':
return digit, true
case '6':
return '9', true
case '9':
return '6', true
default:
return 0, false
}
}
复杂度分析
- 时间复杂度：$O(n)$，
n为字符串长度，最多检查一半字符对和一个中心位。- 空间复杂度：$O(1)$，只使用两个指针和固定的数码映射。
关键点总结
[!green]
- 整体旋转包含数码映射和位置反转，必须一起检查。
- 映射互为逆，因此每对只检查左字符到右字符的方向即可。
- 中心位必须映射成自身，循环不能跳过它。
易错点总结
[!yellow]
- 只检查字符是否属于
0、1、6、8、9：合法字符仍可能没有与对称位置正确配对。- 用普通回文的两端相等判断：
6与9应互相配对，不能要求它们相同。- 循环使用
left < right：会漏掉奇数长度的中心位检查。- 混淆 Java 的无效标记 0 与字符
'0'：前者表示没有映射，后者是合法数码；Go 则通过独立的valid返回值区分。- 只推进一侧指针：之后比较的就不再是互相对应的旋转位置。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 247. 中心对称数 II | 中等 | 原题生成给定长度的全部中心对称数，本题只按成对映射验证一个字符串。 |
| 9. 回文数 | 简单 | 普通回文要求两端数码相同，本题旋转180度需要映射配对，6和9可互换。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！