力扣118双周赛

第 118 场双周赛

查找包含给定字符的单词

模拟

class Solution {
public:
    vector<int> findWordsContaining(vector<string>& words, char x) {
        vector<int>res;
        for(int j = 0 ; j < words.size() ; j ++){
            bool f = false;
            string t = words[j];
            for(int i = 0 ; i < t.size() ; i ++){
                if(t[i] == x)f = true;
            }
            if(f)res.push_back(j);
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

最大化网格图中正方形空洞的面积

长和宽分别找最长的连续部分，取最小相乘

class Solution {
public:
    int maximizeSquareHoleArea(int n, int m, vector<int>& hBars, vector<int>& vBars) {
        ranges::sort(hBars);
        ranges::sort(vBars);
        int res = 0 , a = 0 , b = 0 , c = 0;
        int last = -1;
        for(int i = 0 ; i < hBars.size() ; i ++){
            if(last == -1){last = hBars[i] ; a = max(a , 1); c = 1;continue;}
            if(hBars[i] - last == 1){
                c ++;
            }else{
                a = max(a , c);
                c = 1;
            }
            last = hBars[i];
            
        }
        a = max(a , c);
        last = -1;
        for(int i = 0 ; i < vBars.size() ; i ++){
            if(last == -1){last = vBars[i] ; b = max(b , 1); c = 1;continue;}
            if(vBars[i] - last == 1){
                c ++;
            }else{
                b = max(b , c);
                c = 1;
            }
            last = vBars[i];          
        }
        b = max(b , c);
        res = (min(a,b) + 1) * (min(a,b) + 1);
        return res;
    }
};
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

购买水果需要的最少金币数

用dp[i][0]表示买前i个水果且不买第i个水果的最少金币数
用dp[i][1]表示买前i个水果且买第i个水果的最少金币数

class Solution {
public:
    int minimumCoins(vector<int>& prices) {
        int n = prices.size();
        int dp[1005][2];
        //初始化
        for(int i = 0 ; i <= n ; i ++){
            dp[i][0] = dp[i][1] = 999999;
        }
        dp[1][1] = prices[0];
        //dp
        for(int i = 1 ; i < n ; i ++){
            //买第i个
            dp[i + 1][1] = min(dp[i][0] ,dp[i][1]) + prices[i];
            //不买第i个
            for(int j = i; j + j >= i  + 1; j --){
                dp[i + 1][0] = min(dp[i + 1][0] , dp[j][1]);
            }
        }
        return min(dp[n][0],dp[n][1]);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

找到最大非递减数组的长度

单调队列优化DP

class Solution {
public:
/*
    f[i] 表示操作 nums[0] 到 nums[i] 所得到的最长非递减数组的长度
    last[i] 表示在 f[i] 尽量大的前提下，nums[0] 到 nums[i] 操作后的最后一个数的最小值
    s[i]前i个数的前缀和

    f[i] = max(f[j]) + 1
    当s[i] - s[j] >= last[j]时可转移
    s[i] >= s[j] + last[j]
    用单调队列来维护 j，满足从队首到队尾的 j 和 s[j]+last[j] 都是严格递增的。
*/
    int findMaximumLength(vector<int> &nums) {
        int n = nums.size();
        vector<long long> s(n + 1), last(n + 1);
        vector<int> f(n + 1), q(n + 1); // 数组模拟队列
        int front = 0, rear = 0;
        for (int i = 1; i <= n; i++) {
            s[i] = s[i - 1] + nums[i - 1];

            // 1. 去掉队首无用数据（计算转移时，直接取队首）
            while (front < rear && s[q[front + 1]] + last[q[front + 1]] <= s[i]) {
                front++;
            }

            // 2. 计算转移
            f[i] = f[q[front]] + 1;
            last[i] = s[i] - s[q[front]];

            // 3. 去掉队尾无用数据
            while (rear >= front && s[q[rear]] + last[q[rear]] >= s[i] + last[i]) {
                rear--;
            }
            q[++rear] = i;
        }
        return f[n];
    }
};
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

–