携程 – 笔试编程题 – 部分解析

嗯 – 很悲催，最后一题入了最小生成树的坑，没出来…所以只AC2.3…心疼自己。

携程2017技术类校园招聘开发工程师在线考试
编程题 | 30分 1/2
二分查找
时间限制：C/C++语言 1000MS；其他语言 3000MS
内存限制：C/C++语言 65536KB；其他语言 589824KB

题目描述：
请写一个二分查找算法查找一个数最先出现的index，如果数不在集合中需要返回(-1)-当前数应该出现的位置。
例如 [1,3,6],查找5,5应该是在index=2的位置但并不在集合中。返回(-1)-2 = -3。

输入
第一行读入一个整数x，表示要查找的数；
第二行读入一个正整数n，表示待查找数组的元素个数；
第三行读入n个递增整数，构成待查找的数组。

输出
整数x在数组中出现的索引位置(索引从0开始计数)；如果不存在，返回(-1)-当前数应该出现的位置。

样例输入
3
5
0 1 3 5 6
样例输出
2

代码如下：

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main()
{
	//freopen("input.txt", "r", stdin);
	
	long long key;
	cin >> key;
	long long  num;
	cin >> num;
	vector <long long > v;
	for(int i=0; i<num; i++)
	{
		long long  tmp;
		cin >> tmp;
		v.push_back(tmp);
	}
	
	long long  begin = 0;
	long long  end = num;
	long long  mid = (begin + end) / 2;
	while(begin < end)
	{
		//cout << begin << " : " << end << " : " << mid << endl; 
		if(v[mid] == key)
		{
			break;
		}
		else if(v[mid] > key)
		{
			end = mid;
			mid = (begin + end) / 2;
		}
		else // <
		{
			begin = mid + 1;
			mid = (begin + end) / 2;
		}
	}
	if(begin >= end)
	{
		mid = -1 - mid;
	}
	cout << mid << endl;
}

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

int main()

{

//freopen("input.txt", "r", stdin);

long long key;

cin >> key;

long long num;

cin >> num;

vector <long long > v;

for(int i=0; i<num; i++)

{

long long tmp;

cin >> tmp;

v.push_back(tmp);

}

long long begin = 0;

long long end = num;

long long mid = (begin + end) / 2;

while(begin < end)

{

//cout << begin << " : " << end << " : " << mid << endl;

if(v[mid] == key)

{

break;

}

else if(v[mid] > key)

{

end = mid;

mid = (begin + end) / 2;

}

else // <

{

begin = mid + 1;

mid = (begin + end) / 2;

}

if(begin >= end)

{

mid = -1 - mid;

}

cout << mid << endl;

}

第一题 – 确认AC…

第二题 – 题面被吃了…

解析在这里：做了发现是LeetCode的原题 – 所以去AC了一下…

http://blog.tk-xiong.com/archives/1051

最后一题：

携程2017技术类校园招聘开发工程师在线考试
编程题 | 20分 1/1
遍历最短路径长度
时间限制：C/C++语言 1000MS；其他语言 3000MS
内存限制：C/C++语言 65536KB；其他语言 589824KB

题目描述：
暴风降临的龙母丹妮莉丝·坦格利安要骑着她的龙以最快的速度游历各国，她的谋士们纷纷献策规划路线。
作为她的谋士之一和仰慕者的你，决定冒险穿越到21世纪借助计算机来寻求最优路线。
请设计一段程序，读取各国两两之间的距离，距离以邻接矩阵表示，并计算出遍历各国的最短路径长度。

输入
第一行：国家数量，假设为n
后续n行是国家间距离的邻接矩阵表示

输出
遍历各国的最短路径长度

样例输入
4
0,1,2,3
1,0,4,5
2,4,0,2
3,5,2,0

样例输出
5

思路的话 – 据说是DFS剪枝过了…

我是卡在了最小生成树 – 33%…心疼自己。

携程 – 笔试编程题 – 部分解析