递归问题中的原子整数或 int[] (LeetCode124)

Question

所以这是 LeetCode 第 124 题 我使用没有全局变量的 Java，为什么我们需要使用 int[] 或 atomic 但不能使用 int 来存储最大值？我在这里缺乏什么知识？public int maxGain(TreeNode currNode, int[] res) {        if(currNode == null) { return 0; }        int leftBestSum = Math.max(maxGain(currNode.left, res), 0);        int rightBestSum = Math.max(maxGain(currNode.right, res), 0);        // update best result if it's better to start a new path        int currNodeAndChildSum = currNode.val + leftBestSum + rightBestSum;        // if currSum is better than the best result, start new path        res[0] = Math.max(res[0], currNodeAndChildSum);        // else if currSum is not better than the best result, pass back the best result path to        // its parent for later compare use        int currBestPathSum = currNode.val + Math.max(leftBestSum, rightBestSum);        return currBestPathSum;    }    public int maxPathSum(TreeNode root) {        int[] res = new int[] {Integer.MIN_VALUE};        maxGain(root, res);        return res[0];    }

Answer 1

在 C、C++、C#、PHP、Perl 等具有引用的语言中，您可以将指针或对值的引用传递给函数并就地修改它：

#include <stdio.h>

void doit(int *ptr_to_n) {

    *ptr_to_n = 42; // modifies the value pointed to by ptr_to_n by a dereference

}

int main(void) {

    int n = 415;

    doit(&n);

    printf(" %d\n", n); // => 42

    return 0;

}

Java 是严格按值传递的，不提供指针或寻址运算符。您在此处提供的代码滥用数组来克服此限制。在下面的代码中，调用范围中对数组的引用被复制并按值传递给res，但res仍然指向与 相同的底层对象arr，因此数组本身没有被复制，只是被别名化了。

class Main {

    public static void main(String[] args) {

        int n = 415;

        int[] arr = {415};

        doit(n);

        doitPointer(arr);

        System.out.println("Copy primitive: " + n);

        System.out.println("Copy reference to object: " + arr[0]);

    }

    static void doit(int n) {

        n = 42; // assignment to local variable which will be unavailable in outer scope

    }

    static void doitPointer(int[] res) {

        res[0] = 42; // assignment to element in referenced array, available in outer scope

    }

}

输出：

Copy primitive: 415

Copy reference to object: 42

在竞争性编程中，这是一种可以简化逻辑的有用且可接受的技术，但通常这在生产环境中是懒惰的做法，因为它破坏了封装，使代码难以推理并具有语义成本。

使用一个类来封装值，将函数放在一个范围内，以便它们可以修改私有类成员，或者重写逻辑以避免引用的需要。

Answer 2

这真的很hacky。您正试图通过使用容器作为输入变量来破解此解决方案以允许输出参数。您将它放在一个容器中以避免整数的按值传递性质，这会将参数复制到函数中。

相反，为什么不只返回多个值呢？

/**

 * Return an array containing the overall nodes 

 * maximum height and the overall max gain.

 **/

public int[] maxGain(TreeNode currNode) {

    if (currNode == null) {

        return new int[] { 0, Integer.MIN_VALUE };

    }

    int[] leftResult = maxGain(currNode.left);

    int[] rightResult = maxGain(currNode.right);

    int maxHeight = Math.max(leftResult[0], rightResult[0]) + currNode.val;

    int currGain = leftResult[0] + rightResult[0] + currNode.val;

    int maxGain = Math.max(currGain, Math.max(leftResult[1], rightResult[1]));

    return new int[] { maxHeight, maxGain };

}

public int maxPathSum(TreeNode root) {

    int[] result = maxGain(root);

    return result[1];

}