2024/05/30记录
算法笔记 新题目 480. 滑动窗口中位数 - 力扣（LeetCode） https://leetcode.cn/problems/sliding-window-median/description/?envType=study-plan-v2&envId=2024-spring-sprint-100 30. 串联所有单词的子串 - 力扣（LeetCode） https://leetcode.cn/problems/…
算法笔记
新题目
480. 滑动窗口中位数 - 力扣（LeetCode）
class Solution {
// 左边是大根堆
// Compartor记得使用Integer来比较，或者使用Comparator.reversOrder()
PriorityQueue<Integer> left = new PriorityQueue<>((o1, o2) -> Integer.compare(o2, o1));
// 右边是小根堆
PriorityQueue<Integer> right = new PriorityQueue<>((o1, o2) -> Integer.compare(o1, o2));
// 记录那些需要被删除的元素，用于延迟删除
Map<Integer, Integer> map = new HashMap<>();
public double[] medianSlidingWindow(int[] nums, int k) {
int cnt = nums.length - k + 1;
double[] ans = new double[cnt];
int index = 0;
// 默认右边比左边多一个，如果窗口大小是奇数
for (int i = 0; i < k; i++) {
right.offer(nums[i]);
}
for (int i = 0; i < k / 2; i++) {
left.offer(right.poll());
}
ans[index++] = getMid(k);
for (int i = k; i < nums.length; i++) {
int balance = 0; // balance = left.size() - right.size()
int l = nums[i - k];
map.put(l, map.getOrDefault(l, 0) + 1);
// 左边是大根堆 左边的堆顶 <= 右边的堆顶
if (!left.isEmpty() && l <= left.peek()) {
balance--;
} else {
balance++;
}
int r = nums[i];
if (!left.isEmpty() && r <= left.peek()) {
left.offer(r);
balance++;
} else {
right.offer(r);
balance--;
}
// 别忘记平衡
if (balance < 0) { // 说明右边多了
left.offer(right.poll());
} else if (balance > 0) {
right.offer(left.poll());
}
while (!left.isEmpty() && map.getOrDefault(left.peek(), 0) > 0) {
// 记住要实时更新map
map.put(left.peek(), map.getOrDefault(left.peek(), 0) - 1);
left.poll();
}
while (!right.isEmpty() && map.getOrDefault(right.peek(), 0) > 0) {
map.put(right.peek(), map.getOrDefault(right.peek(), 0) - 1);
right.poll();
}
ans[index++] = getMid(k);
}
return ans;
}
public double getMid(int k) {
if (k % 2 == 0) return ((long) left.peek() + right.peek()) * 0.5;
return right.peek();
}
}30. 串联所有单词的子串 - 力扣（LeetCode）
// 1447ms 32.04% 龟速版
class Solution {
Map<String, Integer> map = new HashMap<>();
public List<Integer> findSubstring(String s, String[] words) {
// 这题的思路感觉像是大的滑动窗口，依次检测，检测的时候使用小的窗口
for (int i = 0; i < words.length; i++) {
map.put(words[i], map.getOrDefault(words[i], 0) + 1);
}
int k = words[0].length();
int w = k * words.length;
List<Integer> ans = new ArrayList<>();
// 这个遍历条件要注意，可以写成 <= s.length() - w 也可以写为 < s.length() - w + 1
for (int i = 0; i < s.length() - w + 1; i++ ) {
if (check(s, i, i + w - 1, k)) {
ans.add(i);
}
}
return ans;
}
// 传入的范围左闭右闭
public boolean check(String s, int start, int end, int k) {
Map<String, Integer> tMap = new HashMap<>();
for (int i = start; i <= end - k + 1; i += k) {
String t = s.substring(i, i + k);
if (!map.containsKey(t)) {
return false;
}
tMap.put(t, tMap.getOrDefault(t, 0) + 1);
}
for (Map.Entry<String, Integer> e : tMap.entrySet()) {
// 使用Integer进行大小比较的时候，还是使用equals更好，直接使用=可能会出现Bug
if (!e.getValue().equals(map.get(e.getKey()))) {
return false;
}
}
return true;
}
}658. 找到 K 个最接近的元素 - 力扣（LeetCode）
39 ms 5.43% 龟速版
class Solution {
public List<Integer> findClosestElements(int[] arr, int k, int x) {
PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> {
if (Math.abs(o2 - x) == Math.abs(o1 - x)) return o2 - o1;
return Math.abs(o2 - x) - Math.abs(o1 - x);
});
for (int i = 0; i < arr.length; i++) {
queue.offer(arr[i]);
while (queue.size() > k) {
queue.poll();
}
}
List<Integer> ans = new ArrayList<>(queue);
Collections.sort(ans);
return ans;
}
}23ms 17.31% 不同的思路，这个直接排序
class Solution {
public List<Integer> findClosestElements(int[] arr, int k, int x) {
List<Integer> list = new ArrayList<Integer>();
for (int num : arr) {
list.add(num);
}
Collections.sort(list, (a, b) -> {
if (Math.abs(a - x) != Math.abs(b - x)) {
return Math.abs(a - x) - Math.abs(b - x);
} else {
return a - b;
}
});
List<Integer> ans = list.subList(0, k);
Collections.sort(ans);
return ans;
}
}3ms 99.61% 快解法 二分查找 + 双指针
class Solution {
public List<Integer> findClosestElements(int[] arr, int k, int x) {
int right = binarySearch(arr, x);
int left = right - 1;
while (k-- > 0) {
if (left < 0) {
right++;
} else if (right >= arr.length) {
left--;
} else if (x - arr[left] <= arr[right] - x) {
left--;
} else {
right++;
}
}
List<Integer> ans = new ArrayList<>();
for (int i = left + 1; i < right; i++) {
ans.add(arr[i]);
}
return ans;
}
public int binarySearch(int[] arr, int x) {
int low = 0, high = arr.length - 1;
while (low < high) {
int mid = low + (high - low) / 2;
if (arr[mid] >= x) {
high = mid;
} else {
low = mid + 1;
}
}
return low;
}
}632. 最小区间 - 力扣（LeetCode）
class Solution {
public int[] smallestRange(List<List<Integer>> nums) {
int rangeLeft = 0, rangeRight = Integer.MAX_VALUE;
int minRange = rangeRight - rangeLeft;
int max = Integer.MIN_VALUE;
int size = nums.size();
// 这个数组存储了nums.length个指针，用于遍历各个数组
int[] next = new int[size];
// 优先级队列按照每个数组的逻辑最左组成小根堆，每次都能获取到，所有数组中，最小的那一个
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>((index1, index2) -> {
return nums.get(index1).get(next[index1]) - nums.get(index2).get(next[index2]);
});
// 将所有数组的第一个元素加入优先级队列，同时维护目前队列中元素的最大值
for (int i = 0; i < size; i++) {
priorityQueue.offer(i);
max = Math.max(max, nums.get(i).get(0));
}
while (true) {
// 每次都取出最小值，计算得到当前的元素范围，并尝试更新最小元素范围
int minIndex = priorityQueue.poll();
int curRange = max - nums.get(minIndex).get(next[minIndex]);
if (curRange < minRange) {
minRange = curRange;
rangeLeft = nums.get(minIndex).get(next[minIndex]);
rangeRight = max;
}
next[minIndex]++;
// 将有一个数组的元素用尽，就结束了
if (next[minIndex] == nums.get(minIndex).size()) {
break;
}
priorityQueue.offer(minIndex);
max = Math.max(max, nums.get(minIndex).get(next[minIndex]));
}
return new int[]{rangeLeft, rangeRight};
}
}718. 最长重复子数组 - 力扣（LeetCode）
class Solution {
public int findLength(int[] nums1, int[] nums2) {
int[][] dp = new int[nums1.length + 1][nums2.length + 1];
int ans = Integer.MIN_VALUE;
for (int i = 1; i <= nums1.length; i++) {
for (int j = 1; j <= nums2.length; j++) {
if (nums1[i - 1] == nums2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
}
ans = Math.max(ans, dp[i][j]);
}
}
return ans;
}
}