力扣周赛253题解

吐槽：大家都挺能卷的，打不过，打不过…

T1. 检查字符串是否为数组前缀

暴力即可：

class Solution {
public:
    bool isPrefixString(string s, vector<string>& words) {
        string now="";
        for(auto v:words){
            if(now==s){
                return true;
            }
            now+=v;
        }
        if(now==s) return true;
        return false;
    }
};

T2.移除石子使总数最小

贪心，每次选择石子数目最多的石子堆执行操作，用大根堆维护，时间复杂度为$O(klog(n))$。

class Solution {
public:
    int minStoneSum(vector<int>& piles, int k) {
        priority_queue<int> q;
        for(int v:piles){
            q.push(v);
        }
        for(int test=1;test<=k;test++){
            int u=q.top();q.pop();
            u-=u/2;
            q.push(u);
        }
        int ans=0;
        while(!q.empty()){
            ans+=q.top();q.pop();
        }
        return ans;
    }
};

T3.使字符串平衡的最小交换次数

计算该字符串的balance，由于’[‘和’]’的数目相同，因此剩下的失配的也一定相同。

剩下的适配的子序列可以写成如下形式：

balance个]后面balance个[

对于每次交换，实际上就是把[变成]，把]变成[，显然答案为$\lceil\frac{balance}{2}\rceil$。

class Solution {
public:
    int minSwaps(string s) {
        int balance=0;
        for(char c:s){
            if(c=='[') balance++;
            else{
                if(balance) --balance;
            }
        }
        return (balance+1)/2;
    }
};

T4. 找出到每个位置为止最长的有效障碍赛跑路线

题意就是对于每个$i$，求以$a_{i}$结尾的最长非递减上升子序列的长度。

只需要把经典的非递减上升子序列的求法中二分INF改成二分$a_{i}+1$即可。时间复杂度为$O(nlog(n))$。

const int INF = 1e9+10;
class Solution {
public:
    vector<int> longestObstacleCourseAtEachPosition(vector<int>& a) {
        int n=(int)a.size();
        vector<int> dp(n,INF);
        vector<int> ans(n);
        for(int i=0;i<n;i++){
            int x=upper_bound(dp.begin(),dp.end(),a[i])-dp.begin();
            dp[x]=a[i];
            ans[i]=lower_bound(dp.begin(),dp.end(),a[i]+1)-dp.begin();
        }
        return ans;
    }
};