2024/05/30记录

算法笔记

新题目

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

旧题目

54. 螺旋矩阵 - 力扣（LeetCode）

289. 生命游戏 - 力扣（LeetCode）

48. 旋转图像 - 力扣（LeetCode）

73. 矩阵置零 - 力扣（LeetCode）

20. 有效的括号 - 力扣（LeetCode）

94. 二叉树的中序遍历 - 力扣（LeetCode）

402. 移掉 K 位数字 - 力扣（LeetCode）

316. 去除重复字母 - 力扣（LeetCode）

321. 拼接最大数 - 力扣（LeetCode）

387. 字符串中的第一个唯一字符 - 力扣（LeetCode）

2071. 你可以安排的最多任务数目 - 力扣（LeetCode）

933. 最近的请求次数 - 力扣（LeetCode）

936. 戳印序列 - 力扣（LeetCode）