233. 数字 1 的个数

题目

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

示例:

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

提示1:
Beware of overflow.

tips

注意这是一类观察规律的编程题,解题的技巧体现在对规律的观察上

解法1

暴力法,超时

class Solution {
public:
    int countDigitOne(int n) {

    	if(n < 1)
    		return 0;
    	int ret = 0;
    	for(int i = 1;i <= n;i++)
    	{
    		int number = i;
    		while(number)
    		{
    			if(number%10 == 1)
    				ret++;
    			number/=10;
    		}
    	}
    	return ret;        
    }

}; 

解法2

通过观察,找到规律,直接计算出来的递归解法,从最高位,从小到大,进行计数,等完全排除最高位的影响后,再从次一位递归进行计数

class Solution {
public:
    int countDigitOne(int n)
    {
        if(n < 1)
    		return 0;
    	if(n<10)
    	    return 1;
    	//数字的位数	
    	int len = 0;
    	int number = n;
    	while(number)
    	{
    		len++;
    		number/=10;  
        }
    	int ret = 0;
    	//最高位的权重
    	int temp = pow(10,len-1);
    	//取出最高位的值
    	int first = n/temp;
    	if(first == 1)
    	{
    		//最高位取0,这时的计数值由其他的位贡献
            ret+=(len-1)*(temp/10);//高中的排列组合问题
            //最高位可以贡献的计数值
    		ret+= (n%temp)+1;          
    	}
    	else
    	{   
    		//最高位取0~first-1时,由其他位贡献的计数值
    		ret+=first*(len-1)*(temp/10);
    		//最高位可以贡献的计数值(此时最高位取值1)
    		ret+= temp;
    	}
    	ret+= countDigitOne(n%temp);
    	return ret;
    }

}; 

233. 数字 1 的个数

上一篇:怎么获取页面dom节点数量


下一篇:简单Dos命令