刷题记录

1. kmp 模式匹配

class Solution {
    /**
     * 使用KMP算法在haystack中查找needle的首次出现位置
     * @param haystack 主字符串
     * @param needle 要查找的子串
     * @return 首次出现的位置索引，未找到返回-1
     */
    public int strStr(String haystack, String needle) {
        // 处理特殊情况：空子串直接返回0
        if (needle.length() == 0) return 0;

        // 生成KMP算法的next数组（部分匹配表）
        int[] next = new int[needle.length()];
        getNext(next, needle);

        int j = -1; // 模式串指针，初始化为-1（表示尚未开始匹配）
        for (int i = 0; i < haystack.length(); i++) { // 主串指针i永不回退
            // 当字符不匹配时，根据next数组回退模式串指针
            while (j >= 0 && haystack.charAt(i) != needle.charAt(j + 1)) {
                j = next[j]; // 核心操作：利用前缀信息跳过不可能的比较
            }
            
            // 当前字符匹配，模式串指针前进
            if (haystack.charAt(i) == needle.charAt(j + 1)) {
                j++;
            }
            
            // 完全匹配时返回起始位置
            if (j == needle.length() - 1) {
                // 计算起始位置：当前i的位置减去模式串长度 + 1
                return i - needle.length() + 1;
            }
        }
        return -1;
    }

    /**
     * 生成KMP算法的next数组（部分匹配表）
     * 核心思想：计算模式串的最长相同前后缀长度，用于失配时快速跳转
     * @param next 生成的next数组
     * @param s 模式串
     */
    private void getNext(int[] next, String s) {
        int j = -1; // 前缀末尾位置（同时表示当前最长相同前后缀长度）
        next[0] = j; // 初始化第一个位置的next值为-1
        for (int i = 1; i < s.length(); i++) { // i表示后缀末尾位置
            // 前后缀不相同，回退到前一个匹配位置
            while (j >= 0 && s.charAt(i) != s.charAt(j + 1)) {
                j = next[j]; // 核心操作：利用已计算的next信息快速回退
            }
            
            // 找到相同的前后缀，j前进
            if (s.charAt(i) == s.charAt(j + 1)) {
                j++;
            }
            
            // 记录当前位置的最长相同前后缀长度
            next[i] = j; 
        }
    }
}

2. 滑动窗口最大值

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums==null||nums.length==0||k<=0) return new int[0];
        int n = nums.length;
        int[] res = new int[n-k+1];
        Deque<Integer> q = new LinkedList<>();
        for(int i=0;i<n;i++){
            // 范围是[i-k+1, i]，删掉不匹配的下标
            while(!q.isEmpty() && q.peekFirst()<i-k+1){
                q.pollFirst();
            }
            // 维护队列的单调性，队首下标对应的元素最大
            while(!q.isEmpty() && nums[q.peekLast()]<nums[i]){
                q.pollLast();
            }
            // 将当前下标插入到合适位置（从后往前看）
            q.offerLast(i);
            // 从i=k-1开始就已经遍历完第一个窗口了
            // 此后隔一步添加一个res值就是目标值
            if(i>=k-1){
                res[i-k+1] = nums[q.peekFirst()];
            }
        }
        return res;
    }
}

3. 优先队列寻找前k个高频元素

public class Solution {
    /**
     * 使用最大堆策略获取前K个高频元素
     * 时间复杂度：O(n log n) 适用于n个不同元素的情况
     * 空间复杂度：O(n) 用于存储哈希表和优先队列
     * @param nums 输入数组
     * @param k 需要返回的高频元素个数
     * @return 前k个高频元素数组
     */
    public int[] topKFrequent(int[] nums, int k) {
        // 步骤1：频率统计 - 使用哈希表记录每个数字出现次数
        // 关键点：getOrDefault方法简化计数逻辑
        Map<Integer, Integer> frequencyMap = new HashMap<>();
        for (int num : nums) {
            frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
        }

        // 步骤2：创建最大堆 - 按频率降序排列
        // 比较器说明：pair2[1] - pair1[1]实现最大堆（每次取频率最高的元素）
        // 空间权衡：将所有元素入堆，当k<<n时可考虑最小堆优化（见注释说明）
        PriorityQueue<int[]> maxHeap = new PriorityQueue<>(
            (pair1, pair2) -> pair2[1] - pair1[1]
        );
        
        // 将哈希表条目转换为堆元素 [数字, 频率]
        for (Map.Entry<Integer, Integer> entry : frequencyMap.entrySet()){
            maxHeap.add(new int[]{entry.getKey(), entry.getValue()});
        }

        // 步骤3：提取结果 - 从堆中取出前k个元素
        int[] result = new int[k];
        for(int i = 0; i < k; i++){
            // 每次poll操作时间复杂度O(log n)
            result[i] = maxHeap.poll()[0]; // 提取数字部分
        }
        
        return result;
    }
}

// 算法优化提示：
// 当k远小于不同元素数量n时，建议使用最小堆优化（时间复杂度降为O(n log k)）
// 实现方式：
// 1. 创建大小为k的最小堆（Comparator维持堆顶为当前最小频率）
// 2. 遍历频率哈希表：
//    - 当堆大小<k时直接添加
//    - 否则比较当前元素频率与堆顶频率，保留更大的
// 3. 最后将堆中元素输出

// 边界条件注意：
// 1. 题目保证k在有效范围内（1 ≤ k ≤ 不同元素个数）
// 2. 结果数组元素顺序不影响答案正确性（本题只要求元素集合）