算法与数据结构——网易笔试题（一）

算法题 13：二叉堆（网易2016实习研发工程师）

思路：

************************************************************************************************************************************

算法题 15：暗黑的字符串（网易2017年秋招）

题目：一个只包含’A’、’B’和’C’的字符串，如果存在某一段长度为3的连续子串中恰好’A’、’B’和’C’各有一个，那么这个字符串就是纯净的，否则这个字符串就是暗黑的。

例如：
BAACAACCBAAA 连续子串”CBA”中包含了’A’,’B’,’C’各一个，所以是纯净的字符串
AABBCCAABB 不存在一个长度为3的连续子串包含’A’,’B’,’C’,所以是暗黑的字符串

你的任务就是计算出长度为n的字符串(只包含’A’、’B’和’C’)，有多少个是暗黑的字符串 (1 ≤ n ≤ 30)。

***********************************************************************************************************************************

算法题 20：取不同颜色球的概率（网易游戏笔试题）

题目：有6种不同颜色的球，分别记为1,2,3,4,5,6，每种球有无数个。现在取5个球，求在以下的条件下：
1). 5种不同颜色，
2). 4种不同颜色的球，
3). 3种不同颜色的球，
4). 2种不同颜色的球，
它们的概率。

***********************************************************************************************************************************

算法题 23：赛马比赛（网易、美团）

题目1（网易笔试题）：25匹马5个跑道，怎样选出最快的5匹来？最少的次数

题目2（2016美团校招笔试题）：30个马赛跑，5个跑道，找出前五名，至少找几次

题目3：64匹马，8条跑道，分几次可以选出最快的4匹？

拓展题目：n匹马（1

***********************************************************************************************************************************

算法题 24：跳石板（网易校招）

题目：

小易来到了一条石板路前，每块石板上从1挨着编号为：1、2、3…….

这条石板路要根据特殊的规则才能前进：对于小易当前所在的编号为K的 石板，小易单次只能往前跳K的一个约数(不含1和K)步，即跳到K+X(X为K的一个非1和本身的约数)的位置。 小易当前处在编号为N的石板，他想跳到编号恰好为M的石板去，小易想知道最少需要跳跃几次可以到达。

例如：
N = 4，M = 24：
4->6->8->12->18->24
于是小易最少需要跳跃5次，就可以从4号石板跳到24号石板

***********************************************************************************************************************************

算法题 28：冒险游戏（网易游戏）

题目：在一冒险游戏里，你见到一个宝箱，身上有N把钥匙，其中一把可以打开宝箱，假如没有任何提示，随机尝试，问：
1). 恰好第K次（1=

***********************************************************************************************************************************

算法题 56：比较重量（网易笔试题）

题目：小明陪小红去看钻石，他们从一堆钻石中随机抽取两颗并比较她们的重量。这些钻石的重量各不相同。在他们们比较了一段时间后，它们看中了两颗钻石g1和g2。现在请你根据之前比较的信息判断这两颗钻石的哪颗更重。

给定两颗钻石的编号g1,g2，编号从1开始，同时给定关系数组vector,其中元素为一些二元组，第一个元素为一次比较中较重的钻石的编号，第二个元素为较轻的钻石的编号。最后给定之前的比较次数n。请返回这两颗钻石的关系，若g1更重返回1，g2更重返回-1，无法判断返回0。输入数据保证合法，不会有矛盾情况出现。

测试样例：
2,3,[[1,2],[2,4],[1,3],[4,3]],4
返回: 1

***********************************************************************************************************************************

算法题 34：最大的奇约数（网易笔试题）

题目：

小易是一个数论爱好者，并且对于一个数的奇数约数十分感兴趣。一天小易遇到这样一个问题： 定义函数f(x)为x最大的奇数约数，x为正整数。例如:f(44) = 11.
现在给出一个N，需要求出 f(1) + f(2) + f(3)…….f(N)

例如： N = 7
f(1) + f(2) + f(3) + f(4) + f(5) + f(6) + f(7) = 1 + 1 + 3 + 1 + 5 + 3+ 7 = 21
小易计算这个问题遇到了困难，需要你来设计一个算法帮助他。

输入描述:
输入一个整数N (1 ≤ N ≤ 1000000000)

输出描述:
输出一个整数，即为f(1) + f(2) + f(3)…….f(N)

输入例子:
7

输出例子:
21

***********************************************************************************************************************************

算法题 72：二叉树（网易笔试）

有一棵二叉树，树上每个点标有权值，权值各不相同，请设计一个算法算出权值最大的叶节点到权值最小的叶节点的距离。二叉树每条边的距离为1，一个节点经过多少条边到达另一个节点为这两个节点之间的距离。

给定二叉树的根节点root，请返回所求距离。

***********************************************************************************************************************************

算法题 86：小易的升级之路（网易笔试）

