小马智行 2019年9月18日 不一定正确的题解
第一题写完一运行发现A20%，酒肉朋友同款瞪眼后发现可以回头走。。吐血而亡。DFS没时间改BFS了。 (直接输出-1也是20%)
第一题，给一些钥匙，一些门，走过钥匙才能开门，最短路。DFS一定不行，感觉应该是先判断连通在BFS？
#
给一些实例，每个实例是一副地图，有1234四把钥匙，FZYG四门，只有拿到了钥匙才能进对应的门，给你起点，问能否找到一条路开开四扇门，有则输出最短路径长度，否则输出-1
现在想想也没那么难
#小马复盘第一题：
#原题忘了，1234是钥匙，FZYG是门，有个起点x,y吧,#是障碍物不能走，只能先有钥匙才能有对应门。其他的忘了
#难点应该是在可以回头走，无解的情况不会写，所以BFS不知道怎么做，当时用DFS写的，以为不能回头，肯定错了
#后来看了别人写的，明白了，可以回头走，但那是在更新了状态的情况下，依旧可以用visited+BFS
#自己造的示例，答案应该是11。特别标注了从~开始走
'''
3 3 5
#####
#123#
#4$$#
#$$~#
FZYG#
'''
#有思路是dfs或bfs走到两两之间的距离，再组合出所有情况或归并排序出所有合法偏序状态，直接+起来取最小
#通过观察别人的题解找到另一种容易实现思路，就是把钥匙和门的状态当成判断visited的标准，就是点+钥匙门状态遍历过了就不需要遍历了
#原题输出多个示例，这里只给出一个示例的解法
import queue
#读输入，预设初值
visited = set()
f = open('input/input_xiaoma1.txt','r')
a = list(map(int,f.readline().strip().split()))
st,en,rows=a[0],a[1],a[2]
data = []
for _ in range(rows):
data.append(list(f.readline().strip()))
f.close()
#data[1][1]='2'，对应无解情况，输出4557430888798830399原问题输出-1，都一样
dic = {'1':1,'2':2,'3':4,'4':8,'F':16,'Z':32,'Y':64,'G':128}
direction = [(0,1),(0,-1),(1,0),(-1,0)]
visited_all = 255
cur_steps = 0
cur_visit = 0
cur = (st,en,cur_visit,cur_steps)
visited.add((st,en,cur_visit))
#
q=queue.Queue()
q.put(cur)
res = 0x3f3f3f3f3f3f3f3f
while(q.empty()==False):
cur = q.get()
cur_x,cur_y,cur_visit,cur_steps=cur[0],cur[1],cur[2],cur[3]
#print(cur_x,cur_y,cur_visit,cur_steps)
#跳出判断
if cur_visit==visited_all:
res = cur_steps
break
#方向更改
for i in range(4):
next_x,next_y,next_steps=cur_x+direction[i][0],cur_y+direction[i][1],cur_steps+1
#超出地图边界或者障碍物
if next_x<0 or next_x>=rows or next_y<0 or next_y>=rows:
continue
if data[next_x][next_y]=='#':
continue
#正常无门无钥匙路段
if data[next_x][next_y] not in dic.keys():
#if data[next_x][next_y]=='&':
next_visit = cur_visit
if (next_x,next_y,next_visit) not in visited:
#没走过这格子，走一下
visited.add((next_x,next_y,next_visit))
q.put((next_x,next_y,next_visit,next_steps))
continue
else:
continue
#有门有钥匙路段
#写else里可读性更好一点
else:
next_visit = cur_visit | dic[data[next_x][next_y]]
if (next_x,next_y,next_visit) in visited:
continue
#如果是门，要判断钥匙走过了,没走过跳出
if dic[data[next_x][next_y]]>=16 and (dic[data[next_x][next_y]]//16) & cur_visit == 0:
continue
#next_visit = cur_visit + dic[data[next_x][next_y]]
#print(next_x,next_visit,next_x)
visited.add((next_x,next_y,next_visit))
q.put((next_x,next_y,next_visit,next_steps))
continue
print(res)
代码输出为11，更多的没试
青蛙跳格子
第二题看到的第一眼就知道这题A了，动态规划。
青蛙向前跳一格子或者跳到同色最近的格子。
#
做题的IDE里面有，直接拿过来了，秒A的题，基本所有人都过了
第一个赋值-1，后面的赋值前一个的坐标
n = int(input())
data = [int(x) for x in input().split()]
dic = {}
pre_index = [-1 for _ in range(len(data))]
for index,i in enumerate(data):
if i not in dic.keys():
dic[i]=index
pre_index[index]=-1
else:
pre_index[index]=dic[i]
dic[i]=index
#print(dic)
#print(pre_index)
dp = [0]*(len(data))
for index in range(1,len(data)):
dp[index] = 1+dp[index-1]
if pre_index[index]!=-1:
dp[index]=min(dp[index],1+dp[pre_index[index]])
print(dp[-1]) 第三题划窗
给一些数据，窗长度，求窗内取出最大最小值的最大均值。
秋招中频题。见剑指offer
#
#小马复盘第三题
#滑动窗口最大均值，要去去掉最大最小值，其实就是求和-最大-最小，找到最大的这个和，然后除以个数-2就可以
#输入输出忘了，但无所谓，假设长度N，窗长K，数据都是整数，输出要求是小数那不用考虑保留几位精度，好像是说差距很小就算对
'''
10 4
10 1 9 2 8 3 7 4 6 5
'''
f = open('input/input_xiaoma3.txt','r')
a = [int(x) for x in f.readline().strip().split()]
M,K=a[0],a[1]
data = list(map(int,f.readline().strip().split()))
f.close()
from collections import deque
#初始化滑动窗口最大值
def get_max(data,M,K):
cur_data = data[:]
#初始化
d = deque()
for i in range(K):
if not d:
d.append(i)
continue
#注意是小于等于
while d and data[d[-1]]<=data[i]:
d.pop()
d.append(i)
#读数据
res = []
for i in range(K-1,M):
#更新deque
while d and data[d[-1]]<data[i]:
d.pop()
d.append(i)
#上一步一定会补充一个数字，假如上一步清空了d又补上了最新的，那么最新的index一定是i,这里i指的是滑窗右索引
#假如没有，那么那说明新来的太小了，补在最后，但无论如何，deque的左端弹出一定不会是的deque为空
if d[0]<=i-K:
d.popleft()
res.append(data[d[0]])
return res
def get_min(data,M,K):
cur_data = [-i for i in data]
res = [-i for i in get_max(cur_data,M,K)]
return res
def get_sum(data,M,K):
cur_sum = sum(data[:K])
res = [cur_sum]
for i in range(K,M):
cur_sum+=(data[i]-data[i-K])
res.append(cur_sum)
return res
data_max = get_max(data,M,K)
data_min = get_min(data,M,K)
data_sum = get_sum(data,M,K)
#
print(data_max)
print(data_min)
print(data_sum)
输出为
[10, 9, 9, 8, 8, 7, 7]
[1, 1, 2, 2, 2, 3, 4]
[22, 20, 22, 20, 22, 20, 22]
剩下的就简单了，遍历一次即可，(sum-max-min)/(K-2)取最大 第四题，没最优思路，DFS硬写
放棋子，四周地雷指示数+1，超过雷限制剪枝，小于也应该剪其实。
#
一个棋盘，黑白交错，黑色棋子是数字，白色棋子放雷，规则见扫雷。满足数字的多少种防雷的方法。
一言以蔽之，给你扫雷游戏和数字问多少种合法地雷分布。
数据特点，从左上角开始，类似国际象棋棋盘，假设左上角是黑色，所有的黑色格子都标了数字，所有白色是地雷。
应该有更好的解法。
#t = int(input()) def mm(data): if data=='?': return -1 else: return int(data) ccc = 0 def dfs(data,res,cur_x,cur_y): global ccc if(cur_x >= n and cur_y>=n): ccc+=1 for i in range(1,n+1): for j in range(1,n+1): if (i+j)%2==0 and data[i][j]!=res[i][j]: ccc-=1 return None #print(res) x = cur_x y = cur_y+1 if y>n: y=1 x+=1 if x>=n+1: #dfs(data,res,x,y) return None if (x+y)%2==0: dfs(data,res,x,y) else: dfs(data,res,x,y) if res[x-1][y]>=data[x-1][y] or res[x+1][y]>=data[x+1][y] or res[x][y-1]>=data[x][y-1] or res[x][y+1]>=data[x][y+1]: return None else: res[x-1][y]+=1 res[x+1][y]+=1 res[x][y-1]+=1 res[x][y+1]+=1 dfs(data,res,x,y) res[x-1][y]-=1 res[x+1][y]-=1 res[x][y-1]-=1 res[x][y+1]-=1 for _ in range(1): #n = int(input()) n = 3 data = [[10,10,10,10,10],[10,1,-1,1,10],[10,-1,2,-1,10],[10,1,-1,1,10],[10,10,10,10,10]] #data = [[10 for _ in range(n+2)]] #for _ in range(n): #tmp = list(map(mm,list(input()))) #data.append([10]+tmp+[10]) data.append([10 for _ in range(n+2)]) #print(data) res = [[0 for _ in range(n+2)] for _ in range(n+2)] ccc = 0 dfs(data,res,1,1) print(ccc)
学而思公司福利 372人发布
，其实说实话，点评真别写，给面试官印象很不好，你去随便找个差不多类型的写一下，也就一周就能搞完，大厂实习最重要的还是算法
查看15道真题和解析