algorithm - 找到收集目标硬币数量的最少步数

Question

给定一个包含 n 个房屋的列表，每个房屋中都有一定数量的硬币。和一个目标值 t。我们必须找到达到目标所需的最少步数。
这个人可以选择从任何房子开始，然后向右或向左走，并朝那个方向收集硬币，直到达到目标值。但是人不能
改变方向。
示例:5 1 2 3 4 这些假设是 5 个房子的硬币值
，目标是 13 那么所需的最少步骤数是 5，因为我们必须选择所有硬币。

我的想法:
一种方法是为每个索引计算向左或向右方向
达到目标所需的步数，然后取所有这些 2*n 值中的最小值。
有没有更好的方法？

Answer 1

首先，让我们简化并规范化问题。

观察 1:“选择方向”功能是多余的，如果你选择从 j 房子到 i 房子，你可以也从 i 到 j 具有相同的值，因此只看一个方向就足够了。

观察 2: 现在我们可以从左到右看问题(观察 1)，很明显我们正在寻找一个值超过 k< 的子数组.

这意味着我们可以将问题经典化:

Given an array with non negative values a, find minimal subarraywith values summing k or more.

有多种方法可以解决这个问题，一个使用排序映射(例如平衡树)的简单解决方案是从左到右对值求和，然后寻找最后一个值为 sum 的元素 - k.

伪代码:

solve(array, k):
  min_houses = inf
  sum = 0
  map = new TreeMap()
  map.insert(0, -1)  // this solves issue where first element is sufficient on its own.
  for i from 0 to array.len():
    sum = sum + array[i]
    candidate = map.FindClosestLowerOrEqual(sum - k)
    if candidate == null:  // no matching sum, yet
      continue
    min_houses = min(min_houses, i - candidate)
    map.insert(sum, i)
  return min_houses

此解决方案在 O(nlogn) 中运行，因为每次映射插入都需要 O(logn)，并且有 n+1那些。

---

如果我们利用数组的“非负”特性，则可以在 O(n) 中进行优化。这意味着，随着我们在数组中继续进行 - 选择的候选者(在 map 搜索中)总是在增加。

我们可以利用它让两个指针同时运行，并找到最佳匹配，而不是像以前那样从头开始在索引中搜索。

solve(array, k):
  left = 0
  sum = 0
  min_houses = infinity
  for right from 0 to len(array):
    sum = sum + array[right]
    while (left < right && sum >= k):
      min_houses = min(min_houses, right - left)
      sum = sum - array[left]
      left = left + 1
  return min_houses

这在 O(n) 中运行，因为每个索引最多增加 n 次，并且每个操作都是 O(1)。