代码之家 › 专栏 › 技术社区 › TechnoCorner

嵌套列表权重和javascript

array-algorithms algorithm arrays javascript

TechnoCorner · 技术社区 · 6 年前

我试图解决这个问题,在这个问题中,我们计算给定数组的嵌套权重和。

给定一个嵌套的整数列表,返回按深度加权的列表。

例如:

[[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;
};

我正在努力解决逆向问题。即

给定一个嵌套的整数列表,返回按深度加权的列表。从根部到叶,现在权重是自下而上定义的。i、 e,叶水平整数的权重为1,根级整数的权重最大重量。

例子: [[1,1],2,[1,1]]==>解为8。

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

4 回复 | 直到 5 年前

ggorlen Hoàng Huy Khánh 6 年前

这个应该做这项工作,但我希望我有一个额外的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]));

CertainPerformance 6 年前

一个基本的递归解决方案,就像你原来的一样 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

m69 ''snarky and unwelcoming'' 6 年前

如果在遍历期间将每个深度的元素总和存储在数组中,则无需对嵌套数组进行两次遍历即可完成此操作。然后,您知道这个数组的长度是最大深度,您可以将这些和乘以它们的正确权重。

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]],[]]));

-1

Redu 6 年前

也许你可以用一个简单的递归减速机做如下操作。

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