递归问题中的原子整数或 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 是严格的 pass-by-value 并且不提供指针或 address-of 运算符。您在此处提供的代码滥用数组来克服此限制。在下面的代码中，调用范围中对数组的引用被复制并按值传递给 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

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

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

Answer 2

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

相反，为什么不 return 多个值？

/**
 * 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];
}

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

Atomic Integer or int[] in Recursion Question (LeetCode124)

java

recursion

atomic