This is the 13th day of my participation in the August More Text Challenge

233. Number of 1s

Given an integer n, count the number of occurrences of the number 1 in all non-negative integers less than or equal to n.

Example 1:

Input: n = 13 Output: 6Copy the code

Example 2:

Input: n = 0 Output: 0Copy the code

Methods a

Counting problems:

All we need to do is figure out how many occurrences of 1’s in each digit, and then add up the number of occurrences of 1’s in each digit, and that’s the number of occurrences of 1’s in each digit from 1 to n;

For convenience, we subtract the digits from each digit and place them in an array. When iterating over each digit, we have the following calculation rules:

Suppose the given number is abcdefg

  • When I enumerate to C,

  • If c = 0

    • Before c, the range we can choose is 1, 20~ab-1C is the range of choices0 ~ 9999

  • If c = 1

    • Before c, the range you can choose is0~ab-1C is the range of choices0 ~ 9999; Cab, the following selected range is0~defg

  • If c is greater than 1, the value ranges from 0 to AB and from 0 to 9999

According to the above rules, enumerate each digit, and finally add;

class Solution {
    public int countDigitOne(int n) {
        ArrayList<Integer> nums = new ArrayList<>();
        while(n != 0) {
            nums.add(n % 10);
            n /= 10;
        }
​
        int res = 0;
        Collections.reverse(nums);
​
        for (int i = 0; i < nums.size(); i ++ ) {
            
            int left = 0, right = 0, j = i + 1;
            while(j < nums.size()) right = right * 10 + nums.get(j ++);
            j = 0;
            while(j < i) left = left * 10 + nums.get(j ++);
​
            if (nums.get(i) == 0) {
                res += left * (int)Math.pow(10, nums.size() - i - 1);
            }
            else if (nums.get(i) > 1) {
                res += (left + 1) * (int)Math.pow(10, nums.size() - i - 1);
            }else {
                res += left * (int)Math.pow(10, nums.size() - i - 1) + right + 1;
            }
        }
        return res;
    }
}
Copy the code

Note: left and right in the loop refer to the number before and after the current digit of the enumeration; Of course, there is no need to calculate the left every time. We only need to maintain an external left and calculate it iteratively each time. But right still has to be computed through the history, so the complexity of time is not reduced; -_- Similar to this number law related can be classified into digital DP this kind of problem, first pull out each digit, and then for specific problems, to specific analysis;