LeetCode第248题：特殊的回文数III

问题描述

特殊的回文数(Strobogrammatic Number)是指那些在旋转180度后看起来仍然相同的数字。例如，数字“69”在旋转180度后看起来仍然是“69”，而“818”在旋转180度后看起来仍然是“818”。

在这个问题中，我们需要计算在给定范围 [low, high] 内（包括边界）的特殊回文数的数量。

难度：困难

示例：

输入：low = "50", high = "100"
输出：3
解释：69, 88, 96 是三个特殊回文数。

注意：由于范围可能很大，输入的 low 和 high 是字符串形式。

解题思路

特殊回文数有一个特性：旋转180度后，某些数字仍然是同一个数字，而某些数字会变成另一个数字。具体来说：

0 旋转后仍然是 0
1 旋转后仍然是 1
8 旋转后仍然是 8
6 旋转后变成 9
9 旋转后变成 6
其他数字旋转后不再是数字

因此，我们只能使用数字 0, 1, 6, 8, 9 来构建特殊回文数。并且，如果使用数字 6，对应位置必须是 9，反之亦然。

解题步骤

使用递归方法生成所有可能的特殊回文数字
检查生成的特殊回文数是否在给定范围内
统计在范围内的特殊回文数的数量

在递归过程中，我们需要注意以下几点：

长度为奇数的特殊回文数，中间位置只能放 0, 1, 8
长度为偶数的特殊回文数，没有中间位置
数字开头不能是 0（除非是单个数字 0）

具体的实现方法是使用递归函数生成所有特殊回文数。我们从最里面（中间位置）开始，逐渐向外扩展构建数字。

代码实现

C#实现

public class Solution {
    // 定义可以互相翻转的数字对
    private readonly (char, char)[] pairs = new (char, char)[] {
        ('0', '0'), ('1', '1'), ('8', '8'), ('6', '9'), ('9', '6')
    };
    
    public int StrobogrammaticInRange(string low, string high) {
        int count = 0;
        int lowLen = low.Length;
        int highLen = high.Length;
        
        // 转换为长整型以便比较
        long lowNum = long.Parse(low);
        long highNum = long.Parse(high);
        
        // 对于每个可能的长度，生成所有特殊回文数
        for (int len = lowLen; len <= highLen; len++) {
            foreach (string num in GenerateStrobogrammatic(len, len)) {
                long val = long.Parse(num);
                if (val >= lowNum && val <= highNum) {
                    count++;
                }
            }
        }
        
        return count;
    }
    
    // 生成长度为n的特殊回文数（当前递归层处理长度为len的数字）
    private List<string> GenerateStrobogrammatic(int n, int len) {
        // 基本情况：空字符串或单个特殊回文数字
        if (n == 0) return new List<string> { "" };
        if (n == 1) return new List<string> { "0", "1", "8" };
        
        // 递归获取长度为n-2的特殊回文数
        List<string> subResults = GenerateStrobogrammatic(n - 2, len);
        List<string> results = new List<string>();
        
        // 为每个子结果添加外层数字对
        foreach (string sub in subResults) {
            foreach (var (first, last) in pairs) {
                // 如果是最外层，不能以0开头
                if (n == len && first == '0') continue;
                
                results.Add(first + sub + last);
            }
        }
        
        return results;
    }
}

Python实现

class Solution:
    def strobogrammaticInRange(self, low: str, high: str) -> int:
        # 定义可以互相翻转的数字对
        pairs = [('0', '0'), ('1', '1'), ('8', '8'), ('6', '9'), ('9', '6')]
        
        # 生成长度为n的特殊回文数
        def generate_strobogrammatic(n, length):
            # 基本情况
            if n == 0:
                return [""]
            if n == 1:
                return ["0", "1", "8"]
            
            # 递归获取内部子串
            sub_results = generate_strobogrammatic(n - 2, length)
            results = []
            
            # 为每个子结果添加外层数字对
            for sub in sub_results:
                for first, last in pairs:
                    # 如果是最外层且长度大于1，不能以0开头
                    if n == length and first == '0':
                        continue
                    results.append(first + sub + last)
            
            return results
        
        # 主函数逻辑
        count = 0
        low_len, high_len = len(low), len(high)
        low_num, high_num = int(low), int(high)
        
        # 对每个可能的长度生成特殊回文数并计数
        for length in range(low_len, high_len + 1):
            for num_str in generate_strobogrammatic(length, length):
                num = int(num_str)
                if low_num <= num <= high_num:
                    count += 1
        
        return count

C++实现

class Solution {
public:
    int strobogrammaticInRange(string low, string high) {
        // 定义可以互相翻转的数字对
        vector<pair<char, char>> pairs = {
            {'0', '0'}, {'1', '1'}, {'8', '8'}, {'6', '9'}, {'9', '6'}
        };
        
        // 生成长度为n的特殊回文数
        function<vector<string>(int, int)> generateStrobogrammatic = [&](int n, int length) {
            // 基本情况
            if (n == 0) return vector<string>{""};
            if (n == 1) return vector<string>{"0", "1", "8"};
            
            // 递归获取内部子串
            vector<string> subResults = generateStrobogrammatic(n - 2, length);
            vector<string> results;
            
            // 为每个子结果添加外层数字对
            for (const string& sub : subResults) {
                for (const auto& [first, last] : pairs) {
                    // 如果是最外层且长度大于1，不能以0开头
                    if (n == length && first == '0') continue;
                    
                    results.push_back(first + sub + last);
                }
            }
            
            return results;
        };
        
        // 主函数逻辑
        int count = 0;
        int lowLen = low.length(), highLen = high.length();
        
        // 对每个可能的长度生成特殊回文数并计数
        for (int len = lowLen; len <= highLen; len++) {
            for (const string& numStr : generateStrobogrammatic(len, len)) {
                // 数字比较
                if ((len == lowLen && numStr.compare(low) < 0) || 
                    (len == highLen && numStr.compare(high) > 0)) {
                    continue;
                }
                count++;
            }
        }
        
        return count;
    }
};

性能分析

时间复杂度

生成特殊回文数的时间复杂度取决于数字的长度和可能的组合：

长度为n的特殊回文数的数量大约是 5^(n/2)，因为每两位我们有5种可能的数字对
我们需要遍历从low到high长度范围内的所有可能长度
生成并检查每个特殊回文数

总体时间复杂度约为O(highLen * 5^(highLen/2))，其中highLen是high字符串的长度。

空间复杂度

递归调用栈的深度与数字长度有关，约为O(highLen)。存储生成的特殊回文数的空间约为O(5^(highLen/2))。

因此，总体空间复杂度为O(highLen + 5^(highLen/2))，主要由存储生成的特殊回文数所需的空间决定。

优化方向

字符串比较优化：可以先比较长度，再比较字符串，减少不必要的比较操作
提前剪枝：在递归生成过程中，如果确定某个前缀已经超出范围，可以提前停止生成
针对大数情况的优化：当数字范围非常大时，可以考虑更高效的生成和比较方法

代码亮点

递归生成特殊回文数的方法设计合理，从中间向两边扩展
考虑了数字不能以0开头的特殊情况
使用函数式编程风格（尤其是C++实现中）提高了代码可读性
对范围边界处理准确，确保计数不会遗漏或重复