LeeCode 318周赛复盘

T1: 对数组执行操作

思路：模拟

public int[] applyOperations(int[] nums) {
  int n = nums.length;
  for (int i = 0; i < n - 1; ++i) {
    if (nums[i] == nums[i + 1]) {
      nums[i] = 2 * nums[i];
      nums[i + 1] = 0;
    }
  }

  int[] res = new int[n];

  int index = 0;
  for (int i = 0; i < n; i++) {
    if (nums[i] != 0) {
      res[index++] = nums[i];
    }
  }

  return res;
}

T2: 长度为 K 子数组中的最大和

思路：滑动窗口

public long maximumSubarraySum(int[] nums, int k) {
  int n = nums.length;

  if (k > n) {
    return 0;
  }


  // 哈希存储当前窗口内的数组元素
  Map<Integer, Integer> map = new HashMap<>();
  long res = 0;
  long sum = 0;
  int left = 0, right = 0;

  while (right < n) {
    sum += nums[right];
    map.put(nums[right], map.getOrDefault(nums[right], 0) + 1);

    if (right - left + 1 == k) {
      if (map.size() == k) {
        res = Math.max(res, sum);
      }

      sum -= nums[left];
      map.put(nums[left], map.get(nums[left]) - 1);
      if (map.get(nums[left]) == 0) {
        map.remove(nums[left]);
      }

      left += 1;
    }

    right += 1;
  }

  return res;
}

T3: 雇佣 K 位工人的总代价

思路：小顶堆模拟

• 左堆堆顶元素 $$\le$$ 右堆堆顶元素：弹出左堆值
• 左堆堆顶元素 $$\gt$$ 右堆堆顶元素：弹出右堆值

public long totalCost(int[] costs, int k, int candidates) {
  int n = costs.length;
  long res = 0;

  // 考虑特殊情况，快速返回结果
  if (k == n) {
    for (int cost : costs) {
      res += cost;
    }

    return res;
  }

  if (candidates * 2 >= n) {
    Queue<Integer> heap = new PriorityQueue<>();
    for (int cost : costs) {
      heap.offer(cost);
    }

    while (k > 0) {
      res += heap.poll();
      k -= 1;
    }

    return res;
  }

  // 小顶堆模拟
  Queue<int[]> leftMin = new PriorityQueue<>((o1, o2) -> {
    if (o1[0] == o2[0]) {
      return o1[1] - o2[1];
    }
    else {
      return o1[0] - o2[0];
    }
  });

  Queue<int[]> rightMin = new PriorityQueue<>((o1, o2) -> {
    if (o1[0] == o2[0]) {
      return o1[1] - o2[1];
    }
    else {
      return o1[0] - o2[0];
    }
  });

  int curLen = n;

  for (int i = 0; i < candidates; ++i) {
    leftMin.offer(new int[]{costs[i], i});
    rightMin.offer(new int[]{costs[n - 1 - i], n - 1 - i});
  }


  int leftIndex = candidates;
  int rightIndex = n - candidates - 1;
  while (curLen > 2 * candidates && k > 0) {
    if (leftMin.peek()[0] <= rightMin.peek()[0]) {
      res += leftMin.poll()[0];
      leftMin.offer(new int[]{costs[leftIndex], leftIndex});
      leftIndex += 1;
      curLen -= 1;
    }
    else {
      res += rightMin.poll()[0];
      rightMin.offer(new int[]{costs[rightIndex], rightIndex});
      rightIndex -= 1;
      curLen -= 1;
    }

    k -= 1;
  }

  while (k > 0) {
    if (leftMin.isEmpty()) {
      res += rightMin.poll()[0];
    }
    else if (rightMin.isEmpty()) {
      res += leftMin.poll()[0];
    }
    else {
      res += (leftMin.peek()[0] <= rightMin.peek()[0] ? leftMin.poll()[0] : rightMin.poll()[0]);
    }

    k -= 1;
  }

  return res;
}

T4: 最小移动总距离

• 未完成，待更新