byu_rself

LC.P1994[好子集的数目] 方法一：动态规划+状态压缩123456789101112131415161718192021222324252627282930313233343536373839404142class Solution { static int MOD = (int) 1e9 + 7; static int[] p = new int[]{2, 3, 5, 7, 11, 13, 17, 19, 23, 29}; // 30以内的质数 public int numberOfGoodSubsets(int[] nums) { int[] cnts = new int[35]; // 统计数字出现的次数 for (int num : nums) ++cnts[num]; int mask = 1 << 10; long[] f = new long[mask]; f[0] = 1; for (int num = ...

LC.P415[字符串相加] 方法一：高精度加法(模板)1234567891011121314151617181920class Solution { public String addStrings(String num1, String num2) { int n = num1.length(), m = num2.length(); int[] A = new int[n], B = new int[m]; for (int i = n - 1, j = 0; i >= 0; --i, ++j) A[j] = num1.charAt(i) - '0'; for (int i = m - 1, j = 0; i >= 0; --i, ++j) B[j] = num2.charAt(i) - '0'; int carry = 0; StringBuilder builder = new StringBuilder(); ...

LC.P834[树中距离之和] 方法一：换根DP123456789101112131415161718192021222324252627282930313233343536373839404142434445464748class Solution { int n; List<Integer>[] g; int[] ans, size; public int[] sumOfDistancesInTree(int n, int[][] edges) { this.n = n; g = new ArrayList[n]; Arrays.setAll(g, e -> new ArrayList<>()); for (int[] edge : edges) { int x = edge[0], y = edge[1]; g[x].add(y); g[y].add(x); ...

LC.P691[贴纸拼词] 方法一：记忆化搜索+状态压缩12345678910111213141516171819202122232425262728293031323334353637383940414243class Solution { String[] stickers; String target; int[] cache; int m; public int minStickers(String[] stickers, String target) { m = target.length(); cache = new int[1 << m]; Arrays.fill(cache, -1); cache[0] = 0; this.stickers = stickers; this.target = target; int ans = dfs((1 << m) - 1); return ...

LC.P18[四数之和] 方法一：排序+双指针12345678910111213141516171819202122232425262728293031323334353637383940class Solution { public List<List<Integer>> fourSum(int[] nums, int target) { List<List<Integer>> ans = new ArrayList<>(); int n = nums.length; Arrays.sort(nums); for (int a = 0; a < n - 3; ++a) { if (a > 0 && nums[a] == nums[a - 1]) continue; long sum = (long) nums[a] + nums[a + 1] + nums[a + ...

LC.P979[在二叉树中分配硬币] 方法一：DFS123456789101112131415161718192021222324252627282930313233343536/** * 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.P636[函数的独占时间] 方法一：栈1234567891011121314151617181920class Solution { public int[] exclusiveTime(int n, List<String> logs) { int[] ans = new int[n]; Deque<Integer> stack = new ArrayDeque<>(); int cur = -1; for (String log : logs) { String[] s = log.split(":"); int index = Integer.parseInt(s[0]), timestamp = Integer.parseInt(s[2]); if (s[1].equals("start")) { if ...

LC.P670[最大交换] 方法一：选择排序(从后往前)12345678910111213141516171819202122class Solution { public int maximumSwap(int num) { char[] nums = String.valueOf(num).toCharArray(); int n = nums.length; for (int i = 0; i < n; ++i) { int maxIndex = i; // 从后往前选择一个最大的，这个最大的离i越远越好，比如1993，1交换第二个9更优，所以j倒序遍历 for (int j = n - 1; j >= i + 1; --j) { if (nums[j] > nums[maxIndex]) { maxIndex = j; ...

LC.P931[下降路径最小和] 方法一：DFS(超时)12345678910111213141516171819class Solution { int[][] matrix; public int minFallingPathSum(int[][] matrix) { int n = matrix.length, ans = Integer.MAX_VALUE; this.matrix = matrix; for (int col = 0; col < n; ++col) { ans = Math.min(ans, dfs(n - 1, col)); } return ans; } private int dfs(int row, int col) { if (col < 0 || col >= matrix.length) return Integer.MAX_VAL ...

Offer.P34[二叉树中和为某一值的路径] 方法一：DFS1234567891011121314151617181920212223242526272829303132333435363738/** * 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
...