byu_rself

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

LC.P2485[找出中枢整数] 方法一：数学12345678910class Solution { public int pivotInteger(int n) { for (int x = 1; x <= n; ++x) { int a = (1 + x) * x / 2; int b = (x + n) * (n - x + 1) / 2; if (a == b) return x; } return -1; }} 时间复杂度：$O(n)$ 空间复杂度：$O(1)$

Offer.P6[从尾到头打印链表] 方法一：递归1234567891011121314151617181920212223242526272829/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */class Solution { List<Integer> list; public int[] reversePrint(ListNode head) { list = new ArrayList<>(); reverse(head); int n = list.size(); int[] ans = new int[n]; for (int i = 0; i < n; ++i) &# ...