首页 > 2019秋招瓜子&携程笔试题解(含题目) 点赞有offer
头像
编辑于 2018-09-09 13:03
+ 关注

2019秋招瓜子&携程笔试题解(含题目) 点赞有offer

。。。我不是大佬,做的不好。。放一下题目和我的做法
求牛客卫衣,求牛客卫衣,求牛客卫衣

瓜子

下面的代码通过100+80

1.单词逆序

题目描述:对于一个字符串,请设计一个算法,只在字符串的单词间做逆序调整,也就是说,字符串由一些由空格分隔的部分组成,你需要将这些部分逆序。
给定一个原字符串A,请返回逆序后的字符串。例,输入”I am a boy!“输出”boy! a am I“
输入描述:输入一行字符串str。(1<=strlen(str)<=10000)
输出描述:返回逆序后的字符串。
示例1
输入It’s a dog!
输出dog! a It’s


太水了,直接输出就行

#include <iostream>
#include <string>

using namespace std;

int main(){
//    freopen("../in.txt","r",stdin);
    string str[10005];
    int len=0,i;
    while (cin>>str[len++]);
    for(i=len-2;i>0;i--){
//        cout<<str[i]<<endl;
        cout<<str[i]<<" ";
    }
    cout<<str[i]<<endl;
}

2.字符串全排列

题目描述:对K个不同字符的全排列组成的数组, 面试官从中随机拿走了一个, 剩下的数组作为输入, 请帮忙找出这个被拿走的字符串?
比如[“ABC”, “ACB”, “BAC”, “CAB”, “CBA”] 返回 “BCA”
输入描述:第一行输入整数n,表示给定n个字符串。(n == x!-1,2<=x<=10)
以下n行每行输入一个字符串。
输出描述:输出全排列缺少的字符串。
示例1
输入5
ABC
ACB
BAC
CAB
CBA
输出BCA


。赶着做携程,暴力水了一发过了80%,晚上电话贼多。
我写的暴力做法:把所有全排列放到set,然后去掉所有的输入,剩下的就是

我认为正确的做法:统计每一位的不同字符的个数,出现次数最少的就是需要输出的,然后找完之后输出即可
感觉楼下一位大佬说的很对,使用异或的方法,因为一个数A^A=0,不过应该需要考虑一下长度为2的情况(12,21这个情况两位都是技术),对于更长的数字每一位的个数都是偶数了
//此代码仅通过80%
#include<iostream>
#include<algorithm>
#include<set>
#include<cstring>

using namespace std;

set<string> s;
void permutation(char *str, int length) {
    sort(str, str + length);
    do {
        s.insert(str);
    } while (next_permutation(str, str + length));
}

int main() {
//    freopen("../in.txt","r",stdin);
    int n,i;
    char str[40];
    cin>>n;
    cin>>str;
    permutation(str,strlen(str));
    set<string>::iterator it;
    s.erase(str);
//    for(it=s.begin();it!=s.end();it++){
//        cout<<*it<<endl;
//    }
    for(i=1;i<n;i++){
        cin>>str;
        s.erase(str);
    }
    cout<<*s.begin()<<endl;
    return 0;
}

携程

下面的代码通过100+100+87.5

1.bitcount

图片说明
图片说明
图片说明


位运算进行处理

#include <bits/stdc++.h>
using namespace std;
#define ll long long

ll NumberOf1(ll n) {
    ll ans = 0;
    while (n != 0) {
        ++ans;
        n = (n - 1) & n;
    }
    return ans;
}

int main() {
//    freopen("../in.txt","r",stdin);
    ll n;
    cin>>n;
    cout<<NumberOf1(n)<<endl;
}

2.查询满足区间的记录

图片说明
图片说明
图片说明
图片说明
图片说明


不是很明白出题人意图,这么出肯定是水题了啊。

#include <bits/stdc++.h>

using namespace std;
struct node{
    int id;
    int start,end;
};
bool cmp(node a,node b){
    return a.start<b.start;
}
set<int> s;
int main(){
//    freopen("../in.txt","r",stdin);
    int n,A,i;
    node a[5000];
    scanf("%d%d",&n,&A);
    for(i=0;i<n;i++){
        scanf("%d%d%d",&a[i].id,&a[i].start,&a[i].end);
        if(a[i].start<=A&&a[i].end>=A)
            s.insert(a[i].id);
    }
    set<int>::iterator it;
    if(s.size()==0){
        cout<<"null"<<endl;
    }else{
        for(it=s.begin();it!=s.end();it++){
            cout<<*it<<endl;
        }
    }
}

3.LRU Cache图片说明

图片说明
图片说明
图片说明
图片说明


LeetCode上面的题目LeetCode146(这题在更新已有值得时候不会update),今天早上面头条之前刚刚看了一个大佬的写法,头条手写LRU貌似被问烂了,然而我还是这么菜,估计一面凉凉。这个只过了87.5,有点迷

#include <bits/stdc++.h>

using namespace std;
#define ll long long


class LRUCache {

private:
    typedef pair<int, list<int>::iterator> PILI;
    int capacity;
    map<int, PILI> datas;
    list<int> s;
public:
    LRUCache(int capacity) {
        this->capacity = capacity;
    }

    int get(int key) {
        auto iter = datas.find(key);
        if (iter != datas.end()) {
            update(iter);
            return iter->second.first;
        } else
            return -1;
    }

    void put(int key, int value) {
        int length = datas.size();
        auto iter = datas.find(key);
        if (iter != datas.end()) {
            iter->second.first = value;
//            update(iter);
        } else {
            if (length >= capacity) {
                datas.erase(s.back());
                s.pop_back();
            }
            s.push_front(key);
            datas[key] = PILI(value, s.begin());
        }
    }

private:
    void update(map<int, PILI>::iterator iter) {
        int key = iter->first;
        s.erase(iter->second.second);
        s.push_front(key);
        iter->second.second = s.begin();

    }
};

int main() {
//    freopen("../in.txt", "r", stdin);
    char oper;
    int num1, num2, n;
    cin >> n;
    LRUCache *lruCache = new LRUCache(n);
    while (cin >> oper) {
        if (oper == 'p') {
            cin >> num1 >> num2;
            lruCache->put(num1, num2);
        } else if (oper == 'g') {
            cin >> num1;
            cout << lruCache->get(num1) << endl;
        }
    }
}

全部评论

(13) 回帖
加载中...
话题 回帖