题目描述

rt

样例

12
5

算法1

时间复杂度 o(logn) 空间复杂度o(1)

class Solution {
    public int numberOf1Between1AndN_Solution(int n) {
        if(n==0) return 0;
        int ans=0,t=1,m=n;
        while(m>0){
            t*=10;
            int left=n/t;
            int cur=(n%t)/(t/10);
            int right=(n%t)%(t/10);
            m/=10;
            ans+=(left*t/10);
            if(cur==0) ans+=0;
            if(cur==1) ans+=(right+1);
            if(cur>1) ans+=(t/10);
        }
        return ans;
    }
}