Leetcode(第228场周赛)

5676. 生成交替二进制字符串的最少操作数(第一题)

题目

给你一个仅由字符 ‘0’ 和 ‘1’ 组成的字符串 s 。一步操作中,你可以将任一 ‘0’ 变成 ‘1’ ,或者将 ‘1’ 变成 ‘0’ 。

交替字符串 定义为:如果字符串中不存在相邻两个字符相等的情况,那么该字符串就是交替字符串。例如,字符串 “010” 是交替字符串,而字符串
“0100” 不是。

返回使 s 变成 交替字符串 所需的 最少 操作数。

示例 1:
输入:s = "0100"
输出:1
解释:如果将最后一个字符变为 '1' ,s 就变成 "0101" ,即符合交替字符串定义。

示例 2:
输入:s = "10"
输出:0
解释:s 已经是交替字符串。

示例 3:
输入:s = "1111"
输出:2
解释:需要 2 步操作得到 "0101" 或 "1010" 。

思路


 1. 第1个字母为‘0’,往后计算;
 2. 第2个字母为‘1’,往后计算; 取2种情况最小值 

代码

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

5677. 统计同构子字符串的数目(第二题)

题目

给你一个字符串 s ,返回 s 中 同构子字符串 的数目。由于答案可能很大,只需返回对 109 + 7 取余 后的结果。

同构字符串 的定义为:如果一个字符串中的所有字符都相同,那么该字符串就是同构字符串。

子字符串 是字符串中的一个连续字符序列。

示例 1:
输入:s = "abbcccaa"
输出:13
解释:同构子字符串如下所列:
"a"   出现 3 次。
"aa"  出现 1 次。
"b"   出现 2 次。
"bb"  出现 1 次。
"c"   出现 3 次。
"cc"  出现 2 次。
"ccc" 出现 1 次。
3 + 1 + 2 + 1 + 3 + 2 + 1 = 13

示例 2:
输入:s = "xy"
输出:2
解释:同构子字符串是 "x" 和 "y" 。

示例 3:
输入:s = "zzzzz"
输出:15

思路
建立一个数组a,分2种情况,a[i]=1,或者a[i]=a[i-1]+1,每次吧值都加到ans内。

代码

class Solution {
    const int p=1000000007;
    int a[100005];
    
public:
    
    int countHomogenous(string s) {
        int ans=0;
        for(int i=0;i<s.size();i++){
            if(!i || s[i]!=s[i-1]) a[i]=1;
            else a[i]=a[i-1]+1;
            ans+=a[i];
            if(ans>p) ans-=p;
        }
        return ans;
    }
};

5678. 袋子里最少数目的球(第三题)

我不会做这题,答案是某位大神的,不知道为啥二分就好了

题目

给你一个整数数组 nums ,其中 nums[i] 表示第 i 个袋子里球的数目。同时给你一个整数 maxOperations 。

你可以进行如下操作至多 maxOperations 次:

选择任意一个袋子,并将袋子里的球分到 2 个新的袋子中,每个袋子里都有 正整数 个球。 比方说,一个袋子里有 5
个球,你可以把它们分到两个新袋子里,分别有 1 个和 4 个球,或者分别有 2 个和 3 个球。 你的开销是单个袋子里球数目的 最大值
,你想要 最小化 开销。请你返回进行上述操作后的最小开销。

示例 1:
输入:nums = [9], maxOperations = 2
输出:3
解释:
- 将装有 9 个球的袋子分成装有 6 个和 3 个球的袋子。[9] -> [6,3] 。
- 将装有 6 个球的袋子分成装有 3 个和 3 个球的袋子。[6,3] -> [3,3,3] 。
装有最多球的袋子里装有 3 个球,所以开销为 3 并返回 3 。


示例 2:
输入:nums = [2,4,8,2], maxOperations = 4
输出:2
解释:
- 将装有 8 个球的袋子分成装有 4 个和 4 个球的袋子。[2,4,8,2] -> [2,4,4,4,2] 。
- 将装有 4 个球的袋子分成装有 2 个和 2 个球的袋子。[2,4,4,4,2] -> [2,2,2,4,4,2] 。
- 将装有 4 个球的袋子分成装有 2 个和 2 个球的袋子。[2,2,2,4,4,2] -> [2,2,2,2,2,4,2] 。
- 将装有 4 个球的袋子分成装有 2 个和 2 个球的袋子。[2,2,2,2,2,4,2] -> [2,2,2,2,2,2,2,2] 。
装有最多球的袋子里装有 2 个球,所以开销为 2 并返回 2 。


示例 3:
输入:nums = [7,17], maxOperations = 2
输出:7

代码

class Solution {
public:
    int minimumSize(vector<int>& a, int b) {
        int lo=1,hi=1e9;
        while(lo<hi) {
            int mid=(lo+hi)/2;
            long long cnt=0;
            for(int i:a) {
                cnt+=(i-1)/mid;
            }
            if(cnt>b) lo=mid+1;
            else hi=mid;
        }
        return lo;
    }
};

5679. 一个图中连通三元组的最小度数(第4题)

,我同样不会写,同样来自某位大神

题目

给你一个无向图,整数 n 表示图中节点的数目,edges 数组表示图中的边,其中 edges[i] = [ui, vi] ,表示 ui 和
vi 之间有一条无向边。

一个 连通三元组 指的是 三个 节点组成的集合且这三个点之间 两两 有边。

连通三元组的度数 是所有满足此条件的边的数目:一个顶点在三元组内,而另一个顶点不在三元组内。

请你返回所有连通三元组中度数的 最小值 ,如果图中没有连通三元组,那么返回 -1 。

示例 1:
输入:n = 6, edges = [[1,2],[1,3],[3,2],[4,1],[5,2],[3,6]]
输出:3
解释:只有一个三元组 [1,2,3] 。构成度数的边在上图中已被加粗。


示例 2:
输入:n = 7, edges = [[1,3],[4,1],[4,3],[2,5],[5,6],[6,7],[7,5],[2,6]]
输出:0
解释:有 3 个三元组:
1) [1,4,3],度数为 0 。
2) [2,5,6],度数为 2 。
3) [5,6,7],度数为 2 。
 

提示:

2 <= n <= 400
edges[i].length == 2
1 <= edges.length <= n * (n-1) / 2
1 <= ui, vi <= n
ui != vi
图中没有重复的边。

代码

class Solution {
public:
    int deg[405],g[405][405];
    int minTrioDegree(int n, vector<vector<int>>& a) {
        for(auto &v : a) {
            deg[v[0]]++;
            deg[v[1]]++;
            g[v[0]][v[1]]=g[v[1]][v[0]]=1;
        }
        int ans=1e9,ok=0;
        for(int i=1;i<=n;++i) {
            for(int j=i+1;j<=n;++j) {
                if(!g[i][j]) continue;
                if(deg[i]+deg[j]>=ans) continue;
                for(int k=j+1;k<=n;++k) {
                    if(!g[j][k] || !g[i][k]) continue;
                    ans=min(ans,deg[i]+deg[j]+deg[k]);
                    ok=1;
                }
            }
        }
        if(!ok) return -1;
        return ans-6;
    }
};
上一篇:228周赛T2


下一篇:[leetcode]228.汇总区间