image-20210626235353301

GG

5780. 删除一个元素使数组严格递增

暴力一下，

枚举每个元素删除后的数据是不是严格递增的， 数据范围是10001000. 平凡才1e61e6没问题的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    
    bool f(vector<int>& a) {
        for(int i=1;i<a.size();i++) {
            if(a[i] <= a[i-1]) return false;
        }
        return true;
    }    
    bool canBeIncreasing(vector<int>& nums) {
        int n = nums.size();
        vector<int> a;
        for(int i = 0;i<n;i++) {
            a.clear();
            for(int j=0;j<n;j++) {
                if(i == j) continue;
                a.push_back(nums[j]);
            }
            if(f(a)) return true;
        }
            
        return false;
    }
};

5781. 删除一个字符串中所有出现的给定子字符串

开始还想要不要有啥骚操作， 后面觉得暴力没啥问题，然后暴力就过了，，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    string removeOccurrences(string s, string part) {
        int lp = part.size();
        string ss;
        int found;
        while((found = s.find(part)) != string::npos) {
            ss.clear();
            for(int i = 0; i<s.size(); i++) {
                if(found <= i && i< found + lp) continue;
                ss+=s[i];
            }
            s=ss;
        }
        return s;
    }
};

5782. 最大子序列交替和

简单dp？吧，

dp[0] 表示以长度为偶数的子序列的最大值。

dp[1] 表示以长度为奇数的子序列的最大值。

遍历每个数字，计算当前这个数字为奇数或者偶数的最大值， 奇数就是dp[0]减去它，偶数就是d[1]加上它。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    long long maxAlternatingSum(vector<int>& nums) {
        vector<long long> dp(2, 0), dp2(2, 0);
        dp[0] = dp2[0] = -1e9;
        for(auto a: nums) {
            dp2[1] = max(dp[0] - a, dp[1]);
            dp2[0] = max(dp[1] + a, dp[0]);
            
            dp = dp2;
        }
        return max(dp[0], dp2[1]);
    }
};

5783. 设计电影租借系统

模拟题

我是用了一个 map[(shop, movie)] = price，其中price的政府表示借出还是没借出。借出为负，没借出为正。

用一个priority_queue<tuple<price，shop，movie >> 的小顶堆维护借出的。

用n个priority_queue<tuple<price，shop>>的小顶堆维护没借出这个电影的商店。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
class MovieRentingSystem {
public:
    map<tuple<int,int>, int> vis;  // <shop, movie> 没借出+， 借出-;
    priority_queue<tuple<int,int,int>, vector<tuple<int,int,int>>, greater<tuple<int,int,int>>> jc; // price，shop，movie 
    priority_queue<tuple<int,int>, vector<tuple<int,int>>, greater<tuple<int,int>>> wj[300005]; // 【movie】 price，shop
    
    MovieRentingSystem(int n, vector<vector<int>>& entries) {
        for(auto &entry: entries) {
            int shop = entry[0], movie = entry[1], price = entry[2];
            
            vis[tuple(shop, movie)] = price;  // 唯一 键
            wj[movie].push(tuple(price, shop));
        }
    }
    
    vector<int> search(int movie) {
        vector<int> ans;

        vector<tuple<int,int>> tmp;
        map<tuple<int,int>, bool> book;

        int cnt = 0;
        while(cnt < 5 && !wj[movie].empty()) {
            auto [price, shop] = wj[movie].top(); wj[movie].pop();
            if(vis[tuple(shop, movie)] < 0 || book[tuple(shop, movie)] == true) {
                continue;
            }
            ++cnt;
            book[tuple(shop, movie)] = true;
            tmp.push_back(tuple(price, shop));
            ans.push_back(shop);
        }
        
        for(auto t: tmp) {
            wj[movie].push(t);
        }
        
        return ans;
    }
    
    void rent(int shop, int movie) {
        int price = vis[tuple(shop, movie)];  //这时候一定是 正数
        vis[tuple(shop, movie)] = -price;

        jc.push(tuple(price, shop, movie));
    }
    
    void drop(int shop, int movie) {
        int price = vis[tuple(shop, movie)];  //这时候一定是 负数
        vis[tuple(shop, movie)] = -price;
        
        wj[movie].push(tuple(-price, shop));
    }
    
    vector<vector<int>> report() {
        vector<vector<int>> ans;
        vector<int> t(2);
        map<tuple<int,int>, bool> book;
        
        vector<tuple<int,int,int> > tmp;
        int cnt = 0;
        while(cnt < 5 && !jc.empty()) {
            auto [price, shop, movie] = jc.top(); jc.pop();
            if(vis[tuple(shop, movie)] > 0 || book[tuple(shop, movie)] == true) {
                continue;
            }
            ++cnt;
            tmp.push_back(tuple(price, shop, movie));
            book[tuple(shop, movie)] = true;
            t[0] = shop, t[1] = movie;
            ans.push_back(t);
        }
        for(auto tt: tmp) {
            jc.push(tt);
        }
        
        return ans;
    }
};

/**
 * Your MovieRentingSystem object will be instantiated and called as such:
 * MovieRentingSystem* obj = new MovieRentingSystem(n, entries);
 * vector<int> param_1 = obj->search(movie);
 * obj->rent(shop,movie);
 * obj->drop(shop,movie);
 * vector<vector<int>> param_4 = obj->report();
 */