Задача: 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.
😎 Решение:
class Solution {
fun depthSumInverse(nestedList: List<NestedInteger>): Int {
val queue: Queue<NestedInteger> = LinkedList(nestedList)
var depth = 1
var maxDepth = 0
var sumOfElements = 0
var sumOfProducts = 0
while (queue.isNotEmpty()) {
val size = queue.size
maxDepth = maxOf(maxDepth, depth)
repeat(size) {
val nested = queue.poll()
if (nested.isInteger()) {
val value = nested.getInteger()
sumOfElements += value
sumOfProducts += value * depth
} else {
queue.addAll(nested.getList())
}
}
depth++
}
return (maxDepth + 1) * sumOfElements - sumOfProducts
}
}👉Новости 👉База вопросов