Задача: 364. Nested List Weight Sum II
Вам дан вложенный список целых чисел nestedList. Каждый элемент является либо целым числом, либо списком, элементы которого также могут быть целыми числами или другими списками.
Глубина целого числа — это количество списков, внутри которых оно находится. Например, вложенный список [1,[2,2],[[3],2],1] имеет значение каждого целого числа, установленное равным его глубине. Пусть maxDepth будет максимальной глубиной любого целого числа.
Вес целого числа определяется как maxDepth - (глубина целого числа) + 1.
Верните сумму каждого целого числа в nestedList, умноженную на его вес.
Пример:
Input: nestedList = [[1,1],2,[1,1]]
Output: 8
Explanation: Four 1's with a weight of 1, one 2 with a weight of 2.
1*1 + 1*1 + 2*2 + 1*1 + 1*1 = 8
👨💻 Алгоритм:
1⃣Инициализировать первый уровень BFS-дерева, добавив все элементы из входного nestedList в очередь.
2⃣Для каждого уровня извлекать передний элемент из очереди. Если это список, то добавить его элементы в очередь. В противном случае обновить значения sumOfElements, maxDepth и sumOfProducts.
3⃣Когда очередь станет пустой, вернуть значение (maxDepth + 1) * sumOfElements - sumOfProducts.
😎 Решение:
using System;
using System.Collections.Generic;
public class Solution {
public int DepthSumInverse(IList<NestedInteger> nestedList) {
var queue = new Queue<NestedInteger>(nestedList);
int depth = 1, maxDepth = 0, sumOfElements = 0, sumOfProducts = 0;
while (queue.Count > 0) {
int size = queue.Count;
maxDepth = Math.Max(maxDepth, depth);
for (int i = 0; i < size; i++) {
var nested = queue.Dequeue();
if (nested.IsInteger()) {
int value = nested.GetInteger();
sumOfElements += value;
sumOfProducts += value * depth;
} else {
foreach (var ni in nested.GetList()) queue.Enqueue(ni);
}
}
depth++;
}
return (maxDepth + 1) * sumOfElements - sumOfProducts;
}
}
👉Новости 👉Платформа