记2019春招笔试算法题(二)

前言

没啥好说的,感觉自己是个菜逼。

卧槽,就做上两个半,还有一个是brute force,居然过了,我害怕了!

4.14 字节跳动 后台开发

  1. 某公司程序员不够了,现在要把所有的产品经理发展为程序员。每一天,一个程序员可以把他上下左右相邻的产品经理发展为程序员。第二天,这些程序员可以继续发展其他人。求把所有员工都发展为程序员所需的天数。
    说明:矩阵中,产品经理表示为1,程序员表示为2,空白区域表示为0。相邻区域是指二维矩阵的上下左右相邻区域。如果无法把所有员工发展为程序员,则输出-1。
    输入:每一行表示二维矩阵的一行数值。
    输出:一个数字,表示这个天数。

输入样例#1:

0 1 2
1 1 1
1 0 2

输出样例#1:

4

输入样例#2:

1 1
1 0
0 1
2 1
0 1
1 2

输出样例#2:

-1
  1. 有一组连续的帧画像,每一帧包含数个向量表示该帧所拥有的数个特征。当连续的几帧拥有相同的某一向量时,记录这些连续帧的数目为一个时长。求在给定的所有帧中最长连续特征帧的时长。
    输入:第一行为一个正整数n,表示Case的个数。接下来的n个Case,每个Case的第一行有一个正整数m,表示当前Case中包含帧的个数。接下来的m行,每一行的第一个非负整数表示这一帧中包含的向量数量k,后面的2k个整数,每两个数为一组,表示一个特征向量。
    输出:一个数字,表示最长连续特征帧时长。

输入样例#1:

1
6
2 0 0 1 1
1 1 1
2 9 7 1 1
1 9 7
0
3 9 7 0 0 1 1

输出样例#1:

3

输入样例#2:

2
2
2 0 0 1 1
1 2 2
1
3 1 2 3 4 5 6

输出样例#2:

1
1
  1. 有一个跳塔游戏,有编号1-n的共n座塔,每座塔的高度不同。玩家从高度为0的地面起跳,拥有一个能量值E,按顺序跳至每一座塔。当下一座塔的高度h小于E时,E会增加E-h,否则E会减小h-E。一旦玩家的能量值小于0,表示游戏失败。求能保证玩家跳完所有塔所需的初始能量值的最小值。
    输入:第一行为一个正整数n,表示塔的个数。第二行的n个正整数,按顺序表示要跳的每座塔的高度。
    输出:一个数字,表示这个最小值。

输入样例#1:

4
1 2 6 5

输出样例#1:

3

输入样例#2:

3
4 4 4

输出样例#2:

4
  1. 毕业后,小明打算从城市1出发,去城市2、城市3、城市4旅行然后回到城市1。每两个城市之间都有火车通行,每趟火车都有不同的票价,任意两城市间的往返价格相同。求一个旅游路径,保证每个城市只经过一次,最后回到原城市,使得所需的总票价最低。
    输入:四行数据,第i行的四个整数分别表示从第i个城市出发,到每一个城市的票价。
    输出:五个数字,表示这个路径。

输入样例#1:

0 3 1 5
3 0 6 7
1 6 0 4
5 7 4 0

输出样例#1:

1 2 4 3 1

1 3 4 2 1
  1. 有m个人和一艘船,现所有的人均在河的一侧,需要使用这艘船过河。每个人拥有一个过河时间,船每次最多载3个人过河,最少载2个人过河,过河的时间等于船上所有人的过河时间中最大的值。求一个过河顺序,使当所有人都过河时耗费的总时间最短。
    输入:第一行为一个正整数n,表示Case的个数。接下来的n个Case,每个Case只有一行,第一个正整数m表示总人数,后面的m个整数分别表示每个人的过河时间。
    输出:一个数字,表示这个最短时间。

输入样例#1:

1
3 1 2 3

输出样例#1:

3

输入样例#2:

2
7 1 1 1 1 100 100 100
6 1 1 4 5 1 4

输出样例#2:

108
14

发表评论

电子邮件地址不会被公开。 必填项已用*标注