Atomic Integer или int [] в вопросе о рекурсии (LeetCode124)

Question

Итак, это LeetCode. Вопрос 124 Я использовал Java без глобальной переменной. Почему нам нужно использовать int [] или атомарную, но нельзя использовать 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

Это действительно хаки. Вы пытаетесь взломать это решение, чтобы разрешить выходные параметры, используя контейнер в качестве входной переменной. Вы помещаете его в контейнер, чтобы избежать целочисленной передачи по значению, которая скопировала бы параметр в функцию.

Вместо этого, почему бы просто не вернуть несколько значений?

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

Answer 2

В языках со ссылками, такими как 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, поэтому сам массив не копируется, толькоaliased.

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

В конкурентном программировании это полезный и приемлемый метод, который может упростить логику, но обычно это ленивая практика в производственных условиях, потому что этонарушает инкапсуляцию, делает код трудным для рассуждения и имеет семантическую стоимость.

Используйте класс для инкапсуляции значения, поместите функции в область видимости, чтобы они могли модифицировать закрытые члены класса, или переписали логику вИзбегайте необходимости ссылок.