Leetcode 第 78 场双周赛

Posted on | Edited on | In ,
| 6.9k | 58 mins.

上上周的双周赛~

过 2 个题就谢天谢地了😂...

2269. Find the K-Beauty of a Number

Analysis

题目意思稍微有点绕，当时做的时候感觉中文的题干好像读不通顺😂。总之，理解起来花了点时间...
首先要把 num 当作字符串，然后再找出字符串 num 中长度为 k 且能整除 num 的子串，返回这些子串的个数。
然后还有两个限制条件：

  1. 允许有前缀 0。
  2. 0 不能整除任何值。

第一个条件看示例很容易明白，第二个也是常识。

Code

竞赛做的时候，这个题 WA 了两次，一是题目没理解清楚就开始做了，二是有点着急了，写好了就直接提交，没有自己编个样例试试...
这是当时提交通过的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int divisorSubstrings(int num, int k) {
        string str = to_string(num);
        int len = str.length(), ret = 0;
        for(int i = 0; i <= len - k; i++) {
            string tmp = str.substr(i, k);
            int t = stoi(tmp);
            if(t != 0 && num % t == 0) ret++;
        } 
        return ret;
    }
};

不管怎么说，WA 两次真是不应该。
另外，这个题也可以从数学角度思考，依次从 num 的末尾取下 k 位数字组成整数进行判断即可。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int divisorSubstrings(int num, int k) {
        long long ret = 0, mask = pow(10, k);
        for(int x = num; x >= mask / 10; x /= 10) {
            int tmp = x % mask;
            if(tmp != 0 && num % tmp == 0) ret++;
        }
        return ret;
    }
};

2270. Number of Ways to Split Array

Analysis

这个题一看就是前缀和的题目...可惜又 WA 了一次...
WA 的原因是前缀和数组用的int，应该要用long long。实际上，这是第二次在周赛上做前缀和的题目犯这个错误了...
思路就是算出前缀和，然后依次判断即可。

Code

这是当时提交通过的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int waysToSplitArray(vector<int>& nums) {
        int size = nums.size();
        vector<long long> prefixsum(size);
        int ret = 0;
        prefixsum[0] = nums[0];
        for(int i = 1; i < size; i++) {
            prefixsum[i] = prefixsum[i - 1] + nums[i];
        }
        for(int i = 0; i < size; i++) {
            if(i < size - 1 && prefixsum[i] >= (prefixsum[size - 1] - prefixsum[i])) {
                ret++;
                cout << prefixsum[i] << ' ' << i << endl;
            }
        }
        return ret;
    }
};

虽然可以通过，但是代码思路不够清晰，改一下：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int waysToSplitArray(vector<int>& nums) {
        int size = nums.size(), ret = 0;
        long long left = 0, right = accumulate(nums.begin(), nums.end(), 0LL);
        for(int i = 0; i < size - 1; i++) {
            left += nums[i];
            right -= nums[i];
            if(left >= right) ret++;
        }
        return ret;
    }
};

2271. Maximum White Tiles Covered by a Carpet

Analysis

题意很清晰，返回盖住最多的瓷砖数目。换成数学语言就是，如何让更多的符合条件的数（瓷砖）落在区间长度为 carpetlen 的区间中。
这个题想了挺久的，理解清楚题目意思后，就感觉这是个区间贪心的问题，但是没做过类似的问题...还是题做少了。

Code

这个题的思路是排序 + 滑动窗口 + 贪心：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int maximumWhiteTiles(vector<vector<int>>& tiles, int carpetLen) {
        sort(tiles.begin(), tiles.end());
        long long now = 0, ans = 0;
        for(int i = 0, j = 0; i < tiles.size(); i++) {
            while(j < tiles.size() && tiles[j][1] + 1 - tiles[i][0] <= carpetLen) {
                now += tiles[j][1] - tiles[j][0] + 1;
                j++;
            }
            if(j < tiles.size()) ans = max(ans, now + max(0, tiles[i][0] + carpetLen - tiles[j][0]));
            else ans = max(ans, now);
            now -= tiles[i][1] - tiles[i][0] + 1;
        }
        return ans;
    }
};

