Leetcode 第 294 场周赛

Posted on | Edited on | In ,
| 8k | 1:06

上周的周赛...

这周退化成单题选手了😂

2278. Percentage of Letter in String

Analysis

第一个题比较简单，统计下次数，再算一下就可以了。

Code

这是当时提交的代码：

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int percentageLetter(string s, char letter) {
        int cnt = 0;
        for(char c: s) {
            if(c == letter) cnt++;
        }
        return cnt * 100 / s.length();
    }
};

2280. Minimum Lines to Represent a Line Chart

Analysis

这是第三个题，但是是自己第二个提交的题。
题意不难理解，就是找出整个折线图中所有斜率不同的线段。
当时的思路是，用一个变量统计线段数，挨个算相邻点构成的直线的斜率，相同就忽略，不同就加 1。本来一开始是打算直接用 set 的，但是后来想到，斜率相等但不是相邻的线段，是不同的两条线段。

Code

这是当时提交的代码，死在 58 个用例了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int minimumLines(vector<vector<int>>& stockPrices) {
        int size = stockPrices.size();
        if(size == 1) return 0;
        int cnt = 1;
        int prek = (stockPrices[1][1] - stockPrices[0][1]) / (stockPrices[1][0] - stockPrices[0][0]);
        int curk;
        sort(stockPrices.begin(), stockPrices.end());
        for(int i = 2; i < size; i++) {
            curk = (stockPrices[i][1] - stockPrices[i - 1][1]) / (stockPrices[i][0] - stockPrices[i - 1][0]);
            if(curk != prek) cnt++;
            prek = curk;
        }
        return cnt;
    }
};

上面的代码有点小问题，那就是在开始计算之前，就应该排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int minimumLines(vector<vector<int>>& stockPrices) {
        int size = stockPrices.size();
        if(size == 1) return 0;
        sort(stockPrices.begin(), stockPrices.end());
        int cnt = 1;
        int prek = (stockPrices[1][1] - stockPrices[0][1]) / (stockPrices[1][0] - stockPrices[0][0]);
        int curk;
        for(int i = 2; i < size; i++) {
            curk = (stockPrices[i][1] - stockPrices[i - 1][1]) / (stockPrices[i][0] - stockPrices[i - 1][0]);
            if(curk != prek) cnt++;
            prek = curk;
        }
        return cnt;
    }
};

换了下位置，又被卡在第 62 个用例了。
看了下题解，发现这是个精度问题，直接用除法会损失小数，造成本不该相等的斜率相等了，这样就漏解了。将int换成double会被卡在第 80 个用例。幸运的是，C++ 提供了long double这种 16 个字节的基本类型，就可以直接用除法了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int minimumLines(vector<vector<int>>& stockPrices) {
        int size = stockPrices.size();
        if(size == 1) return 0;
        sort(stockPrices.begin(), stockPrices.end());
        int cnt = 1;
        long double prek = (long double)(stockPrices[1][1] - stockPrices[0][1]) / (stockPrices[1][0] - stockPrices[0][0]);
        long double curk;
        for(int i = 2; i < size; i++) {
            curk = (long double)(stockPrices[i][1] - stockPrices[i - 1][1]) / (stockPrices[i][0] - stockPrices[i - 1][0]);
            if(curk != prek) cnt++;
            prek = curk;
        }
        return cnt;
    }
};

但这个题，还可以从判断 3 点是否共线的角度思考，也就是向量的叉积。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int minimumLines(vector<vector<int>>& stockPrices) {
        int size = stockPrices.size();
        if(size == 1) return 0;
        sort(stockPrices.begin(), stockPrices.end());
        int cnt = 1;
        for(int i = 2; i < size; i++) {
            long long x1 = stockPrices[i][0] - stockPrices[i - 1][0], y1 = stockPrices[i][1] - stockPrices[i - 1][1];
            long long x2 = stockPrices[i - 1][0] - stockPrices[i - 2][0], y2 = stockPrices[i - 1][1] - stockPrices[i - 2][1];
            if(y1 * x2 != y2 * x1) cnt++;
        }
        return cnt;
    }
};

当然，判断 3 点是否共线还可以计算这 3 个点组成的三角形面积是否为 0，而三角形的面积计算公式既可以用向量，也可以用海伦凯勒公式。

2279. Maximum Bags With Full Capacity of Rocks

Analysis

这是第二个题，一看就是背包问题，基本没做过类似的题，就直接弃了。上一次做的时候，是春赛的第二题，这次得把两个题都搞定。
仔细一看这个题，实际上是个贪心的题目。为了得到装满石头的背包的最大数量，最开始放石头的背包一定是快装满的背包。

