矩阵求和挑战
下面的算法用于将“下矩阵”转换为“后矩阵”。给定“后矩阵”，找到“前矩阵”。
该算法针对每个 after(x,y) 运行以确定它们的值。给定之后，找到之前的原始值
例子
之后 = [[2,5],[7,17]]
从之前计算之后的值
after[0][0] = before[0][0] = 2
after[0][1] = before[0][0] + before[0][1] = 2 + 3 = 5
after[1][0] = before[0][0] + before[1][0] = 2 + 5 = 7
after[1][1] = before[0][0] + before[0][1] + before[1][0] + before[1][1] = 2 + 3 + 5 + 7 = 17
完成函数 find before matrix 具有以下参数 after[n][m]: 一个 nxm 整数数组
返回： int[n][m] 表示前矩阵的 nxm 整数数组
约束
再输入一个样本
到目前为止我尝试过的
n = gets.to_i
m = gets.to_i
arr = Array.new(n){Array.new(m,0)}
sum = 0
arr_last = 0
arr_first = 0
len = 0
a.each_with_index do |d, outer_index|
len = d.length - 1
d.each_with_index do |b, index|
arr_sum = d[0..index].sum
if index > 0
arr[outer_index][index] = sum + arr_sum
else
arr[outer_index][index] = arr_first + b
end
arr_first += b if index == 0
arr_last = arr_sum if index == len
end
sum += arr_last
end
print arr
但是对于少数测试用例它没有在时间限制内执行并且对于少数测试用例我得到了错误的答案
回答
After 网格中的每个值都是其 Before 值与其左侧和/或上方的所有 Before 值的总和。图中：
B是红色区域中所有 Before 值的总和，Y是绿色和红色区域中所有 Before 值的总和，X是蓝色和红色区域中所有 Before 值的总和，以及A是紫色、蓝色、绿色和红色区域中所有 Before 值的总和。
由于X和Y重叠B，添加X和Y会B计算两次。因此，如果我们开始A，减X并Y，然后添加B（反击加倍），我们得到的前值A，如：A' = A - X - Y + B。
现在我们知道了，代码非常简单：
def before(after)
before = []
after.each_with_index do |row,j|
before[j] = []
row.each_with_index do |v,i|
up = j <= 0 ? 0 : after[j-1][i]
left = i <= 0 ? 0 : after[j][i-1]
up_left = i <= 0 || j <= 0 ? 0 : after[j-1][i-1]
before[j][i] = v - up - left + up_left
end
end
before
end