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的元组，

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

全站热榜

创作者周榜