Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.
I. Title Description:
The robot walks on an XY grid plane of infinite size, starting at point (0, 0) and facing north. The robot can receive three types of commands:
-2: Turn 90 degrees to the left -1: Turn 90 degrees to the right 1 <= x <= 9: Move forward x units of length On the grid there are some grids that are considered obstacles in diction. The ith obstacle is located at the grid point dici [I] = (xi, yi).
The robot cannot walk to the obstacle, it will stay on the grid square in front of the obstacle, but can still continue to attempt the rest of the path.
Returns the square of the maximum Euclidean distance from the origin to all the waypoints (integer coordinates) the robot passes through. (that is, if the distance is 5, return 25)
Note:
- The north said
+YDirection. - East said
+XDirection. - South said
-YDirection. - West said
-XDirection.
The sample
The sample1: Enter: commands = [4, -1.3], Lazy = [] Output:25Explanation: The robot starts at (0.0) :1.Moving north,4One unit, reaching (0.4)
2.Turn right3.Moving to the east3One unit, reaching (3.4) Farthest from the origin is (3.4), the distance is32 + 42 = 25The sample2: Enter: commands = [4, -1.4, -2.4], obstacles = [[2.4]] output:65Explanation: The robot starts at (0.0) :1.Moving north,4One unit, reaching (0.4)
2.Turn right3.Moving to the east1Is then located at (2.4), the robot stops at (1.4)
4.Turn left5.To the north,4One unit, reaching (1.8) Farthest from the origin is (1.8), the distance is12 + 82 = 65
Copy the codeTip:
- 1 <= commands.length <= 104
- Commands [I] is one of the values in the list [-2,-1,1,2,3,4,5,6,7,8,9].
- 0 <= obstacles.length <= 104
- -3 * 104 <= xi, yi <= 3 * 104
- The answer is guaranteed to be less than 231
Ii. Solution:
Method 1: step by step comparison
- Principle. Record the direction, perform x or Y changes, correct x or Y according to the array of obstacles, record the current farthest point.
- Train of thought.
- Record the direction (0,1,2,3 correspond to north, southeast, west),
- Perform x or Y changes depending on the direction
- According to the change and the value before the change, determine whether there is this value in the middle of the block, and then reassign
- Math.max compares the current farthest point math.pow (x,2)+Math.pow(y,2) with the previous farthest point
Code:
var robotSim = function(commands, obstacles) {
let x = 0;
let beforeX = 0
let y = 0;
let beforeY = 0
let max = 0
/ / let _arr = [' n ', 'e', 's', 'w'] / / 'n' north 'e' east 's' south 'w' west
let defalut = 0
for(let i=0; i<commands.length; i++){if(commands[i] === -1){
defalut = (defalut+1+4) %4
continue
} else if(commands[i] === -2){
defalut = (defalut-1+4) %4
continue
}
if(defalut === 0){
y+=commands[i]
} else if(defalut === 1){
x+=commands[i]
}else if(defalut === 2){
y-=commands[i]
}else if(defalut === 3){
x-=commands[i]
}
for(let j=0; j<obstacles.length; j++){if(obstacles[j][0] === x && defalut=== 0 && obstacles[j][1]>beforeY){
y = y>obstacles[j][1] -1? obstacles[j][1] -1:y
continue
}
if(obstacles[j][0] === x && defalut=== 2 && obstacles[j][1]<beforeY){
y = y<obstacles[j][1] +1? obstacles[j][1] +1:y
continue
}
if(obstacles[j][1] === y && defalut=== 1 && obstacles[j][0]>beforeX){
x = x>obstacles[j][0] -1? obstacles[j][0] -1:x
continue
}
if(obstacles[j][1] === y && defalut=== 3 && obstacles[j][0]<beforeX){
x = x<obstacles[j][0] +1? obstacles[j][0] +1:x
continue
}
}
beforeX = x
beforeY = y
max = Math.max(max, Math.pow(x,2) +Math.pow(y,2))}return max
};
Copy the code
- Optimize your thinking. Change your judgment.
Code:
var robotSim = function(commands, obstacles) {
let x = 0;
let beforeX = 0
let y = 0;
let beforeY = 0
let max = 0
let defalut = 0
for(let i=0; i<commands.length; i++){let item = commands[i]
if(item === -1 || item === -2){
defalut = (defalut+1*(item===-2? -1:1) +4) %4
continue
}
if(defalut === 0 || defalut === 2){
y+=item*(defalut===2? -1:1)}else if(defalut === 1 || defalut === 3){
x+=item*(defalut===3? -1:1)}for(let j=0; j<obstacles.length; j++){let ob = obstacles[j]
if(ob[0] === x) {
if(defalut=== 0 && ob[1]>beforeY){
y = y>ob[1] -1? ob[1] -1:y
continue
}
if(defalut=== 2 && ob[1]<beforeY){
y = y<ob[1] +1? ob[1] +1:y
continue}}if(ob[1] === y) {
if(defalut=== 1 && ob[0]>beforeX){
x = x>ob[0] -1? ob[0] -1:x
continue
}
if(defalut=== 3 && ob[0]<beforeX){
x = x<ob[0] +1? ob[0] +1:x
continue
}
}
}
beforeX = x
beforeY = y
max = Math.max(max, x*x+y*y)
}
return max
};
Copy the code
Method two: defect recording method
- Principle. Step by step, record the location of the defect, and use set to extract whether the defect is reached.
Code:
var robotSim = function(commands, obstacles) {
let x = 0;
let y = 0;
const dirX = [0.1.0, -1]
const dirY = [1.0, -1.0]
let max = 0
let dirIndex = 0
const obArr = new Set(a)for(let item of obstacles){
obArr.add(item[0] +The '-'+item[1])}for(let item of commands){
if(item === -1 || item === -2){
dirIndex = (dirIndex+1*(item===-2? -1:1) +4) %4
}else {
for(let i=0; i<item; i++){const tempX = x+dirX[dirIndex]
const tempY = y+dirY[dirIndex]
if(obArr.has(tempX+The '-'+tempY)){
break
}
x = tempX
y = tempY
max = Math.max(max, x*x + y*y)
}
}
}
return max
};
Copy the code
Scheme comparison
Solution 1 Time complexity O(NK) Solution 2 Time complexity O(N+K)
Third, summary
- This problem can be compared step by step method and record defect method two schemes
- Step by step comparison mainly records the direction, performs x or Y changes, corrects x or Y according to the obstacle array, and records the current farthest point.
- The defect recording method moves step by step, records the position of the defect, and uses SET to extract whether the defect has reached the barrier.
If there are any errors in this article, please correct them in the comments section