Ruby 求高效算法
统计出从 0-n 之间 1 的个数，如 n=13，f(0..13)=>6，0 到 13 有 6 个数带有 1，要求不能用字符串方式计算，只能用数学方式。
def f(range)
range.inject do |sum, n|
while n > 0
sum += 1 if n % 10 == 1
n = n / 10
end
sum
end
end
有一道面试题，某次一面试官觉得不够高效，百思不得其解，求高效算法
先分组，1-9 做组 1 10 - 19 组 2 ...... 100 - 199 组 3
满租的情况 对于没一组，1 开头的有一个公式，非 1 开头的又有一个公式。。。
不满租的情况 组内所有数除以 10，记 1 知道可以填满某个租，用公式计算。 余下的重复这个过程，知道为个位数。
应该是可以。。。
irb(main):009:0> sum = 0 irb(main):016:0> [1..13].each do |e| irb(main):017:1 (e.to_s).gsub(/[1]/) {|s| sum +=1} irb(main):018:1> end => [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13] irb(main):019:0> sum => 6
把 13 换成 n 就可以了。
0 到 13 有 6 个数带有 1
这句话有问题，是 5 个数带有 1，但是 1 的出现总数是 6 次。猜是 1 的出现总数。
这题是要找规律，如 0..99，1 在个位上出现了 10 次，在 10 位上出现了 10 次。那 0..13 在个位上出现 2 次，10 位上 4 次。如 0..256，1 在个位上出现 26*1 次，在 10 位上出现 3*10 次，在 100 位出现 1*100 次。如 0..1111，1 在个位上出现 112 次，在 10 位上出现 11*10+2 次，在百位上出现 1*100+12 次，在千位上出现 112 次，共 448 次。
先做个字符版的 f 做验证，再做个 g 来完成。
def f(range)
range.to_a.map(&:to_s).join.count('1')
end
def g(range)
n = range.last
m = nil
sum = 0
x = 1
while (n > 0) do
m = n % 10
n = n / 10
sum += n*x
if m > 1
sum += x
elsif m > 0
sum += range.last % x + 1
end
x = x * 10
end
sum
end
class String
def to_range
t = self.split('..')
(t.first.to_i)..(t.last.to_i)
end
end
puts "f: #{f(ARGV[0].to_range)}, g: #{g(ARGV[0].to_range)}"
结果是 ruby a.rb 0..13 f: 6, g: 6 ruby a.rb 0..99 f: 20, g: 20 ruby a.rb 0..256 f: 156, g: 156 ruby a.rb 0..1111 f: 448, g: 448