Проблема с алгоритмом суммы вложенного списка

Question

Я пытаюсь решить эту проблему "Сумма веса вложенного списка": https://leetcode.com/problems/nested-list-weight-sum/description/

Проблема:

Учитывая список [[1, 1], 2, [1,1]], верните 10. (четыре 1 на глубине 2, один 2 на глубине 1)

Это мое решение.

var depthSum = function (nestedList, sum=0, depth=1) {
    nestedList.forEach((val) => {
        if (Array.isArray(val)) {
            depth = depth+1;
            return depthSum(val, sum, depth);
        } else {
            sum += val * depth;
        }
    });
    return sum;
};

Не уверен, что мне не хватает.Когда я отлаживаю его, в какой-то момент я получаю ответ, но return sum не срабатывает, и я получаю другой ответ.

Может кто-нибудь указать мне ошибку?

Answer 1

Так что один из способов справиться с этим.

Нет смысла возвращаться изнутри вашего forEach, вместо этого вам нужно добавить сумму от рекурсивного вызова к вашей текущей сумме.И поскольку вы делаете это, вам не нужно, чтобы sum был параметром для вашей depthSum функции

var nestedList = [[1,1],2,[1,1]];

var depthSum = function(nestedList, depth = 1) {
  var sum = 0;
  nestedList.forEach((val) => {
    if (Array.isArray(val)) {
      sum += depthSum(val, depth + 1);
    } else {
      sum += val * depth;
    }
  });
  return sum;
};

console.log(depthSum(nestedList))

Answer 2

В соответствии с требованием кода в Leetcode ниже рабочий код.

    var depthSum = function (nestedList,  depth=1) {
    var res = 0;
    nestedList.forEach((val) => {
        if (val.isInteger() === false) {
            res += depthSum(val.getList(),  depth + 1);
        } else {
            res += val.getInteger() * depth;
        }
    });
    return res;
};

Вы не можете использовать Array.isArray(), потому что все члены вернут false.а также вы не можете получить доступ к значениям или списку напрямую.Вам необходимо получить доступ через их API.Входные данные для функции - это не просто массив.См. Тип ввода и API-интерфейсы, представленные в спецификации, следующим образом:

     * function NestedInteger() {
 *
 *     Return true if this NestedInteger holds a single integer, rather than a nested list.
 *     @return {boolean}
 *     this.isInteger = function() {
 *         ...
 *     };
 *
 *     Return the single integer that this NestedInteger holds, if it holds a single integer
 *     Return null if this NestedInteger holds a nested list
 *     @return {integer}
 *     this.getInteger = function() {
 *         ...
 *     };
 *
 *     Set this NestedInteger to hold a single integer equal to value.
 *     @return {void}
 *     this.setInteger = function(value) {
 *         ...
 *     };
 *
 *     Set this NestedInteger to hold a nested list and adds a nested integer elem to it.
 *     @return {void}
 *     this.add = function(elem) {
 *         ...
 *     };
 *
 *     Return the nested list that this NestedInteger holds, if it holds a nested list
 *     Return null if this NestedInteger holds a single integer
 *     @return {NestedInteger[]}
 *     this.getList = function() {
 *         ...
 *     };
 * };
 */
/**
 * @param {NestedInteger[]} nestedList
 * @return {number}
 */

Answer 3

Вы можете использовать Array#reduce и пропустить sum для каждого уровня, возвращая сумму для каждого уровня.

function depthSum(nestedList, level = 1) {
    return nestedList.reduce((sum, val) =>
        sum + (Array.isArray(val)
            ? depthSum(val, level + 1)
            : level * val),
        0);
};

console.log(depthSum([[1, 1], 2, [1, 1]]));