编程之美1:那些关于1的个数的经典面试题 - XIAXIA__的专栏 - 博客频道 - CSDN.NET
public static int getOneShowTimes(int N) { int numPerBit; //存储每一位的数目 int sumTimes = 0; //存储最后的结果 int quan = 1; //每一位的权值,各位为1,十位为10,依次类推 int tempN = N; if (0 == N) { return 0; } while(0 != tempN) { numPerBit = tempN % 10; sumTimes += getOneShowTimesPerBit(N, numPerBit, quan); tempN /= 10; quan *= 10; } return sumTimes; } public static int getOneShowTimesPerBit(int N, int numPerBit, int quan) { if (0 == numPerBit) { return N / (quan * 10) * quan; } else if (1 == numPerBit) { return (N / (quan * 10)) * quan + N % quan + 1; } else { return (N / (quan * 10) + 1 ) * quan; } }
解法1 暴力穷举
层循环要循环N次,内存循环要循环log10N+1 次,所以总的复杂度为O(N(log10N+1))
int getOneShowSumTimes(unsigned int N) { unsigned int count = 0; for (unsigned int i = 0; i <= N; i++) { count += getOneShowTimes(i); } return count; } int getOneShowTimes(unsigned int n) { unsigned count = 0; while(0 != n) { count += (n % 10) == 1 ? 1 : 0; n /= 10; } return count; }
Read full article from 编程之美1:那些关于1的个数的经典面试题 - XIAXIA__的专栏 - 博客频道 - CSDN.NET
题目1 给定一个十进制正整数N,写下从1开始,到N的所有整数,然后数一下其中出现的所有"1"的个数
<1>1位数情况
这个简单,如果N = 3,那么从1到3的所有数字:1,2,3,只有个位数出现1,而且只出现一次。可以发现,N是个位数时,N >=1,那么f(N)= 1;N = 0,f(N)= 0;
<2>2位数情况
<3>3位数情况
同理分析4位数,5位数。。。。。
设N = abcde ,其中abcde分别为十进制中各位上的数字。
如果要计算百位上1出现的次数,它要受到3方面的影响:百位上的数字,百位一下(低位)上的数字,百位一上(高位)上的数字。
如果百位上数字为0,百位上可能出现1的次数由更高位决定。比如:12013,则可以知道百位出现1的情况可能是:100~199,1100~1199,2100~2199,,.........,11100~11199,一共1200个。可以看出是由更高位数字(12)决定,并且等于更高位数字(12)乘以 当前位数(100)。
如果百位上数字为1,百位上可能出现1的次数不仅受更高位影响还受低位影响。比如:12113,则可以知道百位受高位影响出现的情况是:100~199,1100~1199,2100~2199,,.........,11100~11199,一共1200个。和上面情况一样,并且等于更高位数字(12)乘以 当前位数(100)。但同时它还受低位影响,百位出现1的情况是:12100~12113,一共114个,等于低位数字(113)+1。
如果百位上数字大于1(2~9),则百位上出现1的情况仅由更高位决定,比如12213,则百位出现1的情况是:100~199,1100~1199,2100~2199,...........,11100~11199,12100~12199,一共有1300个,并且等于更高位数字+1(12+1)乘以当前位数(100)。
int Sumls(int n) { int iCount=0,iFactor=1,iLowerNum=0,iCurrNum=0,iHigherNum=0; while(n/iFactor!=0) { iLowerNum=n-(n/iFactor)*iFactor; iCurrNum=(n/iFactor)%10; iHigherNum=n/(iFactor*10); switch(iCurrNum) { case 0: iCount+=iHigherNum*iFactor; break; case 1: iCount+=iHigherNum*iFactor+iLowerNum+1; break; default: iCount+=(iHigherNum+1)*iFactor; break; } iFactor*=10; } return iCount; }
long long int Count(long long int n){ //1的个数 long long int count = 0; //当前位 long long int Factor = 1; //低位数字 long long int LowerNum = 0; //当前位数字 long long int CurrNum = 0; //高位数字 long long int HigherNum = 0; if(n <= 0){ return 0; } while(n / Factor != 0){ //低位数字 LowerNum = n - (n / Factor) * Factor; //当前位数字 CurrNum = (n / Factor) % 10; //高位数字 HigherNum = n / (Factor * 10); //如果为0,出现1的次数由高位决定 if(CurrNum == 0){ //等于高位数字 * 当前位数 count += HigherNum * Factor; } //如果为1,出现1的次数由高位和低位决定 else if(CurrNum == 1){ //高位数字 * 当前位数 + 低位数字 + 1 count += HigherNum * Factor + LowerNum + 1; } //如果大于1,出现1的次数由高位决定 else{ //(高位数字+1)* 当前位数 count += (HigherNum + 1) * Factor; } //前移一位 Factor *= 10; } return count; }http://blog.csdn.net/xiaxia__/article/details/44957999
public static int getOneShowTimes(int N) { int numPerBit; //存储每一位的数目 int sumTimes = 0; //存储最后的结果 int quan = 1; //每一位的权值,各位为1,十位为10,依次类推 int tempN = N; if (0 == N) { return 0; } while(0 != tempN) { numPerBit = tempN % 10; sumTimes += getOneShowTimesPerBit(N, numPerBit, quan); tempN /= 10; quan *= 10; } return sumTimes; } public static int getOneShowTimesPerBit(int N, int numPerBit, int quan) { if (0 == numPerBit) { return N / (quan * 10) * quan; } else if (1 == numPerBit) { return (N / (quan * 10)) * quan + N % quan + 1; } else { return (N / (quan * 10) + 1 ) * quan; } }
解法1 暴力穷举
层循环要循环N次,内存循环要循环
int getOneShowSumTimes(unsigned int N) { unsigned int count = 0; for (unsigned int i = 0; i <= N; i++) { count += getOneShowTimes(i); } return count; } int getOneShowTimes(unsigned int n) { unsigned count = 0; while(0 != n) { count += (n % 10) == 1 ? 1 : 0; n /= 10; } return count; }
Read full article from 编程之美1:那些关于1的个数的经典面试题 - XIAXIA__的专栏 - 博客频道 - CSDN.NET