byu_rself

LC.P211[添加与搜索单词-数据结构设计] 方法一：Trie+DFS1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465class WordDictionary { Trie trie; public WordDictionary() { trie = new Trie(); } public void addWord(String word) { trie.add(word); } public boolean search(String word) { return dfs(word, 0, trie); } private boolean dfs(String word, int index, Trie node) { ...

LC.P1993[树上的操作] 方法一：DFS1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071class LockingTree { int[] locked; int[] parent; List<Integer>[] children; public LockingTree(int[] parent) { int n = parent.length; locked = new int[n]; this.parent = parent; children = new List[n]; Arrays.fill(locked, -1); Arrays.setAll(children, k -> new ArrayList<& ...

LC.P2246[相邻字符不同的最长路径] 方法一：树形DP12345678910111213141516171819202122232425262728class Solution { List<Integer>[] g; String s; int ans; public int longestPath(int[] parent, String s) { this.s = s; int n = parent.length; g = new ArrayList[n]; Arrays.setAll(g, k -> new ArrayList<>()); for (int i = 1; i < n; ++i) g[parent[i]].add(i); dfs(0); return ans + 1; } private int dfs(int x) { int ...

LC.P2591[将钱分给最多的儿童] 方法一：分类讨论12345678class Solution { public int distMoney(int money, int children) { if (money < children) return -1; if (money > 8 * children) return children - 1; if (money == 8 * children - 4) return children - 2; return (money - children) / 7; }} 时间复杂度：$O(1)$ 空间复杂度：$O(1)$

LC.P124[二叉树中的最大路径和] 方法一：DFS1234567891011121314151617181920212223242526272829303132333435/** * 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; * } * } */class Solution { ...

LC.P2603[收集树中金币] 方法一：拓扑排序123456789101112131415161718192021222324252627282930313233343536373839404142434445464748class Solution { public int collectTheCoins(int[] coins, int[][] edges) { int n = coins.length; List<Integer>[] g = new ArrayList[n]; Arrays.setAll(g, e -> new ArrayList<>()); int[] degree = new int[n]; for (int[] e : edges) { int x = e[0], y = e[1]; g[x].add(y); g[y].add(x); ...

LCP.P6[拿硬币] 方法一：数学123456789class Solution { public int minCount(int[] coins) { int ans = 0; for (int coin : coins) { ans += (coin + 1) >> 1; } return ans; }} 时间复杂度：$O(n)$ 空间复杂度：$O(1)$

LC.P2560[打家劫舍IV] 方法一：二分查找+动态规划12345678910111213141516171819202122232425262728class Solution { public int minCapability(int[] nums, int k) { int left = 0, right = 0; for (int x : nums) { right = Math.max(right, x); } while (left < right) { int mid = left + right >>> 1; if (check(nums, k, mid)) right = mid; else left = mid + 1; } return right; } private bool ...

LC.P74[搜索二维矩阵] 方法一：二分123456789101112class Solution { public boolean searchMatrix(int[][] matrix, int target) { int m = matrix.length, n = matrix[0].length; int left = 0, right = m * n - 1; while (left < right) { int mid = left + right >> 1; if (matrix[mid / n][mid % n] >= target) right = mid; else left = mid + 1; } return matrix[left / n][left % n] == target; }} 时间复杂度：$O(log(mn)) ...

LC.P653[两数之和IV-输入二叉搜索树] 方法一：哈希表+DFS1234567891011121314151617181920212223242526/** * 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; * } * } */class Solution { Set<In ...