This is the second day of my participation in the November Gwen Challenge. Check out the details: the last Gwen Challenge 2021

1 to n Number of occurrences of 1 in the integer

The number of occurrences of 1 in Offer 43.1 to n

Difficulty: difficulty

Topic: leetcode-cn.com/problems/1n…

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

Limit: 1 <= n < 2^31

Answer key

induction

This problem was solved purely by induction

Iterate from the number to the highest digit, regard N as three parts “high, cur, low”, where cur is the current digit, high is the value before cur, low is the value after cur. Set digit to 1, 10, 100…… according to the current digit It can be inferred by mathematical induction:

  • whencur = 0, the implementation ofres += high * digit
  • whencur = 1, the implementation ofres += high * digit + low + 1
  • whencur > 1, the implementation ofres += high * digit + digit
/ * * *@param {number} n
 * @return {number}* /
var countDigitOne = function (n) {
  let digit = 1,
    res = 0;
  let high = Math.floor(n / 10),
    cur = n % 10,
    low = 0;
  while(high ! = =0|| cur ! = =0) {
    if (cur === 0) res += high * digit;
    else if (cur === 1) res += high * digit + low + 1;
    else res += high * digit + digit;
    low += cur * digit;
    cur = high % 10;
    high = Math.floor(high / 10);
    digit *= 10;
  }
  return res;
};
Copy the code
  • Time complexity: O(logNlogNlogN)
  • Space complexity: O(111)

A digit in a sequence of digits

Offer 44. A digit in a numeric sequence

Difficulty: Medium

Topic: leetcode-cn.com/problems/sh…

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

Limit: 0 <= n < 2^31

Answer key

Looking for a regular

The 101112… Each of the digits is called the digit n, and 10,11,12… This is called num, the starting digit of each digit (1,10,100…). Known as the start.

The digital atmosphere Digit digit Digital number Digital number
1 ~ 9 1 9 9
10 to 99 2 90 180
100 ~ 999 3 900 2700
. . . .
start~end digit 9 * start 9 * start * digit

According to the table:

  • digit = digit + 1
  • start = start * 10
  • count = 9 * start * digit

Solution idea:

  • Determine the number of digits in n, i.e. Digit
  • Determine the number of n, that is, num
  • Determine which digit in num n is, and return the result
  1. Determine the number of digits of n:
The digital atmosphere digits Digital number n = n – count
1 ~ 9 1 9 n – 9
10 to 99 2 180 n – 9 -180
100 ~ 999 3 2700 n – 9 – 180 -2700
start~end digit 9 * start * digit All the way to n <= count

According to the table:

  • The desired digit is in some digit
  • The desired digit is the NTH one digit starting with the number start
  1. Determine the number of n

Digit = 2, start = 10

1 0 1 1 1 2 .
n 1 2 3 4 5 6 .
(n – 1) 0 1 2 3 4 5 .
(n – 1) / 2 0 0 1 1 2 2 .

According to the table:

  • Digit num = start + (n-1)/digit
  1. Determine what digit n is in num
1 0 1 1 1 2 .
n 1 2 3 4 5 6 .
(n – 1) 0 1 2 3 4 5 .
(n – 1) % 2 0 1 0 1 0 1 .

According to the table:

  • The digit is in the (n-1) % 2 digit of num

The overall implementation code is as follows:

/ * * *@param {number} n
 * @return {number}* /
var findNthDigit = function (n) {
  let digit = 1,
    start = 1,
    count = 9;
  while (n > count) {
    n -= count;
    digit += 1;
    start *= 10;
    count = digit * start * 9;
  }
  let num = Math.floor(start + (n - 1) / digit);
  return Number(num.toString(10)[(n - 1) % digit])
};
Copy the code

Practice every day! The front end is a new one. I hope I can get a thumbs up