0

给定一个嵌套的整数列表，返回列表中所有整数的总和，按它们的深度加权

例如，给定列表 {{1,1},2,{1,1}}，函数应返回 10（深度 2 处有四个 1，深度 1 处有一个 *2）

给定列表 {1,{4,{6}}}，函数应返回 27（深度 1 为 1，深度 2 为 4，深度 3 为 *6）

public int depthSum (List<NestedInteger> input)
{
     //Implement this function
}

/**
 * This is the interface that allows for creating nested lists. You should not implement it, or speculate about its implementation
 */
public interface NestedInteger 
{
    // Returns true if this NestedInteger holds a single integer, rather than a nested list
    public boolean isInteger();

    // Returns the single integer that this NestedInteger holds, if it holds a single integer
    // Returns null if this NestedInteger holds a nested list
    public Integer getInteger();

    // Returns the nested list that this NestedInteger holds, if it holds a nested list
    // Returns null if this NestedInteger holds a single integer
    public List<NestedInteger> getList();
}
4

3 回答 3

2

一个想法很简单。

假设您有像 {{1,1},2,{1,1}} 这样的嵌套数组的字符串，
只需遍历字符串并跟踪尚未关闭的大括号数。当前元素的深度应等于直到该点的开括号的数量。

例如 {{1,1},2,{1,1}}

1. Read 1st two characters. The counter for number of open braces is 2.
2. Hence the depth of both the 1s read = 2.
3. Then a closing brace appears, so decrement the counter.
4. The depth of 2 shall be 1.
5. Likewise for the remaining elements.

编辑：对于 NestedInteger 接口，您可以修改上述算法并使用递归实现它。以下是一个似是而非的伪代码。

public int getSum( List<NestedInteger> input, int currDepth ) {

  int sum = 0;
//  iterate through the list.
  if ith element is an Integer, then sum += currDepth*element; // simply add the element to sum
  else  sum += getSum( element, currDepth + 1 ); // get sum for that particular nested list.
  return sum;

}


public int depthSum (List<NestedInteger> input)
{
     return getSum( input, 1 );
}
于 2013-09-30T06:52:43.400 回答
2 
import java.util.ArrayList;
import java.util.List;

public class NestedList {
    public static void main(String[] args) {
        // {{1,1},2,{1,1}}
        List<Object> parent1 = new ArrayList<Object>();

        List<Object> child1 = new ArrayList<Object>();
        child1.add(1);
        child1.add(1);
        parent1.add(child1);

        parent1.add(2);

        List<Object> child3 = new ArrayList<Object>();
        child3.add(1);
        child3.add(1);
        parent1.add(child3);

        System.out.println(getSum(parent1, 1));

        // {1,{4,{6}}}
        List<Object> parent2 = new ArrayList<Object>();
        parent2.add(1);

        List<Object> child11 = new ArrayList<Object>();
        child11.add(4);

        List<Object> child111 = new ArrayList<Object>();
        child111.add(6);

        child11.add(child111);
        parent2.add(child11);
        System.out.println(getSum(parent2, 1));
    }

    private static int getSum(Object list, int depth) {
        if (list == null)
            return 0;

        int sum = 0;
        if (list.getClass() == ArrayList.class) {
            for (Object nestedList : (ArrayList<Object>) list) {
                if (nestedList.getClass() == ArrayList.class)
                    sum += getSum(nestedList, depth + 1);
                else
                    sum += getSum(nestedList, depth);
            }
        } else {
            sum += (Integer) list * depth;
            System.out.println("CurrentSum => " + sum + " integer => " + list
                    + " Depth => " + depth);
        }
        return sum;
    }
}
于 2013-09-30T07:27:42.303 回答
1

您必须为此使用堆栈。

假设字符串是{{1,1},2,{1,1}}。

Step 1: Go through the string to determine its depth.

您可以通过初始化变量depth =0和maxdepth=depth; 每次遇到 '{' 增量depth时，如果depth>maxdepth, maxdepth=depth. 如果遇到 '}'，则递减depth.

的最终值maxdepth将是字符串的深度。在这种情况下maxdepth=2；

Step 2: Declare an array items_depth to the depth given by maxdepth.
Integer[] items_depth = new Integer[maxdepth+1];

items_depth给出任意深度的项目数. 将所有元素初始化items_depth为 0。（最初在任何深度都有零项）。我也假设深度为 0。因此，对于深度 2，将有三个深度 0、1、2 的项目。

Step 3: Go through the string again from left to right
int depth =0;
Stack<Integer> stack = new Stack<Integer>();
while(there are characters in the string)
{    char i = current character;
     if(i=='{')
     {
         depth++;
     }
     if(i is an integer)
     {
         items_depth[depth]++;
         stack.push(Integer.parseInt(i));
     }
     if(i==',')
     {
         continue;

     }
     if(i=='}')
     {
         int temp= items_depth[depth];
         int temp_depth = depth;
         depth--;
         int temp_sum=0;


         for(int i=1;i<=items_depth[temp_depth] && items_depth[temp_depth]>0;i++)
         {
          temp_sum+=stack.pop();   
         }
         items_depth[temp_depth]=0;
         stack.push(temp_sum);
         item_depth[depth]++; 
     }

}
return stack.pop();

从堆栈中弹出的最后一项将是以深度为权重的项的总和。我假设一个字符 int。您必须修改代码以适应其他整数

于 2013-09-30T09:23:06.580 回答