字节跳动笔试题

1. 1. 变身程序员
   1. 题目描述（思路：BFS）
   2. 输入描述
   3. 输出描述

字节跳动 的笔试题，说多了都是泪**:( **
好像对于ACM的同学不算什么，但是对于普通菜鸟来说真的很难了。

1. 变身程序员

题目描述（思路：BFS）

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

在给定的矩形网格中，每个单元格可以有以下三个值之一：

• 0代表空单元格
• 1代表产品经理
• 2代表程序员

每分钟，任何与程序员（在4个正方向上）相邻的产品经理都会变成程序员。

返回直到单元格中没有产品经理为止所必须经过的最小分钟数。若不可能，返回-1。

如：

注：输入只要是“矩形”即可，不一定是n*n的，可以是m*n的

输入描述

• 不固定多行（行数<=10），每行是按照空格分割的数字（不固定，每行数字个数<=10）
• 每个数组项取值只能是0、1、2
• 读取时可以按行读取，直到读取到空行为止，再对读取的所有行做转换处理

输出描述

• 如果能够将所有产品经理变成程序员，则输出最小的分钟数
• 如果不能，则输出-1

示例1

输入

1
2

0 2
1 0

输出

1

-1

示例2

输入

1
2
3

1 2 1
1 1 0
0 1 1

输出

1

3

示例3

输入

1
2
3
4
5
6

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

输出

1

4

2. 特征提取

题目描述（思路：map）

小明是一名算法工程师，同时也是一名铲屎官。某天，他突发奇想，想从猫咪的视频里挖掘一些猫咪的运动信息。为了提取运动信息，他需要从视频的每一帧提取“猫咪特征”。一个猫咪特征是一个二维的vector<x, y>。如果x_1=x_2 && 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
• 满足1<=N<=100000, 1<=M<=10000, 一帧的特征个数满足<=10000。特征取值均为非负整数。
• 如果没有长度大于2的特征运动，返回1

输出描述

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

示例1

输入

1
2
3
4
5
6
7
8
9
10

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

输出

1

3

说明

1

特征<1, 1>在连续的帧中连续出现3次，相比其他特征连续出现的次数大，所以输出3

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，代表建筑物的高度
• 数据范围：N与H(i)均在1-10^5之间

输出描述

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

示例1

输入

1
2

5
3 4 3 2 4

输出

1

4

示例2

输入

1
2

3
1 6 4

输出

1

3

4. 毕业旅行问题

题目描述（思路：dp动态规划）

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

输入描述

• 城市个数 n（1<=n<=20，包括北京）
• 城市间的车票价钱 n行n列的矩阵 m[n][n]

输出描述

• 最小车费花销 s

示例1

输入

1
2
3
4
5

4
0 2 6 5
2 0 4 4
6 4 0 2
5 4 2 0

输出

1

13

说明

1

共4个城市，城市1和城市1的车费为0，城市1和城市2的车费为2，城市1和城市3的车费为6，城市1和城市4的车费为5，依此类推。假设任意两个城市之间均有单程票可购买，且票价在1000元以内，无需考虑极端情况

5. 过河

题目描述

有n个人要过河，但是河边只有一艘船；

船每次最多坐三个人，每个人单独坐船过河的时间为a[i]，两个人或者三个人一起坐船时，过河时间为他们所有人中的最长过河时间；

为了安全起见，要求每次至少有两个人才能过河；

问最短需要多少时间，才能把所有人送过河。

输入描述

• 第一行是整数n，表示测试样例个数

• 每个测试用例的第一行是一个正整数m，表示参加过河的人数（2<=m<100000）

• 第二行是m个正整数a[i]（0<a[i]<100000），表示n个人的单独过河的时间

输出描述

• 对每个测试用例，输出应该准备的最少的过河时间

示例1

输入

1
2
3
4
5

2
2
1 2
4
1 1 1 1

输出

1
2

2
3