> For the complete documentation index, see [llms.txt](https://851958789.gitbook.io/notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://851958789.gitbook.io/notes/0233_number_of_digit_one/slt.md).

# 思路1 找规律 + 暴力

需要通过找规律来分析。

从底到高遍历 n 中的每一位。统计每一位中 1 可能出现的次数。

digit 表示当前位的阶，取 1，10，100... cur 表示当前位 high 表示 cur 右边的数 low 表示 cur 左边的数

* cur == 0，则只有在右边的高位会出现 1。高位每变一次，则会有 digit 个 1 出现

    res += high \* digit
* cur == 1，高位同上。同时加上低位的变化。

    res += high \* digit + low + 1
* cur == others，高位同上。同时加上自己在本 digit 会出现的 1 的个数

    res += high \* digit + digit

假设我们对5014这个数字求解。

（1）个位上1出现的个数：记高位为high=501，当前位为cur=4。 那么高位从0\~500变化的过程中，每一个变化中1只出现1次，即（高位1）这样的数字； 高位是501时，因为当前位是4，所以1只能出现一次，即5011。 所以总共出现的次数为high\*1+1=502。

（2）十位1出现的个数：记高位high=50，当前位为cur=1，低位为low=4。 那么高位从0\~ 49变化的过程中，每一个变化中1出现10次，即（高位10）\~（高位19）这样的数字； 高位为50的时候，因为当前位是1，所以我们要看低位来决定出现的次数，因为低位为4，所以此时出现5次，即5010\~5014这样的数字。 所以总共出现的次数为high\*10+5=505。

（3）百位1出现的个数：记高位high=5，当前位cur=0，低位为low=14。 那么高位从0\~ 4的过程中，每一个变化1出现100次，即（高位100）\~（高位199）这样的数字； 高位为5的时候，因为当前位为0，所以不存在出现1的可能性。 所以总共出现的次数为high\*100+0=500。

（4）千位1出现的次数：记高位high=0，当前位cur=5，低位low=014。 那么因为没有高位所以直接看当前位，因为当前位为5，所以1出现的次数为1000，即1000\~1999这样的数字。 所以总共出现的次数为high\*1000+1000=1000。

综上，最终的结果将每个位置出现1的次数累加即可。

502 + 505 + 500 + 1000 = 2507