题目:输入一个整数n,求从1到n这n个整数的十进制表示中1出现的次数。
例如输入12,从1到12这些整数中包含1 的数字有1,10,11和12,1一共出现了5次。
#include "string.h" #include "stdlib.h" #include <iostream> int NumberOf1(const char* strN); int PowerBase10(unsigned int n); using namespace std; //求取1的个数 int NumberOf1BeforeBetween1AndN_Solution2(int n) { if(n <= 0) return 0; // convert the integer into a string char strN[50]; sprintf(strN, "%d", n); return NumberOf1(strN); } //将int转为string后,分别求取最高位的1的个数和除了最高位之外的1的个数 //21345分为1-1345,1346-21345 int NumberOf1(const char* strN) { if(!strN || *strN < '0' || *strN > '9' || *strN == '\0') return 0; int firstDigit = *strN - '0'; unsigned int length = static_cast<unsigned int>(strlen(strN)); // the integer contains only one digit if(length == 1 && firstDigit == 0) return 0; if(length == 1 && firstDigit > 0) return 1; //最高位的1的个数 int numFirstDigit = 0; //除了最高位外其他位1的个数 int numOtherDigits = firstDigit * (length - 1) * PowerBase10(length - 2); // numRecursive is the number of 1 of integer 1345 int numRecursive = NumberOf1(strN + 1); //当最高位大于1时最高位1的个数 if(firstDigit > 1) numFirstDigit = PowerBase10(length - 1); //当最高位=于1时最高位1的个数 else if(firstDigit == 1) numFirstDigit = atoi(strN + 1) + 1; return numFirstDigit + numOtherDigits + numRecursive; } int PowerBase10(unsigned int n) { int result = 1; for(unsigned int i = 0; i < n; ++ i) result *= 10; return result; } int main() { cout<<NumberOf1BeforeBetween1AndN_Solution2(21345); return 0; }