byu_rself

LC.P1261[在受污染的二叉树中查找元素] 方法一：DFS+哈希表1234567891011121314151617181920212223242526272829303132333435363738394041424344/** * 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; * } * } */cl ...

LC.P2834[找出美丽数组的最小和] 方法一：贪心+等差数列123456789101112131415161718class Solution { private static final int MOD = (int) 1e9 + 7; /* 对于[1, k - 1]内的数字: 1 和 k - 1 只能选其中一个; 2 和 k - 2 只能选其中一个; 3 和 k - 3 只能选其中一个; ... 一直到 k / 2，无论 k 是奇数还是偶数，它都可以选 */ public int minimumPossibleSum(int n, int k) { long m = k / 2; return n <= m ? (int) ((long) (1 + n) * n / 2 % MOD) : (int) ((m * (m + 1) + ((long) k + k + n - m - 1) * ...

LC.P2575[找出字符串的可整除数组] 方法一：模运算123456789101112131415161718192021class Solution { public int[] divisibilityArray(String word, int m) { int n = word.length(); int[] ans = new int[n]; long x = 0; /* 设 a = k1 * m + r1, b = k2 * m + r2 那么 (a + b) mod m = (r1 + r2) mod m = (a mod m + b mod m) mod m 设[0, i - 1]表示的数为 k * m + r, [0, i]表示的数则为 10 * (k * m + r) + nums[i] 则(10 * (k * m + r) + nums[i]) mod m = (10 * r + nums[i] ...

LC.P2917[找出数组中的K-or值] 方法一：位运算123456789101112131415class Solution { public int findKOr(int[] nums, int k) { int ans = 0; for (int i = 0; i < 31; ++i) { int cnt1 = 0; // 统计第i位是1的个数 for (int x : nums) { cnt1 += (x >> i) & 1; } if (cnt1 >= k) { ans |= 1 << i; } } return ans; }} 时间复杂度：$O(nlogM)$，其中 $n$ 为 $nums$ ...

LC.P232[用栈实现队列] 方法一：模拟123456789101112131415161718192021222324252627282930313233343536373839404142class MyQueue { Deque<Integer> s1; Deque<Integer> s2; public MyQueue() { s1 = new ArrayDeque<>(); s2 = new ArrayDeque<>(); } public void push(int x) { s1.push(x); } public int pop() { int x = peek(); s2.pop(); return x; } public int peek() { if (!s2.i ...

LC.P225[用队列实现栈] 方法一：模拟123456789101112131415161718192021222324252627282930313233343536373839404142import java.util.Deque;class MyStack { Deque<Integer> q1; Deque<Integer> q2; public MyStack() { q1 = new ArrayDeque<>(); q2 = new ArrayDeque<>(); } public void push(int x) { q2.offer(x); while (!q1.isEmpty()) { q2.offer(q1.poll()); } Deque<Integer> q = q1; q1 = q2; ...

LC.P2368[受限条件下可到达节点的数目] 方法一：DFS1234567891011121314151617181920212223242526272829303132class Solution { List<Integer>[] g; int ans; Set<Integer> set; public int reachableNodes(int n, int[][] edges, int[] restricted) { g = new List[n]; Arrays.setAll(g, k -> new ArrayList<>()); for (int[] e : edges) { int a = e[0], b = e[1]; g[a].add(b); g[b].add(a); } set = new HashSet<>() ...

LC.P2369[检查数组是否存在有效划分] 方法一：记忆化搜索123456789101112131415161718192021class Solution { int[] nums; int n; Boolean[] f; public boolean validPartition(int[] nums) { this.nums = nums; n = nums.length; f = new Boolean[n]; return dfs(0); } private boolean dfs(int i) { if (i == n) return true; if (f[i] != null) return f[i]; boolean a = i + 1 < n && nums[i] == nums[i + 1]; boolean b = i + 2 < n && ...

LC.P2673[使二叉树所有路径值相等的最小代价] 方法一：贪心 根节点到每个叶子节点的路径值相等，实际上等价于以任意节点为根节点的子树到该子树的每个叶子节点的路径值相等。 12345678910class Solution { public int minIncrements(int n, int[] cost) { int ans = 0; for (int i = n / 2; i > 0; --i) { ans += Math.abs(cost[2 * i - 1] - cost[2 * i]); // 使两个子节点的值变成一样 cost[i - 1] += Math.max(cost[2 * i - 1], cost[2 * i]); // 累加路径和 } return ans; }} 时间复杂度：$O(n)$ 空间复杂度：$O(1)$

LC.P938[二叉搜索树的范围和] 方法一：DFS123456789101112131415161718192021222324252627282930313233/** * 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 { public i ...