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

发布于 2022年 04月 12日 00:47

输入一个整数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;
    }
}

推荐文章