腾讯《后台&综合-第一次笔试》题解

一共五道题，做不完，做了四道，有一道没时间了。

字符串压缩解压：

普通模拟，用栈存下来左括号，每次遇到一个右括号，就把中间的字符串分析一遍，解压

string s;
struct p{
    int l;
    int r;
    p(int a,int b){
        l = a;
        r = b;
    }
};
stack<int> kuo;

int main(){

    cin>>s;
    int n = s.size();
    for(int i=0;i<n;++i){

        if(s[i] == '['){
            kuo.push(i);
        }
        if(s[i] == ']'){
            int t = kuo.top();
            kuo.pop();
            string a = s.substr(t+1, i-t-1);

            bool flag = 0;
            int num = 0;
            string str;
            for(int j=0;j<a.size();++j){
                if(!flag && isdigit(a[j])){
                    num+=a[j]-'0';
                    num*=10;
                }
                else if(a[j] == '|'){
                    flag = true;
                    str = a.substr(j+1, n-j-1);
                    break;
                }
            }
            num/=10;
            string replace;
            for(int j=0;j<num;++j){
                replace +=  str;
            }
            s = s.substr(0,t)+ replace + s.substr(i+1, n-i-1);
            n = s.size();
            i = t+replace.size()-1;

        }
    }
    cout<<s<<endl;
}

放多少个xxx可以覆盖整条河面最小区间覆盖问题

先按照左值排序，然后右值倒叙

struct p{
    int l;
    int r;
    bool operator<(const p & a)const{
        if(l == a.l) return r>a.r;
        return l<a.l;
    }
} arg[100005];

int main(){
    cin>>n>>l;
    for(int i=0;i<n;++i){
        cin>>arg[i].l>>arg[i].r;
    }
    sort(arg, arg+n);
    if(arg[0].l>0){
        cout<<-1<<endl;
        return 0;
    }
    int right = 0, pos = 0, max_len = 0;
    int ans=0;
    while(true){
        if(right >= l){
            break;
        }
        for(int i=pos;i<n;++i){
            if(arg[i].l<=right && arg[i].r > max_len){
                pos = i;
                max_len = arg[i].r;
            }
            if(arg[i].l>right){
                break;
            }
        }
        if(max_len == right){
            cout<<-1<<endl;
            return 0;
        }
        right = max_len;
        ++ans;
    }

    cout<<ans<<endl;

}

反转区间之后问还有多少逆序对，没时间写。。。

前提条件，对于一个个数位n的数组，正序对个数+逆序对个数 = 总对数= n*（n-1）

大概可能的思路是，归并排序的同时计算逆序对个数，计算到正好是我们需要翻转的那一层，记下一个个数k。

最后算出总的逆序对个数ans之后，之前算的那部分逆序对正好是完全算错的， ans - 2^(m-n)*(2^n*(2^n-1)) + 2*k，中间部分为所有的对数，

看得到多少楼

预处理左边能看到的楼。右边能看到的楼，总的看到的数量是左边可以看到的楼+右边可以看到的楼+1

预处理使用栈，如果发现现在需要入栈的楼比栈顶高了，就将它出栈。直到可以放进去位置，此时可以看到的楼的数量为栈的总大小

腾讯《后台&综合-第一次笔试》题解

字符串压缩解压：

放多少个xxx可以覆盖整条河面 最小区间覆盖问题

反转区间之后问还有多少逆序对，没时间写。。。

看得到多少楼

最少可以休息几天

全站热榜

放多少个xxx可以覆盖整条河面最小区间覆盖问题