byu_rself

LC.P2003[每棵子树内缺失的最小基因值] 方法一：DFS12345678910111213141516171819202122232425262728293031323334353637383940class Solution { public int[] smallestMissingValueSubtree(int[] parents, int[] nums) { int n = parents.length, node = -1; int[] ans = new int[n]; Arrays.fill(ans, 1); for (int i = 0; i < n; ++i) { if (nums[i] == 1) { node = i; // 出发点 break; } } if (node == -1) return ...

LC.P871[最低加油次数] 方法一：贪心+优先队列1234567891011121314151617181920class Solution { public int minRefuelStops(int target, int startFuel, int[][] stations) { int ans = 0, remain = startFuel, x = 0, n = stations.length, i = 0; PriorityQueue<Integer> q = new PriorityQueue<>((a, b) -> b - a); while (x < target) { if (remain == 0) { if (!q.isEmpty()) { remain += q.poll(); ++ans; ...

LC.P1465[切割后面积最大的蛋糕] 方法一：贪心+排序12345678910111213141516171819class Solution { private static final int MOD = (int) 1e9 + 7; public int maxArea(int h, int w, int[] horizontalCuts, int[] verticalCuts) { Arrays.sort(horizontalCuts); Arrays.sort(verticalCuts); int m = horizontalCuts.length, n = verticalCuts.length; int x = Math.max(horizontalCuts[0], h - horizontalCuts[m - 1]); int y = Math.max(verticalCuts[0], w - verticalCuts[n - 1]); for ...

LC.P2520[统计能整除数字的位数] 方法一：模拟1234567891011class Solution { public int countDigits(int num) { int x = num, ans = 0; while (x > 0) { int val = x % 10; if (num % val == 0) ++ans; x /= 10; } return ans; }} 时间复杂度：$O(lognum)$ 空间复杂度：$O(1)$

LC.P650[只有两个键的键盘] 方法一：数学123456789101112131415class Solution { public int minSteps(int n) { int ans = 0; for (int i = 2; i * i <= n; ++i) { while (n % i == 0) { n /= i; ans += i; } } if (n > 1) { ans += n; } return ans; }} 时间复杂度：$O(\sqrt{n})$ 空间复杂度：$O(1)$

LC.P2698[求一个整数的惩罚数] 方法一：枚举+DFS12345678910111213141516171819202122class Solution { public int punishmentNumber(int n) { int ans = 0; for (int i = 1; i <= n; ++i) { int x = i * i; if (check(x + "", 0, i)) ans += x; } return ans; } private boolean check(String s, int i, int target) { int m = s.length(); if (i >= m) return target == 0; int x = 0; for (int j = i; j < ...

LC.P965[单值二叉树] 方法一：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 { int val = -1; publi ...

LC.P1155[掷骰子等于目标和的方法数] 方法一：记忆化搜索123456789101112131415161718192021222324252627class Solution { private static final int MOD = (int) 1e9 + 7; int[][] cache; public int numRollsToTarget(int n, int k, int target) { if (target < n || target > n * k) return 0; cache = new int[n + 1][target - n + 1]; for (int[] c : cache) { Arrays.fill(c, -1); } return dfs(n, target - n, k); } private int dfs(int i, int j, int k ...

LC.P368[最大整除子集] 方法一：动态规划123456789101112131415161718192021222324252627282930313233class Solution { public List<Integer> largestDivisibleSubset(int[] nums) { Arrays.sort(nums); int n = nums.length; int[] f = new int[n], g = new int[n]; for (int i = 0; i < n; ++i) { int len = 1, prev = i; for (int j = 0; j < i; ++j) { if (nums[i] % nums[j] == 0) { if (f[j] + 1 > len) { ...

LC.P2525[根据规则将箱子分类] 方法一：模拟123456789101112class Solution { private static final String[] d = {"Neither", "Bulky", "Heavy", "Both"}; public String categorizeBox(int length, int width, int height, int mass) { long v = (long) length * width * height; int bulky = length >= 10000 || width >= 10000 || height >= 10000 || v >= 1000000000 ? 1 : 0; int heavy = mass >= 100 ? 1 : 0; int i = he ...