如何设计此解决方案以应对来自 Algoexpert.io 的不可构造变更挑战

Question

我正在解决 algoexpert.io 编码挑战，但我无法理解题为“不可构造变更”的问题之一的建议解决方案

下面是挑战题：

给定一个表示您拥有的硬币价值的正整数数组，编写一个函数，该函数返回您无法创建的最小找零金额（最小金额）。给定的硬币可以具有任何正整数值并且不一定是唯一的（即，您可以拥有多个相同值的硬币）。

例如，如果给您硬币 = [1, 2, 5]，则您不能创建的最小零钱金额为 4。创建是 1。

// O(nlogn) time, O(n) size.
function nonConstructibleChange(coins) {
  coins = coins.sort((a, b) => a - b); // O(nlogn) time operation
  let change = 0;

  for (coin of coins) {
    if (coin > change + 1) return change + 1;
    change += coin;
  }

  return change + 1;
}

我的问题

我不完全确定解决方案的作者是如何得出这样的直觉的

if the current coin is greater than `change + 1`, the smallest impossible change is equal to `change + 1`.

我可以看到它是如何跟踪的，并且该算法确实通过了所有测试，但我想更多地了解我可以用来设计此规则的过程。

感谢您花时间阅读问题！

Answer 1

这个也花了我一段时间，但这就是我理解它的方式：

假设你已经证明你可以赚 1-8 美分。

你进入下一次迭代，想知道你是否能赚 9 美分。所以你迭代到排序列表中的下一个新硬币。

如果新币 < 9：

• 你知道一个事实，你可以赚 9 美分。
• 例如，如果新硬币是 5：使用新硬币并从您尝试制作的总数中减去它。9 - 5 = 4。然后不管你以前怎么做 4 再做一次。（你已经证明你可以赚 1-8 美分）

如果新币 == 9：

• 你知道一个事实，你可以赚 9 美分。
• 只需使用 9 美分硬币

如果新币 > 9：

• 你知道你不能赚 9 美分的事实
• 这是因为您不能使用新硬币。例如，当你试图赚 9 美分时，10 美分的硬币对你没用，因为它太大了（不能赚 9）
• 如果你不使用新硬币，你也会被搞砸，因为如果你把迄今为止看到的所有硬币加起来，你只能赚到 8 个（不能赚 9 个）

这就是 change + 1 的来源。（您的变量更改 = 8）

if the current coin is greater than `change + 1`, the smallest impossible change is equal to `change + 1`.

Answer 2

当整数排序时，我们总是可以通过对排序后的整数进行累积和来跟踪最高的可构造值。

例如，coins = [1, 2, 5] ==> 1,2,3,5,6,7

在任何时候，如果下一个整数大于 max constructible + 1，则无法构造 max constructible + 1。

[1]       mc=1     ---> 2
[1, 2]    mc=3     ---> 4
[1, 2, 5] mc=7     ---> 8

如果当前整数大于mc + 1，则最小不可能变化等于mc + 1。

因此在本例中，[1, 2, 5]最小值为 4。

可以这样完成（我正在使用go）

    func NonConstructibleChange(array []int) int {
        sort.Ints(array)
        ncc :=1
        for i:=0; i< len(array) && array[i]<=ncc; i++{
            ncc +=array[i]
        }
        return ncc
    }