【 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]--;}
}