Easy-To-Understand solution beats 89%


  • 2
    Z

    The logic is as follows:

    1. Assume start point of squirrel is tree, then the minimal sum of distance of collecting all nuts will always be Sum1 = Sum(2*distance of tree to nut(i) {i=0->n}) (1)
    2. Assume start point of squirrel is not tree, that means we have to go back at first, then it would shorten the total distance if we let our little squirrel collect one (any one) nut by its way to tree at the first time. So the critical part is which one should we take?
    3. Assume we pick nut(i), Result = Min(Sum1 - 2 * distance of tree to nut(i) +(distance of squirrel to nut(i) + distance of tree to nut(i) ) ) = Min(Sum1 - (distance of tree to nut - distance of squirrel to nut ) ). Since Sum1 doesn't change, It finally becomes Result = Sum1 - Max( distance of tree to nut - distance of squirrel to nut ) (2);
      Distance of two point a1[], a2[] can be calculated by Math.abs(a1[0]-a2[0])+Math.abs(a1[1]-a2[1]);
      equation 2 is all you need.
        public int minDistance(int height, int width, int[] tree, int[] squirrel, int[][] nuts) {
            int s1 = 0;int max = Integer.MIN_VALUE;
            for(int[]nut :nuts){
                int treeToNut = distance(tree,nut);
                int squrToNut = distance(squirrel,nut);
                s1 += 2 * treeToNut;
                max = Math.max(max,treeToNut-squrToNut);
            }
            return s1 - max;
        }
        int distance(int[] a1, int[] a2){
            return Math.abs(a1[0]-a2[0])+Math.abs(a1[1]-a2[1]);
        }
    

Log in to reply
 

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