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

上岸算法 · 发表于 2021-10-24 17:33:11

登录后可回复主题

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

x

【 NO.1 句子中的有效单词数】

解题思路
签到题。

代码展示

class Solution {
public int countValidWords(String sentence) {
   String[] words = sentence.split(" ");
   int count = 0;
   for (var word : words) {
         char[] chars = word.trim().toCharArray();
         boolean invalid = false;
         int index = -1;
         for (int i = 0; i < chars.length && !invalid; i++) {
            char c = chars[i];
            if ('0' <= c && c <= '9') {
               invalid = true;
            } else if (c == '-') {
               if (index == -1) {
                     index = i;
               } else {
                     invalid = true;
               }
            } else if (isNotAlpha(c) && i != chars.length - 1) {
               invalid = true;
            }
      }
         if (invalid || index == 0 || index == chars.length - 1) {
            continue;
      }
         if (index > 0 && (isNotAlpha(chars[index - 1]) || isNotAlpha(chars[index + 1]))) {
            continue;
      }
         count++;
   }
   return count;
  }

boolean isNotAlpha(char c) {
   return 'a' > c || c > 'z';
  }

}

【 NO.2 下一个更大的数值平衡数】

解题思路
枚举即可。

代码展示

class Solution {
public int nextBeautifulNumber(int n) {
   for (int i = n + 1; ; i++) {
         if (balance(i)) {
            return i;
      }
   }
  }

private boolean balance(int num) {
   int[] cnt = new int[10];
   for (; num > 0; num /= 10) {
         cnt[num % 10]++;
   }
   for (int i = 0; i < 10; i++) {
         if (cnt[i] != 0 && cnt[i] != i) {
            return false;
      }
   }
   return true;
  }
}

【 NO.3 统计最高分的节点数目】

解题思路
首先进行一次 DFS 求出每个节点的子树大小，然后进行一次 DFS 求出每个节点的分数。

注意计算分数需要用 Long 类型，避免乘法溢出。

代码展示

class Solution {
Long maxScore;
Map<Long, Integer> count;

public int countHighestScoreNodes(int[] parents) {
   List<List<Integer>> children = new ArrayList<>();
   for (int i = 0; i < parents.length; i++) {
         children.add(new ArrayList<>());
   }
   for (int i = 1; i < parents.length; i++) {
         children.get(parents[i]).add(i);
   }
   int[] sum = new int[parents.length];
   calcSum(0, sum, children);
   maxScore = 0L;
   count = new HashMap<>();
   calcMaxScore(0, sum, children);
   return count.get(maxScore);
  }

private void calcMaxScore(int cur, int[] sum, List<List<Integer>> children) {
   long score = 1;
   for (var nxt : children.get(cur)) {
         score *= sum[nxt];
   }
   if (sum[0] - sum[cur] > 0) {
         score *= sum[0] - sum[cur];
   }
   count.put(score, count.getOrDefault(score, 0) + 1);
   maxScore = Math.max(maxScore, score);
   for (var nxt : children.get(cur)) {
         calcMaxScore(nxt, sum, children);
   }
  }

private void calcSum(int cur, int[] sum, List<List<Integer>> children) {
   sum[cur] = 1;
   for (var nxt : children.get(cur)) {
         calcSum(nxt, sum, children);
         sum[cur] += sum[nxt];
   }
  }
}

【 NO.4 并行课程 III】

解题思路
几乎是树型 DP 模板题，比较简单。令 finish(i) 表示完成课程 i 的最短时间，则 finish(i) = max(finish(j)) + time[i]，其中 j 是 i 的前置课程。

代码展示

class Solution {
public int minimumTime(int n, int[][] relations, int[] time) {
   List<List<Integer>> prev = new ArrayList<>();
   for (int i = 0; i < n; i++) {
         prev.add(new ArrayList<>());
   }
   for (int[] rel : relations) {
         prev.get(rel[1] - 1).add(rel[0] - 1);
   }
   int[] mem = new int[n];
   int result = 0;
   for (int i = 0; i < n; i++) {
         result = Math.max(result, finish(i, prev, time, mem));
   }
   return result;
  }

private int finish(int cur, List<List<Integer>> prev, int[] time, int[] mem) {
   if (mem[cur] > 0) {
         return mem[cur];
   }
   if (prev.get(cur).size() == 0) {
         return time[cur];
   }
   for (int p : prev.get(cur)) {
         mem[cur] = Math.max(mem[cur], finish(p, prev, time, mem) + time[cur]);
   }
   return mem[cur];
  }
}

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

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

登录后可回复主题