1到N中1出现的次数

1到N中1出现的次数

这个问题关键在于好好分析一些样例如:
给定123这个数,你说这个从1到123所有数字中,1出现的次数是多少?
首先我们要分析个位上1出现的次数,我们看看什么情况下个位出现1:
1,11,21,31,41,-----91,101,111,121,
因为从1-123中其实就是有多少个十就行了。
你看下从1到100个位出现1的情况:
1,11,21,31,41,51,------91。有多少个呢?
就是10*1=10个 
其实就是从01,11,21,31,41,51-----91当然是10了。
就是1-100中个位有10个1.
然后再从101-123呢个位有多少个1?
就是101,111,121,有(2+1)*1=3个。
其实我们可以这样了。
那么再分析十位上出现1的情况:
1-123.
则有10-19    110-119
有多少个呢?
首先看1-100有
10-19 有10个
然后110-119 有10个
则有(1+1)*10=20个
为什么是1+1?
其实和123中10位数字有关,你想如果是103呢十位有多少个1?
就是1*10=10个
113呢?
就是1*10+3=13.
123呢?
2>1呢
(1+1)*10=20了。
于是就有规律了。 
1到N中1出现的次数
1到N中1出现的次数
源代码:
  1. #ifndef NUMBER_OFONEINDATA_H
  2. #define NUMBER_OFONEINDATA_H
  3. #include<iostream>
  4. unsigned int numberOfOneInData(unsigned int v_data){
  5. if(v_data<=0){
  6. return 0;
  7. }
  8. unsigned int oneCount=0;
  9. unsigned int iFactor=1;
  10. unsigned int icurrentUnitNum=0;
  11. unsigned int iLowerNum=0;
  12. unsigned int iHigherNum=0;
  13. while(v_data/iFactor!=0){
  14. iLowerNum=v_data-(v_data/iFactor)*iFactor;
  15. icurrentUnitNum=(v_data/iFactor)%10;
  16. iHigherNum=v_data/(iFactor*10);
  17. switch (icurrentUnitNum)
  18. {
  19. case 0:
  20. oneCount+=iHigherNum*iFactor;
  21. break;
  22. case 1:
  23. oneCount+=iHigherNum*iFactor+iLowerNum+1;
  24. break;
  25. default:
  26. oneCount+=(iHigherNum+1)*iFactor;
  27. break;
  28. }
  29. iFactor=iFactor*10;
  30. }
  31. return oneCount;
  32. }
  33. #endif



上一篇:linux调度器系列


下一篇:WebService处理大数据量数据