【NO.1 统计字符串中的元音子字符串】
解题思路
签到题。
代码展现
class Solution {
public int countVowelSubstrings(String word) {
int count = 0;
for (int i = 0; i < word.length(); i++) {for (int j = i + 1; j <= word.length(); j++) {count += containsAll(word.substring(i, j));
}
}
return count;}
private int containsAll(String s) {
if (s.contains("a") && s.contains("e") && s.contains("i") && s.contains("o") && s.contains("u")) {for (var c : s.toCharArray()) {if (!"aeiou".contains(String.valueOf(c))) {return 0;}
}
return 1;
}
return 0;}
}
【NO.2 所有子字符串中的元音】
解题思路
顺次计算每个地位的元音字符会被多少个子串计数即可。
代码展现
class Solution {
public long countVowels(String word) {
long result = 0;
for (int i = 0; i < word.length(); i++) {if (!"aeiou".contains(String.valueOf(word.charAt(i)))) {continue;}
long left = i;
long right = word.length() - i - 1;
result += left * right + left + right + 1;
}
return result;}
}
【NO.3 调配给商店的最多商品的最小值】
解题思路
二分答案，假设一个商店最多能调配 x 个商品，那么咱们能够轻易计算出须要多少个商店，即可失去 n 个商店是否调配完这 m 种商品。
代码展现
class Solution {
public int minimizedMaximum(int n, int[] quantities) {
int left = 1;
int right = Arrays.stream(quantities).max().getAsInt();
while (left + 1 < right) {int mid = (left + right) / 2;
if (check(n, quantities, mid)) {right = mid;} else {left = mid;}
}
return check(n, quantities, left) ? left : right;}
private boolean check(int n, int[] quantities, int x) {
int cnt = 0;
for (int q : quantities) {cnt += (q + x - 1) / x;
}
return cnt <= n;}
}
【NO.4 最大化一张图中的门路价值】
解题思路
看似简单，然而察看数据范畴，发现间接回溯即可。
代码展现
class Solution {
int result;
List<Integer> empty = new ArrayList<>();
public int maximalPathQuality(int[] values, int[][] edges, int maxTime) {
Map<Integer, List<Integer>> children = new HashMap<>();
Map<Integer, Map<Integer, Integer>> times = new HashMap<>();
for (int[] e : edges) {if (!children.containsKey(e[0])) {children.put(e[0], new ArrayList<>());
}
if (!children.containsKey(e[1])) {children.put(e[1], new ArrayList<>());
}
if (!times.containsKey(e[0])) {times.put(e[0], new HashMap<>());
}
if (!times.containsKey(e[1])) {times.put(e[1], new HashMap<>());
}
children.get(e[0]).add(e[1]);
children.get(e[1]).add(e[0]);
times.get(e[0]).put(e[1], e[2]);
times.get(e[1]).put(e[0], e[2]);
}
int[] vis = new int[values.length];
result = 0;
dfs(0, 0, 0, maxTime, vis, values, children, times);
return result;}
private void dfs(int pos, int sum, int time, int maxTime, int[] vis, int[] values, Map<Integer, List<Integer>> children, Map<Integer, Map<Integer, Integer>> times) {
if (vis[pos] == 0) {sum += values[pos];
}
vis[pos]++;
if (pos == 0) {result = Math.max(result, sum);
}
for (int nxt : children.getOrDefault(pos, empty)) {if (time + times.get(pos).get(nxt) <= maxTime) {dfs(nxt, sum, time + times.get(pos).get(nxt), maxTime, vis, values, children, times);
}
}
vis[pos]--;}
}