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