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

  }

}