上岸算法LeetCode Weekly Contest 264解题报告
【 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;
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) || isNotAlpha(chars))) {
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;
for (; num > 0; num /= 10) {
cnt++;
}
for (int i = 0; i < 10; i++) {
if (cnt != 0 && cnt != 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).add(i);
}
int[] sum = new int;
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;
}
if (sum - sum > 0) {
score *= sum - sum;
}
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 = 1;
for (var nxt : children.get(cur)) {
calcSum(nxt, sum, children);
sum += sum;
}
}
}
【 NO.4 并行课程 III】
解题思路
几乎是树型 DP 模板题，比较简单。令 finish(i) 表示完成课程 i 的最短时间，则 finish(i) = max(finish(j)) + time，其中 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).add(rel - 1);
}
int[] mem = new int;
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 > 0) {
return mem;
}
if (prev.get(cur).size() == 0) {
return time;
}
for (int p : prev.get(cur)) {
mem = Math.max(mem, finish(p, prev, time, mem) + time);
}
return mem;
}
}
页:
[1]