小易经常沉迷于网络游戏.有一次,他在玩一个打怪升级的游戏,他的角色的初始能力值为 a.在接下来的一段时间内,他将会依次遇见n个怪物,每个怪物的防御力为b1,b2,b3…bn. 如果遇到的怪物防御力bi小于等于小易的当前能力值c,那么他就能轻松打败怪物,并 且使得自己的能力值增加bi;如果bi大于c,那他也能打败怪物,但他的能力值只能增加bi 与c的最大公约数.那么问题来了,在一系列的锻炼后,小易的最终能力值为多少?

输入描述:
对于每组数据,第一行是两个整数n(1≤n<100000)表示怪物的数量和a表示小易的初始能力值.
第二行n个整数,b1,b2…bn(1≤bi≤n)表示每个怪物的防御力

输出描述:
对于每组数据,输出一行.每行仅包含一个整数,表示小易的最终能力值

输入例子:
3 50
50 105 200
5 20
30 20 15 40 100

输出例子:
110
205

***********************************************************************************************************************************

算法题 93：扫描透镜（网易笔试题）

题目：在N*M的草地上，提莫种了K个蘑菇，蘑菇爆炸的威力极大，兰博不想贸然去闯，而且蘑菇是隐形的。有一种叫做扫描透镜的物品可以扫描出隐形的蘑菇，于是他回了一趟战争学院,买了2个扫描透镜，一个 扫描透镜可以扫描出(3*3)方格中所有的蘑菇，然后兰博就可以清理掉一些隐形的蘑菇。问：兰博最多可以清理多少个蘑菇？

注意：每个方格被扫描一次只能清除掉一个蘑菇。

输入描述:
第一行三个整数:N,M,K,(1≤N,M≤20,K≤100),N,M代表了草地的大小;
接下来K行,每行两个整数x,y(1≤x≤N,1≤y≤M).代表(x,y)处提莫种了一个蘑菇.
一个方格可以种无穷个蘑菇.

输出描述:
输出一行,在这一行输出一个整数,代表兰博最多可以清理多少个蘑菇.

***********************************************************************************************************************************

算法题 98：四叉树（ 网易笔试题）

题目：一个包含n个节点的四叉树，每个节点都有4个指向孩子节点的指针，这个四叉树有（）个空指针。

***********************************************************************************************************************************

算法题 113：平衡二叉排序树的深度（网易2016笔试题）

单选题：依次把结点的关键字的值为50,30,20,150,130,40,80,70,85,15的记录插入到初始化为空的平衡二叉排序树中，在插入过程中平衡树条件如被破坏，则进行必要的调整，得到的平衡二叉排序树的深度为（）
A、3
B、4
C、5
D、6

***********************************************************************************************************************************

算法题 120：调整队形（2017年网易春招笔试题）

在幼儿园有n个小朋友排列为一个队伍，从左到右一个挨着一个编号为(0~n-1)。其中有一些是男生，有一些是女生，男生用’B’表示，女生用’G’表示。小朋友们都很顽皮，当一个男生挨着的是女生的时候就会发生矛盾。作为幼儿园的老师，你需要让男生挨着女生或者女生挨着男生的情况最少。你只能在原队形上进行调整，每次调整只能让相邻的两个小朋友交换位置，现在需要尽快完成队伍调整，你需要计算出最少需要调整多少次可以让上述情况最少。

例如：
GGBBG -> GGBGB -> GGGBB
这样就使之前的两处男女相邻变为一处相邻，需要调整队形2次

输入描述:
输入数据包括一个长度为n且只包含G和B的字符串.n不超过50.

输出描述:
输出一个整数，表示最少需要的调整队伍的次数

输入例子1:
GGBBG

输出例子1:
2

***********************************************************************************************************************************

算法题 122：双核CPU处理多核任务的方案（网易2017春招笔试题）

题目：一种双核CPU的两个核能够同时的处理任务，现在有n个已知数据量的任务需要交给CPU处理，假设已知CPU的每个核1秒可以处理1kb，每个核同时只能处理一项任务。n个任务可以按照任意顺序放入CPU进行处理，现在需要设计一个方案让CPU处理完这批任务所需的时间最少，求这个最小的时间。

输入描述:
输入包括两行：
第一行为整数n(1 ≤ n ≤ 50)
第二行为n个整数length[i](1024 ≤ length[i] ≤ 4194304)，表示每个任务的长度为length[i]kb，每个数均为1024的倍数。

输出描述:
输出一个整数，表示最少需要处理的时间

输入例子1:
5
3072 3072 7168 3072 1024

输出例子1:
9216

***********************************************************************************************************************************

算法题 133：二叉树有几种形态？（网易笔试题）

题目：一个具有3个节点的二叉树可以有 _ 种形态？

***********************************************************************************************************************************