作者:whisper
链接:https://www.proprogrammar.com/article/906
声明:请尊重原作者的劳动,如需转载请注明出处
输入一个整数 n ,求1~n这n个整数的十进制表示中1出现的次数。
例如,输入12,1~12这些整数中包含1 的数字有1、10、11和12,1一共出现了5次。
示例 1:
输入:n = 12 输出:5
示例 2:
输入:n = 13 输出:6
限制:
1 <= n < 2^31
难度:困难;标签:数学;编程语言:C++
class Solution {
public:
// x位数1的个数:1:1,2:20,3:300,n:n*10^(n-1)
int countDigitOne(int n) {
if(n <= 0)return 0;
long dp[12] = {0};
dp[1] = 1;
for(int i = 2; i < 12; i++)
dp[i] += (long)pow(10, i - 1) + 10 * dp[i - 1];
int t = n, c = 0, h = 0;
while(t != 0){
c++;
h = t % 10;
t /= 10;
}
int next = countDigitOne(n - (int)pow(10, c - 1) * h);
return h > 1 ? (int)pow(10, c - 1) + (int)dp[c - 1] * h + next : n - (int)pow(10, c - 1) + 1 + next + (int)dp[c - 1];
}
};
如果知道1~n位数中1的个数为x,那么再增加1位,1~n+1位数中1的个数呢?如果把这一位加在右边最低位,原来n位为x个1,加的1位可取0~9,组合一下前n位1的个数扩大10倍到10x,这里没有算上最低位的1,如果最低位为1,共有10^n种情况,所以如果1~n位有x个1,那么1~n+1共有10^n+10x个1,由此可以用递归来计算,如678,从高位一位一位算,先算600,这是三位数,最高位是1,有10^2种情况(0~99),剩余两位数可取0~99有dp[2]种情况,与最高位组合,有6*dp[2]种情况,所以共有100+dp[2]*6种情况,再加上78的1的个数即可;当最高位是1时,如123,先算最高位1,有24种情况(0~23),再算剩余两位有dp[2]种情况,再算23有next种情况,所以最后的结果要return h>1 ? :
class Solution {
public:
int countDigitOne(int n) {
if (!n)
return 0;
if (n < 10)
return 1;
int m = n;
int l;
int len = 0;
while (m) {
++len;
l = m;
m /= 10;
}
int ll = l*pow(10,len-1);
if (l == 1)
return (n-ll+1) + (ll/10)*(len-1) + countDigitOne(n-ll);
else
return pow(10,len-1) + (ll/10)*(len-1) + countDigitOne(n-ll);
}
};
一样的解法,写法也基本一样,看我的解法的解释看这个就能理解了
亲爱的读者:有时间可以点赞评论一下
月份 | 原创文章数 |
---|---|
202206 | 4 |
202205 | 2 |
202204 | 1 |
202203 | 11 |
202201 | 2 |
202108 | 7 |
202107 | 3 |
202106 | 16 |
202105 | 10 |
202104 | 16 |
202103 | 56 |
202102 | 14 |
202010 | 3 |
202009 | 3 |
202008 | 7 |
202007 | 7 |
202006 | 10 |
202005 | 11 |
202004 | 22 |
202003 | 52 |
202002 | 44 |
202001 | 83 |
201912 | 52 |
201911 | 29 |
201910 | 41 |
201909 | 99 |
201908 | 35 |
201907 | 73 |
201906 | 121 |
201811 | 1 |
201810 | 2 |
201804 | 1 |
201803 | 1 |
201802 | 1 |
201707 | 1 |
全部评论