力扣266場周賽

1 問題

5918. 統計字元串中的元音子字元串

子字元串 是字元串中的一個連續（非空）的字元序列。元音子字元串 是 僅 由元音（'a'、'e'、'i'、'o' 和 'u'）組成的一個子字元串，且必須包含 全部五種 元音。給你一個字元串 word ，統計并傳回 word 中 元音子字元串的數目 。

示例：

輸入：word = "aeiouu"

輸出：2

解釋：下面列出 word 中的元音子字元串（斜體加粗部分）：

- "aeiouu"

解析：該題題意就是找到由元音子字元串的個數，由于給出的資料範圍n <= 100很小，是以可以直接采用暴搜來解決，周遊所有的子字元串，如果滿足題意就直接在結果上加一；此處采用雙for來周遊所有的子字元串。時間複雜度為O(n^2);

代碼

const int N = 27; class Solution { public:     bool snt[N], cnt[N];     int countVowelSubstrings(string word) {         char bu[5] = {'a', 'e', 'i', 'o', 'u'};         int n = word.size(), res = 0;         for (char c: bu) {             int t = c - 'a';             snt[t] = true;         }         for (int i = 0; i < n; i ++){             int t = word[i] - 'a';             if (!snt[t]) continue;             int num = 0, p = 0;             memset(cnt, 0, sizeof cnt);             for (int j = i; j < n; j ++) {                 int k = word[j] - 'a';                 if (!snt[k]) break;                 if (!cnt[k]) {                     cnt[k] = true;                     p ++;                 }                 if (p >= 5) num ++;             }             res += num;         return res;     } };

5919. 所有子字元串中的元音

給你一個字元串 word ，傳回 word 的所有子字元串中 元音的總數 ，元音是指 'a'、'e'、'i'、'o' 和 'u' 。子字元串 是字元串中一個連續（非空）的字元序列。注意：由于對 word 長度的限制比較寬松，答案可能超過有符号 32 位整數的範圍。計算時需當心。

示例；

輸入：word = "aba"

輸出：6

解釋：所有子字元串是："a"、"ab"、"aba"、"b"、"ba" 和 "a" 。- "b" 中有 0 個元音- "a"、"ab"、"ba" 和 "a" 每個都有 1 個元音- "aba" 中有 2 個元音，是以，元音總數 = 0 + 1 + 1 + 1 + 1 + 2 = 6 。

解析：此題與第一題有些類似，不過該題是要求出包含元音子字元串的元音的個數總和，此題不可以采用暴搜，資料範圍為1e5，否則會tle；不過此題可以反過來想，要求我們找到包含元音子字元串， 那麼我們可以找到每一個元音字元，然後求出它所能構成的子字元串的數量即可。

例如 babe 找到元音字元’a’、’e’ 分别位于1、3的位置；對于’a’來說，他所能構成的包含自身的子字元串的數量為，a左邊的個數乘以右邊個數！解釋：左邊部分時即為b， 右邊部分為be，而右邊部分可以選0個、1個、2個  (注意題目中要求為連續的子字元串) 是以有三種，同理左邊部分有兩種，所有總共包含a的子字元串數量為2*3 = 6種。

typedef long long LL;     long long countVowels(string word) {         LL res = 0ll;         int n = word.size();         for (int i = 0; i < n; i ++ ) {             if (word[i] == 'a' || word[i] == 'e' || word[i] == 'i' || word[i] == 'o' || word[i] == 'u') {                 res = res + (LL)(i + 1) * (n - i);

5920. 配置設定給商店的最多商品的最小值

給你一個整數 n ，表示有 n 間零售商店。總共有 m 種産品，每種産品的數目用一個下标從 0 開始的整數數組 quantities 表示，其中 quantities[i] 表示第 i 種商品的數目。

你需要将 所有商品 配置設定到零售商店，并遵守這些規則：

一間商店 至多 隻能有 一種商品 ，但一間商店擁有的商品數目可以為 任意 件。

配置設定後，每間商店都會被配置設定一定數目的商品（可能為 0 件）。用 x 表示所有商店中配置設定商品數目的最大值，你希望 x 越小越好。也就是說，你想 最小化 配置設定給任意商店商品數目的 最大值 。請你傳回最小的可能的 x 。

輸入：n = 6, quantities = [11,6]

輸出：3

解釋： 一種最優方案為：- 11 件種類為 0 的商品被配置設定到前 4 間商店，配置設定數目分别為：2，3，3，3 。- 6 件種類為 1 的商品被配置設定到另外 2 間商店，配數目分别為：3，3 。配置設定給所有商店的最大商品數目為 max(2, 3, 3, 3, 3, 3) = 3 。

解析：此題的題意為給出quantities.size()個數，每一個數可以平攤到n個商店中的一些商店(或者全部)當中(解釋：如果k平攤到m個商店當中， 那麼每個商店的取值就為m/k或者ceil(m/k) )，但是每一個商店隻能平攤quantities的某一個數，最後求最大值的最小；

此題有兩種思考方式：

第一種就是貪心去模拟，每一次貪心的取最大的quantities[i]，然後分攤商店的個數+1，進行分攤操作。其實也就是去模拟整個過程，但是此題模拟的時間複雜度很高，很容易逾時。

第二種二分，可以注意到該題的資料範圍為1 <= quantities[i] <= 1e5,是以我們去枚舉所有的分攤操作的可能性，就是每一個商店分攤的數量，最後判斷每一個quantities[i]全部配置設定完畢後會不會超過n個商店的個數。此處枚舉可以采用二分進行枚舉; 時間複雜度為O(mlog1e5).

const int N = 100010;     int m;     bool check(vector<int>& quantities, int k, int n){         int num = 0;         for (int i = 0; i < m; i ++) {             num += ceil((double)quantities[i]/k);             if (num > n) return false;         return true;     int minimizedMaximum(int n, vector<int>& quantities) {         m = quantities.size();         int l = 1, r = 100000;         while(l < r) {             int mid = l + r >> 1;             if (check(quantities, mid, n)) r = mid;             else l = mid + 1;         return r;

5921. 最大化一張圖中的路徑價值

給你一張 無向 圖，圖中有 n 個節點，節點編号從 0 到 n - 1 （都包括）。同時給你一個下标從 0 開始的整數數組 values ，其中 values[i] 是第 i 個節點的 價值 。同時給你一個下标從 0 開始的二維整數數組 edges ，其中 edges[j] = [uj, vj, timej] 表示節點 uj 和 vj 之間有一條需要 timej 秒才能通過的無向邊。最後，給你一個整數 maxTime 。合法路徑 指的是圖中任意一條從節點 0 開始，最終回到節點 0 ，且花費的總時間 不超過 maxTime 秒的一條路徑。你可以通路一個節點任意次。一條合法路徑的 價值 定義為路徑中 不同節點 的價值 之和 （每個節點的價值 至多 算入價值總和中一次）。請你傳回一條合法路徑的 最大 價值。注意：每個節點 至多 有 四條 邊與之相連。

輸入：values = [0,32,10,43], edges = [[0,1,10],[1,2,15],[0,3,10]], maxTime = 49

輸出：75

解釋：一條可能的路徑為：0 -> 1 -> 0 -> 3 -> 0 。總花費時間為 10 + 10 + 10 + 10 = 40 <= 49 。通路過的節點為 0 ，1 和 3 ，最大路徑價值為 0 + 32 + 43 = 75 。

解析：該題就是一個一般的圖論問題，從0出發最終回到0，且途徑的時間不超過給出的最大時間限制；此題注意到10 <= timej, maxTime <= 100、每個節點至多有四條邊；是以說步數不會超過10次，采用深搜可以解決此題，不用擔心會逾時；用鄰接表記錄每一條邊、時間、價值三種資料，然後dfs周遊所有可能，記錄從0出發最終回到0點的最大價值。

const int N = 4010, M = 1010;     int e[N], ne[N], w[N], idx, h[M], Times, res;     bool snt[N];     void add(int a, int b, int c){         e[idx] = b;         ne[idx] = h[a];         w[idx] = c;         h[a] = idx ++;     void dfs(vector<int>& values, int time, int val, int value){         if (time >= Times) {             if (time == Times && val == 0) res = max(res, value);             return;         if (val == 0) res = max(res, value);         int p = values[val];         values[val] = 0;         for (int i = h[val]; i != -1; i = ne[i]) {             int k = e[i], t = time + w[i];             dfs(values, t, k, value + values[k]);         values[val] = p;     int maximalPathQuality(vector<int>& values, vector<vector<int>>& edges, int maxTime) {         Times = maxTime;         memset(h, -1, sizeof h);         for (auto ed: edges) {             int s = ed[0], d = ed[1], c = ed[2];             add(s, d, c);             add(d, s, c);         dfs(values, 0, 0, values[0]);         return  res;

2 總結

本部落格是力扣266場周賽的題解，如果存在不懂的地方可以在評論區提出，這裡會耐心解答！關注公衆号：算法與程式設計之美，我們會不斷的更新力扣周賽題解，codeforces題解等比賽題解。

實習編輯：李欣容