Links

43.1~n整数中1出现的次数

一、 题目

输入一个整数 n ,求1~n这n个整数的十进制表示中1出现的次数。
例如,输入12,1~12这些整数中包含1 的数字有1、10、11和12,1一共出现了5次。
示例 1:
输入:n = 12
输出:5
示例 2:
输入:n = 13
输出:6
限制:
1 <= n < 2^31
注意:本题与主站 233 题相同:https://leetcode-cn.com/problems/number-of-digit-one/
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

二、 分析

2.1 暴力

当然遍历全部数字,进行累加理论上是可行的。但是如果真写出这样的代码就别想通过面试了🤷‍♂️。

2.2 按位分析

我们需要知道一个前提,1出现的次数和就是1在每一位上出现的次数的和。那么我们如何计算出每一位上出现1的次数呢?
下面我们以310562为例进行一下分析。
百位
我们想知道在这位出现1的次数,我们定义当前位的数字为 num = 5 , 其左边的所有数字为 pre = 310 , 右边的数字为 aft = 62 ,当前位为 base = 100
  • 左组合数量:
    • 0 ~ 310
    • pre + 1
  • 右组合数量:
    • 0 ~ 99
    • base
      • 因为 1 < 5 ,百位为1时位数足够,可以取到 99
      • 其实就等于当前的,即100
次数 = (pre + 1) * base
1
千位
pre = 31, num = 0, base = 1000, aft = 562
1
  • 当前位为0,当为1时必须需要前面退位,如上图变化
    • 前范围变为 0 ~ 30
  • 左组合数量
    • 0 ~ 30
    • pre
  • 右组合数量:
    • 0 ~ 999
    • base
次数 = (pre * base)
万位
pre = 3, num = 1, base = 10000, aft = 0562
3
  • 当 pre 取 0 ~ 2 时:
    • 左组合数量
      • 0 ~ 2
      • pre
    • 右组合数量:
      • 0 ~ 999
      • base
  • 当 pre 取 3 时:
    • 左组合数量
      • 3
      • 1
    • 右组合数量:
      • 0 ~ 562
      • (aft + 1)
次数 = (pre * base) * (aft + 1)
左数 & 右数
上面将所有三种特殊情况的次数计算方式都推导出来了。剩下推出 pre aft num 的公式即可。
  • 根据规律推导出:
    • pre = n / base / 10
    • aft = n % base
    • num = n / base % 10
下面我们就可以根据上面的公式完成遍历的逻辑了。

三、 编码

func countDigitOne(_ n: Int) -> Int {
var base = 1
var sum = 0
while base <= n {
let pre = n / base / 10
let aft = n % base
let num = n / base % 10
if num == 1 {
sum += ((pre * base) + (aft + 1))
}
else if num == 0 {
sum += (pre * base)
}
else {
sum += ((pre + 1) * base)
}
base *= 10
}
return sum
}
4