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

采用双指针,一个指向每一个word,一个指向s
1. word没扫完,但是s截止了,说明最后一个单词没匹配成功 flag = false
2. 所有word扫完了,但是s没扫完,说明s不匹配所有的单词  flag = false

class Solution {
public:
    bool isPrefixString(string s, vector<string>& words) {
        int i = 0;
        for(auto word: words){
            int j = 0;
            while(i < s.size() && j < word.size() && s[i] == word[j]) i ++ , j ++ ;
            if(j >= word.size()){
                if(i >= s.size()) return true;
                else continue;
            }else return false;
        }
        if(i < s.size()) return false;
        return true;
    }
};

移除石子使总数最小

每次取最大值,然后将其减去1/2倍
取最大值可以用堆实现

class Solution {
public:
    int minStoneSum(vector<int>& piles, int k) {
        priority_queue<int> heap;
        for(auto pile: piles) heap.push(pile);
        while(heap.size() && (k -- )){
            auto t = heap.top(); heap.pop();
            t -= t / 2;
            heap.push(t);
        }
        int res = 0;
        while(heap.size()){
            res += heap.top();
            heap.pop();
        }
        return res;
    }
};

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

对于每个不合法的 左括号
通过一次交换,可以使得当前左括号匹配成功
并且交换过来的括号也可以匹配上一个括号
所以对于每个不合法的左括号, 让前缀和加2, 变成一个合法的括号

class Solution {
public:
    int minSwaps(string s) {
        int sum = 0, cnt = 0;
        for(auto t: s){
            if(t == '[') sum += 1;
            else sum -= 1;
            if(sum < 0) cnt ++ , sum = 1;
        }
        return cnt;
    }
};

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

其实就是对于每个位置,找以其为结尾的最长上升子序列
假设当前下标为 i 值为 val
那么相当于找到在 i 之前的比 val 小或者等的最长的子序列, 加 1 就是 当前的最长的

找 i 之前比 某个值小的所有的最大值, 可以使用线段树, 但是我们发现这个 max 只会递增 或者 不变,
所以可以使用树状数组维护最大值即可

另外, 由于值很大, 数量很少, 所以需要离散化一下

const int N = 1e5 + 10;

class Solution {
public:
    int tr[N], n;
    vector<int> alls;

    int lowbit(int x){ return x & -x; }
    void add(int x, int val){
        for(int i = x;i <= n;i += lowbit(i)) tr[i] = max(tr[i], val);
    }
    int query(int x){
        int res = 0;
        for(int i = x;i;i -= lowbit(i)) res = max(res, tr[i]);
        return res;
    }
    int get(int val){
        return lower_bound(alls.begin(), alls.end(), val) - alls.begin();
    }
    vector<int> longestObstacleCourseAtEachPosition(vector<int>& obstacles) {
        n = obstacles.size();
        alls.clear(); alls.push_back(0);
        for(auto &t: obstacles) alls.push_back(t);
        sort(alls.begin(), alls.end());
        alls.erase(unique(alls.begin(), alls.end()), alls.end());

        memset(tr, 0, sizeof tr);
        // for(int i = 0;i < alls.size();i ++ ) cout << alls[i] << ' ';
        // cout << endl;
        vector<int> dp(n + 1, 0);
        vector<int> res; res.clear();
        for(int i = 0;i < n; ++ i){
            int id = get(obstacles[i]);
            dp[id] = query(id) + 1;
            // cout << id << ' ' << query(id) << endl;
            res.push_back(dp[id]);
            add(id, dp[id]);
        }
        // cout << endl;
        return res;
    }
};