【 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 empty = new ArrayList<>();

   public int maximalPathQuality(int[] values, int[][] edges, int maxTime) {

       Map<Integer, List> 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> 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]--;

  }

}