网站开发设计制作推广,自贡做网站公司,学编程大概多少钱一个月,中国网站排名站长之家// 面试题43#xff1a;从1到n整数中1出现的次数// 题目#xff1a;输入一个整数n#xff0c;求从1到n这n个整数的十进制表示中1出现的次数。例如// 输入12#xff0c;从1到12这些整数中包含1 的数字有1#xff0c;10#xff0c;11和12#xff0c;1一共出现了5次。#incl…// 面试题43从1到n整数中1出现的次数// 题目输入一个整数n求从1到n这n个整数的十进制表示中1出现的次数。例如// 输入12从1到12这些整数中包含1 的数字有11011和121一共出现了5次。
#include cstdio
#include cstring
#include cstdlibint NumberOf1Between1AndN(int n)
{if(n0)return 0;//数字转字符串char str[50];sprintf(str,%d,n);//21345变为“21345”return NumberOf1(str);
}int NumberOf1(const char* str)
{if(!str||*str0||*str9||*str0)return 0;//假设输入21345int first*str-0;//最高位字符串转整数 2unsigned int length static_castunsigned int(strlen(str));//5if(length1first0)//输入为0return 0;if(length1first0)//输入为1-9return 1;//输入str “21345”//numFirst是数字10000--19999的第一位的数目//开头是1, 后面四位为1-9里任意一个 供10×10×10×10,写一个函数实现这个计算int numFirst0;if(first1)//2numFirstPowerBase10(length-1);else if(first1)//12345numFirstatoi(str1)1;//atoi为char转int atoi(str1)结果是2345//numOtherDigits为 1346--21345除第一位之外的数位中的数目int numOtherDigitsfirst*(length-1)*PowerBase10(length-1)//2*(5-1)*10*10*10//numRecursive是1---1345中的数目,递归实现int numRecursiveNumberOf1(str1);//numberOf1(1345)return numFirstnumOtherDigitsnumRecursive;}int PowerBase10(unsigned int n)
{int result1;for(int i0;in;i)result*10;return result;
}void Test(char* testName,int n,int expected)
{if(testNamenullptr)printf(failed n);int resultNumberOf1Between1AndN(n);if(resultexpected)printf(pass n);else{printf(failed n);}}void Test()
{Test(Test1, 1, 1);Test(Test2, 5, 1);Test(Test3, 10, 2);Test(Test4, 55, 16);Test(Test5, 99, 20);Test(Test6, 10000, 4001);Test(Test7, 21345, 18821);Test(Test8, 0, 0);
}int main()
{char str[]12345;int first*str-0;int numatoi(str1);printf(first%d n,first);//1printf(num%d n,num);//2345Test();return 0;
}
int NumberOf1Between1AndN(unsigned int n)
{int number 0;for(unsigned int i 1; i n; i)number NumberOf1(i);return number;
}int NumberOf1(unsigned int n)
{int number 0;while(n){if(n % 10 1)number ;n n / 10;}return number;
}
