Skip to content

Commit 43a02af

Browse files
refactor 573
1 parent 2445622 commit 43a02af

File tree

1 file changed

+4
-35
lines changed
  • src/main/java/com/fishercoder/solutions

1 file changed

+4
-35
lines changed

src/main/java/com/fishercoder/solutions/_573.java

Lines changed: 4 additions & 35 deletions
Original file line numberDiff line numberDiff line change
@@ -1,54 +1,23 @@
11
package com.fishercoder.solutions;
22

3-
/**
4-
* 573. Squirrel Simulation
5-
*
6-
* There's a tree, a squirrel, and several nuts.
7-
* Positions are represented by the cells in a 2D grid.
8-
* Your goal is to find the minimal distance for the squirrel to collect all the nuts and
9-
* put them under the tree one by one.
10-
* The squirrel can only take at most one nut at one time and can move in four directions -
11-
* up, down, left and right, to the adjacent cell.
12-
* The distance is represented by the number of moves.
13-
14-
Example 1:
15-
16-
Input:
17-
Height : 5
18-
Width : 7
19-
Tree position : [2,2]
20-
Squirrel : [4,4]
21-
Nuts : [[3,0], [2,5]]
22-
Output: 12
23-
24-
Explanation:
25-
26-
Note:
27-
28-
All given positions won't overlap.
29-
The squirrel can take at most one nut at one time.
30-
The given positions of nuts have no order.
31-
Height and width are positive integers. 3 <= height * width <= 10,000.
32-
The given positions contain at least one nut, only one tree and one squirrel.
33-
*/
343
public class _573 {
354

365
public static class Solution1 {
376

387
/**
398
* reference: https://leetcode.com/articles/squirrel-simulation
40-
*
9+
* <p>
4110
* 1. The order in which to pick the nuts does not matter except the first one
4211
* because for all the other nuts, the squirrel needs to travel back and forth.
43-
*
12+
* <p>
4413
* 2. For the first nut to be picked, there's some distance we might be able to save, what is this distance?
4514
* It is the difference between the squirrel's original starting point to the first nut and that the distance from this
4615
* first nut to the tree.
4716
* This is because, only for the first nut, the squirrel does NOT need to travel back and forth, it only needs to travel from
4817
* its starting position to the nut position and then return to the tree.
49-
*
18+
* <p>
5019
* 3. For the rest of all other nuts, the squirrel always needs to go back and forth.
51-
*
20+
* <p>
5221
* 4. So how can we find the first nut to go to so that we could have the maximum saved distance?
5322
* We iterate through all of the nuts and keep updating the savedDist as below:
5423
*/

0 commit comments

Comments
 (0)