讨论/技术交流/🏆 第 228 场力扣周赛/
🏆 第 228 场力扣周赛
2
共 52 个回复

Leetcode 第228场周赛题解

Problem A - 生成交替二进制字符串的最少操作数

我们或者将字符串变为0101...0101,或者将字符串变成1010...1010。所以,我们统计奇数和偶数位置上0和1的数目,然后选择两种方案中较优的那个即可。

  • 时间复杂度O(N)\mathcal{O}(N)。
  • 空间复杂度O(1)\mathcal{O}(1)。
class Solution:
    def minOperations(self, s: str) -> int:
        oz = 0
        oo = 0
        ez = 0
        eo = 0
        for i, c in enumerate(s):
            if i % 2 == 0:
                if c == '0':
                    ez += 1
                else:
                    eo += 1
            else:
                if c == '0':
                    oz += 1
                else:
                    oo += 1
        return min(oz + eo, ez + oo)

Problem B - 统计同构子字符串的数目

找出每一个最长的由相同字符组成的子串,假设其长度为LL,则其对答案的贡献为L(L+1)2\frac{L(L+1)}{2}。

注意最后的结果要取模。

  • 时间复杂度O(∣S∣)\mathcal{O}(|S|)。
  • 空间复杂度O(1)\mathcal{O}(1)。
class Solution:
    def countHomogenous(self, s: str) -> int:
        x = '$'
        cnt = 0
        ans = 0
        for c in s + '#':
            if c == x:
                cnt += 1
            else:
                ans += cnt * (cnt + 1) // 2
                x = c
                cnt = 1
        return ans % 1000000007

Problem C - 袋子里最少数目的球

可能第一反应会考虑每次贪心选取球最多的那个袋子将其分为两半。但本题的操作次数最多可以达到10910^9,逐次进行模拟显然是不现实的;另一方面,样例1(只有一个袋子,里面装着9个球,最多操作2次)也已经说明这一贪心策略是不对的。如果我们采用贪心方法,得到的结果会是[9]→[5,4]→[4,3,2][9]\rightarrow[5,4]\rightarrow[4,3,2],最后的代价是44,而按照样例中的方法[9]→[6,3]→[3,3,3][9]\rightarrow[6,3]\rightarrow[3,3,3],最后的代价是33。

不妨考虑下面这个问题:

如果要求最后的代价不超过KK,我们最少需要操作多少次?

我们可以先考虑只有一个袋子的情形。假设袋子里有M>KM>K个球,为了使代价不超过KK,同时操作次数尽可能小,我们应当每次分出KK个球。这样,我们一共需要分⌊M−1K⌋\lfloor\frac{M-1}{K}\rfloor次。

扩展到NN个袋子的情形:因为袋子之间没有相互影响,我们只要把每个袋子的结果累加起来即可,也即总共需要∑⌊MiK⌋\sum\lfloor\frac{M_i}{K}\rfloor次。

解决了这一问题,我们就可以利用二分答案的方法来求解原问题了。

  • 时间复杂度O(Nlog⁡MAXN)\mathcal{O}(N\log MAXN)。
  • 空间复杂度O(1)\mathcal{O}(1)。
class Solution:
    def minimumSize(self, nums: List[int], maxOperations: int) -> int:
        lo = 1
        hi = max(nums)
        while lo <= hi:
            mid = (lo + hi) // 2
            tot = 0
            for num in nums:
                tot += (num - 1) // mid
            if tot <= maxOperations:
                hi = mid - 1
            else:
                lo = mid + 1
        return lo

Problem D - 一个图中连通三元组的最小度数

方法一:暴力

数据范围N≤400N\leq400是一个典型的O(N3)\mathcal{O}(N^3)范围,所以直接暴力枚举三元组即可。

为了快速判断连通性,可以先把边集转为邻接矩阵。同时我们统计每个点的度数,方便最后计算总度数(对于一个连通三元组,总度数为三个点的总度数减去它们内部的度数,也就是2×3=62\times3=6)。

  • 时间复杂度O(N3)\mathcal{O}(N^3)。
  • 空间复杂度O(N2)\mathcal{O}(N^2)。
