便利蜂2020春招在线考试 4.10 参考代码
3个算法题, 3AC, 职位是JAVA开发工程师
第一题
leetcode 53 Maximum subarray problem , 算法导论第四章
我就贴我笔记里的, 我自己交的没存
algo
time O(n) space O(1)
n表示数组长度
DP(具有最优化子结构), 可用数学归纳法证明 , 考虑以num[i],0<=i<n结尾的所有子串
code
class Solution: def maxSubArray(self, nums: List[int]) -> int: cur=nums[0] ans=cur for i in range(1,len(nums)):# 每次只考虑nums的前i+1个数 # 这一行, cur存着以nums[i-1]结尾的子串的和的最大值 if cur>0: cur+=nums[i] else: cur=nums[i] ans=max(ans,cur) return ans
第二题
描述
给了一个无向图, 无向图的边还有两种名字, 需要手动创建这个无向图,
再给一个起点和终点, 找出起点到终点的最短路径,
code
import queue
# bfs with path
mp={}
dirname_mp = {1:"north",-1:"south",2:"east",-2:"west"}
# d
# north 1
# south -1
# east 2
# west -2
# d of s1 is s2
def union(s1,s2,d):
con(s1,s2,d)
con(s2,s1,-d)
def con(s1,s2,d):
if s1 not in mp :
mp[s1]={d:s2}
else:
mp[s1][d]=s2
union("DAOTIAN1", "TULU1",-1)
union("DAOTIAN", "TULU1",1)
union("TULU2", "TULU1",-2)
union("DAOTIAN", "TULU",-1)
union("CUNKOU", "TULU",1)
union("CUNKOU", "NONGSHE",2)
# TULU2 right part
union("TULU2", "JIEDAO",2)
union("LIUJIABUDI", "JIEDAO",-1)
union("JIEDAO", "TIEPU",-1)
union("JIEDAO1", "JIEDAO",-2)
union("JIEDAO1", "XIAOJIUGUAN",-1)
union("JIEDAO1", "GAOJIADAYUAN",2)
union("JIEDAO2", "GAOJIADAYUAN",-2)
union("TULU3", "JIEDAO2",-2)
union("QINGSHILU", "TULU3",-2)
union("PIANFANG", "ZHENGYUAN",-2)
union("FANTING", "ZHENGTING",-2)
union("XIYIFANG", "HOUYUAN",-2)
union("HOUYUAN", "GUIGE",-2)
union("ZHENGTING", "PIANTING",-2)
union("ZHENGYUAN", "ZHANGFANG",-2)
union("ZHENGYUAN", "GAOJIADAYUAN",-1)
union("ZHENGYUAN", "ZHENGTING",1)
union("ZHENGTING", "HOUYUAN",1)
union("HOUYUAN","HUAYUAN",1)
union("YASHI","GUIGE",-1)
q = queue.Queue()
sta,end= input().split(",")
class Step:
def __init__(self, name, prev=None):
self.name = name
self.prev = prev
q.put(Step(sta))
def popAll(q):
while not q.empty():
yield q.get()
def back_print(step):
buf = []
while step.prev!=None:
for d in [1,-1,2,-2]:
if d in mp[step.prev.name] and mp[step.prev.name][d]==step.name:
break
buf.append(dirname_mp[d])
step = step.prev
print(",".join(reversed(buf)))
covered = {sta}
while not q.empty():
for cur_step in list(popAll(q)):
for nxt_name in mp[cur_step.name].values():
if nxt_name==end:
back_print(Step(nxt_name, cur_step))
break
if nxt_name not in covered:
q.put(Step(nxt_name, cur_step))
covered.add(nxt_name) 第三题
描述
给一个数组, 例如[1,4,1,1,2,0,5], 记作arr,
一开始在位置为0的商店上, 开着arr[0]油量的车子
每个元素的索引代表一个商店的位置, 每到一个位置为i的商店可以选择 换一个油量为arr[i]车子, 之前那个车子舍弃, 或者保持原来的车子
数组长度记作n
输出 从位置为0的商店到位置为n-1的商店 使用车子数量的最小值, 如果到达不了输出-1
algo
time:O(n*n) space:O(n)
本质上还是一个二维dp, 只不过可以节省成一维dp
我用dp2[cnt][j]表示用 最多cnt辆车, 到达j位置商店, 最多能有多少油
code
def main():
arr = list(map(lambda x:int(x), input().split(',')))
n = len(arr)
if n<=1: return 0
dp = [0]*n
cnt=1
dp[0]=arr[0]
for i in range(1,n):
dp[i] = dp[i-1] - 1
while cnt<=n:
for i in range(cnt-1, n):
# dp[i] 未赋新值前存着dp2[cnt][i]
if i==n-1 and dp[i]>=0:
print(cnt)
return
# 只靠cnt辆车能否到达位置为i的商店, 并换乘到这辆车
if dp[i]>=0:
dp[i]=max(arr[i],dp[i])
else:
pass
# 这个地方逻辑比较复杂, 可以按dp[i]是否>=0分类讨论
if i!=cnt-1:
# dp[i-1] 存着 dp2[cnt+1][i-1]
dp[i]=max(dp[i],dp[i-1]-1)
cnt+=1
print(-1)
main() 
阿里云二面53人在聊