byu_rself

LC.P2312[卖木头块] 方法一：动态规划12345678910111213141516171819class Solution { public long sellingWood(int m, int n, int[][] prices) { int[][] pr = new int[m + 1][n + 1]; for (int[] p : prices) { pr[p[0]][p[1]] = p[2]; } long[][] f = new long[m + 1][n + 1]; for (int i = 1; i <= m; ++i) { for (int j = 1; j <=n; ++j) { f[i][j] = pr[i][j]; // 垂直切割 for (int k = 1; k < ...

LC.P2789[合并后数组中的最大元素] 方法一：贪心+倒序遍历12345678910class Solution { public long maxArrayValue(int[] nums) { int n = nums.length; long sum = nums[n - 1]; for (int i = n - 2; i >= 0; --i) { sum = nums[i] <= sum ? sum + nums[i] : nums[i]; } return sum; }} 时间复杂度：$O(n)$ 空间复杂度：$O(1)$

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