网易、大众、京东算法工程师岗编程题

ゞ浴缸里的玫瑰 2022-08-09 12:48 203阅读 0赞

*  问题描述:

> *V先生有一天工作得很晚，回家的时候要穿过一条长度为l的笔直街道，这条街道上有n个路灯。假设这条街起点为0，终点为l，第i个路灯的坐标为ai。路灯发光能力以正数d来衡量，其中d表示路灯能够照亮的街道上的点与路灯的最远距离，所有路灯发光能力相同。为了让V先生看清回家的路，路灯必须照亮整天街道，又为了节省电力希望找到最小的d是多少？*
> 
> 输入：  
> 
> 
> 输入两行数据，第一行是两个整数：路灯数目n(1<=n<=1000)，街道长度(1<=l<=pow(10, 9))。第二行有n个整数ai(0<=ai<=l)，表示路灯坐标，多个路灯可以在同一个地方，也可以安放在终止点位置。  
> 
> 
> 样例输入：
> 
>     7 15
>     15 5 3 7 9 14 0
> 
> 结果：
> 
>     2.5
> 
> 解题思路：找出相邻坐标差值中最大的，然后除以2便是最小的d。
> 
> 代码步骤：先进行输入处理，将其保存在v中，再对其进行由小到大的排序，然后计算找出相邻坐标中最大的差值。  
> 
> 
> 代码如下：
> 
>     #include<iostream>
>     #include<algorithm>
>     #include<vector>
>     using namespace std;
>     void main()
>     {
>     	int NumofStreetlight, StreetLength;
>     	cin >> NumofStreetlight >> StreetLength;
>     	vector<float> v(NumofStreetlight);
>     	int i = 0;
>     	auto iterator = v.begin();
>     	float coordinate;
>     	for (int i = 0; i < NumofStreetlight; ++i)
>     	{
>     		cin >> coordinate;
>     		v[i] = coordinate;
>     	}
>     	sort(v.begin(), v.end());   //注意这里是v.end()
>     	float front_dist = *v.begin();  //这里要考虑了前边界情况
>     	float back_dist = StreetLength - *(v.end()-1);   //这里要考虑了后边界情况
>     	float max_boarddist = max(front_dist, back_dist);
>     	float temp_dist = 0;
>     	for ( auto it2=v.begin()+1; it2 !=v.end(); ++it2)
>     	{
>     		if (*it2 - *(it2 - 1)>temp_dist)
>     		temp_dist = *it2-*(it2-1) ;
>     	}
>     	if (max_boarddist > temp_dist)cout<< max_boarddist;
>     	else cout<<temp_dist / 2;
>     }
> 
>   
> 
> 
> ## 大众点评数据挖掘岗综合题 ##
> 
> 该题题目为：
> 
> *N个为排序的整数，在线性时间内，求这N个数在数轴上相邻两个数之间的最大差值（写出关键算法）*
> 
> 该题和上面那题思路一样。
> 
> 另外大众点评综合题第三题是贝叶斯公式的运用，题目描述如下：
> 
> *某公司有两个部门，A部门有30名女生和24名男生，B部分有12名女生和42名男生。现在从两个部门中挑选出一个女生来安排一次联谊团建，请问这个女生来自A部门的概率为多少？*
> 
> 解:
> 
>  *  设H1表示A部门，H2表示B部门，P(H1) = P(H2) = 0.5, P(E|H1) = 30/54, P(E|H2) = 12/54;
>  *  设E表示女生，则问题转成求P(H1|E)；
>  *  P(E) = P(E|H1)P(H1) + P(E|H2)P(H2) = 7/18;
>  *  根据条件概率公式有：
>  *  P(H1|E) = P(H1)P(E|H1)/P(E) = 0.5(30/54)/(7/18) = 0.714
> 
>   
> 
> 
> ## 京东算法岗综合题 ##
> 
>  *  问题描述：
>  *  *输入数据仅包含一组测试样例，对于每组测试案例，共有两行输入数据，输入第一行代表要处理的字符串s1(不超过50)，输入第二行代表替换的字符串s2（不超过10）.*
>  *  样例输入：
>     
>         You are the best 123 To be NO.1 Yes Thank you very much %%%
>     
>     样例输出：
>     
>         You1234are1234the1234best ToYesbeYesNO.1 Thank%%%you%%%very%%%much
>     
>     解题思路：可以参阅《剑指offer》P46页替换空格那道题。代码如下：
>     
>         #include<iostream>
>         #include<algorithm>
>         #include<vector>
>         using namespace std;
>         #define MaxLength 100
>         char arr[MaxLength];
>         void ReplaceBlank(char arr1[], char arr2[])
>         {
>         	if (arr1 == NULL || arr2 == NULL)return;
>         	int len1 = strlen(arr1), len2 = strlen(arr2);
>         	if (len1 <= 0 || len2 <= 0)return;
>         	strcpy_s(arr, arr1);
>         	int numberOfBlank = 0;
>         	for (int i = 0; arr[i]!='\0'; ++i)
>         		if (arr[i] == ' ')++numberOfBlank;
>         	int originalIndex = len1, newIndex = len1 + (len2 - 1) *numberOfBlank;
>         	if (newIndex > MaxLength)return;
>         	while (newIndex>originalIndex)
>         	{
>         		if (arr[originalIndex] == ' ')
>         			for (int j = len2 - 1; j >=0; --j)arr[newIndex--] = arr2[j];
>         		else arr[newIndex--] = arr[originalIndex];	
>         		--originalIndex;
>         	}
>         }
>         void PrintArray(char arr[],int len)
>         {
>         	if (arr == NULL || len == 0)return;
>         	int i = 0;
>         	while (arr[i]!='\0')
>         	{
>         		cout << arr[i];
>         		++i;
>         	}
>         	cout << endl;
>         }
>         int main()
>         {
>         	char arr1[] = "We are happy.";
>         	char arr2[] = "%20";
>         	ReplaceBlank(arr1, arr2);
>         	int stringLength = strlen(arr);
>         	PrintArray(arr, stringLength);
>         	return 0;
>         }
>     
>      *  问题描述：
>      *  *小东和三个小朋友在一起玩小球，他们是一种新玩法。他们站在楼房的不同层，假设小东站在的楼层距离地面N米，球从小东的手里自由落下，每次落地后跳回返回原地面的一半；再落回地下，再反跳回原高度的一半。小东和三个小朋友站在不同的楼层，同时放下手中不同的小球，当小球全部落下地面不跳事，求4个小球一共经过了多少米？（数字都为整数）。*
>     
>     输入：
>     
>     *输入4个数字，分别表示四个小球距离地面的高度，所有输入的数字都为整数，范围不能超过整数所能表示的最大值。*  
>     
>  *  输出：  
>     
>  *  *输出为4个小球经过的总长度*  
>     
>  *  样例输入：
>     
>         100 90 80 70
>     
>     样例输出：
>     
>         996
>     
>     解题思路：这道题只要不是等比数列取极限定势思维先入为主，并且注意到了数字都为整数这条信息，就非常非常容易做了，代码如下：
>  *      #include<iostream>
>         #include<algorithm>
>         #include<vector>
>         using namespace std;
>         int SumDistanceofOne(int n)
>         {
>         	if (n == 1)return 1;
>         	else return (n + n / 2 + SumDistanceofOne(n / 2));
>         }
>         int main()
>         {
>         	int high1, high2, high3, high4;
>         	cin >> high1 >> high2 >> high3 >> high4;
>         	int sum = SumDistanceofOne(high1) + SumDistanceofOne(high2) + SumDistanceofOne(high3) + SumDistanceofOne(high4);
>         	cout << sum << endl;
>         }
>     
>       
>       
>