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
C# решение
сопоставлено/оригинал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;
}
}C++ решение
auto-draft, проверить перед отправкой#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
public int DepthSumInverse(IList<NestedInteger> nestedList) {
var queue = new queue<NestedInteger>(nestedList);
int depth = 1, maxDepth = 0, sumOfElements = 0, sumOfProducts = 0;
while (queue.size() > 0) {
int size = queue.size();
maxDepth = 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;
}
}Java решение
сопоставлено/оригиналclass Solution {
public int depthSumInverse(List<NestedInteger> nestedList) {
Queue<NestedInteger> Q = new LinkedList<>();
Q.addAll(nestedList);
int depth = 1;
int maxDepth = 0;
int sumOfElements = 0;
int sumOfProducts = 0;
while (!Q.isEmpty()) {
int size = Q.size();
maxDepth = Math.max(maxDepth, depth);
for (int i = 0; i < size; i++) {
NestedInteger nested = Q.poll();
if (nested.isInteger()) {
sumOfElements += nested.getInteger();
sumOfProducts += nested.getInteger() * depth;
} else {
Q.addAll(nested.getList());
}
}
depth++;
}
return (maxDepth + 1) * sumOfElements - sumOfProducts;
}
}JavaScript решение
сопоставлено/оригиналclass Solution {
depthSumInverse(nestedList) {
const queue = [...nestedList];
let depth = 1;
let maxDepth = 0;
let sumOfElements = 0;
let sumOfProducts = 0;
while (queue.length) {
const size = queue.length;
maxDepth = Math.max(maxDepth, depth);
for (let i = 0; i < size; i++) {
const nested = queue.shift();
if (nested.isInteger()) {
const value = nested.getInteger();
sumOfElements += value;
sumOfProducts += value * depth;
} else {
queue.push(...nested.getList());
}
}
depth++;
}
return (maxDepth + 1) * sumOfElements - sumOfProducts;
}
}Python решение
сопоставлено/оригиналfrom collections import deque
class Solution:
def depthSumInverse(self, nestedList):
queue = deque(nestedList)
depth = 1
maxDepth = 0
sumOfElements = 0
sumOfProducts = 0
while queue:
size = len(queue)
maxDepth = max(maxDepth, depth)
for _ in range(size):
nested = queue.popleft()
if nested.isInteger():
value = nested.getInteger()
sumOfElements += value
sumOfProducts += value * depth
else:
queue.extend(nested.getList())
depth += 1
return (maxDepth + 1) * sumOfElements - sumOfProductsGo решение
сопоставлено/оригиналpackage main
type NestedInteger struct {
// This is a placeholder structure for the NestedInteger implementation
}
func (ni NestedInteger) IsInteger() bool {
// Placeholder method
return false
}
func (ni NestedInteger) GetInteger() int {
// Placeholder method
return 0
}
func (ni NestedInteger) GetList() []*NestedInteger {
// Placeholder method
return nil
}
func depthSumInverse(nestedList []*NestedInteger) int {
queue := append([]*NestedInteger(nil), nestedList...)
depth, maxDepth, sumOfElements, sumOfProducts := 1, 0, 0, 0
for len(queue) > 0 {
size := len(queue)
if depth > maxDepth {
maxDepth = depth
}
for i := 0; i < size; i++ {
nested := queue[0]
queue = queue[1:]
if nested.IsInteger() {
value := nested.GetInteger()
sumOfElements += value
sumOfProducts += value * depth
} else {
queue = append(queue, nested.GetList()...)
}
}
depth++
}
return (maxDepth + 1) * sumOfElements - sumOfProducts
}Algorithm
Инициализировать первый уровень BFS-дерева, добавив все элементы из входного nestedList в очередь.
Для каждого уровня извлекать передний элемент из очереди. Если это список, то добавить его элементы в очередь. В противном случае обновить значения sumOfElements, maxDepth и sumOfProducts.
Когда очередь станет пустой, вернуть значение (maxDepth + 1) * sumOfElements - sumOfProducts.
😎
Вакансии для этой задачи
Показаны активные вакансии с пересечением по тегам задачи.