Easy Java Solution


  • 0
    D

    Bottom-up algorithm:

        public int pathSum(int[] nums) {
            int sum = 0;
            if(nums == null || nums.length == 0) return sum;
            Map<Integer, Integer> map = new HashMap<Integer, Integer>();
            for(int i = nums.length - 1; i >= 0; i--) {
                int posi = nums[i] / 10;
                int val = nums[i] % 10;
                int count = map.containsKey(posi) ? map.get(posi) : 1;
                sum += val * count;
                int parent = (posi/10-1) * 10 + ((posi%10)+1) / 2;
                if(!map.containsKey(parent)) map.put(parent, 0);
                map.put(parent, map.get(parent) + count);
            }
            return sum;
        }
    

Log in to reply
 

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