整数中1出现的次数

求出1_{13的整数中1出现的次数,并算出100}1300的整数中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