今天下午创业教育课上无聊,想起来一道微软的面试题,即求1~n中1出现的次数
例如n=11 则1一共出现4次:1 10 11
这个问题我仔细思考了一阵,推出了一个很快的解法(复杂度lg(N))...写在BLOG上保存
思路: 首先确定个位1的个数,再统计十位1的个数,.....统计最高位1的个数全部累加即为所求.
设n=497 则过程如下:
个位1数:
由于497中的"49"是由于个位进位得到的,不难想出个位一共进了49位,每次进位个位出现一个1,因此个位1的个数等于490/10+剩下'7'包含1个个数共计490/10+1=50个
十位1数:
不难想到497中十位以上的数字全部是由十位的进位产生的,因此十位共进位400/100=4次,而十位每 个1又包含着个位的10个数字,因此497中十位出现1的个数为 400/100 x 10 +10=50次
百位1数:由于百位为最高位,而且百位数字大于1,因此百位包含1个数为100个...
累加得到n=497时 1的总个数为50+50+100=200个.....
基于上面的思路,可以得到一个复杂度为lg(n)的算法..... 实现如下:
#include<iostream> #include<math.h> using namespace std; int get(int n) //返回1~n中1出现的次数,代码比较简洁 { int lenth=(int)(log10(n))+1,i,j,k=1,sum=0; for(i=1;i<=lenth;i++) { k*=10; sum+=n/k*k/10; j=(n%k)*10/k; if(j>1) sum+=k/10; if(j==1) sum+=(n%k)%(k/10)+1; } return sum; } int main() { int n; while(cin>>n&&n) cout<<get(n)<<endl; }
