-
标签：
贪心 -
难度：
简单
- 题目描述
- 解法1 ： 超时版本 1
收到 转向指令，则更新当前朝向；收到 移动指令 时，根据不同朝向调整位置坐标：首先判断 前方 最近障碍物的位置，如果最近距离大于移动指令给定的距离，则前进移动指令的距离，否则只能前进到最近障碍物的前一个网格方块上。
注意一个坑： 返回结果是执行指令过程中离原点的最大距离，而非执行完后终点位置离原点的距离。明确思路后，不难实现如下代码：
class Solution(object):
def robotSim(self, commands, obstacles):
"""
:type commands: List[int]
:type obstacles: List[List[int]]
:rtype: int
"""
orient = 'N'
p = [0,0]
result = 0
for i, c in enumerate(commands):
print('---------------------------------\n',i)
print('c=', c)
if(c == -2):
if(orient == 'N'):
orient = 'W'
elif(orient == 'E'):
orient = 'N'
elif(orient == 'S'):
orient = 'E'
else:
orient = 'S'
if(c == -1):
if(orient == 'N'):
orient = 'E'
elif(orient == 'E'):
orient = 'S'
elif(orient == 'S'):
orient = 'W'
else:
orient = 'N'
if(1<= c <=9):
if(orient == 'E'):
dis = [ob[0] - p[0] for ob in obstacles if ob[1] == p[1] and ob[0] > p[0] ]
if(not dis or min(dis) > c):
p[0] += c
print('orient:', orient)
print('p:',p[0],p[1])
else:
p[0] +=min(dis)-1
print('orient:', orient)
print('p:',p[0],p[1])
if(orient == 'W'):
dis = [p[0] - ob[0] for ob in obstacles if ob[1] == p[1] and ob[0] < p[0] ]
if(not dis or min(dis) > c):
p[0] -= c
print('orient:', orient)
print('p:',p[0],p[1])
else:
p[0] -= min(dis) -1
print('orient:', orient)
print('p:',p[0],p[1])
if(orient == 'N'):
dis = [ob[1] - p[1] for ob in obstacles if ob[0] == p[0] and ob[1] > p[1] ]
if(not dis or min(dis) > c):
p[1] += c
print('orient:', orient)
print('p:',p[0],p[1])
else:
p[1] += min(dis) -1
print('orient:', orient)
print('p:',p[0],p[1])
if(orient == 'S'):
dis = [p[1] - ob[1] for ob in obstacles if ob[0] == p[0] and ob[1] < p[1] ]
if(not dis or min(dis) > c):
p[1] -= c
print('orient:', orient)
print('p:',p[0],p[1])
else:
p[1] -= min(dis) -1
print('orient:', orient)
print('p:',p[0],p[1])
result = max(result,p[0]**2 + p[1]**2)
print('result:',result)
return result
- 解法2: 超时版本2
解法1 超时了， 判断超时主要由 判断前方最近障碍物 这一步造成的，这一步我有一个 遍历大数组 （即数组 obstacles）的操作。优化方法是：前进一步，查看当前位置是否存在障碍物，即 “走一步，看一步”“， 这是一个大数组查找的操作。可以通过下面的一个小例子来比较 python list 的遍历和查找的效率。
# list 的查找时间
in:
from time import time
a = 100 * np.random.rand(100000)
a[20] = 3
a = list(a)
start = time()
b = 3 in a
elapsed = (time() - start)
print("Time used:",elapsed)
out： Time used: 8.153915405273438e-05
# list 的遍历时间
in:
from time import time
a = 100 * np.random.rand(100000)
a[20] = 3
a = list(a)
start = time()
b = [i for i in a if i >2]
elapsed = (time() - start)
print("Time used:",elapsed)
out: Time used: 0.02106785774230957
class Solution(object):
def robotSim(self, commands, obstacles):
"""
:type commands: List[int]
:type obstacles: List[List[int]]
:rtype: int
"""
orient = 'N'
p = [0,0]
result = 0
start = time()
for i, c in enumerate(commands):
if(c == -2):
if(orient == 'N'):
orient = 'W'
elif(orient == 'E'):
orient = 'N'
elif(orient == 'S'):
orient = 'E'
else:
orient = 'S'
if(c == -1):
if(orient == 'N'):
orient = 'E'
elif(orient == 'E'):
orient = 'S'
elif(orient == 'S'):
orient = 'W'
else:
orient = 'N'
if(1<= c <=9):
if(orient == 'E'):
move = c
while(move>0):
next_p = [p[0] + 1, p[1]]
if next_p not in obstacles:
p = next_p
move -= 1
else:
break
if(orient == 'W'):
move = c
while(move>0):
next_p = [p[0] - 1, p[1]]
if next_p not in obstacles:
p = next_p
move -= 1
else:
break
if(orient == 'N'):
move = c
while(move>0):
next_p = [p[0], p[1] + 1]
if next_p not in obstacles:
p = next_p
move -= 1
else:
break
if(orient == 'S'):
move = c
while(move>0):
next_p = [p[0], p[1] - 1]
if next_p not in obstacles:
p = next_p
move -= 1
else:
break
result = max(result,p[0]**2 + p[1]**2)
elapsed = (time() - start)
print("Time used:",elapsed)
return result
- 解法3 ：AC 版本
很遗憾，解法 2 也超时了，无法从算法角度进行进一步优化了。只能去看看 discussion, 发现 Python 中 不同数据结构的查找效率具有显著差异，可以通过 【CSDN: Python 中list ,set,dict的大规模查找效率】 中的一个例子获得直观感受, 查找效率对比： set>dict>list
in:
import numpy
import time
l=[]
sl=set()
dl=dict()
r=numpy.random.randint(0,10000000,100000)
for i in range(0,100000):
l.append(r[i])
sl.add(r[i])
dl.setdefault(r[i],1)
#生成3种数据结构供查找，常规的list,集合sl,字典dl.里面的元素都是随机生成的，
#为什么要随机生成元素？这是防止某些结构对有序数据的偏向导致测试效果不客观。
start=time.clock()
for i in range(100000):
t=i in sl
end=time.clock()
print("set:",end-start)
#计算通过set来查找的效率
start=time.clock()
for i in range(100000):
t=i in dl
end=time.clock()
print("dict:",end-start)
#计算通过dict的效率
start=time.clock()
for i in range(100000):
t=i in l
end=time.clock()
print('list:', end-start) # 时间过长（>10 min ）
out:
set: 0.008858999999972639
dict: 0.011525000000006003
---------------------------------------------------------------------------
KeyboardInterrupt Traceback (most recent call last)
<ipython-input-25-f68b2e8e02d4> in <module>()
27 start=time.clock()
28 for i in range(100000):
---> 29 t=i in l
30 end=time.clock()
31 print('list:', end-start) # 时间过长（>10 min ）
KeyboardInterrupt:
class Solution(object):
def robotSim(self, commands, obstacles):
"""
:type commands: List[int]
:type obstacles: List[List[int]]
:rtype: int
"""
orient = 'N'
p = [0,0]
result = 0
obstacles = set(map(tuple, obstacles))
start = time()
for i, c in enumerate(commands):
if(c == -2):
if(orient == 'N'):
orient = 'W'
elif(orient == 'E'):
orient = 'N'
elif(orient == 'S'):
orient = 'E'
else:
orient = 'S'
if(c == -1):
if(orient == 'N'):
orient = 'E'
elif(orient == 'E'):
orient = 'S'
elif(orient == 'S'):
orient = 'W'
else:
orient = 'N'
if(1<= c <=9):
if(orient == 'E'):
move = c
while(move>0):
next_p = (p[0] + 1, p[1])
if next_p not in obstacles:
p = next_p
move -= 1
else:
break
if(orient == 'W'):
move = c
while(move>0):
next_p = (p[0] - 1, p[1])
if next_p not in obstacles:
p = next_p
move -= 1
else:
break
if(orient == 'N'):
move = c
while(move>0):
next_p = (p[0], p[1] + 1)
if next_p not in obstacles:
p = next_p
move -= 1
else:
break
if(orient == 'S'):
move = c
while(move>0):
next_p = (p[0], p[1] - 1)
if next_p not in obstacles:
p = next_p
move -= 1
else:
break
result = max(result,p[0]**2 + p[1]**2)
elapsed = (time() - start)
print("Time used:",elapsed)
return result
- 其他解法*
暂略。
网友评论