Code

没想到回过神来想到的第一种解法是重新构造结构体在排序...

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
class Solution {
public:
    struct package{
        long long remain, size, now;
        package(): remain(0), size(0), now(0){}
    };
    int maximumBags(vector<int>& capacity, vector<int>& rocks, int additionalRocks) {
        int n = capacity.size();
        package pak[n];
        for(int i = 0; i < n; i++) {
            pak[i].size = capacity[i];
            pak[i].now = rocks[i];
            pak[i].remain = pak[i].size - pak[i].now;
        }
        sort(pak, pak + n, [](package a, package b) { return a.remain < b.remain; });
        int cnt = 0;
        for(int i = 0; i < n; i++) {
            if(pak[i].remain != 0) {
                additionalRocks -= pak[i].remain;
                if(additionalRocks >= 0) cnt++;
                else break;
            } else if(pak[i].remain == 0) cnt++;
        }
        return cnt;
    }
};

实际上用 multiset 就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int maximumBags(vector<int>& capacity, vector<int>& rocks, int additionalRocks) {
        multiset<int> remains;
        int n = capacity.size();
        for(int i = 0; i < n; i++) {
            remains.insert(capacity[i] - rocks[i]);
        }
        int cnt = 0;
        for(auto &i: remains) {
            if(i != 0) {
                additionalRocks -= i;
                if(additionalRocks >= 0) cnt++;
                else break;
            } else if(i == 0) cnt++;
        }
        return cnt;
    }
};

使用 multiset 容器的时间、空间消耗都很大，不如直接换成 vector，然后排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int maximumBags(vector<int>& capacity, vector<int>& rocks, int additionalRocks) {
        vector<int> remains;
        int n = capacity.size();
        for(int i = 0; i < n; i++) {
            remains.push_back(capacity[i] - rocks[i]);
        }
        sort(remains.begin(), remains.end());
        int cnt = 0;
        for(auto &i: remains) {
            if(i != 0) {
                additionalRocks -= i;
                if(additionalRocks >= 0) cnt++;
                else break;
            } else if(i == 0) cnt++;
        }
        return cnt;
    }
};

果然，快多了...
这么一看的话，这个题当时是可以做出来的，没经过仔细思考，直接认为这个题需要用 dfs 来求解...大意失荆州了啊~

2281. Sum of Total Strength of Wizards

Analysis

题意不难理解，就是算出所有子数组最小值与对应的和的积然后再相加。

参考思路：计算每个数字作为最小值的贡献。

如这篇题解所说先做一下 907 比较好。仔细拆分下来这个题实际上是前缀和 + 单调栈 + 数学，不过自己能单独做出来，估计得很长一段时间后了。

Code

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
class Solution {
public:
    const int mod = 1e9 + 7;
    int totalStrength(vector<int>& strength) {
        int n = strength.size();
        stack<int> st;
        vector<int> left(n, -1), right(n, n);
        for(int i = 0; i < n; i++) {
            while(!st.empty() && strength[st.top()] > strength[i]) {
                right[st.top()] = i;
                st.pop();
            }
            if(!st.empty()) left[i] = st.top();
            st.push(i);
        }
        vector<int> psum = strength;
        for(int i = 1; i < n; i++) {
            psum[i] = (psum[i] + psum[i - 1]) % mod;
        }
        vector<int> ppsum = psum;
        for(int i = 1; i < n; i++) {
            ppsum[i] = (ppsum[i] + ppsum[i - 1]) % mod;
        }
        auto f = [&](int l, int r) {
            if(r < 0) return 0;
            if(l < 0) return ppsum[r];
            return (ppsum[r] - ppsum[l] + mod) % mod;
        };
        int ret = 0;
        for(int i = 0; i < n; i++) {
            int l = left[i] + 1, r = right[i] - 1;
            long long sleft = 1ll * f(l - 2, i - 1) * (r - i + 1) % mod;
            long long sright = 1ll * f(i - 1, r) * (i - l + 1) % mod;
            ret += 1ll * strength[i] * (((sright - sleft) + mod) % mod) % mod;
            ret %= mod;
        }
        return ret;
    }
};

Summary

这次周赛大意了，本来第二个题可以做的，结果把时间都花在第三个题上了（大致思路是对的，但没做出来）。第二题的主要问题是，搞错题目类型了，然后就放掉了...
第三题其实是每日一题见过的类似题目，但是升级到中等题就做不出来了...
第四题是个很不错的单调栈 + 前缀和的综合题，花时间把这个题吃透应该能有所值。

总之，这周的周赛有点亏😭。

Buy me a coffee ? :)
0%