首页 > 便利蜂3月20日暑期实习算法笔经
头像
张麻子不是张牧之
编辑于 2021-04-07 20:03
+ 关注

便利蜂3月20日暑期实习算法笔经

  1. 给定一组词组,每个词组包含id和字符串的映射,现输入另一组词组,要求找出新的词组与老的词组的diff关系,diff要求如下: 1、id相同且字符串相同的两个词组视为相同 2、id相同,且字符串不同的输出modify+id 3、新的词组id在老的词组id中不存在的,视为新增,输出add+id 4、老的词组id在新的词组id中不存在的,视为删除,输出delete+id 第一行代表老的词组,第二行代表新的词组 每一行是id-字符串的组合,多个词组以逗号分隔 如:1-a,2-b,3-c 一个字符串,多个结果按字符串排序后(直接使用string的compareTo方法比较大小即可)以逗号分隔,如:add-2,delete-2
    通过82%
  2. 在便利店中顾客的结账时间是很重要的指标。结账时间由排队等待时间,和顾客操作付款时间两部分组成。程序输入为顾客列表 customers,每一位顾客 customer[i] 包含两个数值 arriveTime, payDuration。arriveTime 表示顾客挑选完商品去结账的时刻;payDuration 表示顾客操作付款的时间。请计算所有顾客的总结账时间。
  3. 假设有一个矩阵,矩阵由 0 和 1 数字组成。其中1代表这个节点可达,0代表这个节点不可达,从左上角第一个节点出发到右下角最后一个节点,只能上下左右移动,初始节点数为 1,移动一步节点数加 1,问最少需要经过多少节点可以达到。请实现计算最短路径的函数。如果不可达返回0。

我的答案:

  1. 通过82%
    ans=''
    a=input()
    if len(a)>0:
     old = [_.split('-') for _ in a.split(',')]
     old_d = {}
     for i in range(0, len(old)):
         old_d[old[i][0]] = old[i][1]
    else:
     old=[]
     old_d={}
    b=input()
    modified = []
    if len(b)>0:
     new = [_.split('-') for _ in b.split(',')]
     ans = ''
     for i in range(0, len(new)):
         if new[i][0] in old_d and new[i][0] not in modified:
             if old_d[new[i][0]]!=new[i][1]:
                 ans = ans+'modify-'+new[i][0]+','
                 modified.append(new[i][0])
             del old_d[new[i][0]]
         elif new[i][0] not in modified:
             ans = ans + 'add-' + new[i] [0]+ ','
    for i,c in old_d.items():
     ans = ans + 'delete-' + i + ','
    print(ans[:-1])
  2. 通过73%
    n = int(input())
    l = []
    for i in range(n):
     l.append(list(map(float,input().split(','))))
    l.sort(key=lambda x: x[0])
    t=0
    ans=0
    if n>0: t=l[0][0]
    for c in l:
     ans+=(max(t-c[0],0)+c[1])
     t+=c[1]
    print(ans)
  3. AC
    array = [list(map(int,row.split(','))) for row in input().split(';')]
    n_rows = len(array)
    n_cols = len(array[0]) if n_rows>0 else 0
    ans = 2**31-1
    visited = [[False]*n_cols for i in range(n_rows)]
    def dfs(i,j, length):
     global ans
     if i==n_rows-1 and j==n_cols-1:
         ans = min(ans, length)
     if i>0 and not visited[i-1][j] and array[i-1][j]==1:
         visited[i-1][j]=True
         dfs(i-1,j,length+1)
         visited[i - 1][j] = False
     if i+1<n_rows and not visited[i+1][j] and array[i+1][j]==1:
         visited[i+1][j]=True
         dfs(i+1,j,length+1)
         visited[i + 1][j] = False
     if j>0 and not visited[i][j-1] and array[i][j-1]==1:
         visited[i][j-1]=True
         dfs(i,j-1,length+1)
         visited[i][j-1] = False
     if j+1<n_cols and not visited[i][j+1] and array[i][j+1]==1:
         visited[i][j+1]=True
         dfs(i,j+1,length+1)
         visited[i][j+1] = False
    visited[0][0]=True
    dfs(0,0,1)
    if ans==2**31-1:
     print(0)
    else: print(ans)

全部评论

(4) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