0%

Leetcode233

233. 数字 1 的个数

难度困难303收藏分享切换为英文接收动态反馈

给定一个整数 n,计算所有小于等于 n 的非负整数中数字 1 出现的个数。

示例 1:

1
2
输入:n = 13
输出:6

示例 2:

1
2
输入:n = 0
输出:0

提示:

  • 0 <= n <= 2 * 109

Solution

拿到题目很奇怪,这道题暴力解答也就是个稍稍大于o(n)的复杂度,作为hard题目出现,只能说明暴力会超时

那么先回顾一下整体的超时代码段

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
* @param {number} n
* @return {number}
*/
var countDigitOne = function (n) {
let counter = 0;
for (let i = n; i > 0; i--) {
let num = i;
while (num > 0) {
if (num % 10 === 1) {
counter++;
}
num = Math.floor(num / 10);
}
}
return counter
};

超时之后我就开始找规律,个位1只会出现1次,十位只会出现10次,百位是100次,之后是数学方法就不解了(懒orz),答案的主要部分

1
2
3
4
for (let k = 0; n >= mulk; ++k) {
ans += (Math.floor(n / (mulk * 10))) * mulk + Math.min(Math.max(n % (mulk * 10) - mulk + 1, 0), mulk);
mulk *= 10;
}