小马智行 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)
#笔试题目##小马智行##秋招##笔经##Python##校招#
全部评论
第二题dp只过20%,超时了 第三题暴力60%
点赞 回复
分享
发布于 2019-09-18 22:33
如果我说第一题cout << -1就是百分之20😂
点赞 回复
分享
发布于 2019-09-18 23:27
英特尔
校招火热招聘中
官网直投
第一题和第四题看完我就知道我这两个小时是做不出来的 第二题90第三题90 哭了
点赞 回复
分享
发布于 2019-09-18 23:43
第三题维护双端队列可以a100,两个双端队列分别存最大和最小。就第二题70,第三题100……第二题有点暴力超时了尴尬……第一题和第四题就听天由命没做了……
点赞 回复
分享
发布于 2019-09-18 23:59
第三题dp也可以做,妥妥A
点赞 回复
分享
发布于 2019-09-19 00:45
第一题是这样的,首先对8个位置和起始位置分别运行bfs算法求出这9个位置之间的相互距离。之后求8个位置的全排列作为行动顺序,剔除其中不符合要求的顺序(办公室在对应钥匙前面的排列),根据之前求得的两两距离算出每种顺序的步数取最小即为答案
点赞 回复
分享
发布于 2019-09-19 01:06
第一题的那20%是无解输出-1的case😂
点赞 回复
分享
发布于 2019-09-19 15:59

相关推荐

头像
03-13 15:53
Java
点赞 评论 收藏
转发
头像
03-18 09:09
Java
点赞 评论 收藏
转发
点赞 18 评论
分享
牛客网
牛客企业服务