上岸算法LeetCode Weekly Contest 269解题报告
【 NO.1 找出数组排序后的目标下标】解题思路
签到题，循环判断即可。
代码展示
class Solution {
public List<Integer> targetIndices(int[] nums, int target) {
Arrays.sort(nums);
List<Integer> res = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
if (nums == target) {
res.add(i);
}
}
return res;
}
}
【 NO.2 半径为 k 的子数组平均值】
解题思路
使用前缀和计算区间和。注意使用 long 类型以避免溢出。
代码展示
class Solution {
public int[] getAverages(int[] nums, int k) {
if (k == 0) {
return nums;
}
long[] preSum = new long;
preSum = nums;
for (int i = 1; i < nums.length; i++) {
preSum = preSum + nums;
}
int[] res = new int;
Arrays.fill(res, -1);
for (int i = k; i + k < nums.length; i++) {
long sum = 0;
if (i - k == 0) {
sum = preSum;
} else {
sum = preSum - preSum;
}
res = (int) (sum / (long) (k * 2 + 1));
}
return res;
}
}
【 NO.3 从数组中移除最大值和最小值】
解题思路
贪心，按照最小的花费移除即可。详见注释。
代码展示
class Solution {
public int minimumDeletions(int[] nums) {
if (nums.length <= 2) {
return nums.length;
}
// 找出最大值和最小值的下标，由于 len > 2 且元素互不相同，所以最终 max 一定不等于 min
int min = 0, max = 0;
for (int i = 1; i < nums.length; i++) {
if (nums < nums) {
min = i;
}
if (nums > nums) {
max = i;
}
}
// 要移除的元素下标为 max 和 min
// 此时我们只关心下标，谁是最大值谁是最小值不重要
// 为了方便处理，令 min 为较小的下标
if (min > max) {
int t = min;
min = max;
max = t;
}
int res = 0;
int left = 0, right = nums.length - 1;
if (min - left + 1 < right - max + 1) {
res += min - left + 1; // 贪心，移除 min 需要更少的操作，先移除 min
left = min + 1;
res += Math.min(max - left + 1, right - max + 1); // 然后再移除 max
} else {
res += right - max + 1;
right = max - 1;
res += Math.min(min - left + 1, right - min + 1);
}
return res;
}
}
【 NO.4 找出知晓秘密的所有专家】
解题思路
并查集，详见注释。
代码展示
class Solution {
public List<Integer> findAllPeople(int n, int[][] meetings, int firstPerson) {
// 按照时间点将会议分组
TreeMap<Integer, List<int[]>> orderedMeetings = new TreeMap<>();
for (var m : meetings) {
if (!orderedMeetings.containsKey(m)) {
orderedMeetings.put(m, new ArrayList<>());
}
orderedMeetings.get(m).add(m);
}
boolean[] known = new boolean;
known = known = true;
while (!orderedMeetings.isEmpty()) {
// 按照时间顺序处理每一波会议
var entry = orderedMeetings.pollFirstEntry();
var curMeetings = entry.getValue();
// 使用并查集维护当前时间点发生的所有会议中，有关联的人
UnionFind uf = new UnionFind(n);
for (var m : curMeetings) {
uf.merge(m, m);
}
// 枚举所有会议
// 若会议参加人 m 或 m 知晓秘密
// 则把他们所在的根节点也标记为知晓秘密
for (var m : curMeetings) {
if (known] || known]) {
known)] = true;
known)] = true;
}
}
// 枚举所有的参会人，若他们所在的根节点知晓秘密，则把他们也标记为知晓秘密
for (var m : curMeetings) {
if (known)] || known)]) {
known] = true;
known] = true;
}
}
}
List<Integer> res = new ArrayList<>();
for (int i = 0; i < n; i++) {
if (known) {
res.add(i);
}
}
return res;
}
}
class UnionFind {
public UnionFind(int size) {
f = new int;
Arrays.fill(f, -1);
}
public int find(int x) {
if (f < 0)
return x;
return f = find(f);
}
public boolean merge(int a, int b) {
int fa = find(a);
int fb = find(b);
if (fa == fb)
return false;
f = fb;
return true;
}
public Map<Integer, List<Integer>> sets() {
Map<Integer, List<Integer>> res = new HashMap<>();
for (int i = 0; i < f.length; i++) {
int fi = find(i);
if (!res.containsKey(fi)) {
res.put(fi, new ArrayList<>());
}
res.get(fi).add(i);
}
return res;
}
private int[] f;
}
页:
[1]