欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

字节跳动2019春招第二次笔试编程题

程序员文章站 2022-06-09 11:09:35
...

个人主页:http://redtongue.cn or https://redtongue.github.io/

1.变身程序员

题目描述

公司的程序员不够用了,决定把产品经理都转变为程序员以解决开发时间长的问题。

在给定的矩形网格中,每个单元格都可以用以下三个值之一:

  • 值0代表空单元格

  • 值1代表产品经理

  • 值2代表程序员

每分钟,任何与程序员(在四个正方向上)相邻的产品经理都会变成程序员。
返回知道单元格中没有产品经理为止所必须经过的最小分钟数。
如果没有可能,返回-1.

输入描述

不固定多行(行数<=10),每行是按照空格分割的数字(不固定,每行数字个数<=10)
其中每个数组项的取值仅为0,1,2三种
(读取时可以按行读取,知道读取到空行为止,再对读取的所有行做转换处理)

输出描述

如果能够将所有的产品经理变为程序员,则输出最小的分钟数
如果不能够将所有的产品经理变为程序员,则返回-1

示例

示例1

输入:
0 2
1 0
输出:
-1

示例2

输入:
1 2 1
1 1 0
0 1 1
输出:
3

示例3

输入:
1 2
2 1
1 2
0 1
0 1
1 1
输出:
4

分析

  • 深度优先搜索,区别在每一次(每分钟)只会将程序员周围的产品经理变为程序员,不会迭代下去
  • manage记录产品经理的个数,若每一个传播之后,manage不再变化,停止;
  • 若manage=0返回传播时间,反之返回-1。

参考代码

import sys
if __name__ == "__main__":
    def get(A):
        s=0
        for a in A:
            for x in a:
                if(x==1):
                    s+=1
        return s
    lines = sys.stdin.readlines()
    a=[]
    for line in lines:
        a.append(list(map(int,line.split())))
    s=0
    print("a",a)
    manage=get(a)
    row=len(a)
    col=len(a[0])
    
    def dfs(x,y):
        if(x-1>=0 and a[x-1][y]==1):
            a[x-1][y]=2
        if(x+1<row and a[x+1][y]==1):
            a[x+1][y]=2
        if(y-1>=0 and a[x][y-1]==1):
            a[x][y-1]=2
        if(y+1<col and a[x][y+1]==1):
            a[x][y+1]=2
        return
          
    while(manage>0):
        li=[]
        for i in range(row):
            for j in range(col):
                if(a[i][j]==2):
                    li.append((i,j))
        for l in li:
            dfs(l[0],l[1])
        nmanage=get(a)
        print(a)
        s+=1
        if(manage==nmanage):
            break
        manage=nmanage
    if(manage==0):
        print(s)
    else:
        print('-1')

2.特征提取

题目描述

小明是一个算法工程师,同时也是一名铲屎官。某天,他突发奇想,想从猫咪的视频里挖掘一些猫咪的运动信息。为了提取运动信息,他需要从视频的每一帧提取“猫咪特征”。一个猫咪特征是一个两维的vector<x,y>。如果x_1=x_2 and y_1=y_2,那么这俩是同一个特征。

因此,如果猫咪特征连续一致,可以认为猫咪在运动。也就是说,如果特征<a,b>在持续帧里出现,那么它将构成特征运动。比如,特征<a,b>在第2/3/4/7/8帧出现,那么该特征形成两个特征运动2-3-4和7-8.

输入描述

第一行包含一个正整数N,代表测试用例的个数
每个测试用例的第一行包含一个正整数M,代表视频的帧数
接下来M行,每一行代表一帧,其中,第一个数字是该帧的特征个数,接下来的数字是在特征的取值:比如样例输入第三行里,2表示该帧有两个猫咪特征,<1,1>和<2,2>。所有用例的输入特征总数和<=100000
N满足1<=N<=100000,M满足1<=M<=100000,一帧的特征个数满足<=100000.特征取值均为非负整数

输出描述

对于每一个测试用例,输出特征运动的长度作为一行

