上岸算法LeetCode Weekly Contest 266解题报告

上岸算法 · 发表于 2021-11-7 19:34:23

登录后可回复主题

您需要登录才可以下载或查看，没有帐号？注册账号

x

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

帐号		自动登录	找回密码
密码			注册账号

[吹水聊天] 上岸算法LeetCode Weekly Contest 266解题报告

登录后可回复主题