14、重构字符串

class Solution {
public:
    string reorganizeString(string s) {
        int hash[26]={0};
        for(auto c:s) hash[c-'a']++;
        auto cmp = [&](const char &a, const char &b){
            return hash[a-'a'] < hash[b-'a'];
        };
        priority_queue,decltype(cmp)> q(cmp);
        for(int i=0;i<26;i++) {
            if(hash[i] > (s.size()+1)/2) return "";
            else if(hash[i]){
                q.push('a'+i);
            }
        }
        string ans; char t1,t2;
        while(q.size()>1){
            t1 = q.top();q.pop();
            t2 = q.top();q.pop();
            hash[t1-'a']--; hash[t2-'a']--;
            ans+=t1; ans+=t2;
            if(hash[t1-'a']) q.push(t1);
            if(hash[t2-'a']) q.push(t2);
        }
        if(q.size()) ans+=q.top(), q.pop();
        return ans;
    }
};

15、单调递增的数字

class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        int dig[10]={0};
        int cur=0,pos=0,ans=0;
        while(n){dig[cur++] = n%10; n/=10;}
        for(int i=1;idig[i-1]){
                dig[i]--;
                pos=i;
            }
        }
        while(pos) {dig[pos-1]=9; pos--;}
        while(cur) {ans = ans*10 + dig[cur-1]; cur--;}
        return ans;
    }
};

16、柠檬水找零

class Solution {
public:
    bool lemonadeChange(vector& bills) {
        int five = 0, ten = 0;
        for (int i : bills) {
            if (i == 5) five++;
            else if (i == 10) {five--; ten++;}
            else if (ten > 0) {ten--; five--;} 
            else five -= 3;
            if (five < 0) return false;
        }
        return true;
    }
};

17、可以到达的最远建筑

class Solution {
public:
    int furthestBuilding(vector& hs, int bs, int ls) {
        priority_queue q;
        int t=0;
        for(int i=hs.size()-1;i>0;i--) hs[i]-=hs[i-1];
        int i=1;
        for(;ibs) return i-1;
            if(ls) {
                if(t+hs[i]<=bs) {t+=hs[i]; q.push(hs[i]);}
                else{
                    if(q.size() && q.top()& heights, int bricks, int ladders) {
        priority_queue, greater> q;
        for (int i = 1; i < heights.size(); i++) {
            if (heights[i] <= heights[i - 1]) continue;
            int d = heights[i] - heights[i - 1];
            if (ladders > 0) {
                ladders--; q.push(d); // 有梯子时先考虑梯子
            } else {
                if (!q.empty() && d > q.top()) {
                    if (bricks < q.top())  return i - 1;
                    bricks -= q.top();
                    q.pop();
                    q.push(d);
                } else {
                    if (bricks < d)  return i - 1;
                    bricks -= d;
                }
            }
        }
        return n - 1;
    }
};

18、销售价值减少的颜色球

#define LL long long

class Solution {
public:
    int maxProfit(vector& inventory, int orders) {
        const int mod = 1000000007;
        const int n = inventory.size() + 1;

        inventory.push_back(0);
        sort(inventory.begin(), inventory.end());

        LL ans = 0;
        for (int i = n - 1; i >= 1; i--) {
            if (orders >= (LL)(inventory[i] - inventory[i - 1]) * (n - i)) {
                orders -= (inventory[i] - inventory[i - 1]) * (n - i);

                int s = inventory[i - 1] + 1, t = inventory[i], num = t - s + 1;
                ans = (ans + (LL)(s + t) * num / 2 % mod * (n - i)) % mod;
            } else {
                int num = orders / (n - i);
                int t = inventory[i], s = t - num + 1;
                ans = (ans + (LL)(s + t) * num / 2 % mod * (n - i)) % mod;

                int r = orders % (n - i);
                ans = (ans + (LL)(r) * (t - num)) % mod;
                break;
            }
        }
        return ans;
    }
};

19、找出最具竞争力的子序列

class Solution {
public:
    vector mostCompetitive(vector& nums, int k) {
        const int n = nums.size();
        deque q;
        vector ans;

        for (int i = 0; i < n; i++) {
            while (!q.empty() && nums[i] < nums[q.back()])
                q.pop_back();
            q.push_back(i);
            if (i >= n - k) {
                ans.push_back(nums[q.front()]);
                q.pop_front();
            }
        }
        return ans;
    }
};

// 使用vector模拟队列
class Solution {
public:
    vector mostCompetitive(vector& nums, int k) {
        const int n = nums.size();
        vector ans;

        for (int i = 0; i < n; i++) {
            while (!ans.empty() && ans.size() + n - i > k && nums[i] < ans.back())
                ans.pop_back();

            if (ans.size() < k)
                ans.push_back(nums[i]);
        }
        return ans;
    }
};

[Go Back~](# LeetCode题解)

section14-1: 区间贪心

1、无重叠区间【最大不相交区间数量】

class Solution {
public:
    int eraseOverlapIntervals(vector>& intervals) {
        int ans=0;
        auto cmp=[&](const vector&a, const vector&b){
            if(a[1]==b[1]) return (a[1]-a[0])<(b[1]-b[0]);
            else return a[1]=last) last = t[1];
            else ans++;
        }
        return ans;
    }
};

2、用最少数量的箭引爆气球【区间选点】

class Solution {
public:
    int findMinArrowShots(vector>& points) {
        auto cmp = [&](const vector&a, const vector&b){
            return a[1]= s){
                s = max(s,points[i][0]);
                e = min(e,points[i][1]);
            }else{
                ans++;
                s = points[i][0];
                e = points[i][1];
            }
        }
        return ans+1;
    }
};

3、视频拼接【区间覆盖】

class Solution {
public:
    int videoStitching(vector>& clips, int time) {
        auto cmp = [&](const vector&a, const vector&b){
            return a[0]s) return -1;
            int e = 0;
            while(i=time) return ans;
        }
        return -1;
    }
};

[Go Back~](# LeetCode题解)