第 431 场周赛 - 力扣（LeetCode）

Q1 最长乘积等价子数组

模拟即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    typedef long long ll;
    int maxLength(vector<int>& nums) {
        ll n = nums.size(), ans = 1;
        for(int i = 0; i < n ; i++){
            ll a = nums[i], b = nums[i], c = nums[i];
            ll t = i;
            for(int j = i + 1; j < n; j++) {
                if(a > INT_MAX) break;
                a = a * nums[j];
                b = gcd(b, nums[j]);
                c = lcm(c, nums[j]);
                if(a == (b * c)) {
                    t = j;
                }
            }
            ans = max(ans, t - i + 1);
        }
        return ans;
    }
};

Q2 计算字符串的镜像分数

用一个大小为26的数组，每个元素是一个栈，遍历模拟一边即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    long long calculateScore(string s) {
        long long ans = 0;
        stack<int> q[26];
        int n = s.size();
        for(int i = 0; i < n; i++) {
            if(q[25 - (s[i] - 'a')].size()){
                ans += (i - q[25 - (s[i] - 'a')].top());
                q[25 - (s[i] - 'a')].pop();
            }
            else q[s[i] - 'a'].push(i);
        }
        return ans;
    }
};

Q3 收集连续 K 个袋子可以获得的最多硬币数量

贪心 + 滑动窗口

前置题目毯子覆盖的最多白色砖块数

前置题目思路：贪心思路：实际上，毯子右端点放在一段瓷砖中间，是不如直接放在这段瓷砖右端点的（因为从中间向右移动，能覆盖的瓷砖数不会减少），所以可以枚举每段瓷砖的右端点来摆放毯子的右端点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int maximumWhiteTiles(vector<vector<int>>& tiles, int carpetLen) {
        //按照左端点排序
        ranges::sort(tiles, {}, [&](auto& t){return t[0];});

        int ans = 0, cover = 0, l = 0;
        for(auto tile : tiles){
            int tl = tile[0], tr = tile[1];
            cover += (tr - tl + 1);
            // 滑动窗口，l太小了，这个区间中已经不存在这个左端点了
            while(tiles[l][1] + carpetLen - 1 < tr) {
                cover -= (tiles[l][1] - tiles[l][0] + 1);
                l++;
            }
            // 减去左端点所在区间，左端点左边的瓷砖
            int uncover = max(0, (tr - carpetLen + 1 - tiles[l][0]));
            ans = max(ans, cover - uncover);
        }
        return ans;
    }
};

本题思路，与上述类似，是加权的， 所以如果左边区间的权值大于右边就不能简单的对齐右边来滑动窗口了，正着反着都来一遍就可以了

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
class Solution {
    long long maximumWhiteTiles(vector<vector<int>>& tiles, int carpetLen) {
        long long ans = 0, cover = 0, l = 0;
        for(auto tile : tiles){
            long long tl = tile[0], tr = tile[1], v = tile[2];
            cover += (tr - tl + 1) * v;
            while(tiles[l][1] + carpetLen - 1 < tr) {
                cover -= (long long)(tiles[l][1] - tiles[l][0] + 1) * tiles[l][2];
                l++;
            }
            long long uncover = max(0LL, (tr - carpetLen + 1 - tiles[l][0]) * tiles[l][2]);
            ans = max(ans, cover - uncover);
        }
        return ans;
    }
public:
    typedef long long ll;
    long long maximumCoins(vector<vector<int>>& coins, int k) {
        ranges::sort(coins, {}, [&](auto& c) {return c[0];});
        long long ans = maximumWhiteTiles(coins, k);
		
        // 反着来一遍，reverse一下，并且加上负号。
        reverse(coins.begin(), coins.end());
        for(auto& t : coins) {
            int tmp = t[0];
            t[0] = -t[1];
            t[1] = -tmp;
        }
        return max(ans, maximumWhiteTiles(coins, k));

    }
};