class Solution {
public:
    int minTrioDegree(int n, vector<vector<int>>& edges) {
        vector<vector<bool>> d(n, vector<bool>(n));
        vector<int> deg(n);
        for (auto &e : edges) {
            d[e[0] - 1][e[1] - 1] = d[e[1] - 1][e[0] - 1] = true;
            deg[e[0] - 1]++;
            deg[e[1] - 1]++;
        }
        int ans = INT_MAX;
        for (int i = 0; i < n; ++i)
            for (int j = i + 1; j < n; ++j) {
                if (!d[i][j])
                    continue;
                for (int k = j + 1; k < n; ++k) {
                    if (d[i][k] && d[j][k]) 
                        ans = min(ans, deg[i] + deg[j] + deg[k] - 6);
                }
            }
        return ans == INT_MAX ? -1 : ans;
    }
};

方法二:给无向图定向

考虑更大的数据范围N≤2×105,M≤min⁡(N(N−1)2,2×105)N\leq2\times10^5,M\leq\min(\frac{N(N-1)}{2},2\times10^5)。此时上面的暴力解法显然不再成立。

一个可行的做法是给无向图定向。这里需要用到一些推导。

  • 我们把所有边的方向定为从度数小的点连向度数大的点(如果度数相等则可以任意连接,下面的参考代码中是从标号小的连向标号大的)。
  • 可以证明,此时任意点的出度不会超过2M\sqrt{2M}。因为如果一个点的出度超过了2M\sqrt{2M},则由于我们上面的规则,可知这些点的度数也都大于2M\sqrt{2M},从而这些点的总度数将超过2M2M,而这是不可能的。

有了这一保证,我们就可以逐个枚举第一个点uu,枚举其所有相邻点vv,然后枚举vv的所有相邻点ww,检查u,v,wu,v,w是否能构成连通三元组,然后更新答案。

总复杂度是多少呢?枚举uu和vv的时间复杂度是O(M)\mathcal{O}(M);而对于每一对(u,v)(u,v),由于vv的出度不超过2M\sqrt{2M},所以枚举ww的时间复杂度是O(M)\mathcal{O}(\sqrt{M})。

  • 时间复杂度O(M32)\mathcal{O}(M^{\frac{3}{2}})。
  • 空间复杂度O(N+M)\mathcal{O}(N+M)。
class Solution {
public:
    int minTrioDegree(int n, vector<vector<int>>& edges) {
        vector<unordered_set<int>> d(n);
        for (auto &e : edges) {
            int u = e[0] - 1, v = e[1] - 1;
            d[u].insert(v), d[v].insert(u);
        }
        
        vector<vector<int>> adj(n);
        for (auto &e : edges) {
            int u = e[0] - 1, v = e[1] - 1;
            if (d[u].size() < d[v].size() || (d[u].size() == d[v].size() && u < v))
                adj[u].emplace_back(v);
            else
                adj[v].emplace_back(u);
        }

        int ans = INT_MAX;
        for (int u = 0; u < n; ++u)
            for (int v : adj[u])
                for (int w : adj[v])
                    if (d[u].count(w))
                        ans = min(ans, (int)(d[u].size() + d[v].size() + d[w].size() - 6));
        
        return ans == INT_MAX ? -1 : ans;
    }
};
23

第一次看到 5 分的第四题。。。

6

大佬写题比我看题还快😭

3

真的想爆粗口,结束两分钟内才将两个都卡在最后一例的题目搞定。上天再给我两分钟

/**
1. 要么奇数位全为1,偶数位为0
2. 要么偶数位全为1,奇数位为0
*/
class Solution {
    public int minOperations(String s) {
        int a = 0, b=0;
        int c = 0, d=0;
        char[] chars = s.toCharArray();
        int n = chars.length;
        for(int i = 0; i < n; i++){
            if(i % 2 == 0){
                a++;
                if(chars[i] == '1'){
                    b++;
                }
            }else{
                c++;
                if(chars[i] == '1'){
                    d++;
                }
            }
        }
        return Math.min(b + (c-d), (a-b) + d);
    }
}

