byu_rself

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

LC.P1713[得到子序列的最少操作次数] 方法一：贪心+动态规划+二分123456789101112131415161718192021222324252627282930class Solution { public int minOperations(int[] target, int[] arr) { int n = target.length; Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < n; ++i) map.put(target[i], i); List<Integer> list = new ArrayList<>(); for (int x : arr) { if (map.containsKey(x)) { list.add(map.get(x)); ...

LC.P1726[同积元组] 方法一：数学+哈希表12345678910111213141516class Solution { public int tupleSameProduct(int[] nums) { Map<Integer, Integer> map = new HashMap<>(); for (int i = 1; i < nums.length; ++i) { for (int j = 0; j < i; ++j) { int x = nums[i] * nums[j]; map.merge(x, 1, Integer::sum); } } int ans = 0; for (int v : map.values()) { ans += v * (v - 1) / ...