This is the 21st day of my participation in the August More Text Challenge

Offer 43. 1 ~ n number of occurrences of 1 in the integer

The title

Enter an integer n and find the number of occurrences of 1 in the decimal representation of n integers.

For example, if you enter 12, 1, and 12, the digits that contain 1 are 1, 10, 11, and 12. 1 appears five times.

Example 1:

Input: n = 12 Output: 5Copy the code

Example 2:

Input: n = 13 Output: 6Copy the code

Limitations:

  • 1 <= n < 2^31

Methods a

Counting problem: 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 can be;

class Solution {
    public int countDigitOne(int n) {
​
        List<Integer> num = new ArrayList<>();
        while(n != 0) {
            num.add(n % 10);
            n /= 10;
        }
        Collections.sort(num, (a, b)->{
            return -1;
        });
        
        if (num.size() == 1) return 1;
        
        int pre = 0, res = 0;
        for (int i = 0; i < num.size(); i ++ ) {
            int cur = num.get(i);
            if (cur == 0) {
                res += pre * Math.pow(10, num.size() - i - 1);
                pre = pre * 10 + cur;
            }
            else if (cur == 1) {
                int cnt = 0;
                int j = i + 1;
                while(j < num.size()) cnt = cnt * 10 + num.get(j ++);
                res += pre * Math.pow(10, num.size() - i - 1) + cnt + 1;
                pre = pre * 10 + cur;
            }else {
                res += (pre + 1) * Math.pow(10, num.size() - i - 1);
                pre = pre * 10 + cur;
            }
        }
        return res;
    }
}
Copy the code

Offer 44. A digit in a numeric sequence

The title

Figures for 0123456789101112131415… Serialized to a character sequence. In this sequence, bit 5 (counting from subscript 0) is 5, bit 13 is 1, bit 19 is 4, and so on.

Write a function to find any NTH digit.

Example 1:

Input: n = 3 Output: 3Copy the code

Example 2:

Input: n = 11 Output: 0Copy the code

Limitations:

  • 0 <= n < 2^31

Methods a

Digital analysis:

  • Find out what the NTH digit is

    • Each time will benMinus all the lengthsdigitThe length of the digit number, until it is not subtracted enough

  • Find the digit in which the NTH digit is in the digit, i.e. (n-1)/digit

  • Find the digit where the NTH digit is in the digit, i.e. (n-1) % digit

class Solution { public int findNthDigit(int n) { long digit = 1, start = 1, count = 9; while(n > count) { n -= count; digit += 1; start *= 10; count = 9 * digit * start; } long num = start + (n - 1) / digit; String number = String.valueOf(num); char[] res = number.toCharArray(); return res[(int)((n - 1) % digit)] - '0'; }}Copy the code