首页 > 代码库 > 《Cracking the Coding Interview》——第18章:难题——题目4
《Cracking the Coding Interview》——第18章:难题——题目4
2014-04-29 01:05
题目:数数从0到n总共有多少个数字‘2’?
解法:数位动态规划,可以O(log10(n))时间内解决。
代码:
1 // 18.4 Count the number of 2s from 0 to n. 2 #include <iostream> 3 using namespace std; 4 5 int main() 6 { 7 int d, i; 8 long long int base; 9 long long int sum; 10 long long int s[11]; 11 long long int n; 12 13 s[0] = 0; 14 base = 1; 15 for (i = 1; i < 10; ++i) { 16 s[i] = 10 * s[i - 1] + base; 17 base *= 10; 18 } 19 20 while (cin >> n && n > 0) { 21 base = 1; 22 i = 0; 23 while (base * 10 <= n) { 24 base *= 10; 25 ++i; 26 } 27 28 sum = 0; 29 while (n > 0) { 30 d = n / base; 31 sum += d * s[i]; 32 if (d > 2) { 33 sum += base; 34 } else if (d == 2) { 35 sum += n % base + 1; 36 } 37 n %= base; 38 39 base /= 10; 40 --i; 41 } 42 43 cout << sum << endl; 44 } 45 46 return 0; 47 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。