这个方法为什么失败?

huangapple go评论84阅读模式
英文:

Why does this method fail?

问题

最近在面试中遇到了这个问题。给定一个整数数组,找到一个最小的整数 x,可以作为起始点,以便当您将数组中的每个数字添加到运行总数时,运行总数永远不会低于 1。他们给我的 Java 函数存根接受一个列表集合,并要求我返回一个长整型。对我来说,这个解决方案似乎应该有效,但它在每个测试用例中都失败了。为什么?

public static long minStart(List<Integer> arr) {
    long minStart = 0;
    long runningTotal = minStart;
    for(int i = 0; i<arr.size(); i++){
        runningTotal += arr.get(i);
        if(runningTotal<1){
            minStart++;
            i = 0;
            runningTotal = minStart;
        }
    }
    return minStart;
}
英文:

Recently ran into this question in an interview. Given an array of integers, find the smallest integer x that can be used as a starting point so that when you add each number from the array to the running total, the running total never goes below 1. The function stub they gave me, for Java, took in a list collection and I was supposed to return a long. This solution to me seems like it has to work, but failed every test case. Why?

public static long minStart(List&lt;Integer&gt; arr) {
    long minStart = 0;
    long runningTotal = minStart;
    for(int i = 0; i&lt;arr.size(); i++){
        runningTotal += arr.get(i);
        if(runningTotal&lt;1){
            minStart++;
            i = 0;
            runningTotal = minStart;
        }
    }
    return minStart;
}

答案1

得分: 1

问题在于,在你的for循环中,你使用i = 0;来重置,但在下一次迭代中,for循环会将i递增为1,这意味着你跳过了列表中的第一个数字。我建议只需将该行更改为i = -1;

英文:

The issue here is that in your for loop, you use i = 0; to reset, but then on the very next iteration, the for loop is going to increment i to equal 1, which means you skipped over the first number in the list. I would just try simply changing that line to be i = -1;.

答案2

得分: 0

Your problem here is the if block - you should not have one.

I also suspect you misunderstood the question, which I read as return 1 - the minimum of the running total.

Something like this:

public static long minStart(List<Integer> arr) {
    long total = 0; // long to avoid integer overflow
    long min = Long.MAX_VALUE;
    for (int n : arr) {
         total += n;
         min = Math.min(min, total);
    }
    return 1 - min;
}

To further reduce the amount of code, you could replace the loop with just:

for (int n : arr)
     min = Math.min(min, total += n);
 
This may or may not impress, depending on your audience.

<details>
<summary>英文:</summary>

Your problem here is the `if` block - you should not have one.

I also suspect you misunderstood the question, which I read as *return 1 - the minimum of the running total*.

Something like this:

    public static long minStart(List&lt;Integer&gt; arr) {
        long total = 0; // long to avoid integer overflow
        long min = Long.MAX_VALUE;
        for (int n : arr) {
             total += n;
             min = Math.min(min, total);
        }
        return 1 - min;
    }

---

To further reduce the amount of code, you could replace the loop with just:

    for (int n : arr)
         min = Math.min(min, total += n);
 
This may or may not impress, depending on your audience.


</details>



huangapple
  • 本文由 发表于 2020年7月28日 01:36:26
  • 转载请务必保留本文链接:https://go.coder-hub.com/63120612.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定