LC.P823[带因子的二叉树]
LC.P823[带因子的二叉树]
方法一:记忆化搜索1234567891011121314151617181920212223242526272829303132333435class Solution { private static final int MOD = (int) 1e9 + 7; long[] cache; Map<Integer, Integer> map; int[] arr; public int numFactoredBinaryTrees(int[] arr) { this.arr = arr; int n = arr.length; Arrays.sort(arr); map = new HashMap<>(n); for (int i = 0; i < n; ++i) map.put(arr[i], i); cache = new long[n]; Arrays.fill ...
LC.P1879[两个数组最小的异或值之和]
LC.P1879[两个数组最小的异或值之和]
方法一:动态规划+状态压缩123456789101112131415161718192021222324252627class Solution { private static final int INF = 0x3f3f3f3f; public int minimumXORSum(int[] nums1, int[] nums2) { int n = nums1.length, mask = 1 << n; int[][] f = new int[n + 10][mask]; for (int i = 0; i <= n; ++i) Arrays.fill(f[i], INF); f[0][0] = 0; for (int i = 1; i <= n; ++i) { for (int s = 0; s < mask; ++s) { ...
LC.P57[插入区间]
LC.P57[插入区间]
方法一:排序+区间合并1234567891011121314151617181920212223242526class Solution { public int[][] insert(int[][] intervals, int[] newInterval) { int[][] newIntervals = new int[intervals.length + 1][2]; for (int i = 0; i < intervals.length; ++i) { newIntervals[i] = intervals[i]; } newIntervals[intervals.length] = newInterval; return merge(newIntervals); } // LC.P56[合并区间] private int[][] merge(int[][] interv ...
LC.P56[合并区间]
LC.P56[合并区间]
方法一:排序+一次遍历12345678910111213141516class Solution { public int[][] merge(int[][] intervals) { Arrays.sort(intervals, (a, b) -> a[0] - b[0]); List<int[]> ans = new ArrayList<>(); ans.add(intervals[0]); for (int i = 1; i < intervals.length; ++i) { int start = intervals[i][0], end = intervals[i][1]; if (ans.get(ans.size() - 1)[1] < start) { ans.add(intervals[i]); } ...
LC.P870[优势洗牌]
LC.P870[优势洗牌]
方法一:贪心+排序123456789101112131415class Solution { public int[] advantageCount(int[] nums1, int[] nums2) { int n = nums1.length; Arrays.sort(nums1); int[] ans = new int[n]; Integer[] index = new Integer[n]; for (int i = 0; i < n; ++i) index[i] = i; Arrays.sort(index, (a, b) -> nums2[a] - nums2[b]); int left = 0, right = n - 1; for (int num : nums1) { ans[num > nums2[index[left]] ? index[left++ ...
LC.P649[Dota2参议院]
LC.P649[Dota2参议院]
方法一:贪心+循环队列12345678910111213141516class Solution { public String predictPartyVictory(String senate) { int n = senate.length(); Deque<Integer> rd = new ArrayDeque<>(), dd = new ArrayDeque<>(); for (int i = 0; i < n; ++i) { if (senate.charAt(i) == 'R') rd.offer(i); else dd.offer(i); } while (!rd.isEmpty() && !dd.isEmpty()) { int a = rd.poll(), b = ...
LC.P228[汇总区间]
LC.P228[汇总区间]
方法一:双指针123456789101112class Solution { public List<String> summaryRanges(int[] nums) { List<String> ans = new ArrayList<>(); int n = nums.length; for (int i = 0, j; i < n; i = j + 1) { j = i; while (j + 1 < n && nums[j + 1] == nums[j] + 1) ++j; ans.add(i == j ? String.valueOf(nums[i]) : String.format("%d->%d", nums[i], nums[j])); } return ans; & ...
LC.P236[二叉树的最近公共祖先]
LC.P236[二叉树的最近公共祖先]
方法一:DFS+回溯1234567891011121314151617181920212223242526272829303132/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { List<TreeNode> a = new ArrayList<>(), b = new ArrayList<>(); dfs(root, p, a); dfs( ...
LC.P235[二叉搜索树的最近公共祖先]
LC.P235[二叉搜索树的最近公共祖先]
方法一:DFS123456789101112131415161718/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { int x = root.val; if (p.val < x && q.val < x) return lowestCommonAncestor(root.left, p, q); if (p.val > x && ...
LC.P1448[统计二叉树中好节点的数目]
LC.P1448[统计二叉树中好节点的数目]
方法一:DFS12345678910111213141516171819202122232425262728/** * 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 { public int ...