5918. 统计字符串中的元音子字符串
子字符串 是字符串中的一个连续（非空）的字符序列。
元音子字符串 是 仅 由元音（'a'、'e'、'i'、'o' 和 'u'）组成的一个子字符串，且必须包含 全部五种 元音。
给你一个字符串 word ，统计并返回 word 中 元音子字符串的数目 。
示例 1：
输入：word = “aeiouu”
输出：2
解释：下面列出 word 中的元音子字符串（斜体加粗部分）：
- “aeiou_u”
- “**_aeiouu**”
示例 2：
输入：word = “unicornarihan”
输出：0
解释：word 中不含 5 种元音，所以也不会存在元音子字符串。
示例 3：
输入：word = “cuaieuouac”
输出：7
解释：下面列出 word 中的元音子字符串（斜体加粗部分）：
- “cuaieuo_uac”
- “cuaieuouac”
- “cuaieuouac”
- “cuaieuouac”
- “cuaieuouac”
- “cuaieuouac”
- “cuaieuoua_c”
示例 4：
输入：word = “bbaeixoubb”
输出：0
解释：所有包含全部五种元音的子字符串都含有辅音，所以不存在元音子字符串。
提示：
1 <= word.length <= 100word仅由小写英文字母组成
思路：
- 用正则找出所有全部由元音字母构成的子字符串
- 处理每一个子字符串
- 遍历每一个下标，从当前位置开始需要多长的子字符串才能满足恰好包含全部5种元音字符
class Solution {public int countVowelSubstrings(String word) {String[] ss = word.split("[^aeiou]");int len = 0;for (String s : ss) {int n = s.length();for (int i = 0; i + 4 < n; i++) {for (int j = i + 4; j < n; j++) {if (check(s.substring(i, j + 1))) {len += n - j;break;}}}}return len;}boolean check(String s){Set<Character> set = new HashSet<>();for (int i = 0; i < s.length(); i++)set.add(s.charAt(i));return set.size() == 5;}}
//当然可以加一个优化，如果从当前字符位置开始直至结尾都不能包含5个元音字符，说明已经找完，后续不用遍历class Solution {public int countVowelSubstrings(String word) {String[] ss = word.split("[^aeiou]");int len = 0;for (String s : ss) {int n = s.length();for (int i = 0; i + 4 < n; i++) {boolean flag = false;for (int j = i + 4; j < n; j++) {if (check(s.substring(i, j + 1))) {len += n - j;flag = true;break;}}if (!flag)break;}}return len;}boolean check(String s){Set<Character> set = new HashSet<>();for (int i = 0; i < s.length(); i++)set.add(s.charAt(i));return set.size() == 5;}
方法二：双指针 + dp
- 使用正则预处理所有只含元音字符的子字符串
- 遍历每一个子字符串，使用双指针，统计每个字符的个数和不同种类的字符的个数
- 当快指针指向的位置包含所有元音字母，在不减少字符种类的情况下移动慢指针，并统计子串个数
- 快指针继续向后移动，子串个数在前一个位置的基础个数上可能增加，因为新加的字符可能使得包含整个元音字符的子字符串后移，故个数会增加
class Solution {public int countVowelSubstrings(String word) {String[] ss = word.split("[^aeiou]");int res = 0;for (String s : ss) {Set<Character> set = new HashSet<>();int[] cnt = new int[26];int pre = 0;for (int i = 0, j = 0; i < s.length(); i++) {set.add(s.charAt(i));cnt[s.charAt(i) - 'a']++;if (set.size() == 5) {pre = Math.max(pre, 1);while (cnt[s.charAt(j) - 'a'] > 1) {cnt[s.charAt(j) - 'a']--;j++;pre++;}}res += pre;}}return res;}}
5919. 所有子字符串中的元音
给你一个字符串 word ，返回 word 的所有子字符串中 元音的总数 ，元音是指 'a'、'e'、'i'、'o' 和 'u' 。
子字符串 是字符串中一个连续（非空）的字符序列。
注意：由于对 word 长度的限制比较宽松，答案可能超过有符号 32 位整数的范围。计算时需当心。
示例 1：
输入：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 。
示例 2：
输入：word = “abc”
输出：3
解释：
所有子字符串是：”a”、”ab”、”abc”、”b”、”bc” 和 “c” 。
- “a”、”ab” 和 “abc” 每个都有 1 个元音
- “b”、”bc” 和 “c” 每个都有 0 个元音
因此，元音总数 = 1 + 1 + 1 + 0 + 0 + 0 = 3 。
示例 3：
输入：word = “ltcd”
输出：0
解释：“ltcd” 的子字符串均不含元音。
示例 4：
输入：word = “noosabasboosa”
输出：237
解释：所有子字符串中共有 237 个元音。
提示：
1 <= word.length <= 105word由小写英文字母组成
思路：
考虑每一个位置的字符，如果是元音字符，它出现的总次数 = (左边字符数 + 1) * (右边字符数 + 1) ，辅音直接跳过即可
class Solution {public long countVowels(String word) {Set<Character> set = new HashSet<>(){{add('a');add('e');add('i');add('o');add('u');}};long res = 0;int n = word.length();for (int i = 0; i < n; i++) {if (set.contains(word.charAt(i))) {long a = i + 1, b = n - i;res += a * b;}}return res;}}
//另一种初始化方式class Solution {public long countVowels(String word) {Set<Character> set = new HashSet<>();Collections.addAll(set, 'a', 'e', 'i', 'o', 'u');long res = 0;int n = word.length();for (int i = 0; i < n; i++) {if (set.contains(word.charAt(i))) {long a = i + 1, b = n - i;res += a * b;}}return res;}}
5920. 分配给商店的最多商品的最小值
给你一个整数 n ，表示有 n 间零售商店。总共有 m 种产品，每种产品的数目用一个下标从 0 开始的整数数组 quantities 表示，其中 quantities[i] 表示第 i 种商品的数目。
你需要将 所有商品 分配到零售商店，并遵守这些规则：
- 一间商店 至多 只能有 一种商品 ，但一间商店拥有的商品数目可以为 任意 件。
- 分配后，每间商店都会被分配一定数目的商品（可能为
0件）。用x表示所有商店中分配商品数目的最大值，你希望x越小越好。也就是说，你想 最小化 分配给任意商店商品数目的 最大值 。
请你返回最小的可能的 x 。
示例 1：
输入：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 。
示例 2：
输入：n = 7, quantities = [15,10,10]
输出：5
解释：一种最优方案为：
- 15 件种类为 0 的商品被分配到前 3 间商店，分配数目为：5，5，5 。
- 10 件种类为 1 的商品被分配到接下来 2 间商店，数目为：5，5 。
- 10 件种类为 2 的商品被分配到最后 2 间商店，数目为：5，5 。
分配给所有商店的最大商品数目为 max(5, 5, 5, 5, 5, 5, 5) = 5 。
示例 3：
输入：n = 1, quantities = [100000]
输出：100000
解释：唯一一种最优方案为：
- 所有 100000 件商品 0 都分配到唯一的商店中。
分配给所有商店的最大商品数目为 max(100000) = 100000 。
提示：
m == quantities.length1 <= m <= n <= 1051 <= quantities[i] <= 105
思路：二分结果
最少情况是每家店铺一件物品，最多情况是有最大数量的商品属于一家
二分每家商品的物品数量，统计将所有商品按该物品数量进行划分需要的店铺数，与给定店铺数比较，找到小于等于给定店铺数的物品数量划分
class Solution {public int minimizedMaximum(int n, int[] quantities) {Arrays.sort(quantities);int l = 1, r = quantities[quantities.length - 1];while (l < r) {int mid = l + r >> 1;int cnt = 0;for (int x : quantities) {cnt += x / mid;if (x % mid != 0)cnt++;}if (cnt > n)l = mid + 1;elser = mid;}return l;}}
5921. 最大化一张图中的路径价值
给你一张 无向 图，图中有 n 个节点，节点编号从 0 到 n - 1 （都包括）。同时给你一个下标从 0 开始的整数数组 values ，其中 values[i] 是第 i 个节点的 价值 。同时给你一个下标从 0 开始的二维整数数组 edges ，其中 edges[j] = [uj, vj, timej] 表示节点 uj 和 vj 之间有一条需要 timej 秒才能通过的无向边。最后，给你一个整数 maxTime 。
合法路径 指的是图中任意一条从节点 0 开始，最终回到节点 0 ，且花费的总时间 不超过 maxTime 秒的一条路径。你可以访问一个节点任意次。一条合法路径的 价值 定义为路径中 不同节点 的价值 之和 （每个节点的价值 至多 算入价值总和中一次）。
请你返回一条合法路径的 最大 价值。
注意：每个节点 至多 有 四条 边与之相连。
示例 1：
输入：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 。
示例 2：
输入：values = [5,10,15,20], edges = [[0,1,10],[1,2,10],[0,3,10]], maxTime = 30
输出：25
解释：
一条可能的路径为：0 -> 3 -> 0 。总花费时间为 10 + 10 = 20 <= 30 。
访问过的节点为 0 和 3 ，最大路径价值为 5 + 20 = 25 。
示例 3：
输入：values = [1,2,3,4], edges = [[0,1,10],[1,2,11],[2,3,12],[1,3,13]], maxTime = 50
输出：7
解释：
一条可能的路径为：0 -> 1 -> 3 -> 1 -> 0 。总花费时间为 10 + 13 + 13 + 10 = 46 <= 50 。
访问过的节点为 0 ，1 和 3 ，最大路径价值为 1 + 2 + 4 = 7 。
示例 4：
输入：values = [0,1,2], edges = [[1,2,10]], maxTime = 10
输出：0
解释：**
唯一一条路径为 0 。总花费时间为 0 。
唯一访问过的节点为 0 ，最大路径价值为 0 。
提示：
n == values.length1 <= n <= 10000 <= values[i] <= 1080 <= edges.length <= 2000edges[j].length == 30 <= uj < vj <= n - 110 <= timej, maxTime <= 100[uj, vj]所有节点对 互不相同 。- 每个节点 至多有四条 边。
- 图可能不连通。
思路：
整个路径是从0号出发最终回到0号，最多走10步，每一次最多4种选择，故时间复杂度上限为O(4^10=10^6)满足要求，直接爆搜即可
注意一点，有的点可能经过多次，但总价值只会加一次
class Solution {int[] h, e, ne, w;int idx, n, m, max;boolean[] st;public int maximalPathQuality(int[] values, int[][] edges, int maxTime) {n = values.length;m = edges.length;h = new int[n];e = new int[2 * m];ne = new int[2 * m];w = new int[2 * m];Arrays.fill(h, -1);st = new boolean[n];for (int[] p : edges) {int a = p[0], b = p[1], c = p[2];add(a, b, c);add(b, a, c);}st[0] = true;dfs(0, values[0], 0, values, maxTime);return max;}void dfs(int u, int sum, int weight, int[] values, int maxTime) {if (weight > maxTime)return;if (u == 0)max = Math.max(max, sum);for (int i = h[u]; i != -1; i = ne[i]) {int j = e[i], ww = w[i];if (!st[j]) {st[j] = true;dfs(j, sum + values[j], weight + ww, values, maxTime);st[j] = false;}elsedfs(j, sum, weight + ww, values, maxTime);}}void add(int a, int b, int c) {e[idx] = b;ne[idx] = h[a];w[idx] = c;h[a] = idx++;}}
//另一种建图方式class Solution {List<List<int[]>> p = new ArrayList<>();boolean[] st;int n, m, max;public int maximalPathQuality(int[] values, int[][] edges, int maxTime) {n = values.length;m = edges.length;st = new boolean[n];for (int i = 0; i < n; i++)p.add(new ArrayList<>());for (int[] edge : edges) {int a = edge[0], b = edge[1], c = edge[2];p.get(a).add(new int[]{b, c});p.get(b).add(new int[]{a, c});}st[0] = true;dfs(0, values[0], 0, values, maxTime);return max;}void dfs(int u, int sum, int weight, int[] values, int maxTime) {if (weight > maxTime)return;if (u == 0)max = Math.max(max, sum);for (int[] edge : p.get(u)) {int b = edge[0], c = edge[1];if (!st[b]) {st[b] = true;dfs(b, sum + values[b], weight + c, values, maxTime);st[b] = false;} else {dfs(b, sum, weight + c, values, maxTime);}}}}
若有收获，就点个赞吧
0 人点赞
