找到特定功能的最小操作次数

Question

我从公司的采访中得到了这个问题,但我找不到最低限度(根据我的最低操作数是最高数字或最低数字),但我不确定.请有人帮帮我吗？谢谢

问题是 :-

给定一个数组和一个操作foo(index, value),

• 的value可以是1或-1,
• 如果foo(index, value)被调用,它将添加value到index数组的所有元素

找到使所有数组元素为0的最小操作数.

Answer 1

考虑每个元素和前一个元素之间的区别.对于第一个元素,使用与0的差值,即其值.

现在,调用foo(index,value)将恰好改变其中一个差异,要么增加它,要么将它减少1.

由于您想要的结果所有这些差异都等于0,并且foo()只能将其中一个更改为1,因此您需要调用foo()的最小次数是差异绝对值的总和.

Answer 2

让我们a用元素命名我们的数组

[a[0], a[1], a[2], ...., a[n]]

要a[0]变为0 的最小操作数是呼叫foo(0, 1)或foo(0, -1)确切abs(a[0])时间.在此之后,阵列将成为

[0, a[1] - a[0], a[2] - a[0], ...., a[n] - a[0]]

请注意,此结果不取决于a[0]是正还是负.

向前应用这个逻辑,我们可以将结果总结为

第1步(如上所述)

[0, a[1] - a[0], a[2] - a[0], a[3] - a[0], ...., a[n] - a[0]]abs(a[0])经营后

第2步

[0, 0, a[2] - a[0] - (a[1] - a[0]) , a[3] - a[0] - (a[1] - a[0]), ...., a[n] - a[0] - (a[1] - a[0])]

要不就

[0, 0, a[2] - a[1] , a[3] - a[1], ...., a[n] - a[1]]abs(a[1] - a[0])经营 后

第3步

[0, 0, 0 , a[3] - a[1] - (a[2] - a[1]), ...., a[n] - a[1] - (a[2] - a[1])]

要不就

[0, 0, 0, a[3] - a[2] ...., a[n] - a[2]]abs(a[2] - a[1])经营 后

...... 步骤N + 1

[0, 0, 0, 0, ..., 0]abs(a[n] - a[n-1])经营 后

所以最小的操作次数是

abs(a[0]) + abs(a[1] - a[0]) + abs(a[2] - a[1]) + ... + abs(a[n] - a[n-1])

或者干脆

差异的绝对值之和

正如Matt Timmermans所说