题目

暴力（超时）

枚举每一个比n小的数，然后算它们的含有1的数量，相加即可。

class Solution {
public:
    int countDigitOne(int n) {
        int ans = 0;
        for (int i = 1; i < n; ++i) {
            int cnt = 0;
            int num = i;
            while (num != 0){
                if(num % 10 == 1){
                    cnt++;
                }
                num /= 10;
            }
            ans += cnt;
        }
        return ans;
    }
};

但是，当用例非常大的时候，比如，n=824883294，会超时，过不了所有用例，放弃！

动态规划

数位DP

模拟

行李箱的滚轮密码锁，我们固定其中的某一位，然后可以随意滑动其他位，算出其他位有多少种可能。 问题是我们该如何统计出可能的次数呢？

• 假设我们想要得到十位上1出现的次数，当前我们的指针指向十位，我们称之为当前位。

• 我们用num 代表当前位的位因子， 则：

  • 指针指向个位时，num = 1
  • 指针指向十位时，num = 10
  • 指针指向百位时，num = 100
  • …

• 我们将
  
  当前位的左边定义为高位，右边定义为低位
  
  。 比如：n = 1004 ，此时指针指向十位（当前位）num = 10，高位为百位，千位，低位为个位

• 而且我们某一位的取值范围为 0 ~ 9,那么我们可以将这 10 个数分为 3 类，小于 1 （当前位数字为 0 ），等于 1（当前位数字为 1 ） ，大于 1（当前位上数字为 2 ~ 9），下面我们就来分别考虑三种情况。

下面我们来举几个例子，重点讨论十位上 3 种不同情况。

假设

n = 1004

，我们想要计算出小于等于 1004 的非负整数中，十位上出现 1 的次数。也就是当前位为十位，数字为 0 时，十位上出现 1 的次数。

思路

可以得出如下表格。

可以看出，上表的数据非常有规律。接下来我们要做的就是根据给定 n 的范围，再来求出其出现 ‘1’ 的次数。

建模思路如下：

• 首先，我们可以很快的确定一点，假如
  
n

  是
  
x

  位数，那么n至少会有对应表格中(x-1)位数总和的次数。例如n=233，那么其结果至少大于20，因为光是0~99区间内，‘1’ 就出现了20次。n 大于99，其结果一定大于20。我们不妨把这个值称为“基础”，例如13的“基础”是1；566的“基础”是20；2846的“基础”是300…以此类推。