去哪儿2016.10.10在线笔试writeup
速写一下这个题解。
filename extension
时间限制：C/C++语言 1000MS；其他语言 3000MS
内存限制：C/C++语言 65536KB；其他语言 589824KB
题目描述：
Please create a function to extract the filename extension
from the given path,return the extracted filename extension or null
if none.
输入
输入数据为一个文件路径
输出
对于每个测试实例，要求输出对应的filename extension
样例输入
Abc/file.txt
样例输出
txt
思路：找最后一个/，之后的内容都是文件名（没有/的话，整个字符串是文件名）
然后找文件名中最后一个 . （dot），之后的内容都是扩展名（没有 . （dot）的话，就不存在扩展名，请输出null）
代码略。
=================================================================================
统计字符
时间限制：C/C++语言 1000MS；其他语言 3000MS
内存限制：C/C++语言 65536KB；其他语言 589824KB
题目描述：
给定一个英文字符串,请写一段代码找出这个字符串中首先出现三次的那个英文字符。
输入
"qywyery23tdd"
输出
y
样例输入
Have you ever gone shopping and
样例输出
e
思路：开一个256的int数组（hashmap也行，随你），然后使用计数排序思想，出现一次，相应的位置+1，当一个【英文字符】出现3次的时候，输出并退出。
注意是【英文字符】，不然你只有25%的分数。
===================================================================================
酒店价格
时间限制：C/C++语言 1000MS；其他语言 3000MS
内存限制：C/C++语言 65536KB；其他语言 589824KB
题目描述：
酒店房间的价格录入是通过时间段来录入的，比如10月1日至10月7日800元，10月8日至10月20日500元，请实现以下函数int[][]
merge(int[][]
dateRangePrices)，输入是某个酒店多个日期段的价格，每个日期段（终止日期大于等于起始日期）和对应的价格使用长度为3的数组来表示，比如[0,
19, 300], [10, 40,
250]分别表示从某天开始第1天到第20天价格都是300，第11天到第41天价格都是250，这些日期端有可能重复，重复的日期的价格以后面的为准，
请以以下规则合并并输出合并结果：
1.相邻两天的价格如果相同，那么这两个日期段应该合并
2.合并的结果应该以起始日期从小到大排序
输入
[0, 100, 300], [40, 50, 350]
输出
[0, 39, 300], [40, 50, 350], [51, 100, 300]
样例输入
1 1 100
2 3 100
4 5 110
样例输出
[1, 3, 100],[4, 5, 110]
思路：
注意，大部分说直接for循环，写到一个一维数组，这样搞下去的，肯定挺不过面试官这么问：
1、如果时间不是整数，是小数，怎么办？
1.5 2.33333306 150
2.0 3.0 300
2、如果时间范围很大（比如是毫秒的时间戳），怎么办？
12 2026595952 150
52652 1985958952 200
合并区间当然也可以，但是这里还需要拆分区间，很恶心。
当然是想办法绕过了。
接下来是一个经典套路。
我博客里写过了：http://blog.csdn.net/fcxxzux/article/details/52346364
的C题，这里直接摘抄前半部分。
首先我们看一个面试真题：
给出一份对某种资源占用的记录（这种资源可以被多个进程共享），记录中包括开始时刻和截止时刻（左闭右开）。
求这种资源共计被占用的时长（如果多个进程同时占用，也只记录一份用时）
比如，
{1,3}
{2,4}
占用时长：3（1时刻1个，2时刻2个，3时刻1个，其他时间没人占用，共计有3个时间有人占用）
没有任何训练，只会C语言的人：搞一个统计数组，一个元素对应一个时刻，然后对每个记录，在统计数组里，从开始到结束，每个元素+1
这个时间复杂度是O(n*Time)的，当然不是什么能说服面试官的做法。
更高效的做法是：
将{a,b}拆成2个标记，记成{a,增加一个作业}，{b,减少一个作业}，得到2n个标记，之后按时间从前到后排序（同时刻的按先减少再增加排序），排序后从前到后扫一遍，记录所有至少1个作业的时间段的长度，累加起来就行了。
比如上面的例子，拆开，并排序：
{1,增加}{2,增加}{3,减少}{4,减少}
之后从左到右：
1时刻，开始有人占用，记下来这个时刻
2时刻，又来一个人，记2人
3时刻，少了一个，记1个人
4时刻，再少一个，没人用了，累加一下之前被占用时间：4-1=3
时间复杂度，这个是O(n+nlogn+n)=O(nlogn)的
然后我们来考虑一下，借鉴这个思路。
这种线段覆盖类问题，上来一个线段拆成2个标记，一般不会错的。
拆出来以后，就是每个题有各自的需求了。
这里，我的处理方法是：
用set<>（红黑树）维护目前覆盖的线段，其中的类要求实现比较的方法：按在输入里，靠后的在前面。
然后对排序后的标记，从前到后扫一遍，2步
1、执行：增加标记就增加，删除标记就删除
2、维护答案：先判断是不是这一天的都处理完了，处理完了然后考虑是不是应该增加一个记录。如果我们并没有开始写一条记录，或者和前面的记录的价格不一样了，那就完成当前这条记录，并新建一个。
（为了方便处理，代码里把输入的左闭右闭变成左闭右开）
代码如下：
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
#include <limits.h>
#include <math.h>
#include <algorithm>
#include <set>
using namespace std;
typedef long long ll;
struct Rec{
int id,day,price,type;
bool operator<(const Rec&b)const{
return day<b.day;
}
}r[200005];
struct Point{
int id,price;
Point(){}
Point(int a,int b):id(a),price(b){}
bool operator<(const Point &b)const{
return id>b.id;
}
};
int res[200005][3];
int rescount=0;
int main(){
int n=0;
int x,y,z;
while(~scanf("%d%d%d",&x,&y,&z)){
r[2*n].id=n;
r[2*n].day=x;
r[2*n].price=z;
r[2*n].type=0;
r[2*n+1].id=n;
r[2*n+1].day=y+1;
r[2*n+1].price=z;
r[2*n+1].type=1;
++n;
}
sort(r,r+2*n);
int startDate=-1,startPrice=-1;
set<Point> s;
for(int i=0;i<2*n;i++){
if(r[i].type==0){
s.insert(Point(r[i].id,r[i].price));
}else{
s.erase(Point(r[i].id,r[i].price));
}
if(i+1==2*n||r[i].day!=r[i+1].day){
if(s.size()==0){
if(startDate!=-1){
res[rescount][0]=startDate;
res[rescount][1]=r[i].day-1;
res[rescount][2]=startPrice;
++rescount;
}
startDate=startPrice=-1;
}else{
set<Point>::iterator it=s.begin();
if(it->price!=startPrice){
if(startDate!=-1){
res[rescount][0]=startDate;
res[rescount][1]=r[i].day-1;
res[rescount][2]=startPrice;
++rescount;
}
startDate=r[i].day;
startPrice=it->price;
}
}
}
}
for(int i=0;i<rescount;++i){
printf(i==0?"[%d, %d, %d]":",[%d, %d, %d]",res[i][0],res[i][1],res[i][2]);
}
return 0;
}
投递网易等公司10个岗位 >