byu_rself

LC.P306[累加数] 方法一：回溯1234567891011121314151617181920212223242526272829303132333435363738394041424344454647class Solution { String num; int n; List<List<Integer>> list = new ArrayList<>(); public boolean isAdditiveNumber(String num) { this.num = num; n = num.length(); return dfs(0); } private boolean dfs(int u) { int m = list.size(); if (u == n) return m >= 3; int max = num.charAt(u) == '0' ...

LC.P2490[回环句] 方法一：模拟12345678910class Solution { public boolean isCircularSentence(String sentence) { String[] s = sentence.trim().split(" "); int n = s.length; for (int i = 0; i < n; ++i) { if (s[i].charAt(s[i].length() - 1) != s[(i + 1) % n].charAt(0)) return false; } return true; }} 时间复杂度：$O(n)$ 空间复杂度：$O(n)$ 方法二：模拟(空间优化)123456789101112class Solution { public boolean isCircularSentence(Stri ...

LC.P90[子集II] 方法一：排序+哈希表+回溯123456789101112131415161718192021222324class Solution { List<Integer> path = new ArrayList<>(); Set<List<Integer>> ans = new HashSet<>(); int[] nums; public List<List<Integer>> subsetsWithDup(int[] nums) { Arrays.sort(nums); this.nums = nums; dfs(0); return new ArrayList<>(ans); } private void dfs(int i) { if (i == nums.length) { ans.a ...

LC.P78[子集] 方法一：回溯(选或不选)123456789101112131415161718192021222324class Solution { List<List<Integer>> ans = new ArrayList<>(); List<Integer> path = new ArrayList<>(); int[] nums; public List<List<Integer>> subsets(int[] nums) { this.nums = nums; dfs(0); return ans; } private void dfs(int i) { if (i == nums.length) { ans.add(new ArrayList<>(path)); // 固定答案 retu ...

LC.P1253[重构2行二进制矩阵] 方法一：贪心1234567891011121314151617181920212223242526class Solution { public List<List<Integer>> reconstructMatrix(int upper, int lower, int[] colsum) { List<Integer> first = new ArrayList<>(), second = new ArrayList<>(); for (int sum : colsum) { int a = 0, b = 0; if (sum == 2) { a = 1; b = 1; --upper; --lower; } else ...

LC.P95[不同的二叉搜索树II] 方法一：回溯123456789101112131415161718192021222324252627282930313233343536373839/** * 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.P390[消除游戏] 方法一：数学123456789101112131415class Solution { public int lastRemaining(int n) { int head = 1, step = 1; boolean left = true; while (n > 1) { if (left || n % 2 != 0) { head += step; } step *= 2; left = !left; n /= 2; } return head; }} 时间复杂度：$O(log_2n)$ 空间复杂度：$O(1)$

LC.P1186[删除一次得到子数组最大和] 方法一：动态规划1234567891011121314class Solution { public int maximumSum(int[] arr) { int n = arr.length, ans = Integer.MIN_VALUE; int[][] f = new int[n + 1][2]; // 除 2 防止负数相加溢出 Arrays.fill(f[0], Integer.MIN_VALUE / 2); for (int i = 0; i < n; i++) { f[i + 1][0] = Math.max(f[i][0], 0) + arr[i]; f[i + 1][1] = Math.max(f[i][1] + arr[i], f[i][0]); ans = Math.max(ans, Math.max(f[i + 1][0], f[i + 1 ...

LC.P621[任务调度器] 方法一：桶原理1234567891011121314class Solution { public int leastInterval(char[] tasks, int n) { int[] cnt = new int[26]; int max = 0, total = 0; for (char task : tasks) ++cnt[task - 'A']; for (int i = 0; i < 26; ++i) { max = Math.max(max, cnt[i]); } for (int i = 0; i < 26; ++i) { total += max == cnt[i] ? 1 : 0; } return Math.max(tasks.length, (n + 1) * (max - 1 ...

LC.P2028[找出缺失的观测数据] 方法一：数学12345678910111213141516class Solution { public int[] missingRolls(int[] rolls, int mean, int n) { int m = rolls.length, s = m + n; int total = s * mean; // 总和 for (int roll : rolls) total -= roll; // n个元素的总和范围需在[n, 6 * n] if (total < n || total > 6 * n) return new int[0]; int[] ans = new int[n]; Arrays.fill(ans, total / n); int d = total - (total / n * n); for (int i = 0; d-- > 0; ++i) ...