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 ...
LC.P2304[网格中的最小路径代价]
LC.P2304[网格中的最小路径代价]
方法一：记忆化搜索1234567891011121314151617181920212223242526272829class Solution { int m, n; int[][] grid; int[][] moveCost; int[][] cache; public int minPathCost(int[][] grid, int[][] moveCost) { m = grid.length; n = grid[0].length; this.grid = grid; this.moveCost = moveCost; cache = new int[m][n]; int ans = Integer.MAX_VALUE; for (int j = 0; j < n; ++j) { ans = Math.min(ans, dfs(0, j)); ...
LC.P274[H指数]
LC.P274[H指数]
方法一：二分查找123456789101112131415class Solution { public int hIndex(int[] citations) { int left = 0, right = citations.length; while (left < right) { int mid = left + right + 1 >> 1; int s = 0; for (int x : citations) { if (x >= mid) ++s; } if (s >= mid) left = mid; else right = mid - 1; } return left; }}
时间复杂度：$O(nlo ...