Train of thought 1

The simplest method is to find the number of 1 in each number from 1 to n respectively. Since the number of digits of the integer n is O(logn), we need to judge how many ones there are in a number, and we need to judge whether each bit is 1, so a number needs to judge O(logn) times, and there are n numbers in total, so the time complexity of this method is O(nlogn).

/*
     *      Accumulates the number of occurrences of each integer 1 in 1 to n.
     *      Each time, judge whether the current bit is 1 by finding the remainder of 10
     */
    public int countNum(int n){
        int number = 0;
        for(int i = 1;i<= n;i++){
            number+=numberOf1(i);
        }
        return number;
    }
    //Directly returns the 1 contained in the current number
    public int numberOf1(int n){
        int number =0;
        while(n!=0){
            if(n %10 == 1)
                number++;
            n = n/10;
        }
        return number;
    }

Train of thought 2

Consider everyone,

1) This bit is greater than 1, and the number of 1 in this bit is ([n/10^(b+1]+1)*10^b
2) This bit is equal to 0, which is ([n/10^(b+1)])*10^b
3) This bit is equal to 1, plus n mod 10^b + 1 on the basis of 0

For example: 30143
Since 3 > 1, the number of times that 1 appears on a bit is (3014 + 1) * 1
Since 4 > 1, the number of occurrences of 1 on the tens is (301 + 1) × 10
Since 1 = 1, the number of occurrences of 1 in the hundreds is (30 + 0) × 100 + (43 + 1)
Since 0 < 1, the number of times of occurrence of 1 on the 1000 bit is (3 + 0) × 1000

Note: for example, the occurrence of one hundred is 100-199, and the meaning of * 100 is 100-199100 times in a single step, * 30 is due to the occurrence of 30 times of 100-199, + (43 + 1) is due to the incompleteness of the last 301 * *.

The schematic diagram of the whole process is as follows:

It should be noted that since the maximum input data required by the test system is 1000000000, int will overflow and long long will be used. In addition, a may be larger than b, but there is no explanation. It's a bit of a pit.

    /*
     *      According to the law of numbers, count the number of 1 from 1 to the two ends of the interval, and then subtract
     *      For example, count(a,b)=count(0,b)-count(0,a-1)
     */
    public long countNum1(long num) {
        if(num<=0) return 0;
        long count  = 0;//Count the total number of occurrences of 1
        long current;//Value of current bit
        long base = 10;//Base of current bit
        long remain = 0;//When the current bit is 1, the number remaining after the current bit, for example, 132, then remain=32

        while(num>0) {
            //Current bit
            current = num%10;
            //Count the possible values of all bits on the left of the current bit, such as 3012. If the current bit is 2, num=302
            num = num/10;
            //Determine the number of times the current bit may appear 1 according to the value of the current bit
            if(current > 1) {
                count += (num+1)*base; 
            }else if(current==1) {
                count += (num*base + remain + 1);
            }else {
                count += num*base;
            }

            //Incomplete partial values may be needed to solve the next bit
            remain += current*base;
            base *= 10;
        }
        return count;
    }

    //Find the number of occurrences of 1 in the specified interval
    public long count(long a,long b) {
        long result;
        if(a>b) {
            result = countNum1(a) - countNum1(b-1);
        }else {
            result = countNum1(b) - countNum1(a-1);
        }
        return result;
    }