想法有了但是没实现出来:
按位找,从个位到最高位,每一位1个数之和
具体来讲,分成当前位curr,当前位之前所有位:高位high,以及当前位之后所有位:低位low
维护一个i,i=1表示当前个位,i=10十位,以此类推
那么,对于个位上的1,我们首先要看,这个数有多少个10,因为0-9十个数里面有1个1,而high刚好是有多少个10,另外,如果当前也就是个位>1,会多加一个1
对于十位上的1,我们首先要看有多少个100,因为0-99一共100数字,十位上出现10次1,high刚好是有多少100,当前i=10,那么10个一组,10位出现1成组次数为high*i,但是high中少一部分,如果curr=0,就不少了,因为当前不存在十位上有的情况,如果i=1,那么low中有多少个数字,就有多少加1个新增,因为10位置上的没计算在low中,如果curr>1,那么十位数上的10个都在了,都要加上,加个i
对于百位,千位等也是一样
下面是计算high,curr,与low,因为i表示当前是哪位
high=n/(i*10),也就是前一位做个位,有多少个
curr=(n/i)%10,因为n/i结果是当前位做个位,之后%10就取出当前位
low=n-(n/i)*i,n/i当前位个位,*i以后当前位之后所有都是0,n-之后就求出来之后的位数了
最后到n/i=0,也就是i比最高位高为止
class Solution { public int countDigitOne(int n) { long count=0; long i=1; while(n/i!=0){ long high=n/(10*i); long curr=(n/i)%10; long low=n-(n/i)*i; if(curr==0){ count = count + high * i; }else if(curr>1){ count = count +high*i+i; }else { count=count+high*i+low+1; } i=i*10; } return (int)count; } }