byu_rself

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 ...

LC.P268[丢失的数字] 方法一：哈希表1234567891011class Solution { public int missingNumber(int[] nums) { Set<Integer> set = new HashSet<>(); for (int num : nums) set.add(num); int n = nums.length; for (int i = 0; i <= nums.length; ++i) { if (!set.contains(i)) return i; } return n; }} 时间复杂度：$O(n)$ 空间复杂度：$O(n)$ 方法二：排序12345678910class Solution { public int missingNumber(int[] nums) { Arr ...

LC.P85[最大矩形] 方法一：二维转一维+单调栈将矩阵的每一行看作是柱状图。 示例 [[“1”,”0”,”1”,”0”,”0”], 第一层，高度为[“1”,”0”,”1”,”0”,”0”] [“1”,”0”,”1”,”1”,”1”], 第二层，高度为[“2”,”0”,”2”,”1”,”1”] [“1”,”1”,”1”,”1”,”1”], 第三层，高度为[“3”,”1”,”3”,”2”,”2”] [“1”,”0”,”0”,”1”,”0”]] 第四层，高度为[“4”,”0”,”0”,”3”,”0”] 求出每一层的最大面积可用LC.P84[柱状图中最大的矩形]，并取其中的最大值即为答案。 12345678910111213141516171819202122232425262728293031323334353637383940class Solution { public int maximalRectangle(char[][] matrix) { if (matrix.leng ...