【 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[i] == 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[nums.length]; preSum[0] = nums[0]; for (int i = 1; i < nums.length; i++) { preSum[i] = preSum[i - 1] + nums[i]; } int[] res = new int[nums.length]; Arrays.fill(res, -1); for (int i = k; i + k < nums.length; i++) { long sum = 0; if (i - k == 0) { sum = preSum[i + k]; } else { sum = preSum[i + k] - preSum[i - k - 1]; } res[i] = (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[i] < nums[min]) { min = i; } if (nums[i] > nums[max]) { 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[2])) { orderedMeetings.put(m[2], new ArrayList<>()); } orderedMeetings.get(m[2]).add(m); } boolean[] known = new boolean[n]; known[0] = known[firstPerson] = true; while (!orderedMeetings.isEmpty()) { // 依照工夫程序解决每一波会议 var entry = orderedMeetings.pollFirstEntry(); var curMeetings = entry.getValue(); // 应用并查集保护以后工夫点产生的所有会议中，有关联的人 UnionFind uf = new UnionFind(n); for (var m : curMeetings) { uf.merge(m[0], m[1]); } // 枚举所有会议 // 若会议加入人 m[0] 或 m[1] 通晓机密 // 则把他们所在的根节点也标记为通晓机密 for (var m : curMeetings) { if (known[m[0]] || known[m[1]]) { known[uf.find(m[0])] = true; known[uf.find(m[1])] = true; } } // 枚举所有的参会人，若他们所在的根节点通晓机密，则把他们也标记为通晓机密 for (var m : curMeetings) { if (known[uf.find(m[0])] || known[uf.find(m[1])]) { known[m[0]] = true; known[m[1]] = true; } } } List<Integer> res = new ArrayList<>(); for (int i = 0; i < n; i++) { if (known[i]) { res.add(i); } } return res;}
}
class UnionFind {
public UnionFind(int size) {
f = new int[size]; Arrays.fill(f, -1);}
public int find(int x) {
if (f[x] < 0) return x; return f[x] = find(f[x]);}
public boolean merge(int a, int b) {
int fa = find(a); int fb = find(b); if (fa == fb) return false; f[fa] = 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;
}