网页制作作品/天津seo结算
明天就将是网易互娱的二面了，这也应该会是我整个秋招生涯的最后一个面试，这段时间找工作的过程很忐忑，也很感慨，但是现在还不是享受胜利果实的时刻，还是写一篇对网易互娱的一道经典题目的理解吧。
1.题目
这是网易互娱的经典面试题，从大概一个多月前就看到了，往年也出现过多次，但是在牛客网上一直找不到恰当的解决方案。这段时间和一位很厉害的学姐，以及一位师弟讨论了一下，总结出了这种问题的解法。题目具体如下：
- 1.一条公路上有多个点，每个点都有一辆车，给定公路坐标轴，车的速度和行驶方向，求最早两辆车相遇的时间；
- 2.一条直线上多个点运动 知道所有点的位置，和速度包括方向。当两个点相碰时，追及或对撞两个点消失，问什么时候达到稳定状态，也就是以后都不会发生碰撞。
2.思想
题目本身，不难。其实第1题就是第2题的初始情况。解决这个题，需要从宏观的角度去计算思考，具体为明确“相遇”的概念本身：只有当前点的左右两点才会与其相遇，另外的点不可能越过其左右的点来与其相遇。所以在计算相遇时，最常规的思想就是不断地计算每个点与其两侧相邻点的相遇时间（最左边和最右边的两个点只能算一侧），或者说得知两者无法相遇（即速度方向和大小相同）
而解决问题的思想也正是这种想法，只不过相遇后的“消失”如果真的要“消失”那么说涉及到删除操作，真正实现时还是使用懒惰删除的策略，即用标志位来代替删除。
3.代码
代码中使用数组p来代表线上的点坐标，数组v代表线上每个点的速度大小与方向（符号为方向），数组isGone的状态表示已经相遇后点的“消失”状态，数组totaltime用于存储各个相遇的时间，其余注释见代码。
vector<double> calculateTime2(vector<double> &p, vector<double> &v)
{vector<bool> isGone(p.size(), false);vector<double> totalTime;while (true){//1.循环开始，建立存储当前趟循环的map，用于存储每组（两点）的相遇时间，以及是哪两个点map<double, vector<double>> crash;for (double i = 0; i < p.size(); i++){//2.如果当其点已经被标记为删除，则跳过if (isGone[i] == true)continue;for (double j = i + 1; j < p.size(); j++){//3.如果当其点已经被标记为删除，则跳过if (isGone[j] == true)continue;//4.如果两点速度大小与方向完全相同，表示两者永不相遇，跳过if (v[i] - v[j] == 0)continue;//5.如果有两个点可以计算相遇时间，则计算，计算完成后跳出，因为一次只算两个点的double time = abs((p[i] - p[j]) / (v[i] - v[j]));crash.insert({ time,vector<double>({ i,j }) });break;}}//6.查看每趟计算中的相遇情况for (auto &s : crash)cout << s.first << " " << s.second[0] << " " << s.second[1] << endl;//7.当当前数据中无法再计算出相遇点时，返回if (crash.empty())return totalTime;else{//8.否则，懒惰删除时间最小的点，然后重新进入循环计算double time = (*crash.begin()).first;totalTime.push_back(time);int a = (*crash.begin()).second[0];int b = (*crash.begin()).second[1];cout << a << " " << b << endl;isGone[a] = true;isGone[b] = true;}}
}int main()
{vector<double> p({ 1.2,23.9,2.023,13.212,6.13,-100.12,122 });vector<double> v({ 2.56,30.345,-10.234,23.121,100.111,-50.08,-1000.8 });vector<double> temp = calculateTime2(p, v);return 0;
}
4.改进
很明显，这种算法的时间复杂度，我认为应该最高可以达到O(n3)的状态，但是具体是多少还需要多考虑。
其可以改进的地方主要是在懒惰删除点之后的情况，因为往往一次只懒惰删除掉时间最短的那一组点，涉及到的相关点可能就只有相邻的四个点，所以在这里其实可以大大优化，但是其优化方法可能实现起来也并不简单。