学习内容

1. 力扣每日一题

https://leetcode.cn/problems/lexicographically-minimum-string-after-removing-stars?envType=daily-question&envId=2025-06-07

先是尝试优先队列，最小堆找前面的最小元素，然后遇到*就删除，但时间复杂度为On2，特殊用例超时了。
然后发现可以用栈模拟二十六个字母，栈中存储下标，遇到*出栈最小的字符。
优化点：可以使用二进制掩码来表示最小的非空栈在哪里。

2. 学习完java并发篇

笔记记录在java并发篇.

3. 把昨天的题用堆来完善一下

维护小顶堆求前k大的元素。

4. 学习KMP算法.

KMP算法是一种字符串匹配算法，它的时间复杂度为O(n+m)，其中n是文本串的长度，m是模式串的长度。
贴一个模板,原理已经理解了，但是代码还需要再写一遍：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
    // KMP 算法
    // ss: 原串(string)  pp: 匹配串(pattern)
    public int strStr(String ss, String pp) {
        if (pp.isEmpty()) return 0;
        
        // 分别读取原串和匹配串的长度
        int n = ss.length(), m = pp.length();
        // 原串和匹配串前面都加空格，使其下标从 1 开始
        ss = " " + ss;
        pp = " " + pp;

        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();

        // 构建 next 数组，数组长度为匹配串的长度（next 数组是和匹配串相关的）
        int[] next = new int[m + 1];
        // 构造过程 i = 2，j = 0 开始，i 小于等于匹配串长度 【构造 i 从 2 开始】
        for (int i = 2, j = 0; i <= m; i++) {
            // 匹配不成功的话，j = next(j)
            while (j > 0 && p[i] != p[j + 1]) j = next[j];
            // 匹配成功的话，先让 j++
            if (p[i] == p[j + 1]) j++;
            // 更新 next[i]，结束本次循环，i++
            next[i] = j;
        }

        // 匹配过程，i = 1，j = 0 开始，i 小于等于原串长度 【匹配 i 从 1 开始】
        for (int i = 1, j = 0; i <= n; i++) {
            // 匹配不成功 j = next(j)
            while (j > 0 && s[i] != p[j + 1]) j = next[j];
            // 匹配成功的话，先让 j++，结束本次循环后 i++
            if (s[i] == p[j + 1]) j++;
            // 整一段匹配成功，直接返回下标
            if (j == m) return i - m;
        }

        return -1;
    }
}
许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。