数码吧

1~n整数中1出现的次数

输入一个整数n,求1~n这n个整数的十进制表示中1出现的次数

• 如1~12的整数中，包含1的数字有1，10,11,12，共出现了5次
• 思路

1. 将cur指向当前位，high代表比当前位高的几位，low代表比当前位低的位数。

2. cur值的不同，要求我们分情况看：

   1. cur = 0 时:

      1出现的次数只由高位决定，例如3306，cur指向十位，digit = 10,百位和千位决定了十位上1出现的次数：0010~3219 只看高低位，即000~329，1出现的次数为329-000=330； 其实换一种理解方式就是33x10=330 (high×digit)。每个十位上，从0到9十个数，每个1就有10个各位上的1。

   2. cur = 1 时： 1出现的次数由高位high和低位low共同决定，例如3316，cur指向十位，digit = 10，高位high = 33,低位low = 6。出现1的数字范围为0010~3316，只看高低位，即000~336，出现次数为336-0+1=337次。其实就是在0010~3219的基础上多了3310~3316中的7个1。于是有计算公式：high × digit + low + 1;

   3. cur > 1时： 此时出现的次数就仅由高位决定了。例如3336，cur指向十位，digit = 10，高位high = 33,低位low = 6。出现1的数字范围为0010~3319,只看高地位：000~339，出现次数 为339-0+1=340次。其实就是0010~3319，所有的十位上的1都取满了 ，就是00~33为百位，对应的十位为1全部取满，所以为**(high+1)×digit**.

• 变量变化步骤： 按照个十百的顺序慢慢计算，起始cur指向个位，digit为1，low为0，high为n/10,cur为n%10,如此不断往上递推，从个位到高位递推。

while (high != 0 || cur != 0) {
    ......//一堆分情况计算的公式
    low = low + digit * cur;//low为十位和个位数之和
    cur = high % 10;//cur指向某一位，不断前移
    high = high/10;//high代表高位，包含的数字不断减少
    digit = digit * 10;//digit代表cur位为1包含的个数
}

• 代码

class Solution {
    public int countDigitOne(int n) {
        int high = n/10,cur = n%10,low=0;
        int res = 0, digit = 1;
        while (high != 0 || cur != 0) {
          if (cur == 1) res += (high * digit) + low + 1;
          else if(cur < 1) res += (high * digit);
          else if(cur > 1) res += (high + 1) * digit;
          low = low + digit * cur;
          cur = high % 10;
          high = high/10;
          digit = digit * 10;
        }
        return res;
    }
}