LeetCode228场周赛解题报告

LeetCode228场周赛解题报告

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

原题链接

https://leetcode-cn.com/contest/weekly-contest-228/problems/minimum-changes-to-make-alternating-binary-string/

解题思路

直接进行暴力的将二进制字符串枚举,首个字符是0,还是1,枚举之后取最小值

AC代码

class Solution {
public:
    int minOperations(string s) {
        int res = 1e5, tmp;
        tmp = 0;
        for (int i = 0; i < s.size(); i ++ )
        {
            if (i % 2 == 0 && s[i] == '1')
                tmp ++;
            else if (i % 2 == 1 && s[i] == '0')
                tmp ++;
        }
        res = min(res, tmp);
        
        tmp = 0;
        for (int i = 0; i < s.size(); i ++ )
        {
            if (i % 2 == 1 && s[i] == '1')
                tmp ++;
            else if (i % 2 == 0 && s[i] == '0')
                tmp ++;
        }
        res = min(res, tmp);
        return res;
    }
};

统计同构子字符串的数目

原题链接

https://leetcode-cn.com/contest/weekly-contest-228/problems/count-number-of-homogenous-substrings/

解题思路

因为是子串,问题就很好解决了,首先我们将原数组看成 一下形式
a 0 , ⋅ ⋅ ⋅ , a 0 ⏟ n 0 , a 1 , ⋅ ⋅ ⋅ , a 1 ⏟ n 1 , ⋅ ⋅ ⋅ a i , ⋅ ⋅ ⋅ , a i ⏟ n i , ⋅ ⋅ ⋅ , a e d , ⋅ ⋅ ⋅ , a e d ⏟ n e d \underbrace{a_0, \cdot\cdot\cdot, a_0}_{n_0},\underbrace{a_1, \cdot\cdot\cdot, a_1}_{n_1},\cdot\cdot\cdot\underbrace{a_i, \cdot\cdot\cdot, a_i}_{n_i},\cdot\cdot\cdot,\underbrace{a_{ed}, \cdot\cdot\cdot, a_{ed}}_{n_{ed}} n0​ a0​,⋅⋅⋅,a0​​​,n1​ a1​,⋅⋅⋅,a1​​​,⋅⋅⋅ni​ ai​,⋅⋅⋅,ai​​​,⋅⋅⋅,ned​ aed​,⋅⋅⋅,aed​​​。 \quad 其中 ∀ i , a i ≠ a i + 1 \forall i, a_i \not= a_{i+1} ∀i,ai​​=ai+1​
对于第 i i i块, n i n_i ni​他所能构成的同构子字符串的数目

  • 长度为1: n 1 n_1 n1​个
  • 长度为2: n 1 − 1 n_1 - 1 n1​−1个
  • 长度为3: n 1 − 2 n_1 - 2 n1​−2个
  • ···
    因此对于该块 有 ( n 1 + 1 ) ⋅ n 1 2 \frac {(n_1+1)\cdot n_1} 2 2(n1​+1)⋅n1​​个,将每个块加起来即可。

AC代码

typedef long long LL;
const int MOD = 1e9 + 7;
class Solution {
public:
    int countHomogenous(string s) {
        LL cnt = 1, ret = 0;
        s += '.';
        for (int i = 1; i < s.size(); i ++ )
        {
            if (s[i] == s[i - 1])
                cnt ++;
            else
            {
                ret += (cnt + 1) * cnt / 2;
                ret %= MOD;
                // printf("i=%d, tmp=%d\n", i, (cnt + 1) * cnt / 2);
                cnt = 1;
            }
        }
        return ret % MOD;
    }
};

袋子里最少数目的球

原题链接

https://leetcode-cn.com/contest/weekly-contest-228/problems/minimum-limit-of-balls-in-a-bag/

解题思路

一个简单的二分题目,假设最少的代价为 c c c
那么对于某一个含有 x x x求的袋子,那么他至少需要的操作次数为 ⌈ x c ⌉ − 1 \lceil \frac x c \rceil - 1 ⌈cx​⌉−1,减一是因为自己那一份不需要分。那么我们二分最少代价,每次计算出他所需要的操作数量是否符合要求即可。

AC代码

typedef long long LL;
class Solution {
public:
    vector<int> v;
    int cnt;
    bool Check(int t)
    {
        LL ret = 0;
        for (auto x : v)
        {
            ret += x / t + (x % t != 0) - 1;
        }
        return ret <= cnt;
    }
    int minimumSize(vector<int>& nums, int maxOperations) {
        v = nums, cnt = maxOperations;
        int l = 1, r = v[0], mid;
        for (auto x : v)    
            r = max(r, x);
        
        while (l < r)
        {
            mid = l + r >> 1;
            if (Check(mid))
            {
                r = mid;
            }
            else
            {
                l = mid + 1;
            }
        }
        return l;       
    }
};

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

原题链接

https://leetcode-cn.com/contest/weekly-contest-228/problems/minimum-degree-of-a-connected-trio-in-a-graph/

解题思路

因为 n ≤ 400 n \leq 400 n≤400,我们可以直接进行三重循环暴力枚举,不过要进行一些优化。
首先构造出邻接矩阵,并且计算出每个点连接边的个数(类似于有向图的入度,出度)
那么,对于三个点 i , j , k i, j, k i,j,k可是在 O ( 1 ) O(1) O(1)的时间内计算出是否是三元组,并且他的度数。
e[i][j],e[i][k],e[j][k]同时存在表示为三元组,他们的度数为 ind[i] + ind[j] + ind[k] - 6; 减去6是三元组相连的边计算了两遍。用该数字不断的更新答案即可。
本来以为可能被卡需要使用并查集试一下呢,结果发现不需要。

AC代码

const int N = 410;
int e[N][N];
int ind[N];
int par[N];

class Solution {
public:
    int minTrioDegree(int n, vector<vector<int>>& edges) {
        memset(ind, 0, sizeof ind); 
        memset(e, 0, sizeof e);
        for (int i = 0; i < edges.size(); i ++ )
        {
            ind[edges[i][0]] ++, ind[edges[i][1]] ++;
            e[edges[i][0]][edges[i][1]] = 1;
            e[edges[i][1]][edges[i][0]] = 1;
        }
        int ret = 1e9;
        for (int i = 1; i <= n && ret != 0; i ++ )
            for (int j = 1; j <= n; j ++ )
                for (int k = 1; k <= n; k ++ )
                {
                    if (e[i][j] && e[i][k] && e[j][k])
                    {
                        ret = min(ret, ind[i] + ind[j] + ind[k] - 6);
                    }
                }
        if (ret == 1000000000)  return -1;
        return ret;
    }
};
上一篇:微积分小感——0.极限论


下一篇:[CF1392H] ZS Shuffles Cards