上岸算法LeetCode Weekly Contest 269解题报告

上岸算法 · 发表于 2021-11-28 19:33:10

登录后可回复主题

您需要登录才可以下载或查看，没有帐号？注册账号

x

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

帐号		自动登录	找回密码
密码			注册账号

[吹水聊天] 上岸算法LeetCode Weekly Contest 269解题报告

登录后可回复主题