Skip to content
Permalink
Branch: master
Find file Copy path
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
149 lines (113 sloc) 5.94 KB

title:Number of Digit One

Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.

Example:

Input: 13 Output: 6 Explanation: Digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.

法一 - 按位

参考leetcode官方解答。

1.个位数上的1:

  • 每10个数内,出现一次1
  • 如果个位数不为0,一定会出现一次1.

n/10 + min(0,max(1,(n%10-1+1)))

2.十位上的1:

  • 每100次,十位上出现10次1。
  • 当十位数大于1,会出现10次1;如161x(x:[0,9]),+x+1次;16y0(y:[2,9])=+10次。所以只可能加0~10次。
  • 设个位数为x,x = n%100-10 。而且x是大于等于0的,所以用max(0,x),由于要加x+1次,所以用 max(0,x+1)

n/100 * 10 + min(10, max(0 , (n%100-10) +1))

3.百位上的1:

  • 每1000次,百位上出现100次1.
  • 如果百位上的数字大于了2,百位上出现了100次1(不超过100次)
  • 如果百位数是1或者0,百位上会出现(n%1000 -100)+1次1.(不小于0次)

n /1000 *100 + min(100, max(0,n%1000 -100 +1))

如n=1234

  • 个位的1:1234/10*1+min(1,4)=123*1+1=124

  • 十位的1:1234/100*10 + min(10,25)=12*10+10=130

  • 百位的1:1234/1000*100+min(100,(234-100)+1)=1*100+100=200

  • 千位的1:1234/10000*1000+min(1000,(1234-1000)+1)=0*1000+235=235

    总计:124+130+200+235=689

数学模型

$$ n/(degree*10)degree + min(degree,max(0,n%(10degree)-degree+1)) $$

C++ code

class Solution {
public:
    int countDigitOne(int n) {
        if(n<=0)
        return 0;    
        int ret=0;
        for(long long degree=1;degree<=n;degree*=10)       
  			ret += n /(degree*10)*degree + min(degree, max((long long)0, n % (10 * degree) - degree+1));
        return ret;
    }
};

T:O(logn) S:O(1)

总结

1.这种方法是计算个十百千万位上1出现的次数,找到不同位上1出现次数的规律,解得通用公式,一般是一个分段函数。再将所有位上的次数相加,就是最终结果。 2.这道题容易错的地方是n/(degree*10)*degree不能写成n/10,因为可能n/(degree*10)的结果是0。 3.用迭代防止栈溢出,还可以使O(1)。 4.防止栈溢出,用long long来表示大数;同时开始ret要赋初值0,否则是一个很大的数;用中的max()时,要用(long long)强制转换。

法二 - 划分

参考LC高票回答。

含1的数字 1的个数 数字范围
1 1 [1,9]
10 11 12 13 14 15 16 17 18 19 11 [10,19]
21 1 [20,29]
31 1 [30,39]
41 1 [40,49]
51 1 [50,59]
61 1 [60,69]
71 1 [70,79]
81 1 [80,89]
91 1 [90,99]
总计 11+1*9=20 [001,099]
100 101 102 103 104 105 106 107 108 109 11 [100,109]
110 111 112 113 114 115 116 117 118 119 21 [110,119]
120 121 122 123 124 125 126 127 128 129 11 [120,129]
... ... ...
总计 21+11*9=120 [100,199]
... 20 [200,299]=[0,99]
... 20 [300,399]=[0,99]
... ... ...
... 20 [900,999]=[0,99]
总计 120+20*9=300 [001,999]
  • 对于任意两位数,十位数上的数字+1就代表1出现的个数
  • 当十位数大于等于2的时候(x+8)/10,要再加上多出来的10个1.

如:n=3141592,按个十百千万位来划分

  • 当m=100时,a=31415,b=92;百位数1的前缀是""到"3141".所以是3142次。
  • 所以百位是1的时候,出现了 (a/10+1)*100 次。
  • 当m=1000时,a=3141,b=592;千位数1的前缀是""到"314",一共315次。
  • 因为最后一个千位数是1,所以最后一次没有满1000次,而是"000"到"592",一共593次。
  • 所以千位是1的时候,出现了(a/10*1000)+(b+1)次
  • 为了判断最后一位是否为1.用(a+8)/10来获取满载的次数,用a%10==1来判断是否需要添加额外的次数。

C++ code

class Solution {
public:
int countDigitOne(int n) {
    if(n<=0)
    return 0;    
    int ret=0;
    for(long long degree=1;degree<=n;degree*=10)
        {
            long long a = n/degree;
            long long b = n%degree;
            ret+=(a+8)/10 *degree//满载
            +(a%10==1)*(b+1);//a的最后一位为1,会加剩下的余数+1
        }
    return ret;
}
};

总结

1.这种方法的思想是把大范围的数划分为小范围的数来计算。 2.前缀的最后一位如果大于等于2就进满载,即(a+8)/10*degree。如果题目问的是3出现的大小,就大于等于4进满载(a+4)/10*degree。 3.判断最后一位是不是1(a%10==1),如果是1就要加(剩下的余数+1),加1是尾号为000的时候。

You can’t perform that action at this time.