Leetcode 233.数字1的个数

数字1的个数

给定一个整数 n,计算所有小于等于 n 的非负整数中数字 1 出现的个数。

示例:

输入: 13

输出: 6

解释: 数字 1 出现在以下数字中: 1, 10, 11, 12, 13 。

1的总个数为1在1~n所有数中

个位数上有1的个数+十位数上有1的个数+...+亿位数上有1的个数+...

自己动手亲自找一遍规律就能得出答案:

首先,找规律:

13

个位数为1:1 11

十位数为1:10 11 12 13

1的总个数为: 2+4=6

23

个位数为1:1  11 21

十位数为1:10 11 12 13 14 15 16 17 18 19

1的总个数为:3+10=13

345

个位数为1:1 11 21 31 41 51 61 71 81 91 101 111 121 131 141   ...341

十位数为1:10 11 12 13 14 15 16 17 18 19  ...311 312 ...319

百位数为1:100  101...199

1的总个数为:100+40+35=175

进而可得通项:

通项:求某一位的1的个数

高n位*本位(比如百位就乘100)+  0                             (本位小于1)

1*本位                     (本位大于1)

低n位+1                  (本位等于1)

也就是说,某位(各位,十位...)1的总个数可能与其高位,低位以及自己的

值有关,具体对应情况如上

例如算12345:

个位1:1234*1+1(个位>=1加1)

十位1:123*10+10

百位1:12*100+100

千位1:1*1000+1000

万位1:2345+1

1的总个数为:8121

例如算23012:

个位1:2301*1+1

十位1:230*10+2+1  (十位=1加低位即2然后加1)

百位1:23*100            (百位为0加0)

千位1:2*1000+1000

万位1:10000

1的总个数为:19905

通俗来说,某位(个位,十位..)上1的个数=

基础数+当前位为>0,<0,=0时的情况,

而基础数为当前位前面的高位*当前位

(例如:23012,当 当前位为百位时,基础数=23(前高位)*100+上面讨论的情况)

 class Solution {
public:
int countDigitOne(int n) {
int k = 1, sum = 0, curr, large, small = 0;
while (n>0){
curr = n % 10;
large = n / 10;
if (curr>1)
sum = sum + large*k + k;
else if (curr<1)
sum += large*k;
else
sum += large*k + small + 1;
small = small + curr*k;
n = n / 10;
k = k * 10;
}
return sum;
}
};
上一篇:Eclipse中设置作者日期等信息


下一篇:vs2015中将复制过来的文件夹显示目录文件