示例

示例1

输入:
1
8
2 1 1 2 2
2 1 1 1 4
2 1 1 2 2
2 2 2 1 4
0
0
1 1 1
1 1 1
输出:
3

备注

如果没有长度大于2的特征运动,返回1

分析

  • 用字典存储每个特征出现的次数,ans记录特征出现的最大次数,初始为0
  • 遍历每一帧的特征,若字典中存在该特征,则次数加一,反正说明该特征断了,次数置为1,更新ans
  • 返回ans

参考代码

if __name__ == "__main__":
    N=int(input())
    for n in range(N):
        M=int(input())
        d={}
        ans=1
        for m in range(M):
            li=list(map(int,input().split()))
            s=li[0]
            newd={}
            for i in range(s):
                ind=(li[i*2+1],li[i*2+2])
                if(ind in d):
                    newd[ind]=d[ind]+1
                else:
                    newd[ind]=+1
            for nd in newd:
                ans=max(ans,newd[nd])
            d=newd
        print(ans)

3.机器人跳跃问题

题目描述

机器人正在玩一个古老的基于DOS的游戏。游戏中有N+1座建筑----从0到N编号,从左到右排列。编号为0的建筑高度为0个单位,编号为i的建筑的高度为H(i)个单位。

起初,机器人在编号为0的建筑处。每一步,它跳到下一个(右边)建筑。假设机器人在第k个建筑,且它现在的能量值是E,下一步它将跳到第k+1建筑。他将会得到或者失去正比于H(K+1)和E之差的能量。如果H(k+1)>E那么机器人就失去H(K+1)-E的能量值,反之它将得到E-H(K+1)的能量值

游戏目标是到达第N个建筑,在这个过程中,能量值不能为负。现在的问题是机器人以多少能量值开始游戏,才可以保证完成游戏

输入描述

第一行输入,表示一共有N组数据
第二个是N个空格分割的整数,H1,H2,H3,...,Hn代表建筑的高度

输出描述

输出一个单独的数表示完成游戏所需的最小单位的初始能量

示例

示例1

输入:
5
3 4 3 2 4
输出:
4

示例2

输入:
3
4 4 4
输出:
4

示例3

输入:
3
1 6 4
输出:
3

备注

数据约束:
1<=N<=10^5
1<=H(i)<=10^5

分析

  • 用二分查找来找到最小能量值,start=0,end=max(H),高度小于能量值时,能量只增不减,座椅最大值为max(H);
  • 遍历建筑物,更新E值,若中间E小于0,则更新start=mid+1;
  • 反之end=mid;
  • 最后返回end。

参考代码

if __name__ == "__main__":
    N=int(input())
    H=list(map(int,input().split()))
    start=0
    end=max(H)
    while(start<end):
        mid=(start+end)//2
        E=mid
        judge=True
        for h in H:
            if(E < h):
                E-=(h-E)
            else:
                E+=(E-h)
            if(E < 0):
                start=mid+1
                judge=False
                break
        if(judge):
            end=mid
    print(end)

4.毕业旅行问题

题目描述

小明目前在做一份毕业旅行的规划。打算从北京出发,分别去若干个城市,然后再回到北京,每个城市之间均乘坐高铁,且每个城市只去以此。由于经费有限,希望能够通过合理的路线安排尽可能的省一些路上的开销。给定一组城市和每对城市之间的火车票的价钱,找到每个城市只访问一次并返回起点的最小花销。

输入描述

城市个数n(1<=n<=20,包括北京)
城市间的车票价钱,n行n列的矩阵m[n][n]

输出描述

最小花销s

示例

示例1

输入:
4
0 2 6 5
2 0 4 4
6 4 0 2
5 4 2 0
输出:
13
说明:
共四个城市,城市1与城市1的车费是0,城市1和城市2的车费是2,以此类推,无需考虑极端情况。

