首页 > 代码库 > 找1到n所有整数出现1的个数
找1到n所有整数出现1的个数
编程之美2.4
n=12时,1,11,12这3个数包含1,所以1的个数是5.
Line 9是为了防止factor溢出。
1 #include <iostream> 2 #include <stdlib.h> 3 #include <time.h> 4 using namespace std; 5 6 int countOne(int n) { 7 int ans = 0; 8 int factor = 1; 9 while (n / factor >= 10) { // avoid overflow10 int high = n / factor / 10;11 int low = n % factor;12 int current = (n / factor) % 10;13 if (current == 0) {14 ans += high * factor;15 } else if (current == 1) {16 ans += high * factor + low + 1;17 } else {18 ans += (high + 1) * factor;19 }20 factor *= 10;21 }22 if (n / factor == 1) ans += (n % factor) + 1;23 else if (n / factor != 0) ans += factor;24 return ans;25 }26 27 int bruteForce(int n) {28 int ans = 0;29 for (int i = 1; i <= n; ++i) {30 int tmp = i;31 while (tmp) {32 if (tmp % 10 == 1) ans++;33 tmp /= 10;34 }35 }36 return ans;37 }38 39 int main() {40 srand(time(NULL));41 42 for (int i = 0; i < 100; ++i) {43 int n = rand() % 9999999;44 int c1 = countOne(n);45 int c2 = bruteForce(n);46 if (c1 != c2) {47 cout << c1 << " " << c2 << " " << n << endl;48 }49 }50 return 0;51 }
找1到n所有整数出现1的个数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。