KMP
KMP
KMP算法的大致思路：进行模式匹配时，主串指针不回溯，只有模式串回溯，时间复杂度为 $O(n + m)$，其中 $n$ 为主串长度， $m$ 为模式串长度
构建next数组123456789101112131415void getNext(String pp, int[] next) { int m = pp.length(); // 使下标从 1 开始 pp = " " + pp; char[] p = pp.toCharArray(); for (int i = 1, j = 0; i < m; ) { if (j == 0 || p[i] == p[j]) { ++i; ++j; next[i] = j; } else { j = next[j]; // 匹配失败 } } }
KMP模式匹配12345 ...
LC.P2336[无限集中的最小数字]
LC.P2336[无限集中的最小数字]
方法一：有序集合12345678910111213141516171819202122232425class SmallestInfiniteSet { TreeSet<Integer> set = new TreeSet<>(); public SmallestInfiniteSet() { for (int i = 1; i <= 1000; ++i) { set.add(i); } } public int popSmallest() { return set.pollFirst(); } public void addBack(int num) { set.add(num); }}/** * Your SmallestInfiniteSet object will be instantiate ...
LC.P1668[最大重复子字符串]
LC.P1668[最大重复子字符串]
方法一：暴力枚举12345678class Solution { public int maxRepeating(String sequence, String word) { for (int k = sequence.length() / word.length(); k >= 0; --k) { if (sequence.contains(word.repeat(k))) return k; } return 0; }}
时间复杂度：$O(n^2)$
空间复杂度：$O(1)$
方法二：动态规划1234567891011121314class Solution { public int maxRepeating(String sequence, String word) { int n = sequence.length(), m = word.length( ...
LC.P1670[设计前中后队列]
LC.P1670[设计前中后队列]
方法一：两个双端队列123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869class FrontMiddleBackQueue { Deque<Integer> left; Deque<Integer> right; public FrontMiddleBackQueue() { left = new ArrayDeque<>(); right = new ArrayDeque<>(); } /** * 调整长度 * 保证 0 <= right.size() - left.size() <= 1 */ private void balance() { ...
LC.P907[子数组的最小值之和]
LC.P907[子数组的最小值之和]
方法一：单调栈（三次遍历）123456789101112131415161718192021222324252627282930313233class Solution { private static final int MOD = (int) (1e9 + 7); public int sumSubarrayMins(int[] arr) { int n = arr.length; int[] left = new int[n], right = new int[n]; Deque<Integer> stack = new ArrayDeque<>(); stack.push(-1); for (int i = 0; i < n; ++i) { // 左边界 left[i] 为左侧严格小于 arr[i] 的最近元素位置（不存在时为-1） while (stack ...
LC.P1457[二叉树中的伪回文路径]
LC.P1457[二叉树中的伪回文路径]
方法一：DFS+位运算1234567891011121314151617181920212223242526272829/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */public class Solution { pub ...
LC.P677[键值映射]
LC.P677[键值映射]
方法一：Trie+DFS123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960class MapSum { Trie trie; public MapSum() { trie = new Trie(); } public void insert(String key, int val) { trie.insert(key, val); } public int sum(String prefix) { Trie node = trie; for (int i = 0; i < prefix.length(); ++i) { int u = prefix.charAt(i) - 'a'; ...
LC.P2824[统计和小于目标的下标对数目]
LC.P2824[统计和小于目标的下标对数目]
方法一：枚举12345678910111213class Solution { public int countPairs(List<Integer> nums, int target) { int ans = 0, n = nums.size(); for (int i = 0; i < n - 1; ++i) { for (int j = i + 1; j < n; ++j) { if (nums.get(i) + nums.get(j) < target) { ++ans; } } } return ans; }}
时间复杂度：$O(n^2)$
空间复杂度：$O(1)$
方法二：排序+二分查找 ...
LC.P1410[HTML实体解析器]
LC.P1410[HTML实体解析器]
方法一：模拟1234567891011121314151617181920212223242526272829303132333435363738class Solution { private static final Map<String, String> map = new HashMap<>(){{ put(""", "\""); put("'", "'"); put("&", "&"); put(">", ">"); put("<", "<"); put("&fr ...
LC.P1786[从第一个节点出发到最后一个节点的受限路径数]
LC.P1786[从第一个节点出发到最后一个节点的受限路径数]
方法一：堆优化Dijkstra+动态规划123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657class Solution { private static final int MOD = (int) 1e9 + 7; public int countRestrictedPaths(int n, int[][] edges) { Map<Integer, List<int[]>> map = new HashMap<>(); for (int[] e : edges) { int a = e[0], b = e[1], w = e[2]; map.computeIfAbsent(a, k -> new Arr ...