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

html5 • • 问答

我正在解决 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`.

if the current coin is greater than `change + 1`, the smallest impossible change is equal to `change + 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）

以上是如何设计此解决方案以应对来自Algoexpert.io的不可构造变更挑战的全部内容。
THE END
分享
二维码
< <上一篇
下一篇>>