This is the 13th day of my participation in the August More text Challenge. For details, see: August More Text Challenge

Leetcode -233- The number of digits 1

[Blog link]

The way to study 🐔

The nuggets home page

[Topic description]

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

Tip:

0 <= n <= 2 * 109

Related Topics

• recursive
• mathematics
• Dynamic programming
• 👍 👎 0 253

[Topic link]

Leetcode title link

[making address]

Code link

[思路介绍]

Idea 1: Violent scanning

• Concatenate the string and count the number of 1s
• There is no doubt that this will explode

public int countDigitOne(int n) {
    int res = 0;
    StringBuilder sb = new StringBuilder();
    for (int i = 1; i <= n; i++) {
        sb.append(i);
    }
    for (char c:sb.toString().toCharArray()
         ) {
        if (c == '1'){
            res+=1; }}return res;
}
Copy the code

• Time complexity O(n)
• Space complexity O(n*m)

---

Idea 2: Analog counting

• For the integer 12304
• We can define the numeric digit in the current digit, cur
• Ex: calculatecur == 0When the pointer moves to10when
  • You can find that the number containing 1 ranges from 00010 to 12219
  • Quantity CNT = 123 * 10
• Ex: calculateCur = = 1When, the pointer moves toA 10000 – bitwhen
  • You can find that the number containing 1 ranges from 10000 to 12304
  • Quantity CNT = 0 * 10000 + 2304 + 1
• Ex: calculatecur > 1When the pointer moves toThe three digits 1, 100 and 1000when
  • The number containing 1 ranges from 00001 to 12301
  • The 100 digits range from 00101 to 12199, including 1
  • The 1000 digits range from 01001 to 11999, including 1
  • Cnt1 = (1230+1) * 1
  • cnt100 = (12+1) * 100
  • cnt1000 = (1+1) * 1000
• res = 1231 + 1230 + 1300 + 2000 +2305

public int countDigitOne(int n) {
    int res = 0, digit = 1, high = n / 10, cur = n % 10, low = 0;
    while(high ! =0|| cur ! =0) {
        if (cur == 0) {
            res += high * digit;
        } else if (cur == 1) {
            res = res + high * digit + 1 + low;
        } else {
            res += (high + 1) * digit;
        }
        low += cur * digit;
        digit *= 10;
        cur = high % 10;
        high /= 10;
    }
    return res;
}
Copy the code

• Order LGN in time.
• Space complexity O(1)