leetCode 874
机器人在一个无限大小的网格上行走，从点 (0, 0) 处开始出发，面向北方。该机器人可以接收以下三种类型的命令：
-2：向左转 90 度
-1：向右转 90 度
1 <= x <= 9：向前移动 x 个单位长度
在网格上有一些格子被视为障碍物。
第 i 个障碍物位于网格点 (obstacles[i][0], obstacles[i][1])
如果机器人试图走到障碍物上方，那么它将停留在障碍物的前一个网格方块上，但仍然可以继续该路线的其余部分。
返回从原点到机器人的最大欧式距离的平方。
示例 1：
输入: commands = [4,-1,3], obstacles = []
输出: 25
解释: 机器人将会到达 (3, 4)
示例 2：
输入: commands = [4,-1,4,-2,4], obstacles = [[2,4]]
输出: 65
解释: 机器人在左转走到 (1, 8) 之前将被困在 (1, 4) 处
提示：
0 <= commands.length <= 10000
0 <= obstacles.length <= 10000
-30000 <= obstacle[i][0] <= 30000
-30000 <= obstacle[i][1] <= 30000
答案保证小于 2 ^ 31
思考过程：
如图：
image.png
原先方向向北，即正上方，当得到-1或-2的转向指令后，方向的变化如下：
| 原方向 | -1 向右转 | -2 向左转 |
|---|---|---|
| (0,1) | (1,0) | (-1,0) |
| (1,0) | (0,-1) | (0,1) |
| (0,-1) | (-1,0) | (1,0) |
| (-1,0) | (0,1) | (0,-1) |
根据上表，得到以下规律：
-1： x轴为0的，x,y换位，不换符号
y轴为0的，x,y换位，且换符号（1 => -1， -1 => 1)
-2: x轴为0的，x,y换位，且换符号（1 => -1， -1 => 1)
y轴为0的，x,y换位，不换符号
根据以上规律，只要转向，x,y都要换位，需要判断的是换位后，x,y哪个换符号
如果把(0,1)这样的坐标看做是数组的话，这个问题就转换为哪个index换符号，第0位还是第1位需要换符号
-1: index 1换符号
-2: index 0换符号
看规律，把这个转向的数字+2，就得到我们所需的index
同时，不需要判断x轴是否为0，原先的方向先换位，把所需的index乘以-1，就是目标方向
举例1：
(0,1) 原先向北，得到-1指令，应该向右转，也就是向东
- 换位得到 (1,0)
- (1,0)[-1+2] = (1,0)[-1+2]*-1
解释： 这里的-1是转向的指令，2是刚才我们算出来的
(1,0)[1] = 0
0 * -1 = 0 - 新方向为 (1,0)
举例2：
(-1, 0 ) 原先向西，得到-2指令，应该向左转，也就是向南
- 换位得到 (0, -1)
- (0, -1)[-2+2] = (0, -1)[-2+2]*-1
解释： 这里的-2是转向的指令，2是刚才我们算出来的
(0, -1)[0] = 0
0 * -1 = 0 - 新方向为 (0, -1)
没有障碍物的代码：
def robotSim0(self, commands):
'''
没有障碍物的版本，小车根据指令走，图上没有障碍物
'''
direct = [0,1] #初始方向
axis = [0,0] #小车初始坐标
for command in commands:
if command in [-1, -2]: #转向指令
direct = direct[::-1]
direct[command+2] = direct[command+2]*-1
continue
move = [i*command for i in direct]
axis = [i+j for i,j in zip(axis,move)]
return axis
增加了障碍物，需要每走一步之前，判断一下是否前面是障碍物，如果是，则不前进，看下一条指令
def robotSim(self, commands, obstacles):
direct = [0,1] #初始方向
axis = [0,0] #小车初始坐标
new_axis = [] #用于记录小车试探性的下一步，如果下一步遇到obstacle，则不走这一步，留在原地
maxd = 0
for command in commands:
if command in [-1, -2]: #转向指令
direct = direct[::-1]
direct[command+2] = direct[command+2]*-1
else:
for step in range(command):
new_axis = [i+j for i,j in zip(axis,direct)]
if new_axis in obstacles: #如果前面有障碍物，就停止
break
axis = [i+j for i,j in zip(axis,direct)]
maxd = max(maxd, axis[0]**2 + axis[1] **2)
return maxd
不过以上代码太慢了，在Leecode上“超出时间限制”...
对obstacles做了一下 set, obstacles = set(map(tuple,obstacles)
就过了...
代码如下：
class Solution(object):
def robotSim0(self, commands):
'''
没有障碍物的版本，小车根据指令走，图上没有障碍物
'''
direct = [0,1] #初始方向
axis = [0,0] #小车初始坐标
for command in commands:
if command in [-1, -2]: #转向指令
direct = direct[::-1]
direct[command+2] = direct[command+2]*-1
continue
move = [i*command for i in direct]
axis = [i+j for i,j in zip(axis,move)]
return axis
def robotSim(self, commands, obstacles):
direct = [0,1] #初始方向
axis = [0,0] #小车初始坐标
new_axis = [] #用于记录小车试探性的下一步，如果下一步遇到obstacle，则不走这一步，留在原地
maxd = 0
obstacles = set(map(tuple,obstacles))
for command in commands:
if command in [-1, -2]: #转向指令
direct = direct[::-1]
direct[command+2] = direct[command+2]*-1
else:
for step in range(command):
# new_axis = [i+j for i,j in zip(axis,direct)]
new_axis = [axis[0]+direct[0], axis[1]+direct[1]]
if tuple(new_axis) in obstacles: #如果前面有障碍物，就停止
break
# axis = [i+j for i,j in zip(axis,direct)]
axis = new_axis
maxd = max(maxd, axis[0]**2 + axis[1] **2)
return maxd
def test_robotSim():
s = Solution()
assert s.robotSim([4,-1,3],[]) == 25
assert s.robotSim([4,-1,4,-2,4],[2,4]) == 65
if __name__ == '__main__':
s = Solution()
print(s.robotSim0([4,-1,3]))
print(s.robotSim([4,-1,3],[]))
print(s.robotSim0([4,-1,4,-2,4]))
print(s.robotSim([4,-1,4,-2,4],[[2,4]]))
print('*'*40)
commands = [1,2,-2,5,-1,-2,-1,8,3,-1,9,4,-2,3,2,4,3,9,2,-1,-1,-2,1,3,-2,4,1,4,-1,1,9,-1,-2,5,-1,5,5,-2,6,6,7,7,2,8,9,-1,7,4,6,9,9,9,-1,5,1,3,3,-1,5,9,7,4,8,-1,-2,1,3,2,9,3,-1,-2,8,8,7,5,-2,6,8,4,6,2,7,2,-1,7,-2,3,3,2,-2,6,9,8,1,-2,-1,1,4,7]
obstacles = [[-57,-58],[-72,91],[-55,35],[-20,29],[51,70],[-61,88],[-62,99],[52,17],[-75,-32],[91,-22],[54,33],[-45,-59],[47,-48],[53,-98],[-91,83],[81,12],[-34,-90],[-79,-82],[-15,-86],[-24,66],[-35,35],[3,31],[87,93],[2,-19],[87,-93],[24,-10],[84,-53],[86,87],[-88,-18],[-51,89],[96,66],[-77,-94],[-39,-1],[89,51],[-23,-72],[27,24],[53,-80],[52,-33],[32,4],[78,-55],[-25,18],[-23,47],[79,-5],[-23,-22],[14,-25],[-11,69],[63,36],[35,-99],[-24,82],[-29,-98],[-50,-70],[72,95],[80,80],[-68,-40],[65,70],[-92,78],[-45,-63],[1,34],[81,50],[14,91],[-77,-54],[13,-88],[24,37],[-12,59],[-48,-62],[57,-22],[-8,85],[48,71],[12,1],[-20,36],[-32,-14],[39,46],[-41,75],[13,-23],[98,10],[-88,64],[50,37],[-95,-32],[46,-91],[10,79],[-11,43],[-94,98],[79,42],[51,71],[4,-30],[2,74],[4,10],[61,98],[57,98],[46,43],[-16,72],[53,-69],[54,-96],[22,0],[-7,92],[-69,80],[68,-73],[-24,-92],[-21,82],[32,-1],[-6,16],[15,-29],[70,-66],[-85,80],[50,-3],[6,13],[-30,-98],[-30,59],[-67,40],[17,72],[79,82],[89,-100],[2,79],[-95,-46],[17,68],[-46,81],[-5,-57],[7,58],[-42,68],[19,-95],[-17,-76],[81,-86],[79,78],[-82,-67],[6,0],[35,-16],[98,83],[-81,100],[-11,46],[-21,-38],[-30,-41],[86,18],[-68,6],[80,75],[-96,-44],[-19,66],[21,84],[-56,-64],[39,-15],[0,45],[-81,-54],[-66,-93],[-4,2],[-42,-67],[-15,-33],[1,-32],[-74,-24],[7,18],[-62,84],[19,61],[39,79],[60,-98],[-76,45],[58,-98],[33,26],[-74,-95],[22,30],[-68,-62],[-59,4],[-62,35],[-78,80],[-82,54],[-42,81],[56,-15],[32,-19],[34,93],[57,-100],[-1,-87],[68,-26],[18,86],[-55,-19],[-68,-99],[-9,47],[24,94],[92,97],[5,67],[97,-71],[63,-57],[-52,-14],[-86,-78],[-17,92],[-61,-83],[-84,-10],[20,13],[-68,-47],[7,28],[66,89],[-41,-17],[-14,-46],[-72,-91],[4,52],[-17,-59],[-85,-46],[-94,-23],[-48,-3],[-64,-37],[2,26],[76,88],[-8,-46],[-19,-68]]
print(s.robotSim(commands, obstacles))
网友评论