【leetcode】233.数字1的个数

面tx的时候上来就是这道题，我只想出来暴力的思路，肯定不得分了，赶快学习一下正确的解法。

题目

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

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

示例 1：

输入：n = 13
输出：6

示例 2：
输入：n = 0
输出：0

提示：
0 <= n <= 10^9

注意题目的意思，比如给定的数字n是13，那么1到13中，1一共出现了6次，分别是1、10、11（两个1）、12、13。

暴力的办法就是直接两层循环计算每一位是不是1，是1就count++，最终返回count就行；

思路

基本说明

这里学习一下Krahets大佬的思路：https://leetcode.cn/problems/number-of-digit-one/solutions/2362053/233-shu-zi-1-de-ge-shu-qing-xi-tu-jie-by-pgb1/

思路是将每一位置1后，其他的位会有多少种组合，加起来就是总的1的数量。

比如三位数中，1的个数是：个位数为1时组合的个数+十位数为1时其他数的个数+百位数为1时其他位的组合个数。更多位的数也是这个思路，以此类推。

假设n=22时，1的个数是[1,22]中X1的个数（1、11、21）+[1,22]中1X的个数（10-19，注意这里的11只关注十位数的1），最终得到的结果就是13个。

实例图

提供的数是n，一共有k位，我们可以把n当作Nk N(k-1) ... N1 N0（Nk代表每一位的数）；

cur是当前遍历到的第i个数，Ni（下标）;
high是当前数高位的数，Nk N(k-1) N(k-2) ... N(i+1);
low是当前数低位的数，N(i-1) N(i-2) ... N1 N0;
dights是当前的权值，为10^i；

这个权值是当前位为1时，往后会出现多少个组合，比如cur为十位的时候，其他位和这一位能构成的1的组合是10到19，即10个1（注意这里不关注11的个位数的1），和10^1的结果一致。百位也是如此，能构成1的组合是100到199，一共100个1，也是10^2的值。

具体的分为下面三个情况

cur为0；
cur为1；
cur大于1，即2到9；

1.cur为0

假设n=3404，cur为第1位（从右往左数第二个），hight为34，low为4，dights为10^1=10；此时1出现的次数只和high和dights有关。公式如下
$$
high * dights
$$
你可以把3404想象成一个4位的拨动密码锁，当cur位固定为1了之后，我们需要想办法将这个密码锁拨动到不大于n的最大位置3319。对应high的变动位置是0到33（一共有34个），low的变动位置是0到9（一共10个）。

可得，0到33中，每一次high的变化都会出现10个1（xx10~xx19）。所以得出公式 high * dights，本例子中即为34*10 = 340个1。

cur为0，所以1的个数只与high有关，与low位无关，为什么？

因为十位的cur为0的时候，密码锁不可能拨动到341x的位置（超出范围了），此时不管low位是多少，都不会有更多1的组合，组合被锁定在了低于3404的0010~3319之中。和下文cur为1的情况对照能更好的理解这个情况。

2.cur为1

假设n=3414。十位的cur为1的时候，密码锁就可以拨动到341x的位置了，此时1的个数和high/low都有关系。

high包括00~33的34个10~19（340个1，和上文一致），low包括3410~341x的1的个数，例子中low为4，低位可决定的1的范围是3410到3414，一共有5个数，对应low+1。

此时可以得到公式如下
$$
higt * dights + (low + 1)
$$
下为这种情况的示意图

3.cur大于1

假设n=3434，十位的cur大于1了，可选值已经超过了3419。此时密码锁的拨动还是只和high有关系，可以拨动的范围已经包揽了00~34，一共是35个10~19，公式如下
$$
(high + 1) * dights
$$

下为这种情况的示意图

最终我们只需要遍历每一位的数，将值给加起来，就是题目的和。

代码

有了每一种情况的公式，代码就很容易写出来了。这里需要注意的就是high/low/cur是如何移动到下一位的，以及什么时候需要跳出循环。

class Solution {
public:
    int countDigitOne(int n) {
        int count = 0; // 结果
        // 不大于10的时候只会有一个
        if (n < 10 && n > 0) {
            return 1;
        }
        // 个位数 dights = 10^0 = 1
        long dights = 1;
        // high/cur/low 初始化为个位时的取值
        long high = n / 10; // 除去个位的其他值
        long cur = n % 10;  // 当前位是个位
        long low = 0;       // 个位没有low

        // high和cur同时为0代表遍历结束
        while (high != 0 || cur != 0) {
            if (cur == 0) {
                count += high * dights;
            } else if (cur == 1) {
                count += high * dights + low + 1;
            } else if (cur > 1) {
                count += (high + 1) * dights;
            }
            // 倍增，dights = 10^i
            dights *= 10;
            // 移动到下一位
            // 当cur为十位的时候，high是n/100
            // 当cur为百位的时候，high是n/1000
            high = n / (dights * 10);
            // 当cur为十位的时候，cur是(n/10)%10计算出来的
            // 当cur为百位的时候，cur是(n/100)%10计算出来的
            cur = (n / dights) % 10;
            // 当cur为十位的时候，low是%10计算出来的
            // 当cur为百位的时候，low是%100计算出来的
            low = n % dights;
        }
        return count;
    }
};