gpt4 book ai didi

algorithm - 给定 N,找到最大的 *奇数/偶数 * 加起来得到 N

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:20:19 24 4
gpt4 key购买 nike

我想问一个基于这个问题的后续问题: Given n, find the maximum numbers added to get n

如果我只能用奇数求和N怎么办,有什么公式可以概括吗?谢谢!

例如给定 7,ans 为 1,对于 7给定 16,ans 是 4,对于 1+3+5+7给定 13,ans 为 3,对于 1+5+7

最佳答案

我将提出解决您问题的代码,然后尝试证明/捍卫它。

  public static int maxOddSumToInt(final int n) throws IllegalArgumentException {
if(n < 0) throw new IllegalArgumentException("n must be positive");

LinkedList<Integer> currentNums = new LinkedList<>();
currentNums.add(1);
int sum = 1;
int next = 3;
while(sum < n) {
currentNums.add(0, next);
sum += next;
next += 2;
}
while (sum > n) {
int r = currentNums.remove(0);
sum -= r;
while(sum < n) {
currentNums.set(0, currentNums.get(0) + 2);
sum += 2;
}
}
return currentNums.size();
}

你的问题的关键是你只想要count 最独特的奇数总和到目标。因此,我们如何得出最大计数并不重要,重要的是我们确信我们拥有它。

使用最多数字的捷径是尽可能使用最小的数字。因此,例如,我们希望使用 1,3,5,7,9, ... 而不是 1,9,15。因此,第一步是尽可能多地按升序包含数字,直到我们达到或超过我们的目标。如果我们成功了,太好了!根据定义,这是要使用的最大数量的数字集,因为没有更小的数字可供使用。例如,对于输入“9”,算法将加 1、加 3、加 5,看到它命中 9 并返回大小 3。

如果我们超过目标,我们将删除最后一次添加,因为这显然使它不再可能。通过与上面类似的逻辑,这意味着我们在 (n) 处的任何大小的集合都将不起作用,因为我们之前有最小求和集,甚至它太大了。因此,我们尝试大小为 n-1 的集合。从这里开始,如何我们试图达到我们的目标并不重要,只是我们检查是否有任何一组大小 n-1 有效。因此,为简单起见,我们将最近添加的内容反复增加 2 以查看是否达到目标。这既确保我们不会重复数字(我们正在使最大的数字变大,因此它不可能成为重复的)并且如果我们再次超过目标并需要重复此步骤,我们可以进行一次移除,并且肯定会再次低于我们的目标。

总时间复杂度有点棘手。我想我可以声称它在最坏的情况下是 O(N^2),其中 N 是目标的值。最坏的情况是该数字只能由其自身表示(大小为 1 的集合),因此我们构建一个集合求和直到超过它 (O(N)),然后删除每个 while递增直到我们再次超过 (N*O(N))。基于数字的东西可能会有更严格的限制,但我并没有想到。

算法没有做的一件事是优雅地处理无效输入。如果你给它一个没有解决方案的数字,它将永远运行。如果您能为此找到一个简单的数字测试,您可以将它添加到顶部的非法参数异常中。

关于algorithm - 给定 N,找到最大的 *奇数/偶数 * 加起来得到 N,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/38194974/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com