第二题

/**
1. 等价于出现多少多长相等字串
2. 双指针
3. []
*/
class Solution {
    int max = 1000000007;
    public int countHomogenous(String s) {
        char[] chars = s.toCharArray();
        int n = chars.length;
        int i=0,j=0;
        long re = 0;
        if(n <= 1){
            return n;
        }
        while(j < n){
            if(chars[j] != chars[i]){
                long l = j - i + 0l;
                re = (re + (l + 1)*l/2%max)%max;
                i = j;
            }
            j++;
        }
        if(i != j){
            long l = j - i + 0l;
            re = (re + (l + 1)*l/2%max)%max;
        }
        return (int)re;
    }
}

第三题

/**
1. l + k = 最后的长度
2. 这种操作是二分查找逼近
3. 如果可以这样操作,再逼近
4. 每次只能对一个袋子进行操作,操作的必定是大的
5. 如果对一个袋子操作,要求其分裂后满足最大为k,则至少需要操作 x/k - 1 || x/k次
6. 实现
*/
class Solution {
    public int minimumSize(int[] nums, int maxOperations) {
        int l = 1, r = 0;
        int n = nums.length;
        Arrays.sort(nums);
        r = nums[n-1];
        //int re = r;
        while(r > l){
            int mid = l + (r-l)/2;
            int tmp = t(mid, nums);
            //System.out.println(mid + "," + tmp);
            if(tmp > maxOperations){
                l = mid + 1;
            }else{
                //re = Math.min(mid, re);
                r = mid;
            }
        }
        return l;
    }
    public int t(int mid, int [] a){
        int re = 0;
        for(int i = 0; i<a.length; i++){
            if(a[i] > mid){
               re += a[i]%mid == 0 ? a[i]/mid - 1 : a[i]/mid;  
            }
        }
        return re;
            
    }
}

第四题

class Solution {
    /**
    1. 可以看出一个连通三元的顶点的度数为 (点的度-2)*3
    2. 故只要找出所有的三元组,及其顶点的度,即可获取min值
    3. 如何判断一个三元组?
    4. 一个顶点的子节点存在边,就构成三元组
    5. 所以进行两次遍历
    6. 模拟
    7. [a,b][b,c][a,c]就是
    8. 等价于 a的子节点 和 b的子节点存在交集
    */
    public int minTrioDegree(int n, int[][] edges) {
        HashMap<Integer, Set<Integer>> map = new HashMap<>();
        int [] de = new int[n+1];
        for(int [] tmp : edges){
            de[tmp[0]]++;
            de[tmp[1]]++;
            map.computeIfAbsent(tmp[0], v->new HashSet<>()).add(tmp[1]);
            map.computeIfAbsent(tmp[1], v->new HashSet<>()).add(tmp[0]);
        }
        //System.out.println(map);
        int re = Integer.MAX_VALUE;
        for(int [] tmp : edges){
            int a = tmp[0];
            int b = tmp[1];
            Set<Integer> at = map.get(a);
            Set<Integer> bt = map.get(b);
            
            //System.out.println(ct);
            for(Integer c : at){
                if(bt.contains(c)){
                    re = Math.min(de[a]+de[b]+de[c]-6, re);
                }
            }
        }
        return re == Integer.MAX_VALUE ? -1 : re;
    }
}
2

真的是参加过的最简单的一次周赛了😂

2

意思是,放放水,让大家接着过年。

2

已经修改

1

第三题挺突然的

1

最后一题没用数组用的字典,就超时了。。。要是题目不给 N 的范围就好了

1

啊,最后一题看到有人WA,多检查了一分钟,奖品无了。(;´༎ຶД༎ຶ`)

1