首页 > 2020.09.13爱奇艺秋招笔试(3道简单编程题AK)
头像
joshua0509
编辑于 2020-09-13 17:05
+ 关注

2020.09.13爱奇艺秋招笔试(3道简单编程题AK)

第一题:AC 给一个字符串,求最长的无重复字符的子串的长度
思路:直接模拟,用set判断是否重复,用两个指针 l, r 记录当前子串的区间,每次更新答案即可
代码:
#include<bits/stdc++.h>
using namespace std;

int main(void)
{
#ifndef ONLINE_JUDGE
    freopen("a.txt", "r", stdin);
#endif

    int n;
    string s;
    while(getline(cin, s)) {
        set<unsigned char> tb;
        if(s.size() == 0) {
            cout << 0 << endl;
            continue;
        }

        int ans = 1;
        int l = 0;
        int r = 0;
        int n = s.size();
        while(r < n) {
            if(l >= r || tb.find(s[r]) == tb.end()) {
                tb.insert(s[r++]);
            } else {
                tb.erase(s[l]);
                l++;
            }
            ans = max(ans, r - l);
        }
        cout << ans << endl;
    }
    return 0;
}

第二题:AC 给一个长度文n的整数数组,其中有一个元素出现了超过n次,求出该元素
思路:直接计数,用cnt记录次数,val记录出现cnt次的元素,遍历时判断相等就++cnt, 不相等就--,
--cnt后如果 = 0,就更新元素,最后直接输出val即可
代码:
#include<bits/stdc++.h>
using namespace std;

int main(void)
{
#ifndef ONLINE_JUDGE
    freopen("b.txt", "r", stdin);
#endif

    int n = 0;
    int x;
    string s;
    while(getline(cin, s)) {
        stringstream ss(s);
        vector<int> a;
        while (ss >> x) a.push_back(x);
        int val = a[0];
        int cnt = 1;
        for(int i = 1; i < a.size(); ++i) {
            if(a[i] == val) ++cnt;
            else {
                --cnt;
                if(cnt == 0) {val = a[i]; cnt = 1;}
            }
        }
        cout << val << endl;
    }
    return 0;
}

第三题:AC 给一个整数序列,求出该序列中满足 a + b + c = 0 的元组的序列,每个答案一行
思路:这个题当然可以直接采取暴力检索,如果长度为n,时间复杂度为O(N^3) ,判断如果元素超过1000个就会超时,
所以考虑降维,复杂度降到O(N^2),因为有 a + b + c = 0, 变成 a + b = -c, 也就是,只需要枚举 (a+b) 和 -c 即可,
先从小到达排序原数组,然后从第一个>= 0 位置(记为:r )的-c开始往右枚举,在-c的左边(区间为:[0, r-1] )查找 a + b = -c的元组,
每次枚举r时,检索[0, r-1] 最多需要r次,所以最后总的时间复杂度O(N * (N-1) / 2),一次AC, 耗时0ms
代码:
#include<bits/stdc++.h>
using namespace std;
#define ios ios::sync_with_stdio(false),cin.tie(0);

using pii = pair<int,int>;
const int maxn = 10005;
int a[maxn];
int n;

vector<pii> getSum(int l, int r, int val) {
    vector<pii> ans;
    while(l < r) {
        if(a[l] + a[r] > val) r--;
        else if(a[l] + a[r] < val) l++;
        else {
            ans.push_back({a[l], a[r]});
            while(l < r && a[l] == a[l+1]) l++;
            while(l < r && a[r] == a[r-1]) r--;
            l++;
            r--;
        }
    }
    return ans;
}

int main(void)
{
#ifndef ONLINE_JUDGE
    freopen("c.txt", "r", stdin);
#endif

    string s;
    while(getline(cin, s)) {
        stringstream ss(s);
        n = 0;
        int x;
        while(ss >> x) a[n++] = x;
        sort(a, a+n);
        set<vector<int>> ans;
        int r = 0;
        while(r < n && a[r] < 0) ++r; 
        for(; r < n; ++r) {
            vector<pii> segs = getSum(0, r-1, -a[r]);
            if(segs.size() == 0) continue;
            for(auto& p : segs) ans.insert({p.first, p.second, a[r]});
        }
        for(auto& v : ans) {
            cout << v[0] << " " << v[1] << " " << v[2] << endl;
        }
    }
    return 0;
}

全部评论

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

推荐话题

相关热帖

近期热帖

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

近期精华帖

热门推荐