concept

The depth-first Search algorithm (DFS) is an algorithm used to traverse or Search a tree or graph. Traverse the nodes of the tree as deep as possible, searching branches of the tree as deep as possible. When all edges of node V have been explored, the search goes back to the starting node of the edge where node V was found. This process continues until all nodes reachable from the source node have been discovered. If there are undiscovered nodes, one of them is selected as the source node and the process is repeated until all nodes have been accessed. Belong to blind search.

Depth-first search is a classical algorithm in graph theory. The depth-first search algorithm can generate the corresponding topological sorting list of the target graph, and the topological sorting list can conveniently solve many related graph theory problems, such as the maximum path problem and so on.

John Hopcroft and Robert Tajan shared computing’s highest prize, the Turing Prize, in 1986 for their work on the depth-first search algorithm. (From – Wikipedia)

The original problem

339. Nested List Weight Sum

Given a nested list of integers, return the sum of all integers in the list weighted by their depth.

Each element is either an integer, or a list — whose elements may also be integers or other lists.

Example 1:

Input: [[1,1],2,[1,1]] Output: 10 Explanation: Four 1’s at depth 2, one 2 at depth 1. Example 2:

Input: [1,[4,[6]]] Output: 27 Explanation: One 1 at depth 1, one 4 at depth 2, and one 6 at depth 3; 1 plus 42 plus 63 is 27.

339. Sum of weights for nested lists

Given a list of nested integers, returns the sum of the weights of all elements in a depth-first search

Each element is either an integer or a list — the elements of a list are also integers or lists

Case 1:

Input: [[1,1],2,[1,1]] Output: 10 Description: The depth of four 1s is 2, and the depth of one 2 is 1.

Example 2:

Input: [1,[4,[6]] Output: 27 Description: One “1” has a depth of 1, one “4” has a depth of 2, and one “6” has a depth of 3. 1 plus 42 plus 63 is 27.

  • In LeetCode, this problem belongs to the depth-first search multiple algorithm classification

The original prompt

/**
 * // This is the interface that allows forcreating nested lists. * // You should not implement it, or speculate about its implementation * public interface NestedInteger { * // Constructor initializes an empty nested list. * public NestedInteger(); * * // Constructor initializes a single integer. * public NestedInteger(int value); * * / / @return true if this NestedInteger holds a single integer, rather than a nested list. * public boolean isInteger(); * * / / @return the single integer that this NestedInteger holds, if it holds a single integer
 *     // Return null if this NestedInteger holds a nested list
 *     public Integer getInteger();
 *
 *     // Set this NestedInteger to hold a single integer.
 *     public void setInteger(int value);
 *
 *     // Set this NestedInteger to hold a nested list and adds a nested integerto it. * public void add(NestedInteger ni); * * / / @return the nested list that this NestedInteger holds, if it holds a nested list
 *     // Return null if this NestedInteger holds a single integer
 *     public List<NestedInteger> getList();
 * }
 */
Copy the code

Analysis of the question

Observe NestedInteger’s method, isInteger() indicates whether the current element contains Integer data, true indicates yes, and false indicates a nested include list. GetInteger () gets the Integer value that the current element contains. Because of the nested data structure, it is not difficult to think of the typical depth-first search idea

Concept design

When searching the current list, if the current element contains only Integer but not nested structure, the current node element (depth *Integer) is calculated to calculate the weight of the current element and then add. If the current element is a nested List structure, the weight sum of the current sublist can be calculated recursively

Pseudo code:

The DFS method has two parameters: list and node depth. Sum =0; sum=0; 2, loop through the input parameter List<NestedInteger> List; I. If the list element is an Integer non-list (nested sublist), calculate the weight of the current element as Integer value * depth; Add the calculated weight values to the total weight and variable sum; Ii. If the list element is not an Integer but a nested sublist, the DFS method is recursively called to calculate the weight sum of the list, and the element depth needs to be increased by 1. 3. Return the weight and sum at the end of the loop; 2. If the depth of the outermost element node is 1, call the DFS method directly to pass in the list, and get the sum of the weights directly with the depth of 1.Copy the code

Coding practices

	private int dfs(List<NestedInteger> list, int depth) {
		int sum = 0;
		for (NestedInteger e : list) {
			sum += e.isInteger() ? e.getInteger() * depth : helper(e.getList(), depth + 1);
		}
		return sum;
	}
	
	public int depthSum(List<NestedInteger> nestedList) {
		return helper(nestedList, 1);
	}	

Copy the code

conclusion

This topic is relatively simple, focusing on understanding the idea of depth-first traversal and simple practice, no Easter eggs. For the depth first algorithm, there will be further explanation of advanced blog questions