题目难度: 困难原题链接今天继续更新 Leetcode 的剑指 Offer专项突击版系列, 大家在公众号算法精选里回复剑指offer2就能看到该系列当前连载的所有文章了, 记得关注哦~题目描述给定一个整数 num计算所有小于等于 num 的非负整数中数字 1 出现的个数。示例 1输入num 0输出0示例 2输入num 13输出6提示0 num 109题目思考可否单独统计每一位上的 1?解决方案思路一个最简单的思路是从 1 到 num 依次遍历, 然后统计各个数字的 1 的数目并累加, 但观察题目数据规模, 最大都到了 2^31, 这个做法肯定会超时换个思路, 如果我们可以单独统计每一位上的 1 在多少个数中存在, 这样只需要遍历所有位数并累加结果即可举个例子, 假如num 12x45, 现在要统计1~12x45在第 x 位上 1 的数目, 显然这里分为三种情况:x 1: 此时要想这一位上有 1, 那么前两位的范围只能是 0~11, 而后两位的范围则可以是 0~99, 也即00100, 00101, ..., 11199这么多种可能性, 只考虑该位上的 1, 那么它的数目就是左右取值范围的乘积, 也即12*100x 1: 此时显然仍包含第一种情况中的可能性, 但它有额外的部分, 也即前两位是 12, 然后后面的范围是 0~45, 加起来就是12*100 1*46个 1x 1: 此时仍包含第一种情况中的可能性, 但对于前两位是 12 来说, 后面的取值范围就是 0~99 了, 因为12199 12x45, 所以加起来就是12*100 1*100个 1综合这三种情况, 就能够计算出每一位上的 1 的数目, 最后累加起来就是总的 1 的数目注意x 1的数目是所有情况下共享的, 所以可以先计算出这一部分, 然后针对x 1和x 1再额外计算剩余部分, 从而减少代码冗余下面的代码对必要步骤有详细的解释, 方便大家理解复杂度时间复杂度O(logN)只需要遍历 num 的每一位, 总位数是 logN空间复杂度O(1)不需要额外空间代码classSolution:defdigitOneInNumber(self,num:int)-int:# 对每一位进行判断, 左右相乘, 分大于等于小于1三种情况res0# 将数字先转成字符串, 方便对每一位的处理sstr(num)fori,xinenumerate(s):# 对应x1时的左边部分的取值范围# 注意对于最高位而言, 它的左边部分为0, 这是因为最高位不可能小于1, 所以这部分不应该有left0ifi0elseint(s[0:i])# 对应x1时的右边部分的取值范围right10**(len(s)-i-1)ifx1:# 当x1时, 直接加上分析的左右部分乘积即可resleft*rightelifx1:# 当x1时, 需要额外加上右边的计数, 对于例子12x45 (x1)来说, 就是46# 注意如果此时是最低位, 那么额外只有1种可能, 就是上限n本身, 所以最低位1的话只需要加上1extra1ifilen(s)-1elseint(s[i1:])1resleft*rightextraelse:# 当x1时, 需要额外加上1*rightres(left1)*rightreturnres大家可以在下面这些地方找到我~我的 GitHub我的 Leetcode我的 CSDN我的知乎专栏我的头条号我的牛客网博客我的公众号: 算法精选, 欢迎大家扫码关注~