延续前面累加数组的问题,现在多一个限值变量 给定一个任意数组 a 和一个限值 n, 问题:在数组 a 的基础上得到一个数组 b,使得数组 b 的和为 n,具体看以下测试用例
/////////////////////////////////////////////////////////
之前的表述可能太抽象了,也太无聊了,我再具体形象一点,可以更能容易理解:
比如,现在有 k 个篮子 (每个篮子都有自己的数字编号),和 n 个苹果;
每个篮子只能放一定数量的苹果,a=[e_0, e_1, ..., e_k-1],那么现在要把这个 n 个苹果,按篮子的编号顺序,不断放入篮子中,而且一个篮子放满了之后再放入下一个篮子。
如果篮子都放满了,苹果还有剩余,则把剩余的苹果放在仓库里,假定仓库可以放无限多的苹果。
现在想要知道的是所有装苹果的篮子(可能有些篮子是空的)的苹果数量,以及仓库中的数量(可能篮子不够装)
假设这个方法叫 f(a, n),a 数组代表所有篮子的容量,n 是苹果数量 以下是各种情况的测试用例
/////////////////////////////////////////////////////////
# []表示没有篮子,所有苹果都得放在仓库里
f([], 2) # => [2]
# 第一个篮子就够放了
f([3,2,4,5], 2) # => [2]
f([3,2,4,5], 6) # => [3,2,1]
f([3,2,4,5], 10) # => [3,2,4,1]
# 所有篮子都不够装,最后剩余2个苹果要放在仓库里
f([3,2,4,5], 16) # => [3,2,4,5,2]
/////////////////////////////////////////////////////////
这个也不是什么面试题,只是我实际中遇到的动态分组问题。我写了一个比较丑陋的方法,虽然测试了下都没问题,但是还是觉得看着别扭,可能是我想的太复杂的,大家可以先参考下。我觉得应该有更简单明了的方法,有兴趣的同学可以想一下。
def f(a, n)
#先求a的累加数组,也就是篮子的累积容量
b = a.inject([]) { |sum,e| sum << e + (sum[-1] || 0) }
#初始化output数组
c=[]
#确定需要多少个篮子以及是否需要放在仓库里
m = (b.length==0) ? 1 : ((b.index{|e| e >= n } || b.length) + 1)
m.times do |i|
if m == 1
c << n
elsif i < m-1
c << a[i]
else
c << n - (b[i-1] || 0)
end
end
c
end