思路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