编程之美2.4

n=12时，1，11，12这3个数包含1，所以1的个数是5.

Line 9是为了防止factor溢出。

1 #include 
     
       2 #include 
      
        3 #include 
       
         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 }