求出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
网友评论