# 题目

• 示例 1：
输入：n = 13


• 示例 2：
输入：n = 0



0 <= n <= 2 * 10^9

# 暴力法

## java 实现

/**
* 最基本的思路：
*
* 直接统计各个位数的信息。
* @param n
* @return
*/
public static int countDigitOne(int n) {
int sum = 0;
for(int i = 1; i <= n; i++){
sum += countOne(i);
}
return sum;
}

// 可以用除法，也可以转换为字符串处理。
private static int countOne(int n) {
int count = 0;
String string = n+"";
char[] chars = string.toCharArray();
for(char c : chars){
if(c == '1') {
count++;
}
}
return count;
}


# 数字找规律

## 思路

(1) xyz * 1000                     if d == 0
(2) xyz * 1000 + abc + 1           if d == 1
(3) xyz * 1000 + 1000              if d > 1


## 3 个场景详解

（1）数字 4560000 千位有多少 1？

4551000 to 4551999 (1000)
4541000 to 4541999 (1000)
4531000 to 4531999 (1000)
...
1000 to 1999 (1000)


（2）数字 4561234 千位有多少 1？

4561000-4561234 (1234+1)
4551000 to 4551999 (1000)
4541000 to 4541999 (1000)
4531000 to 4531999 (1000)
...
1000 to 1999 (1000)


（3）数字 4562345 呢？

4561000-4561999 (1000)
4551000 to 4551999 (1000)
4541000 to 4541999 (1000)
4531000 to 4531999 (1000)
...
1000 to 1999 (1000)


## java 实现

int countDigitOne(int n) {
if (n < 1) {
return 0;
}

long digit = 1;
int high = n / 10, current = n % 10, low = 0;
int count = 0;

while (high != 0 || current != 0) {
if (current == 0) {
count += high * digit;
}
else if (current == 1) {
count += high * digit + low + 1;
}
else {
count += (high + 1) * digit;
}

// 更新
low += current * digit;
current = high % 10;
high /= 10;
digit *= 10;
}

return count;
}


Runtime: 0 ms, faster than 100.00% of Java online submissions for Number of Digit One.
Memory Usage: 35.9 MB, less than 33.83% of Java online submissions for Number of Digit One.


# 拓展

private static int count(int n, int x) {
int cnt = 0;
int mul =1;
int left =n;
int right =0;
if(n==0) {
return x<1?n:0;
}

while(left>0) {
int digit = left%10;
left/=10;
if(digit == x) {
cnt+=left*mul;
cnt+=right+1;
}
else if(digit<x) {
cnt+=left*mul;
}
else {
cnt+=(left+1)*mul;
}

if(x == 0&&mul>1) {
cnt-=mul;
}

right+=digit*mul;
mul*=10;
}

return cnt;
}


# 参考资料

https://leetcode-cn.com/problems/number-of-digit-one/