2019网易游戏开发岗位没写完的最后一题

in with 0 comment

时间来不及没写完，还是记录一下题目原型，只测试了样例。

原型大概是有n（20w）个基站，每个基站有一个海拔a[i]。有q（20w)个查询，每个查询是一场洪水，海拔小于洪水高度的基站会被淹没，然后剩下的基站相连的可以形成一个集群。每一场洪水是独立的，问每个查询对应有几个集群。

由于输入和查询都比较大，如果使用O(N*Q)的暴力查询一定是超时的。我们可以把离线排序洪水高度，假设第k高的洪水的集群数是确定的，那么第k+1高的洪水其实只要check一下k~k+1之间的基站，然后淹没掉就可以了，淹没的时候check一下该基站的左右两侧来更新集群数。而k~k+1的基站我们可以一开始记录基站的index，然后按照高度排序。这样就可以用二分快速找到k~k+1基站的位置。这样计算下来，时间复杂度大概是O(QlogN+N)

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

const int N = 200005;

struct DATA{
    int value;
    int index;
    DATA(){value=0; index=0;}
    DATA(int a, int b):value(a), index(b){}
};
DATA arr[N];

struct QUERY{
    int value;
    int index;
    int res;
    QUERY(){value=0; index=0; res=0;}
    QUERY(int a, int b, int c):value(a), index(b), res(c){}
};
QUERY query[N];

int block[N] = {0};


int main() {
    int n, q, x;
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> arr[i].value;
        arr[i].index = i;
    } 
    sort(arr, arr+n, [](const DATA& a, const DATA& b) {
        return a.value < b.value;
    });
    cin >> q;
    for(int i = 0; i < q; i++) {
        cin >> query[i].value;
        query[i].index = i;
        query[i].res = 1;
    }
    // 查询值从小到大排序
    sort(query, query+q, [](const QUERY& a, const QUERY& b) {
        return a.value < b.value;
    });
    size_t last_fill_pos = 0;
    for(int i = 0; i < q; ++i) {
        if(i > 0) query[i].res = query[i-1].res;
        // 二分查找a中>query[i]的位置
        DATA key(query[i].value, 0);
        size_t safe_pos = upper_bound(arr+last_fill_pos, arr + n, key, [](const DATA& a, const DATA& b){
            return a.value < b.value;
        }) - arr;
        // 小于idx的位置全部淹没。
        while(last_fill_pos < safe_pos) {
            int pos = arr[last_fill_pos].index;
            // check block
            if((pos - 1 >= 0 && block[pos-1] == 0) && (pos+1 < n) &&  block[pos+1] == 0) {
                query[i].res ++;
            }
            if((pos - 1 >= 0 && block[pos-1] == 1) && (pos+1 < n) &&  block[pos+1] == 1) {
                query[i].res --;
            }
            if(pos == 0 && block[pos+1] == 1 || pos == n-1 && block[pos-1] == 1) {
                query[i].res --;
            }
            block[pos] = 1;
            last_fill_pos++;
        }
    }
    // 查询按照输入排序
    sort(query, query+q, [](const QUERY& a, const QUERY& b) {
        return a.index < b.index;
    });
    for(int i = 0; i < q; i++) {
        cout << query[i].res << endl;
    }
 //   system("pause");
    return 0;
}
// 10
// 6 12 20 14 15 15 7 19 18 13
// 6
// 15 23 19 1 17 24

补充：
还有一题也记录下，题意大概是给定一个字符串，至多修改两次使得包含字符全为N的子串的长度最大，求出长度。
这题之前做过类似的，是百度的最后一题，是求一个二进制串最多修改k次，使得1串最长。直接按照原来的代码写的，
但是看原来的代码还是有点奇怪。所以重新写下，也是没有测试，希望下次能遇到原题测一下。

大概的方法就是两个下标，一个下标前进，当前进的下标无法前进时（即k次修改机会也用完时），那么后一个下标前进，把修改机会让出来。这里用了一个数据结构保存被修改的下标的下一个位置，这样可以再无法前进时，快速调整后一个下标。

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

int max_same_str(const string& str, char s_chr, int k) {
    // 非s_chr串的下一个位置
    queue<int> fast_jump;
    // 滑窗左右边界（闭区间）
    int left = 0, right =0;
    int len = str.size();
    int max_ch_cnt = 0;
    while(right < len) {
        // 滑动右边界
        if(str[right] == s_chr || k > 0) {
            if(str[right] != s_chr) {
                fast_jump.push(right+1);
                --k;
            }
            ++right;
        }
        else {
            // 收缩左边界
            max_ch_cnt = max(max_ch_cnt, right-left);
            left = fast_jump.front();
            fast_jump.pop();
            ++k;
        }
    }
    max_ch_cnt = max(max_ch_cnt, right-left);
    return max_ch_cnt;
}

int main() {
    string str;
    int k;
    cin >> k;
    while(k--) {
        cin >> str;
        cout << max_same_str(str, 'N', 2) << endl;
    }
    // system("pause");
    return 0;
}
// 3
// NNTN
// NNNNGGNNNN
// NGNNNNGNNNNNNNNSNNNN

本文由 shinelin 创作，采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Aug 11, 2019 at 01:07 pm

→ ↓ ↑
Responses