• Topic link
• The answer to the reference

The main idea

• The number n is converted to string to make it easier to process each bit individually, and s[I] represents the number being processed
• Formula: the number of 1 within the x-digit, is
  $x*10 ^ {x-1}$
• From single digitss[0]Start processing and store the corresponding result for each bitdp[i].
• Take n = 2134 as an example
  • If s[I] = 3, thenDp [3] = OnesIn(0~34)
  1. s[i] == 1In the examplei = 1, to deal with 0 ~ 134,
     $Dp [I] = One sIn(0 ~ 99) + One sIn(0 ~ 34) + One sIn(100)$Among themOnes in the hundreds=ones in (100) + ones in (101~134)
  2. s[i] ! = 1When assumingi=0,s[i] = 2.
     $Dp [I] = s[I] * One sIn (0 ~ 999) + One sIn (1000) + One sIn (dp[I +1])$

Code implementation

X = len(s)-i-1 in x∗10x−1x*10 ^ {x-1}x∗10x−1

class Solution:
    def countDigitOne(self, n: int) -> int:
        s = []
        s = str(n)
        l = len(s)
        dp = [0 for _ in range(l+1)]
        for i in range(l-1, -1, -1):
            x = l-i-1
            if s[i] == '1': 
                dp[i] = x*pow(10, x-1) + dp[i+1] + n%int(pow(10, x)) + 1 
            else:
                dp[i] = (int(s[i])-int('0'))*(x)*pow(10, x-1) + min(1, int(s[i])-int('0'))*pow(10,x) + dp[i+1]
        return int(dp[0])
Copy the code