java - 切木棍: Hackerrank warmup challenge

Question

我一直在努力解决 Hackerrank 上的热身挑战。对于这个特殊的挑战 - https://www.hackerrank.com/challenges/cut-the-sticks - 我已经编写了一些代码，尽管它在我看来在逻辑上是正确的，但我没有得到正确的答案。

我的代码 -

import java.util.*;

public class Solution {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int lengths[] = new int[n];
        List<Integer> output = new LinkedList<Integer>();

        for (int i = 0; i < n; i++)
            lengths[i] = sc.nextInt();

        sc.close();
        Arrays.sort(lengths);

        for (int i = 0; i < n; i++) {
            if (lengths[i] == 0)
                continue;
            else {
                output.add(n - i);
                for (int j = i; j < n; j++) {    // This loop isn't working like it should
                    lengths[j] -= lengths[i];
                 // System.out.print(lengths[j] + " ");  // For debugging purposes
                }
             // System.out.println("");
            }
        }

        for (int i = 0; i < output.size(); i++)
            System.out.println(output.get(i));
    }
}

对于以下输入 -

6
5 4 4 2 8 2

我得到的输出是 -

6
5
4
3
2
1

正确的输出应该是 -

6
4
2
1

我尝试在代码中标记的 for 循环运行过程中显示长度数组的值(带有注释)，这就是我从与上面相同的输入得到的结果 -

0 2 4 4 5 8 
0 4 4 5 8 
0 4 5 8 
0 5 8 
0 8 
0 
6
5
4
3
2
1

我完全不明白为什么会发生这种情况。

Answer 1

问题出在这里:

lengths[j] -= lengths[i];

当i == j为真时，这会改变lengths[i]的值。您需要先保存该值。

 final int v = lengths[i];
 for (int j = i; j < n; j++) {
     lengths[j] -= v;
 }