338. 计数问题 - AcWing题库
https://www.acwing.com/problem/content/340/
思路是来自acwing y总和Alicia编程果果的代码:
AcWing 338. 计数问题---超短写法 - AcWinghttps://www.acwing.com/solution/content/7128/
根据他们的代码思路我整理了以下的内容:
题目要求求数字i在[1,n]之间的整数中出现的次数.
可以枚举数字 n 的每一位, 当数字i确定在这一位出现的时候, 计算在 [1,n] 之间的所有整数中有多少种可能性并累加.
因此当数字 n 的每一位都枚举过后, 代表数字 i 出现在数字n的每一位时, 在 [1,n] 范围内的整数的所有可能性都累加上了.
比如数字 n 是 abcdefg, 固定数字 i 出现在 d 的位置, 那么所有可能性就是左侧可能性 * 右侧可能性:
1<= xxx i yyy<= abc d efg
由题意可知, xxx<= abc, 所以分成以下两个情况讨论:
(1) xxx = 0 ~ abc -1, yyy = 0 ~ 999 随便取, 可能性 res = abc * 1000, 即左边* 10的(d的位数)次幂
(2) xxx = abc, 此时 d >= i, 分情况讨论:
如果d >i, yyy = 0 ~ 999, 随便取, 可能性 res = 1000, 即 10的(d的位数)次幂
如果d = i, yyy = 0 ~ efg, 可能性 res = efg + 1, 即右边的数字 + 1
代码:代码也是根据果果的代码, 添加了注释来帮助复习:
# include# includeusing namespace std;
int dgt(int n) // 计算整数n有多少位
{
int res = 0;//存储位数
while (n) ++ res, n /= 10;//只要不为0 就除10,结果保留的是整数. 最后一次/10是0,跳出循环
return res;//返回整数n的位数
}
int cnt(int n, int i) // 计算从1到n的整数中数字i出现多少次
{
int res = 0, d = dgt(n);//res 存储数字i出现的次数, d是整数n的位数
for (int j = 1; j<= d; ++ j) // 枚举数字n的每一位, 从右到左, 计算数字i出现多少次
{
// l和r是数字n第j位左边和右边的整数 (abc和efg); dj是整数n第j位的数字
int p = pow(10, j - 1), //pow求x的y次幂 用来计算l和r 或者自己写一个power10函数
l = n / p / 10, r = n % p,
dj = n / p % 10;//取余数 就是j位的数字
// 当第j位左边的整数小于l (xxx = 000 ~ abc - 1), 此时 res = 左侧可能性 * 右侧随便取
if (i) res += l * p;//如果i不为0,左边的可能数量(l)*右边可能性数量(全部), 如果j是4 p就是1000, l*1000
if (!i && l) res += (l - 1) * p; //如果i = 0, 左边高位不能全为0, (视频中xxx = 001 ~ abc - 1)
// 当第j位左边的整数等于l (xxx = abc)的情况, 此时 要看第j位数字的大小来计算
if ( (dj >i) && (i || l) ) res += p;//如果第j位数字dj >i, i和l都不是0, 那么右侧随便取, 可能性就是p
if ( (dj == i) && (i || l) ) res += r + 1;//如果dj == i, i和l都不是0, 那么能取到j位右侧[0,r]之间所有整数
}
return res;
}
int main()
{
int a, b;//两个整数a 和 b
while (cin >>a >>b , a) //不断读取输入, 直到输入的a,b是0,0就结束输入
{
if (a >b) swap(a, b);//保证a 如果pow() 函数不熟悉的话, 可以按照y总解法, 自己写一个power函数, 求10 的 x次方, 调用的时候可以写 int p = power10(j - 1):
int power10(int x) //返回10的x次方
{
int res = 1;
while (x--) res *= 10;
return res;
}你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
