LeetCode 246. 中心对称数

2024-01-17 HGNULB 约 6 分钟

文章信息 6 个分类 3 个标签

分类

题目描述

✅ 246. 中心对称数

题意分析

给一个用字符串表示的数字 num，问它旋转 180 度之后看起来是否和原来一样。旋转 180 度就是把纸转半圈，注意不是照镜子——转半圈同时颠倒了左右和上下。

把这个物理描述翻译成可判定的条件，需要分两步。第一步，单个数字转 180 度后能不能仍然是一个合法数字：0、1、8 转过来还是自己，6 转过来变成 9，9 转过来变成 6，而 2 3 4 5 7 转过来根本不成形。所以只要串里出现这五个字符中的任何一个，答案立刻是 false。

第二步，整串怎么对齐。因为旋转把左右也颠倒了，原串的第一个字符转过去会落到新串的最后一个位置。所以判定条件是：对每个下标 i，num[i] 旋转后的字符必须等于 num[n-1-i]。这是一个从两端向中间的对称条件，而不是从左到右的顺序条件。

约束里给的是字符串而不是整数，这是个明确信号：数字可能很长、可能有前导零（题目允许 "00" 这类输入），所以不能先转成整数再处理，只能逐字符判断。

边界有三处。空串按定义自反，返回 true。长度为奇数时中间那个字符会和自己配对，此时要求它旋转后等于自己，也就是只能是 0、1、8；6 和 9 单独放在正中间是不合法的，这是本题最容易漏的一条。长度为偶数时没有自配对的字符。

还有一点要澄清：题目不要求 num 是「有效数字」，"00" 是合法输入且答案为 true，不需要对前导零做任何额外拒绝。

解法：双指针对称映射

核心思路

旋转 180 度会同时改变字符和左右位置。合法映射只有 0↔0、1↔1、6↔9、8↔8、9↔6，因此用双指针直接检查两端，不必构造旋转后的新字符串。

对每一对 (left,right)，左字符旋转后必须等于右字符。映射是自逆的，所以验证一个方向已经足够。

循环不变量是：left 外侧已经检查过的字符对全部满足旋转映射。每轮验证当前一对后同时内收；使用 left <= right，让奇数长度的中心字符也接受“旋转后仍等于自身”的检查。

正确性说明：旋转后的第 right 位正是原串第 left 位的映射。算法逐对检查所有对应位置，任何失败都足以否定；全部通过则旋转后每一位都与原串相同。中心位只有 0、1、8 能通过，边界也被统一覆盖。

解题步骤

初始化 left = 0、right = num.length - 1。

查询左字符的旋转映射；字符不合法则返回 false。

若映射结果不等于右字符，返回 false。

两个指针同时内收，直到区间为空；随后返回 true。

"69"、"818" 合法；"66" 的两端映射不匹配；"161" 会在中心 6 处失败。"00" 也合法，题目按字符串判断，不应擅自拒绝前导零。

代码实现

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)$。最多检查一半字符对。

空间复杂度：$O(1)$。只使用两个指针和常数映射分支。

关键点总结

物理旋转要同时落实为“字符映射”和“左右位置互换”。

双指针直接判定比构造、反转再比较少用线性空间。

中心字符也必须自映射，因此循环条件要包含 left == right。

6 与 9 互换，0、1、8 自映射，其余数字非法。

易错点总结

只检查字符是否属于 01689："66" 会被误判为真，实际旋转后是 "99"。

循环使用 left < right："161" 的中心 6 未检查，会错误返回真。

忘记交换 6 和 9："69" 会被误判为假。

先转成整数：会丢失 "00" 的长度信息，长字符串还可能溢出。

构造映射串后忘记反转："69" 会得到 "96" 并与原串错误比较。

只移动一个指针：后续配对位置错乱，可能重复检查或漏掉字符。

相似题目

题目	难度	考察点
125. 验证回文串	简单	同样是相向双指针，但映射退化为恒等，重点在跳过非字母数字与大小写归一
9. 回文数	简单	输入是整数不能转字符串时，要用「反转一半数字」的取模技巧处理奇偶长度
680. 验证回文串 II	简单	允许删一个字符，双指针失配时要分叉成两条贪心验证，考察容错分支的设计
234. 回文链表	简单	链表拿不到随机下标，需先用快慢指针找中点再反转后半段才能相向比较
344. 反转字符串	简单	双指针交换而非比较，是本题「相向收拢」骨架最基础的写法
面试题 01.04. 回文排列	简单	判定的是能否重排成回文，条件从下标对应变成「奇数次字符至多一个」
267. 回文排列 II	中等	不只判定还要构造全部方案，需要在半串上做去重全排列再镜像拼接