统计字符串中的元音子字符串
签到题。
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;
}
}
所有子字符串中的元音
依次计算每个位置的元音字符会被多少个子串计数即可。
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;
}
}
分配给商店的最多商品的最小值
二分答案，假定一个商店最多能分配 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;
}
}
最大化一张图中的路径价值
看似复杂，但是观察数据范围，发现直接回溯即可。
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]--;
}
}