LeetCode第246题：中心对称数

问题描述

中心对称数（Strobogrammatic Number）是指在旋转180度后看起来依然相同的数。例如，数字“69”在旋转180度后看起来仍然是“69”，数字“88”旋转后也是“88”，而数字“962”旋转后则不是一个有效的数字。

编写一个函数来判断一个数字（以字符串形式表示）是否是中心对称数。

难度：简单

示例：

示例 1:
输入: num = "69"
输出: true

示例 2:
输入: num = "88"
输出: true

示例 3:
输入: num = "962"
输出: false

示例 4:
输入: num = "1"
输出: true

解题思路

要判断一个数字是否是中心对称数，我们需要知道哪些数字在180度旋转后仍然是有效的数字：

• 0 旋转后是 0
• 1 旋转后是 1
• 8 旋转后是 8
• 6 旋转后是 9
• 9 旋转后是 6
• 其他数字（2, 3, 4, 5, 7）在旋转后不是有效的数字

利用这个特性，我们可以使用双指针方法从字符串的两端向中间移动，检查每对数字是否满足中心对称的条件。具体步骤如下：

1. 创建一个映射表，记录每个数字旋转180度后的结果
2. 使用两个指针，一个从字符串的开始（left），一个从字符串的结尾（right）
3. 当 left <= right 时，检查 num[left] 旋转后是否等于 num[right]
4. 如果任何一对不满足条件，返回 false
5. 如果所有对都满足条件，返回 true

代码实现

C#实现

public class Solution {
    public bool IsStrobogrammatic(string num) {
        // 记录每个数字旋转180度后的结果
        int[] map = new int[] {0, 1, -1, -1, -1, -1, 9, -1, 8, 6};
        
        // 双指针，从两端向中间移动
        int left = 0, right = num.Length - 1;
        
        while (left <= right) {
            // 将字符转换为数字
            int leftDigit = num[left] - '0';
            int rightDigit = num[right] - '0';
            
            // 检查leftDigit旋转后是否等于rightDigit
            if (map[leftDigit] != rightDigit) {
                return false;
            }
            
            left++;
            right--;
        }
        
        return true;
    }
}

Python实现

class Solution:
    def isStrobogrammatic(self, num: str) -> bool:
        # 记录每个数字旋转180度后的结果
        rotated_digits = {
            '0': '0',
            '1': '1',
            '8': '8',
            '6': '9',
            '9': '6'
        }
        
        left, right = 0, len(num) - 1
        
        while left <= right:
            # 如果当前数字不在映射表中，或者旋转后不等于另一端的数字
            if num[left] not in rotated_digits or rotated_digits[num[left]] != num[right]:
                return false
            
            left += 1
            right -= 1
            
        return True

C++实现

class Solution {
public:
    bool isStrobogrammatic(string num) {
        // 记录每个数字旋转180度后的结果
        vector<int> map = {0, 1, -1, -1, -1, -1, 9, -1, 8, 6};
        
        int left = 0, right = num.size() - 1;
        
        while (left <= right) {
            // 将字符转换为数字
            int leftDigit = num[left] - '0';
            int rightDigit = num[right] - '0';
            
            // 检查leftDigit旋转后是否等于rightDigit
            if (map[leftDigit] != rightDigit) {
                return false;
            }
            
            left++;
            right--;
        }
        
        return true;
    }
};

性能分析

时间复杂度

算法的时间复杂度为 O(n)，其中 n 是输入字符串的长度。我们只需要遍历一次字符串的一半。

空间复杂度

算法的空间复杂度为 O(1)，因为我们只使用了固定大小的映射表和几个变量，不受输入字符串大小的影响。

代码亮点

1. 使用数组映射实现O(1)时间复杂度的旋转查询
2. 双指针技巧减少了遍历次数，只需要检查字符串的一半
3. 优雅地处理了特殊情况：当字符串长度为奇数时，中间的数字只能是0、1或8

相关题目

• LeetCode 247. 中心对称数 II - 中等
• LeetCode 248. 中心对称数 III - 困难