小馬智行 2019年9月18日不一定正確的題解

第一題寫完一運(yùn)行發(fā)現(xiàn)A20%，酒肉朋友同款瞪眼后發(fā)現(xiàn)可以回頭走。。吐血而亡。DFS沒時(shí)間改BFS了。 (直接輸出-1也是20%)

第一題，給一些鑰匙，一些門，走過鑰匙才能開門，最短路。DFS一定不行，感覺應(yīng)該是先判斷連通在BFS？

給一些實(shí)例，每個(gè)實(shí)例是一副地圖，有1234四把鑰匙，F(xiàn)ZYG四門，只有拿到了鑰匙才能進(jìn)對應(yīng)的門，給你起點(diǎn)，問能否找到一條路開開四扇門，有則輸出最短路徑長度，否則輸出-1

現(xiàn)在想想也沒那么難

#小馬復(fù)盤第一題：
#原題忘了，1234是鑰匙，F(xiàn)ZYG是門，有個(gè)起點(diǎn)x,y吧,#是障礙物不能走，只能先有鑰匙才能有對應(yīng)門。其他的忘了
#難點(diǎn)應(yīng)該是在可以回頭走，無解的情況不會寫，所以BFS不知道怎么做，當(dāng)時(shí)用DFS寫的，以為不能回頭，肯定錯(cuò)了
#后來看了別人寫的，明白了，可以回頭走，但那是在更新了狀態(tài)的情況下，依舊可以用visited+BFS
#自己造的示例，答案應(yīng)該是11。特別標(biāo)注了從~開始走
'''
3?3?5
#####
#123#
#4$$#
#$$~#
FZYG#
'''
#有思路是dfs或bfs走到兩兩之間的距離，再組合出所有情況或歸并排序出所有合法偏序狀態(tài)，直接+起來取最小
#通過觀察別人的題解找到另一種容易實(shí)現(xiàn)思路，就是把鑰匙和門的狀態(tài)當(dāng)成判斷visited的標(biāo)準(zhǔn)，就是點(diǎn)+鑰匙門狀態(tài)遍歷過了就不需要遍歷了
#原題輸出多個(gè)示例，這里只給出一個(gè)示例的解法
import?queue
#讀輸入，預(yù)設(shè)初值
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'，對應(yīng)無解情況，輸出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里可讀性更好一點(diǎn)
????????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了，動態(tài)規(guī)劃。

青蛙向前跳一格子或者跳到同色最近的格子。

做題的IDE里面有，直接拿過來了，秒A的題，基本所有人都過了

第一個(gè)賦值-1，后面的賦值前一個(gè)的坐標(biāo)

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])

第三題劃窗

給一些數(shù)據(jù)，窗長度，求窗內(nèi)取出最大最小值的最大均值。

秋招中頻題。見劍指offer

#小馬復(fù)盤第三題
#滑動窗口最大均值，要去去掉最大最小值，其實(shí)就是求和-最大-最小，找到最大的這個(gè)和，然后除以個(gè)數(shù)-2就可以
#輸入輸出忘了，但無所謂，假設(shè)長度N，窗長K，數(shù)據(jù)都是整數(shù)，輸出要求是小數(shù)那不用考慮保留幾位精度，好像是說差距很小就算對
'''
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)
????#讀數(shù)據(jù)
????res?=?[]
????for?i?in?range(K-1,M):
????????#更新deque
????????while?d?and?data[d[-1]]<data[i]:
????????????d.pop()
????????d.append(i)
????????#上一步一定會補(bǔ)充一個(gè)數(shù)字，假如上一步清空了d又補(bǔ)上了最新的，那么最新的index一定是i,這里i指的是滑窗右索引
????????#假如沒有，那么那說明新來的太小了，補(bǔ)在最后，但無論如何，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)取最大

第四題，沒最優(yōu)思路，DFS硬寫

放棋子，四周地雷指示數(shù)+1，超過雷限制剪枝，小于也應(yīng)該剪其實(shí)。

一個(gè)棋盤，黑白交錯(cuò)，黑色棋子是數(shù)字，白色棋子放雷，規(guī)則見掃雷。滿足數(shù)字的多少種防雷的方法。

一言以蔽之，給你掃雷游戲和數(shù)字問多少種合法地雷分布。

數(shù)據(jù)特點(diǎn)，從左上角開始，類似國際象棋棋盤，假設(shè)左上角是黑色，所有的黑色格子都標(biāo)了數(shù)字，所有白色是地雷。

應(yīng)該有更好的解法。

#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)

#筆試題目##小馬智行##秋招##筆經(jīng)##Python##校招#