优化区间回文数统计Python代码时间复杂度及补全缺失条件的问询

现有代码的效率问题 #

你当前的代码是遍历区间内每个数，转成字符串后反转比较，时间复杂度为 O((m-n+1)*d)（d是数字的位数）。如果区间范围极大（比如从1到10亿），效率会极低——毕竟大部分数都不是回文，做了大量无用判断。

更高效的方案：直接生成回文数 #

换个思路：利用回文数的对称结构，直接生成所有落在[n,m]范围内的回文数，再统计数量。这种方法的时间复杂度为 O(10^ceil(d/2))（d是m的位数），远低于遍历法。

实现代码 #

def count_palindromes(n, m):
    count = 0
    # 负数无有效回文：比如-121反转后是121-，和原数不等
    if n < 0:
        n = 0
    # 按数字位数分批生成回文数
    max_len = len(str(m))
    for length in range(1, max_len + 1):
        # 生成回文数的前半部分
        half_start = 10 ** ((length - 1) // 2)
        half_end = 10 ** ((length + 1) // 2)
        for half in range(half_start, half_end):
            half_str = str(half)
            # 根据位数奇偶拼接回文数
            if length % 2 == 0:
                palindrome = int(half_str + half_str[::-1])
            else:
                palindrome = int(half_str + half_str[:-1][::-1])
            # 超出范围就停止当前长度的生成，减少无效循环
            if palindrome > m:
                break
            if palindrome >= n:
                count += 1
    # 单独处理0的情况（如果0在区间内）
    if n <= 0 <= m:
        count += 1
    return count

当前函数未处理的潜在条件 #

• 输入顺序错误：当n > m时，现有函数会返回0，但实际应提示输入无效，或自动交换n和m后计算
• 非整数输入：若传入浮点数（如10.5）、字符串等非整数类型，函数会直接抛出TypeError，无类型校验与容错
• 负数回文定义分歧：现有逻辑默认负数不算回文，但如果用户认为-121这类数属于回文，当前逻辑不支持（字符串反转后与原数不等）
• 非法参数无处理：传入None、列表等非法参数时，函数会直接崩溃

时间复杂度提升的核心建议 #

1. 放弃遍历判断，改用生成式枚举：利用回文的对称结构，仅生成前半部分即可拼接出完整回文数，避免大量无效计算
2. 提前终止循环：生成回文数超过m时，直接停止当前长度的生成，减少不必要的循环
3. 分位数批量处理：按数字的位数分批生成回文，避免生成超出目标范围长度的无效回文

内容的提问来源于stack exchange，提问作者Jimmy