美文网首页
整数中1出现的次数

整数中1出现的次数

作者: 九日火 | 来源:发表于2021-01-07 10:00 被阅读0次

    求出113的整数中1出现的次数,并算出1001300的整数中1出现的次数?
    1~13中包含1的数字有1、10、11、12、13因此共出现6次。

    package main
    
    // f(n) = n1*f(10bit-1) + f(n – n1*10bit) + LEFT;
    // 其中
    // if(n1 == 1)
    //     LEFT = n - 10bit+ 1;
    // else
    //     LEFT = 10bit;
    
    func Ones(n int) int {
        if n == 0 {
            return 0
        }
    
        if n > 1 && n < 10 {
            return 10
        }
    
        count := 0
        highest := n
        bit := 0
        for highest >= 10 {
            highest /= 10
            bit++
        }
    
        weight := pow(10, bit)
        if highest == 1{
            count = Ones(weight - 1) + Ones(n - weight) + (n - weight + 1)
        } else {
            count = Ones(weight - 1) + Ones(n - highest*weight) + weight
        }
    
        return count
    }
    
    func pow(a, b int) int {
        res := 1
        for i:=b; i > 0; i-- {
            res *=a
        }
    
        return res
    }
    
    
    class Solution:
        def NumberOfNum1(self, n):
            if n == 0:
                return 0
    
            if n > 1 and n < 10:
                return 1
            ones, m = 0, 1
            while m <= n:
                if ((n // m) % 10) != 0 and ((n // m) & 10) != 1:
                    ones += (n // 10 // m + 1) * m
                elif ((n // m) % 10) == 1:
                    ones += (n // m // 10) * m + n % m + 1
                m *= 10
            return ones
    
    

    相关文章

      网友评论

          本文标题:整数中1出现的次数

          本文链接:https://www.haomeiwen.com/subject/mcknoktx.html