LeetCode228场周赛解题报告
生成交替二进制字符串的最少操作数
原题链接
解题思路
直接进行暴力的将二进制字符串枚举，首个字符是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;
}
};
一个图中连通三元组的最小度数
原题链接
解题思路
因为
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;
}
};