讨论/技术交流/🏆 第 226 场力扣周赛/
🏆 第 226 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛】

image.png

3 分 - 盒子中小球的最大数量
4 分 - 从相邻元素对还原数组
5 分 - 你能在你最喜欢的那天吃到你最喜欢的糖果吗?
6 分 - 回文串分割 IV

3
共 78 个回复

Leetcode 第226场周赛题解

Problem A - 盒子中小球的最大数量

因为数据范围比较小,所以暴力枚举即可。

  • 时间复杂度O((H−L)log⁡H)\mathcal{O}((H-L)\log H)。
  • 空间复杂度O(log⁡H)\mathcal{O}(\log H)。
class Solution:
    def countBalls(self, lowLimit: int, highLimit: int) -> int:
        cnt = collections.Counter()
        for i in range(lowLimit, highLimit + 1):
            cnt[sum(map(int, list(str(i))))] += 1
        return max(cnt.values())

思考

如果数据范围达到101810^{18}呢?

可以参考@Heltion的题解。

Problem B - 从相邻元素对还原数组

因为所有数字都不同,所以首尾两个数字只会出现一次,而其他每个数字会出现两次。

因此,我们从任意一个只出现一次的数字开始,用类似拓扑排序的方法就可以还原出整个数组。当然,我们还原出的也可能是原数组的倒序,因为我们并不知道哪一个是头,哪一个是尾。

  • 时间复杂度O(N)\mathcal{O}(N)。
  • 空间复杂度O(N)\mathcal{O}(N)。
class Solution {
public:
    vector<int> restoreArray(vector<vector<int>>& adjacentPairs) {
        unordered_map<int, vector<int>> adj;
        unordered_map<int, int> in_deg;
        for (auto &v : adjacentPairs) {
            adj[v[0]].emplace_back(v[1]);
            adj[v[1]].emplace_back(v[0]);
            in_deg[v[0]]++;
            in_deg[v[1]]++;
        }
        int start;
        for (auto [num, deg] : in_deg) {
            if (deg == 1) {
                start = num;
                break;
            }
        }
        queue<int> q;
        q.emplace(start);
        vector<int> ans;
        unordered_set<int> vis;
        vis.emplace(start);
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            ans.emplace_back(u);
            for (int v : adj[u]) {
                if (!vis.count(v)) {
                    vis.emplace(v);
                    q.emplace(v);
                }
            }
        }
        return ans;
    }
};

思考

如果原数组中存在相同的元素呢?

Problem C - 你能在你最喜欢的那天吃到你最喜欢的糖果吗?

这题题意有些绕人,但只要理解清楚,实现起来还是比较简单的(需要注意一些细节)。

规则二限制了我们必须按顺序吃糖果,同时,因为同一天可以吃不同类型的糖果,所以我们只要预处理计算出糖果数目的前缀和即可。

对于每一个询问,我们考虑两种极端情况:

  • 每天按照上限dailyCapidailyCap_i去吃,也无法把favoriteTypeifavoriteType_i之前的所有糖果吃完(包括刚好吃完的情形,因为我们还需要至少吃一个favoriteTypeifavoriteType_i类型的糖果)。
  • 每天按照下限11去吃,也会在favoriteDayifavoriteDay_i之前把favoriteTypeifavoriteType_i及之前的所有糖果吃完。

这两种情况是无解的,剩下都是有解的情况。

  • 时间复杂度O(N+Q)\mathcal{O}(N+Q),其中NN是糖果的种数,QQ是询问的个数。
  • 空间复杂度O(N)\mathcal{O}(N)。
typedef long long ll;

class Solution {
public:
    vector<bool> canEat(vector<int>& candiesCount, vector<vector<int>>& queries) {
        int q = queries.size(), n = candiesCount.size();
        vector<bool> ans(q);
        vector<ll> pre(n + 1);
        for (int i = 1; i <= n; ++i)
            pre[i] = pre[i - 1] + candiesCount[i - 1];
        for (int i = 0; i < q; ++i) {
            int t = queries[i][0], d = queries[i][1], c = queries[i][2];
            ll before = pre[t];
            
            // Cannot eat type t even if we eat c candies every day.
            if (1LL * c * (d + 1) <= before)
                continue;
            
            // Type t has been eaten out before day d.
            if (d >= pre[t + 1])
                continue;
            
            ans[i] = true;
        }
        return ans;
    }
};

思考

如果再增加一条规则:每天只能吃同一种类型的糖果,应该如何解题呢?

Problem D - 回文串分割 IV

本题的数据范围较小,O(N2)\mathcal{O}(N^2)的复杂度就足够通过。因此,我们只需要:

  • 用简单的中心扩展法以O(N2)\mathcal{O}(N^2)的时间复杂度找出所有回文串。这里用Manacher可以将时间复杂度降到O(N)\mathcal{O}(N),但并没有必要。

  • 枚举第一段和第二段的结束位置,检查是否能分成三个回文串,同样是O(N2)\mathcal{O}(N^2)的时间复杂度。

  • 时间复杂度O(N2)\mathcal{O}(N^2)。

  • 空间复杂度O(N2)\mathcal{O}(N^2)。

class Solution {
public:
    bool checkPartitioning(string s) {
        int n = s.size();
        vector<vector<bool>> palin(n, vector<bool>(n));
        for (int i = 0; i < n; ++i) {
            int l = i, r = i;
            while (l >= 0 && r < n && s[l] == s[r]) {
                palin[l][r] = true;
                l--;
                r++;
            }
            l = i, r = i + 1;
            while (l >= 0 && r < n && s[l] == s[r]) {
                palin[l][r] = true;
                l--;
                r++;
            }
        }
        for (int i = 0; i + 2 < n; ++i)
            for (int j = i + 1; j + 1 < n; ++j) {
                if (palin[0][i] && palin[i + 1][j] && palin[j + 1][n - 1])
                    return true;
            }
        return false;
    }
};

思考

如果题目改成:能否分成kk(k≤10k\leq10)个回文子串呢?

23

第三题是不是很多人都被“第0天“坑了?

13

刚入坑小白纪念一下第一次4AC,虽然被第三题坑了很久。。

5

为了提高手速,赛前特意修剪了指甲,力求手指和键盘配合的好一点,结果完全没效果嘛!

5

第三题有毒

4

能过啊?5000 ms 的我的代码都过了啊?
LeetCode已经是各大切题网站里对Python最温柔的(之一?)了吧

2

如果一模一样的算法,python不能过(对,说的就是第四题),那么请不要在竞赛中提供python的选项好吗

2

中间测试用例出错,推算了半天直到比赛结束我都不知道为啥没过,直到我看到零神的题解才发现第零天

1

马拉车过的

1

菜鸡第一次4题全ac,记录一下

1