byu_rself

LC.P1654[到家的最少跳跃次数] 方法一：BFS12345678910111213141516171819202122232425262728293031323334class Solution { static final int n = 6000; public int minimumJumps(int[] forbidden, int a, int b, int x) { Set<Integer> set = new HashSet<>(); for (int f : forbidden) set.add(f); Deque<int[]> queue = new ArrayDeque<>(); queue.offer(new int[]{0, 1}); boolean[][] visited = new boolean[n][2]; visited[0][1] = true; ...

LC.P698[划分为k个相等的子集] 方法一：回溯+剪枝1234567891011121314151617181920212223242526272829303132class Solution { int[] nums; boolean[] visited; int n, target, k; public boolean canPartitionKSubsets(int[] nums, int k) { int total = 0; for (int num : nums) total += num; if (total % k != 0) return false; this.nums = nums; n = nums.length; this.k = k; Arrays.sort(nums); visited = new boolean[n]; target = total / k; r ...

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[两个数组最小的异或值之和] 方法一：动态规划+状态压缩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[插入区间] 方法一：排序+区间合并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[合并区间] 方法一：排序+一次遍历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[优势洗牌] 方法一：贪心+排序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参议院] 方法一：贪心+循环队列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[汇总区间] 方法一：双指针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[二叉树的最近公共祖先] 方法一：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( ...