[Java] Store parents in an array (17 ms)


  • 0
    K
    class Solution {
        public int pathSum(int[] nums) {
            if (nums == null || nums.length == 0) {
                return 0;
            }
            Arrays.sort(nums);
            int[] vals = new int[nums.length];
            int[] parents = new int[nums.length];
            int[] sums = new int[nums.length];
            HashSet<Integer> set = new HashSet<>();
            HashMap<Integer, Integer> map = new HashMap<>();
            for (int i = 0; i < nums.length; i++) {
                int depth = nums[i] / 100;
                nums[i] %= 100;
                int position = nums[i] / 10;
                vals[i] = nums[i] % 10;
                int index = (int) Math.pow(2, depth - 1) - 1 + position;
                if (i != 0) {
                    parents[i] = map.get(index / 2);
                    set.add(parents[i]);
                }
                map.put(index, i);
            }
            int sum = 0;
            for (int i = parents.length - 1; i >= 0; i--) {
                if (!set.contains(i)) {
                    sum += getSum(vals, parents, i, sums);
                }
            }
            return sum;
        }
        
        private int getSum(int[] vals, int[] parents, int index, int[] sums) {
            if (index == 0) {
                return vals[0];
            } else {
                if (sums[index] == 0) {
                    sums[index] = getSum(vals, parents, parents[index], sums);
                }
                return sums[index] + vals[index];
            }
        }
    }
    

Log in to reply
 

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