364. Nested List Weight Sum II

leetcode medium

#csharp#graph#leetcode#math#medium#queue#tree

Task

Вам дан вложенный список целых чисел 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# solution

matched/original

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++ solution

auto-draft, review before submit

#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 solution

matched/original

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 solution

matched/original

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 solution

matched/original

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 - sumOfProducts

Go solution

matched/original

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
}

Explanation

Algorithm

Инициализировать первый уровень BFS-дерева, добавив все элементы из входного nestedList в очередь.

Для каждого уровня извлекать передний элемент из очереди. Если это список, то добавить его элементы в очередь. В противном случае обновить значения sumOfElements, maxDepth и sumOfProducts.

Когда очередь станет пустой, вернуть значение (maxDepth + 1) * sumOfElements - sumOfProducts.

😎