My accepted solution in Java


  • 0
    A

    My explanation with a instance.

    The given list:

    [
    [2], --------1th
    [3,4], --------2th
    [6,5,7], --------3th
    [4,1,8,3] --------4th
    ]

    Firstly,I put all elements on 4th into a HashMap(map) as ( i , list.get(i) )

    Then, from 3th to 1th , I always do below:

    1.For each element on current floor,get the left-path-sum and right-path-sum.

    2.Put the smaller one between left-path-sum and right-path-sum into the map as (j,left or right).

    3.To upper floor.

    public class Solution {
        public int minimumTotal(List<List<Integer>> triangle) {
            if(triangle.size()==0) return 0;
            if(triangle.size()==1) return triangle.get(0).get(0);
            Map<Integer,Integer> sumMap=new HashMap<Integer,Integer>();
            int top=triangle.get(0).get(0);
            for(int i=triangle.size()-1;i>=0;i--)
            {
                List<Integer> curList=triangle.get(i);
                if(i==triangle.size()-1)
                {
                    for(int j=0;j<curList.size();j++)
                    {
                        sumMap.put(j,curList.get(j));
                    }
                }
                else
                {
                    for(int j=0;j<curList.size();j++)
                    {
                        int left=curList.get(j)+sumMap.get(j);
                        int right=curList.get(j)+sumMap.get(j+1);
                        if(left<right) sumMap.put(j,left);
                        else sumMap.put(j,right);
                    }
                }
            }
            return sumMap.get(0);
        }
    }

Log in to reply
 

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