Sword finger Offer 43. 1～n Integer 1 Number of times

Sword finger Offer 43. 1～n Integer 1 Number of times

class Solution:
    def countDigitOne(self, n: int) -> int:
        mulk = 1
        ans = 0
        while n >= mulk:
            ans += (n//(mulk * 10)) * mulk + min(max(n % (mulk * 10) - mulk + 1, 0), mulk)
            mulk *= 10
        return ans

That day, I made a set of Xiaomi measurement questions.，The first one is calculation1～nmiddle1Number of times。

Deduction的题号yesSword fingeroffer 43
nyes12in the case of，1 10 11 12middle就出现了5Second-rate1。

因为那套题middle选择题都yes简单难度，So naturally I want to use violent algorithm to crack。

但yes拿到Deductionmiddle找相同的题的时候却发现标签yesdifficulty[Be ashamedR]。Surmo after timeout[picture2]。

Then I actually thought about it directly with mathematical methods，But why too lazy, don’t want to find the rules，[picture三]yes标答，I feel that I have to sink in the future and slowly go to do it.。
#Deduction #algorithm#Deductionalgorithm #Python

Error answer：

[]class Solution:

def countDigitOne(self, n: int) -> int:
    flag = 0
    for i in range(1, int(n)+1):
        for j in ''.join(str(i)):
            if j == '1':
                flag += 1
    return flag