大致过程是枚举瓷砖区间，不超过毯子长度的情况下，将尽可能多的瓷砖放入毯子下，整个窗口的大小就是毯子的长度。当最后一块瓷砖只能部分放入毯子下时，需要单独加上这部分长度。
上面的思路是从瓷砖区间的右端点来思考的，也可以从瓷砖区间的左端点来思考：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int maximumWhiteTiles(vector<vector<int>>& tiles, int carpetLen) {
        sort(tiles.begin(), tiles.end());
        long long now = 0, ans = 0, left = 0;
        for(auto &v: tiles) {
            now += v[1] - v[0] + 1;
            while(tiles[left][1] < v[1] - carpetLen + 1) {
                now -= tiles[left][1] - tiles[left][0] + 1;
                left++;
            }
            ans = max(ans, now - max(v[1] - carpetLen + 1 - tiles[left][0], 0));
        }
        return ans;
    }
};

虽然这个思路简洁一些，但是感觉要难想一些。

2272. Substring With Largest Variance

Analysis

题目还算直接，就是求子串中出现次数最多与最少的字符的次数差。
很容易想到暴力解法，枚举每一个子串，再统计其中出现的次数，作差即可。借助 map，暴力解法的时间复杂度应该是 $O(n^2log\Sigma)$，数据范围是 $10^4$，多半是要超时。
实际上，当时看到这个题目第一反应就是字符串和 dp 的结合题，不过还是把暴力的思路写下来了。

Code

这是当时提交的暴力代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int largestVariance(string s) {
        int len = s.length();
        int maxlv = INT_MIN;
        for(int i = 0; i < len; i++) {
            unordered_map<char, int> cnt;
            for(int j = i; j < len; j++) {
                cnt[s[j] - 'a']++;
                int maxappear = INT_MIN, minappear = INT_MAX;
                for(auto &[c, i]: cnt) {
                    if(i > maxappear) maxappear = i;
                    if(i < minappear) minappear = i;
                }
                maxlv = max(maxlv, maxappear - minappear);
            }
        }
        return maxlv;
    }
};

当时没有借助 map，用的是 unordered_map，时间复杂度是 $O(n^2\Sigma)$，所以还是得想办法用 dp。
看了下大佬的题解，发现这个题的难点在问题的理解与转化上。
按照题意，最大波动值只有 2 个字符（一个出现的次数最多，一个出现的次数最少）决定，至于是哪两种，没办法直接确定，所有的可能共有 $26 \times 25 = 650$ 种。假设枚举到了组合（a，b）（并不是'a'和b），在子串中，将 a 看作是 1，b 看作是 -1，其他字符看作 0，问题就转化为求这个数组最大的连续子列和。
在整个枚举的过程中，还需要注意字符 a 和 b 都必须出现在子字符串中，不能将只包含字符 a 或 b 的子字符串作为答案。同时，用一个变量 diff 来记录字符 a 和字符 b 出现次数之差，初始值为 0，再用另一个变量 diff_with_b 来记录 b 是否出现和 a、b 出现次数之差，初始化为负无穷。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int largestVariance(string s) {
        int ans = 0;
        for(char a = 'a'; a <= 'z'; a++) {
            for(char b = 'a'; b <= 'z'; b++) {
                if(a == b) continue;
                int diff = 0, diff_with_b = -s.length();
                for(char c: s) {
                    if(c == a) {
                        diff++;
                        diff_with_b++;
                    } else if(c == b) {
                        diff_with_b = --diff;
                        diff = max(diff, 0);
                    }
                    ans = max(ans, diff_with_b);
                }
            }
        }
        return ans;
    }
};

将 $s[i]$ 当作字符 a 和 b，还可以进一步优化时间复杂度：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int largestVariance(string s) {
        int ans = 0;
        int diff[26][26] = {0}, diff_with_b[26][26];
        memset(diff_with_b, 0x80, sizeof(diff_with_b));
        for(char ch: s) {
            ch -= 'a';
            for(int i = 0; i < 26; i++) {
                if(i == ch) continue;
                diff[ch][i]++;
                diff_with_b[ch][i]++;
                diff_with_b[i][ch] = --diff[i][ch];
                diff[i][ch] = max(diff[i][ch], 0);
                ans = max(ans, max(diff_with_b[ch][i], diff_with_b[i][ch]));
            }
        }
        return ans;
    }
};

这个优化有点没看懂...

Summary

得整个专题训练下...

Buy me a coffee ? :)
0%