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/

解題思路

因為是子串，問題就很好解決了，首先我們將原數組看成 一下形式
$\underset{n_0}{a_0,???,a_0},\underset{n_1}{a_1,???,a_1},???\underset{n_i}{a_i,???,a_i},???,\underset{n_{ed}}{a_{ed},???,a_{ed}}$。\quad其中$?i,a_i=a_{i+1}$
對于第$i$塊,$n_i$他所能構成的同構子字符串的數目

• 長度為1: $n_1$個
• 長度為2: $n_1?1$個
• 長度為3: $n_1?2$個
• ···
  因此對于該塊 有$\frac{(n_1+1)?n_1}{2}$個，將每個塊加起來即可。

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$
那么對于某一個含有$x$求的袋子，那么他至少需要的操作次數為$?\frac{x}{c}??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\le 400$，我們可以直接進行三重循環暴力枚舉，不過要進行一些優化。
首先構造出鄰接矩陣，并且計算出每個點連接邊的個數（類似于有向圖的入度，出度）
那么，對于三個點$i,j,k$可是在$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;} };

總結

以上是生活随笔為你收集整理的LeetCode228场周赛解题报告的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。