Вложенный список вес суммы javascript

Question

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

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

Например, для:

[[1,1], 2, [1,1]] ====> решение - 10.

Четыре 1 на глубине 2, один 2 на глубине 1.

Вот код, который я написал:

var depthSum = function (nestedList, sum=0, depth=1) {
    for(let i=0; i<nestedList.length; i++){
        let val = nestedList[i];
        if (Array.isArray(val)) {
            return depthSum(val, sum, depth+1);
        } else {
            sum += val * depth;
        }
    };
    return sum;
};

Я пытаюсь решить проблему с обратным. * 1018 то есть *

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

* * Пример тысячу двадцать-три: [[1,1], 2, [1,1]] ===> Решение - 8.

Как я могу использовать тот же подход и решить эту проблему?

(https://leetcode.com/problems/nested-list-weight-sum-ii/description/)

Answer 1

Может быть, вы можете сделать следующее простым рекурсивным редуктором.

var weightOfNested = (a,d=1) => a.reduce((w,e) => Array.isArray(e) ? w + weightOfNested(e,d+1)
                                                                   : w + d*e, 0);
console.log(weightOfNested([[1,1,[3]],2,[1,1]]));

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

var weightOfNested = (a, d = getDepth(a)) => a.reduce((w,e) => Array.isArray(e) ? w + weightOfNested(e,d-1)
                                                                                : w + d*e, 0),
    getDepth       = (a, d = 1, t = 1) => a.reduce((r,e) => Array.isArray(e) ? r === t ? getDepth(e,++r,t+1)
                                                                                       : getDepth(e,r,t+1)
                                                                             : r, d);
console.log(weightOfNested([[1,1,[3]],2,[1,1]])); // depth is 3

Answer 2

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

Вы можете использовать reduce (который является подходящим методом для преобразования объекта в единое значение) и условный (троичный) оператор, чтобы сделать ваш код кратким и менее повторяющимся:

const depthCheck = (item) => (
  Array.isArray(item)
  ? 1 + Math.max(...item.map(depthCheck))
  : 0
);

// verification:
console.log(depthCheck([[1,1],2,[1,1]])); // total depth 2
console.log(depthCheck([[1,1],2,[1,1,[2,2]]])) // total depth 3
console.log(depthCheck([[1,1,[2,[3,3]]],2,[1,1,[2,2]]])) // total depth 4
console.log('-----')

const depthSum = (nestedList, weight=depthCheck(nestedList)) => (
  nestedList.reduce((a, val) => a + (
    Array.isArray(val)
    ? depthSum(val, weight - 1)
    : val * weight
  ), 0)
);

console.log(depthSum([[1,1],2,[1,1]])) // (2)*2 + (1+1+1+1)*1
console.log(depthSum([[1,1],2,[1,1,[2,2]]])) // (2)*3 + (1+1+1+1)*2 + (2+2)*1
console.log(depthSum([[1,1,[2,[3,3]]],2,[1,1,[2,2]]])) // (2)*4 + (1+1+1+1)*3 + (2)*2 + (3+3)*1

Answer 3

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

Обход может быть выполнен с использованием рекурсии или стека, как объяснено в других ответах. Вот пример использования рекурсии:

function weightedSum(array) {
    var sums = [], total = 0;
    traverse(array, 0);
    for (var i in sums)
        total += sums[i] * (sums.length - i);
    return total;

    function traverse(array, depth) {
        if (sums[depth] === undefined)
            sums[depth] = 0;
        for (var i in array) {
            if (typeof array[i] === "number")
                sums[depth] += array[i];
            else traverse(array[i], depth + 1);
        }
    }
}

console.log(weightedSum([[],[]]));
console.log(weightedSum([[1,1],2,[1,1]]));
console.log(weightedSum([1,[[],2,2],1,[[3,3,[[5]]],[3]],[]]));

Answer 4

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

const search = a => {
  let sum = 0;
  let depth = 0;
  const stack = [[a, 0]];

  while (stack.length) {
    const curr = stack.pop();

    if (curr[1] > depth) {
      depth = curr[1];
    }

    for (const e of curr[0]) {
      if (Array.isArray(e)) {
        stack.push([e, curr[1] + 1]);
      }
    }
  }

  stack.push([a, ++depth]);

  while (stack.length) {
    const curr = stack.pop();

    for (const e of curr[0]) {
      if (Array.isArray(e)) {
        stack.push([e, curr[1] - 1]);
      }
      else {
        sum += e * curr[1];
      }
    }
  }

  return sum;
};

console.log(search([[1,1],2,[1,1]]));
console.log(search([]));
console.log(search([6]));
console.log(search([[[[3]]]]));
console.log(search([[2],1]));