sketch做网站,wordpress采集自动伪原创,郑州优化网站公司有哪些,郑州最好的妇科医院排行LeetCode228场周赛解题报告
生成交替二进制字符串的最少操作数
原题链接
https://leetcode-cn.com/contest/weekly-contest-228/problems/minimum-changes-to-make-alternating-binary-string/
解题思路
直接进行暴力的将二进制字符串枚举#xff0c;首个字符是0#xf…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/
解题思路
因为是子串问题就很好解决了首先我们将原数组看成 一下形式 a0,⋅⋅⋅,a0⏟n0,a1,⋅⋅⋅,a1⏟n1,⋅⋅⋅ai,⋅⋅⋅,ai⏟ni,⋅⋅⋅,aed,⋅⋅⋅,aed⏟ned\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}}n0a0,⋅⋅⋅,a0,n1a1,⋅⋅⋅,a1,⋅⋅⋅niai,⋅⋅⋅,ai,⋅⋅⋅,nedaed,⋅⋅⋅,aed。\quad其中∀i,ai̸ai1\forall i, a_i \not a_{i1}∀i,aiai1 对于第iii块,nin_ini他所能构成的同构子字符串的数目
长度为1: n1n_1n1个长度为2: n1−1n_1 - 1n1−1个长度为3: n1−2n_1 - 2n1−2个··· 因此对于该块 有(n11)⋅n12\frac {(n_11)\cdot n_1} 22(n11)⋅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/
解题思路
一个简单的二分题目假设最少的代价为 ccc 那么对于某一个含有xxx求的袋子那么他至少需要的操作次数为⌈xc⌉−1\lceil \frac x c \rceil - 1⌈cx⌉−1减一是因为自己那一份不需要分。那么我们二分最少代价每次计算出他所需要的操作数量是否符合要求即可。
AC代码
typedef long long LL;
class Solution {
public:vectorint 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(vectorint 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≤400n \leq 400n≤400我们可以直接进行三重循环暴力枚举不过要进行一些优化。 首先构造出邻接矩阵并且计算出每个点连接边的个数类似于有向图的入度出度 那么对于三个点i,j,ki, j, ki,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, vectorvectorint 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;}
};
