byu_rself

LC.P745[前缀和后缀搜索] 方法一：暴力(哈希表)1234567891011121314151617181920212223242526class WordFilter { Map<String, Integer> map; public WordFilter(String[] words) { map = new HashMap<>(); for (int i = 0; i < words.length; ++i) { String word = words[i]; int n = word.length(); for (int pref = 1; pref <= n; ++pref) { for (int suff = 1; suff <= n; ++suff) { map.put(word.substring(0 ...

LC.P2455[可被三整除的偶数的平均值] 方法一：模拟123456789101112class Solution { public int averageValue(int[] nums) { int sum = 0, cnt = 0; for (int num : nums) { if (num % 6 == 0) { ++cnt; sum += num; } } return cnt == 0 ? 0 : sum / cnt; }} 时间复杂度：$O(n)$ 空间复杂度：$O(1)$

LC.P676[实现一个魔法字典] 方法一：Trie12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061class MagicDictionary { Trie node; public MagicDictionary() { node = new Trie(); } public void buildDict(String[] dictionary) { for (String s : dictionary) node.insert(s); } public boolean search(String searchWord) { return node.query(searchWord, node, 0, false); } private static ...

LC.P1439[有序矩阵中的第k个最小数组和] 方法一：暴力(遍历+排序)123456789101112131415161718192021class Solution { public int kthSmallest(int[][] mat, int k) { int n = mat[0].length; List<Integer> pre = new ArrayList<>(k), cur = new ArrayList<>(n * k); pre.add(0); for (int[] row : mat) { cur.clear(); for (int a : pre) { for (int b : row) { cur.add(a + b); } } ...

LC.P212[单词搜索II] 方法一：回溯123456789101112131415161718192021222324252627282930313233343536373839404142434445class Solution { Set<String> set; List<String> ans = new ArrayList<>(); char[][] board; int[][] dirs = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; int m, n; boolean[][] visited = new boolean[15][15]; public List<String> findWords(char[][] board, String[] words) { this.board = board ...

LC.P1093[大样本统计] 方法一：模拟123456789101112131415161718192021222324252627class Solution { int[] count; public double[] sampleStats(int[] count) { this.count = count; int minimum = Integer.MAX_VALUE, maximum = -1, cnt = 0, mode = 0; double sum = 0; for (int i = 0; i < count.length; ++i) { if (count[i] > 0) { minimum = Math.min(minimum, i); maximum = Math.max(maximum, i); cnt += count[i]; ...

LC.P1091[二进制矩阵中的最短路径] 方法一：BFS12345678910111213141516171819202122232425262728class Solution { public int shortestPathBinaryMatrix(int[][] grid) { if (grid[0][0] == 1) return -1; int n = grid.length; grid[0][0] = 1; Deque<int[]> queue = new ArrayDeque<>(); queue.offer(new int[]{0, 0}); int ans = 1; while (!queue.isEmpty()) { int size = queue.size(); while (size-- > 0) { ...

LC.P591[标签验证器] 方法一：栈123456789101112131415161718192021222324252627282930313233343536373839404142class Solution { public boolean isValid(String code) { int n = code.length(), i = 0; Deque<String> stack = new ArrayDeque<>(); while (i < n) { if (code.charAt(i) == '<') { // 起始标签 if (i == n - 1) return false; if (code.charAt(i + 1) == '/') { // 结束标签 int j ...

LC.P2451[差值数组不同的字符串] 方法一：哈希表123456789101112131415161718class Solution { public String oddString(String[] words) { Map<String, List<String>> map = new HashMap<>(); int n = words[0].length(); for (String word : words) { var cs = new char[n - 1]; for (int i = 0; i < n - 1; ++i) { cs[i] = (char) (word.charAt(i + 1) - word.charAt(i)); } String s = String.valueOf(cs); ...

LC.P1377[T秒后青蛙的位置] 方法一：BFS123456789101112131415161718192021222324252627282930313233343536373839404142434445464748class Solution { public double frogPosition(int n, int[][] edges, int t, int target) { List<Integer>[] g = new List[n + 1]; Arrays.setAll(g, k -> new ArrayList<>()); for (int[] edge : edges) { int u = edge[0], v = edge[1]; g[u].add(v); g[v].add(u); } Deque<Pair<Integer, Doub ...