本文共 1116 字，大约阅读时间需要 3 分钟。

题目描述：

输入一个整数n，求从1到n这n个整数的十进制表示中1出现的次数。

例如输入12，从1到12这些整数中包含“1”的数字有1，10，11和12，其中“1”一共出现了5次。

样例

输入： 12输出： 5

分析：

直接枚举n个数，复杂度太高。现在比如51023，对于第一个数5 > 1，若最高位是1，有10000-19999共10000种情况；第二个数就是1，左边数是0-4时，右边可以是000-999，左边数为5时，右边数是000-023，一共5*1000+24=5024种情况；第三个数为0，要使它为1，左边可以是0-50，右边可以是0-99，共5100种情况；第四个数是2，当其为1时，左边可以是0-510，右边可以是0-9，一共5100种情况；第五个数是3，当其为1，左边的数可以是0-5102，共5103种情况。1一共出现了30337次。

通过上例可以发现，我们考察某数n=abcde时，比如考察c这一位，如果c大于1，则左边可以是0-ab，右边可以是0-99；如果c等于1，左边是0-ab-1时，右边可以是0-99，左边是ab时，右边可以是0-de；如果c等于0，则左边可以是0-ab-1，右边可以是0-99。所以我们需要求出每一位左边和右边的数是什么以及当前位的权值。

所以很容易得到以下程序：

class Solution {public:    int numberOf1Between1AndN_Solution(int n) {        if(!n)  return 0;        vector
   
     num;        while(n)    num.push_back(n % 10),n /= 10;        int ans = 0;        for(int i = num.size() - 1;i >= 0;i--){            int l = 0,r = 0,t = 1;            for(int j = num.size() - 1;j > i;j--)   l = l * 10 + num[j];            for(int j = i - 1;j >= 0;j--)   r = r * 10 + num[j],t *= 10;            ans += l * t;            if(num[i] == 1) ans += r + 1;            else if(num[i] > 1) ans += t;        }        return ans;    }};
   

转载地址：https://blog.csdn.net/qq_30277239/article/details/88378719 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！