分析

  • 遍历所有城市,得到每个状态下的最小车费,s是车费,past记录已遍历的城市包含的车票,形如<a,b>是指从a城市到b城市,初始为{(0,0)},只包含一个城市,车费为0;

  • 遍历,新增加一个城市i,遍历所有的车票<a,b>,使得<i,a>+<i,b>-<a,b>最小,即遍历当前城市最小的花费;

  • 更新past和s;

  • 遍历完,返回s。

参考代码

if __name__ == "__main__":
    n=int(input())
    m=[]
    for i in range(n):
        m.append(list(map(int,input().split())))
    s=0
    past=set()
    past.add((0,0))
    for i in range(1,n):
        a,b=0,0
        cost=m[i][a]+m[i][b]
        for p in past:
            c=m[p[0]][i]+m[p[1]][i]-m[p[0]][p[1]]
            if(c < cost):
                a=p[0]
                b=p[1]
                cost=c
        s+=cost
        past.remove((a,b))
        past.add((a,i))
        past.add((i,a))
    print(s)

4.过河问题

题目描述

将所有人送到河对面,每次只能做2或3个人,且时间是船上人过河时间的最大值。

输入描述

第一行是整数m,表示测试样例格式
每个测试样例的第一行是一个正整数n,表示参加过河的人数;(2<=n<100000)
第二行是n个正整数a[i](0<a[i]<100000),表示n个人的单独过河时间

输出描述

每个测试样例,输出应该准备的最少过河时间。

示例

示例1

输入:
2
2
1 2
4
1 1 1 1
输出:
2
3

分析

  • 用贪心算法来解,分为五种情况,time记录耗时:

  • 1人数大于等于7时,按耗时排序得(a,b,c,d,***,m3,m2,m1),先将最耗时的三人送过去,三个同时过去耗时(2d+c+b+m1),先送过去两个,再送过去一个,耗时(2c+2b+m1+m3),逐个送过去,耗时(3b+m1+m2+m3),耗时为三种情况的最小值;

  • 2人数大于等于6时,按耗时排序得(a,b,c,***,m3,m2,m1),先将最耗时的三人送过去,三个同时过去耗时(2m3+c+b+m1),先送过去两个,再送过去一个,耗时(2c+2b+m1+m3),逐个送过去,耗时(3b+m1+m2+m3),耗时为三种情况的最小值;

  • 3人数等于五个人时,按耗时排序得(a,b,c,d,e),最大两个先过去后面三个再过去,耗时(e+3c+b),逐个过去,耗时(e+d+c+2b);

  • 4人数等于四个人时,按耗时排序得(a,b,c,d),耗时(b+c+d);

  • 5人数等与三或二个人时,耗时最大耗时值;

  • 返回time。

参考代码

if __name__ == "__main__":
    N=int(input())
    for i in range(N):
        n=int(input())
        a=list(map(int,input().split()))
        a.sort()
        time=0
        start=0
        end=n-1
        while(end-start+1>=7):
            p1=a[end]+a[start+1]*2+a[start+2]+a[start+3]*2#过两个小的,再将三个最大的一起过去
            p2=a[end]+a[end-2]+a[start+1]*2+a[start+2]*2#过一个小的,将两个最大的过去,再过去一个大的
            p3=a[end]+a[end-1]+a[end-2]+a[start+1]*3#逐个过最大的
            time+=min(p1,p2,p3)
            end-=3
        while(end-start+1>=6):
            p1=a[end]+a[start+1]*2+a[start+2]+a[start+3]*2
            p2=a[end]+a[end-2]+a[start+1]*2+a[start+2]*2
            p3=a[end]+a[end-1]+a[end-2]+a[start+1]*3
            time+=min(p1,p2,p3)
            end-=3
        if(end-start+1==5):
            p4=a[end]+a[start+1]+a[start+2]*3
            p5=a[start+1]*2+a[start+2]+a[start+3]+a[start+4]
            time+=min(p4,p5)
            end=-1
        if(end-start+1==4):
            time+=sum(a[start+1:end+1])
            end=-1
        if(end-start+1>=2):
            time+=max(a[start:end+1])
        print(time)
相关标签: 笔试