上岸算法 I LeetCode Weekly Contest 232解题报告
本帖最后由 上岸算法 于 2021-3-17 08:30 编辑No.1 仅执行一次字符串交换能否使两个字符串相等解题思路签到题，枚举一遍统计出所有不想等的位置。代码展示class Solution {
public boolean areAlmostEqual(String s1, String s2) {
List<Integer> differ = new ArrayList<>();
for (int i = 0; i < s1.length(); i++) {
if (s1.charAt(i) != s2.charAt(i)) {
differ.add(i);
}
}
return differ.size() == 0 ||
(differ.size() == 2 &&
s1.charAt(differ.get(0)) == s2.charAt(differ.get(1)) &&
s1.charAt(differ.get(1)) == s2.charAt(differ.get(0))
);
}
}
No.2 找出星型图的中心节点解题思路n 个点 n - 1 条边必然是树。因为是星型图，所以叶子结点的度数均为 1. 只要一个节点在边中出现了两次以上，它必然是中心节点。代码展示class Solution {
public int findCenter(int[][] edges) {
Set<Integer> set = new HashSet<>();
for (var edge : edges) {
for (int e : edge) {
if (set.contains(e)) {
return e;
}
set.add(e);
}
}
return -1;
}
}
No.3 最大平均通过率解题思路贪心，每次放一个学生进入某一个班级，进入能提升通过率提升地最多的那个班级。代码展示class Solution {
static class Class {
int pass;
int total;
public Class(int pass, int total) {
this.pass = pass;
this.total = total;
}
double differ() {
return (double) (pass + 1) / (total + 1) - (double) pass / total;
}
}
public double maxAverageRatio(int[][] classes, int extraStudents) {
PriorityQueue<Class> heap = new PriorityQueue<>((c1, c2) -> c1.differ() > c2.differ() ? -1 : 1);
for (var c : classes) {
heap.add(new Class(c, c));
}
for (int i = 0; i < extraStudents; i++) {
Class c = heap.poll();
heap.add(new Class(c.pass + 1, c.total + 1));
}
double sum = 0;
while (!heap.isEmpty()) {
Class c = heap.poll();
sum += (double) c.pass / c.total;
}
return sum / classes.length;
}
}
No.4 好子数组的最大分数
解题思路单调栈，与最大柱状图类似，找到一个值的左右侧第一个比它小的即可。代码展示class Solution {
public int maximumScore(int[] nums, int k) {
int[] heap = new int;
int top = 0;
int res = 0;
for (int i = 0; i < nums.length; i++) {
while (top > 0 && nums] > nums) {
int right = i;
int left = top > 1 ? heap : -1;
if (left < k && right > k) {
res = Math.max(res, (right - left - 1) * nums]);
}
top--;
}
heap[++top] = i;
}
while (top > 0) {
int right = nums.length;
int left = top > 1 ? heap : -1;
if (left < k && right > k) {
res = Math.max(res, (right - left - 1) * nums]);
}
top--;
}
return res;
}
}联系上岸小助手年糕，参与免费带刷
页:
[1]