Easy understanding DFS 0ms C++ and 48ms python and 84ms javascript solutions


  • 4
    S

    c++:

    class Solution {
        private:
            int DFS(vector<NestedInteger>& nestedList, int depth){
                int n = (int)nestedList.size();
                int sum = 0;
                for(int i=0;i<n;i++){
                    if(nestedList[i].isInteger()){
                        sum += nestedList[i].getInteger()*depth;
                    }
                    else{
                        sum += DFS(nestedList[i].getList(),depth+1);
                    }
                }
                return sum;
            }
        public:
            int depthSum(vector<NestedInteger>& nestedList) {
                return DFS(nestedList, 1);
            }
    };
    

    Python:

    class Solution(object):
        def depthSum(self, nestedList):
            """
            :type nestedList: List[NestedInteger]
            :rtype: int
            """
            def DFS(nestedList, depth):
                temp_sum = 0
                for member in nestedList:
                    if member.isInteger():
                        temp_sum += member.getInteger() * depth
                    else:
                        temp_sum += DFS(member.getList(),depth+1)
                return temp_sum
            return DFS(nestedList,1)
    

    Javascript:

    /**
     * @param {NestedInteger[]} nestedList
     * @return {number}
     */
    var dfs = function(nestedList,depth){
        var sum = 0;
        var n = nestedList.length;
        for(var i=0; i<n;i++){
            if(nestedList[i].isInteger()){
                sum += nestedList[i].getInteger() * depth;
            }
            else{
                sum += dfs(nestedList[i].getList(),depth+1);
            }
        }
        return sum;
    };
    var depthSum = function(nestedList) {
      return dfs(nestedList,1);  
    };

  • 0
    P

    Thanks for providing the solutions.

    One question about Python part:

    What does getList() do here or in general ?


  • 1
    C

    said in Easy understanding DFS 0ms C++ and 48ms python and 84ms javascript solutions:

    i submitted one copy of your code. But the completion time is not 0ms in C++.


  • 0
    W

    A BFS solution:

    int depthSum(vector<NestedInteger>& nestedList) {
            queue<NestedInteger> next;
            int result = 0, level = 1;
            for(auto& elem: nestedList) {
                if(elem.isInteger()) result += level * elem.getInteger();
                else next.push(elem);
            }
            while(!next.empty()) {
                level++;
                int size = next.size();
                while(size--) {
                    auto cur = next.front(); next.pop();
                    auto vec = cur.getList();
                    for(auto& elem: vec) {
                        if(elem.isInteger()) result += level * elem.getInteger();
                        else next.push(elem);
                    }
                }
            }
            return result;
        }
    

  • 0
    Q

    @chowp yeah, I have tried the same thing finding that the time is 3ms rather than 0ms!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.