算法工程师的一些面试题

这里的面试题都是自己看到的，然后感觉比较好的一些面试题目：（会陆续更新）

一、有一个数组 int array[100]；本来应该存放的数为1~100，但是有两个数据丢失了，值变成了0。问如何找出丢失的那两个数？

思路：

在原数组上打表,扫两遍可以得到结果。 例子：数组大小是5,存放1-5,丢了1个数. 原数组：4 2 5 3 0 迭代： 4 2 5 3 0 3 2 5 -1 0 把3和4换一下,把4标记为-1 5 2 -1 -1 0 把3和5换一下，把3标记为-1 0 2 -1 -1 -1 把5和0换一下，把5标记为-1 跳过0 0 -1 -1 -1 -1 2已在正确位置，把2标记-1 跳过所有-1 结束 再次遍历数组,发现array[1]==0，所以数字1丢失。

时间复杂度为O（2n）

二、甲乙两地相距100公里，有一辆火车以每小时15公里的速度离开甲地直奔乙地，另一辆火车以每小时20公里的速度从乙地开往甲地。如果有一只鸟，以30公里每小时的速度和两辆火车同时启动，从甲地出发，碰到另一辆车后返回，依次在两辆火车来回飞行，直到两辆火车相遇，请问，这只小鸟往返了多少次？

选取乙车位参照物：从乙地开往甲地的火车相对静止不动 则： 从甲开往乙的火车速度为：v1＝15＋20＝35km/h 从甲飞往乙的鸟的速度为：v2＝30＋20＝50km/h 从甲开往乙的火车在每次小鸟达到乙的时候开的距离为x 小鸟从乙返回和甲相遇时甲开的距离为y 每一次相遇后甲离乙的距离为s 易得：x＝s*35/50 y=(s-x)*35/85; s=s-x-y

程序实现如下：

#include <iostream>
#include<iomanip>
using namespace std;

int main()
{
	double s = 100;
	double x;
	double y;
	int count=0;  //计算往返次数
	while(s > 0)
	{
		x = s * 35 / 50;
		y = (35 / 85) * (s - x);
		s = s - x - y;
		count++;
	}
	cout<<count<<endl;
	system("pause");
	return 0;
}

三、一共有25匹马，有一个赛场，赛场有5个赛道，就是说最多同时可以有5匹马一起比赛。假设每匹马都跑的很稳定，不用任何其他工具，只通过马与马之间的比赛，试问，最少得比多少场才能知道跑得最快的5匹马？

定义： 1.两匹马的速度快慢，称为一个关系，例如A比B快，则称A和B构成一个关系，用