[Leetcode]2062. 统计字符串中的元音子字符串
子字符串 是字符串中的一个连续（非空）的字符序列。
元音子字符串 是 仅 由元音（'a'、'e'、'i'、'o' 和 'u'）组成的一个子字符串，且必须包含 全部五种 元音。
给你一个字符串 word ，统计并返回 word 中 元音子字符串的数目 。
遍历即可。
class Solution {
public String Vowels = "aeiou";
public boolean isVowelString(String word,int i,int j) {
Set<Character> wordSet = new HashSet<>();
for(int ind=i;ind<=j;++ind) {
var ch = word.charAt(ind);
if(Vowels.indexOf(ch)==-1) return false;
wordSet.add(ch);
}
if(wordSet.size()==5) return true;
return false;
}
public int countVowelSubstrings(String word) {
int res = 0;
for(int i=0;i<word.length();++i) {
for(int j=i+4;j<word.length();++j) {
if(isVowelString(word,i,j)) {
res++;
}
}
}
return res;
}
}
[Leetcode]2063. 所有子字符串中的元音
给你一个字符串 word ，返回 word 的所有子字符串中 元音的总数 ，元音是指 'a'、'e'、'i'、'o' 和 'u' 。
子字符串 是字符串中一个连续（非空）的字符序列。
注意：由于对 word 长度的限制比较宽松，答案可能超过有符号 32 位整数的范围。计算时需当心。
遍历 \(\textit{word}\), 若\(\textit{word}[i]\) 是元音，我们考察它能出现在多少个子字符串中。
设 \(\textit{word}\) 的长度为 \(n\)。子字符串 \(\textit{word}[l..r]\) 若要包含 \(\textit{word}[i]\)，则必须满足
\(0\le l\le i\)
\(i\le r\le n-1\)
这样的 \(l\) 有 \(i+1\) 个，\(r\) 有 \(n-i\) 个，因此有 \((i+1)(n-i)\) 个子字符串，所以 \(\textit{word}[i]\) 在所有子字符串中一共出现了 \((i+1)(n-i)\) 次。
累加所有出现次数即为答案。
class Solution {
public String Vowels = "aeiou";
public long countVowels(String word) {
long res = 0;
long n = word.length();
for(long i=0;i<n;++i) {
Character ch = word.charAt((int)i);
if(Vowels.indexOf(ch)!=-1) {
res += (i+1) * (n-i);
}
}
return res;
}
}
[Leetcode]2064. 分配给商店的最多商品的最小值
给你一个整数 n ，表示有 n 间零售商店。总共有 m 种产品，每种产品的数目用一个下标从 0 开始的整数数组 quantities 表示，其中 quantities[i] 表示第 i 种商品的数目。
你需要将 所有商品 分配到零售商店，并遵守这些规则：
一间商店 至多 只能有 一种商品 ，但一间商店拥有的商品数目可以为 任意 件。
分配后，每间商店都会被分配一定数目的商品（可能为 0 件）。用 x 表示所有商店中分配商品数目的最大值，你希望 x 越小越好。也就是说，你想 最小化 分配给任意商店商品数目的 最大值 。
请你返回最小的可能的 x 。
二分法。
class Solution {
public int minimizedMaximum(int n, int[] quantities) {
int lo = 1,hi = Arrays.stream(quantities).max().getAsInt();
while(lo<=hi) {
int mid = lo+((hi-lo)>>1);
if(canDistribute(n,quantities,mid)) hi = mid -1;
else lo = mid+1;
}
return lo;
}
public boolean canDistribute(int n, int[] quantities, int target) {
int times = 0;
for(int quantity:quantities) {
times += quantity/target;
if(quantity%target!=0) times++;
}
if(times>n) return false;
return true;
}
}
[Leetcode]2065. 最大化一张图中的路径价值
给你一张 无向 图，图中有 n 个节点，节点编号从 0 到 n - 1 （都包括）。同时给你一个下标从 0 开始的整数数组 values ，其中 values[i] 是第 i 个节点的 价值 。同时给你一个下标从 0 开始的二维整数数组 edges ，其中 edges[j] = [uj, vj, timej] 表示节点 uj 和 vj 之间有一条需要 timej 秒才能通过的无向边。最后，给你一个整数 maxTime 。
合法路径 指的是图中任意一条从节点 0 开始，最终回到节点 0 ，且花费的总时间 不超过 maxTime 秒的一条路径。你可以访问一个节点任意次。一条合法路径的 价值 定义为路径中 不同节点 的价值 之和 （每个节点的价值 至多 算入价值总和中一次）。
请你返回一条合法路径的 最大 价值。
注意：每个节点 至多 有 四条 边与之相连。
DFS。根据题目的数据范围，至多能走 \(10\) 条边，这意味着搜索的层数至多为 \(10\)；同时，题目保证每个节点至多有四条边与之相连，因此每次搜索时至多会递归 \(4\) 次。因此计算量至多为 \(4^{10}\)。需要注意的就是经过一个节点，直接把其价值置空。
这样，重复的经过就不会重复统计价格了。 当然DFS返回前需要还原现场。DFS的时候记录的状态包括路径价值和，累计时间。
退出条件为：时间超过阈值。更新最大价值则必须在终点为0的时候才可。
class Solution {
public int res;
public int maximalPathQuality(int[] values, int[][] edges, int maxTime) {
res = values[0];
var graph = new HashMap<Integer,ArrayList<ArrayList<Integer>>>();
for(var edge:edges) {
int u=edge[0], v=edge[1],time=edge[2];
ArrayList<Integer> toConnection = new ArrayList<>() {{add(v);add(time);}};//Arrays.asList(v,time) ;
ArrayList<Integer> fromConnection = new ArrayList<>() {{add(u);add(time);}};
if(!graph.containsKey(u)) graph.put(u,new ArrayList<ArrayList<Integer>>());
if(!graph.containsKey(v)) graph.put(v,new ArrayList<ArrayList<Integer>>());
var toConnections = graph.getOrDefault(u,new ArrayList<ArrayList<Integer>>());
var fromConnections = graph.getOrDefault(v,new ArrayList<ArrayList<Integer>>());
toConnections.add(toConnection);
fromConnections.add(fromConnection);
}
dfs(0,0,0,values,maxTime,graph);
return res;
}
public void dfs(int curPoint, int curValue, int curTime, int[] values, int maxTime, HashMap<Integer,ArrayList<ArrayList<Integer>>> graph) {
curValue += values[curPoint];
values[curPoint] = 0;
if(curPoint==0) res = Math.max(res,curValue);
for(var toConnection:graph.getOrDefault(curPoint,new ArrayList<ArrayList<Integer>>())) {
int nextPoint = toConnection.get(0), useTime = toConnection.get(1);
if(curTime+useTime>maxTime) continue;
dfs(nextPoint,curValue,curTime+useTime,values.clone(),maxTime,graph);
}
}
}