180-求1～n这n个整数的十进制表示中出现1的次数

朴灿烈づ我的快乐病毒、 2022-10-29 07:41 112阅读 0赞

**题目如下：**  
输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。  
例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。

示例 1：  
输入：n = 12  
输出：5

示例 2：  
输入：n = 13  
输出：6

## 解题思路1 ##

1.计算个位数是1的次数 :  
count = (number/10)*1+(number%10==0?0:1);  
2.计算十位数是1的次数 :  
count = (number/100)10+(number%100)  
// k= (n%(i10));  
//count(i) = (n/(i*10))*i+(if (k > i*2-1) i else if(k < i)0 else k-i+1 );

**先统计个位是1的次数，接着统计十位是1的次数，以此类推下去**

#include<stdio.h>
    #include<math.h>
    int NumberOf1Between1AndN_Solution(int n)
    {
        
    	int count = 0;
    	for (int i = 1; i <= n; i *= 10)
    	{
        
    		count = count + (n / (10 * i)) * i;
    		int k;
    		k = (n % (i * 10));
    		if (k > i*2-1)
    		{
        
    			count += i;
    		}
    		else if (k < i)
    		{
        
    			count += 0;
    		}
    		else
    		{
        
    			count = count + k - i + 1;
    		}
    	}
    	return count;
    }
    
    int main()
    {
        
    	printf("%d\n",NumberOf1Between1AndN_Solution(12));
    	printf("%d\n",NumberOf1Between1AndN_Solution(13));
    	return 0;
    }

**运行截图如下：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]

## 解题思路2 ##

**在分析之前，首先需要知道一个规律：**  
从 1 至 10，在它们的个位数中，数字1出现了 1 次。  
从 1 至 100，在它们的十位数中，数字1出现了 10 次。  
从 1 至 1000，在它们的百位数中，数字1出现了 100 次。  
依此类推，从 1 至 10i，在它们右数第i位中，数字1出现了10 ^ (i - 1)次。

**对于 n = 2134,要找到从1 ~ 2134这2134个数字中所有1的个数。我们可以对2134进行逐位分析：**

(1)在个位上，从1~2130，包含213个10，因此数字1出现了213次，剩下的数字2131、2132、2133、2134中个位数上只有2131包含树脂字1，剩下的都不包含。所以个位数上的数字1的总数为213 + 1 = 214。

(2)在十位上，从1 ~ 2100，包含了21个100，因此数字1出现了21 \* 10 = 210次，剩下的数字从2101 ~ 2134，只有2110 ~ 2119这10个数字中十位的数字为1，所以十位上的数字1的总数为210 + 10 = 220。

(3)在百位上，从1 ~ 2000，包含了2个1000，因此数字1出现了2 \* 100 = 200次，剩下的数字从2001 ~ 2134，只有2100 ~ 2134这35个数字中的百位的数字为1，所以百位数上数字1的总数为200 + 35= 235。

(4)在千位上，包含了0个10000，因此数字1出现了0 \* 1000 = 0次，剩下的数字中只有1000 ~ 1999这1000个数字中的千位的数字为1，所以千位上的数字1的总数为1000。

因此从1 ~ 2134这n个数字中，数字出现的总的次数为 214 + 220 + 235 +1000 = 1669。  
**总结一下以上的步骤，可以得到这么一个规律：**  
对于数字n，计算它的第i(i从1开始，从右边开始计数)位数上包含的数字1的个数：  
假设第i位上的数字为x的话，则  
1.如果x > 1的话，则第i位数上包含的1的数目为：(高位数字 + 1）\* 10 ^ (i-1) (其中高位数字是从i+1位一直到最高位数构成的数字)

2.如果x < 1的话，则第i位数上包含的1的数目为：(高位数字 ）\* 10 ^ (i-1)

3.如果x == 1的话，则第i位数上包含1的数目为：(高位数字) \* 10 ^ (i-1) +(低位数字+1) (其中低位数字时从第i - 1位数一直到第1位数构成的数字)

#include<stdio.h>
    #include<math.h>
    int NumberOfDigitOne(int n)
    {
        
    	if( n < 0) return 0;
    	int i = 1;
    	int high = n;
    	int count = 0;
    	while(high != 0)
    	{
        
    		high = n / (int)pow(10.0 ,i);//high表示当前位的高位
    		int temp = n / (int)pow(10.0, i - 1);
    		int cur = temp % 10;//cur表示第i位上的值，从1开始计算
    		int low = n  - temp * (int)pow(10.0, i - 1);//low表示当前位的低位
    		if(cur < 1)
    		{
        
    			count += high * (int)pow(10.0, i - 1);
    		}
    		else if(cur > 1)
    		{
        
    			count += (high + 1) * (int)pow(10.0 ,i - 1);
    		}
    		else
    		{
        
    			count += high * (int)pow(10.0, i - 1);
    			count += (low + 1);
    		}
    		i++;
    	}
    	return count;
    }
    
    int main()
    {
        
    	printf("%d\n",NumberOfDigitOne(12));
    	printf("%d\n",NumberOfDigitOne(13));
    	return 0;
    }

**运行截图如下：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]: /images/20221024/0567176dfb6140fd8480393a738e53c5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221024/6b05e457eb814f5db8801a61260514ad.png