public class Solution {
    public int countDigitOne(int n) {
        if(n<0){
            return 0;
        }
        int res =0;
        for(int i=1;i<=n;i++){
            int[] nums=numToArray(i);
            res +=countOne(nums);
        }
        return res;
    }
    
    private int[] numToArray(int n){
        int i=0;
        int tmp = n;
        while(n>0){
            i++;
            n = n/10;
        }
        int[] res= new int[i];
        int index = i-1;
        while(tmp>0){
            res[index--] = tmp%10;
            tmp = tmp/10;
        }
        return res;
    }
    private int countOne(int[] n){
        int res = 0;
        for(int i=0;i<n.length;i++){
            if(n[i] == 1){
                res+=1;
            }
        }
        return res;
    }
}
@@ -781,9 +781,372 @@
 ;%0A    %7D%0A
+    public int countDigitOne2(int n) %7B%0A    %0A        if (n %3C= 0) return 0;%0A        int q = n, x = 1, ans = 0;%0A        do %7B%0A            int digit = q %25 10;%0A            q /= 10;%0A            ans += q * x;%0A            if (digit == 1) ans += n %25 x + 1;%0A            if (digit %3E  1) ans += x;%0A            x *= 10;%0A        %7D while (q %3E 0);%0A        return ans;%0A    %0A    %7D%0A%0A
 %7D

The optimal solution is function2