首页 > 笔经面经 > 去哪儿2016.10.10在线笔试writeup

去哪儿2016.10.10在线笔试writeup

头像
toraoh
编辑于 2016-10-10 22:44:05 APP内打开
赞 5 | 收藏 19 | 回复4 | 浏览7286
速写一下这个题解。

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;
} 

嘛,总体来讲,希望之后看到的同学,主要是要学会这个线段拆成2个标记,排序然后扫过去的思想(这样面试官也不好说什么呢23333),别的也没什么了。

4条回帖

回帖
加载中...
话题 回帖

笔经面经近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