求实现含start number、end number参数的函数：统计不含数字5的整数数量

核心思路 #

直接遍历区间内每个数检查是否含5，在end达到1e9时完全不可行，效率极低。正确的做法是计算f(end) - f(start-1)，其中f(n)表示从0到n（n≥0）或从n到0（n<0）中不含数字5的整数数量。通过数位DP快速计算f(n)，时间复杂度仅与数字的位数相关（最多10位），完全适配大数场景。

分步实现 #

1. 实现正数区间的计数辅助函数count_non_five(n) #

这个函数计算0到n（n≥0）中不含数字5的整数数量，用数位DP逐位统计：

• 将数字转为字符串，逐位分析每一位的可选范围
• 区分"受限"状态（当前位不能超过原数字对应位）和"不受限"状态（当前位可自由选0-9除5）
• 最后检查原数字本身是否不含5，若是则加1（因为前面统计的是小于n的符合条件的数）

代码示例（Python）：

def count_non_five(n):
    if n < 0:
        return 0
    s = str(n)
    length = len(s)
    res = 0
    tight = True  # 标记当前位是否受原数字对应位的限制
    for i in range(length):
        digit = int(s[i])
        if not tight:
            # 不受限时，当前位有9种选择，后续每位也有9种选择
            res += 9 ** (length - i)
            continue
        # 计算当前位可选的小于digit且不含5的数字数量
        less_count = digit - 1 if digit > 5 else digit
        # 后续每位有9种选择，累加这部分数量
        res += less_count * (9 ** (length - i - 1))
        # 如果当前位是5，后续位无需再处理（选5的数不符合要求）
        if digit == 5:
            tight = False
            break
    # 若原数字本身不含5，将其计入结果
    if '5' not in s:
        res += 1
    return res

2. 处理正负混合的区间情况 #

根据start和end的正负性分三种情况计算：

• 两者均为非负数：直接用count_non_five(end) - count_non_five(start-1)
• start负、end非负：拆分为[start, 0]和[1, end]两部分，前者数量等于count_non_five(abs(start))（负数的数字部分不含5等价于其绝对值不含5），后者数量为count_non_five(end) - 1（减去重复统计的0）
• 两者均为负数：区间对应绝对值的[abs(end), abs(start)]，数量为count_non_five(abs(start)) - count_non_five(abs(end)-1)

主函数代码：

def count_without_five(start, end):
    if end >= 0:
        if start >= 0:
            return count_non_five(end) - count_non_five(start - 1)
        else:
            # 负数区间[start,0] + 正数区间[1,end]
            return count_non_five(abs(start)) + (count_non_five(end) - 1)
    else:
        # 均为负数，转换为绝对值区间计算
        abs_start = abs(start)
        abs_end = abs(end)
        return count_non_five(abs_start) - count_non_five(abs_end - 1)

测试验证 #

几个典型场景的测试结果：

• count_without_five(1, 10) → 返回9（1-4、6-10共9个数）
• count_without_five(-5, 5) → 返回9（-4到4共9个数）
• count_without_five(-10, -5) → 返回5（-10、-9、-8、-7、-6共5个数）
• count_without_five(10**9, 10**9) → 返回1（10^9不含5）

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