byu_rself

LC.P2413[最小偶倍数] 方法一：模拟12345class Solution { public int smallestEvenMultiple(int n) { return n % 2 == 0 ? n : 2 * n; }} 时间复杂度：$O(1)$ 空间复杂度：$O(1)$ 方法二：位运算12345class Solution { public int smallestEvenMultiple(int n) { return n << (n & 1); }} 时间复杂度：$O(1)$ 空间复杂度：$O(1)$

LC.P77[组合] 思路：回溯 + 剪枝 方法一：枚举下一个数选哪个123456789101112131415161718192021222324class Solution { List<List<Integer>> ans = new ArrayList<>(); List<Integer> path = new ArrayList<>(); int k; public List<List<Integer>> combine(int n, int k) { this.k = k; dfs(n); return ans; } private void dfs(int i) { int d = k - path.size(); // 还要选d个数 if (d == 0) { ans.add(new ArrayList<& ...

LC.P1187[使数组严格递增] 方法一：动态规划+记忆化搜索+二分12345678910111213141516171819202122232425262728293031323334353637class Solution { int[] a, b; Map<Integer, Integer>[] cache; public int makeArrayIncreasing(int[] a, int[] b) { this.a = a; this.b = b; Arrays.sort(b); int n = a.length; cache = new HashMap[n]; Arrays.setAll(cache, e -> new HashMap<>()); int ans = dfs(n - 1, Integer.MAX_VALUE); return ans < Integer.MAX_VALU ...

LC.P300[最长递增子序列] 方法一：记忆化搜索12345678910111213141516171819202122class Solution { int[] nums, cache; public int lengthOfLIS(int[] nums) { this.nums = nums; int n = nums.length; cache = new int[n]; int ans = 0; for (int i = 0; i < n; ++i) { ans = Math.max(ans, dfs(i)); } return ans; } private int dfs(int i) { if (cache[i] > 0) return cache[i]; for (int j = 0; j < i; ++j) { ...

LC.P1976[到达目的地的方案数] 方法一：dijkstra+拓扑排序+dp1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768class Solution { private static final int MOD = (int) 1e9 + 7; private static final long INF = Long.MAX_VALUE >> 2; int n; long[] dist; int[][] g; int[] in; boolean[] visited; public int countPaths(int n, int[][] roads) { this.n = n; g = new int[n][n]; dist = new long[n]; ...

LC.P954[二倍数对数组] 方法一：排序+哈希表先用哈希表记录数组中每个元素出现的次数，将哈希表中的key(即数组中不同的元素)放入List中，对List进行排序后： 记当前元素为x(对一个有理数而言，乘$2$劲会改变数的大小，不会改变数的正负) 若$x > 0$，且$2 * x$出现的次数小于$x$出现的次数，则无法组成二倍数对数组；否则，可以配对，$将2 * x$出现的次数减去$x$出现的次数 若$x = 0$，因为$2 * x = 0$，需要特殊处理，判断$0$出现的次数是否为偶数 若$x < 0$，因为$x$按升序排列，所以当前$x$需要与$x / 2$配对(例如：$-4$与$-2$配对)，注意：需要判断当前元素出现的次数是否大于$0$，例如：[-4, -2, 2, 4]，遍历$-4$时，与$-2$配对，$-2$出现的次数变为$0$，已配对完成，若不加cnt > 0，则会在map.put(key / 2, map.get(key / 2) - cnt);报错。 1234567891011121314151617181920 ...

LC.P1043[分隔数组以得到最大和] 方法一：动态规划(超时)12345678910111213141516171819class Solution { int[] arr; int k; public int maxSumAfterPartitioning(int[] arr, int k) { this.arr = arr; this.k = k; return dfs(arr.length - 1); } private int dfs(int i) { int ans = 0, max = 0; for (int j = i; j > i - k && j >= 0; --j) { max = Math.max(max, arr[j]); ans = Math.max(ans, dfs(j - 1) + (i - j + 1) * max); ...

LC.P909[蛇梯棋] 方法一：BFS 由于题目中n的范围最大为20，因此可将二维矩阵扁平化为一维矩阵，利用单向BFS求解 123456789101112131415161718192021222324252627282930313233343536373839class Solution { int n; int[] nums; public int snakesAndLadders(int[][] board) { if (board[0][0] != -1) return -1; n = board.length; nums = new int[n * n + 1]; boolean flag = true; for (int i = n - 1, index = 1; i >= 0; --i) { for (int j = flag ? 0 : n - 1; flag ? j < n : j >= 0; j += fl ...

LC.P1036[逃离大迷宫] 方法一：BFS12345678910111213141516171819202122232425262728293031323334class Solution { int EDGE = (int) 1e6, MAX; Set<Long> set = new HashSet<>(); int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; public boolean isEscapePossible(int[][] blocked, int[] source, int[] target) { for (int[] b : blocked) set.add(b[0] * (long) 1e6 + b[1]); int n = blocked.length; MAX = n * (n ...

LC.P1026[节点与其祖先之间的最大差值] 方法一：DFS通过DFS，记录以该节点为根节点的路径上的最大值与最小值，最后更新答案。 1234567891011121314151617181920212223242526272829303132/** * 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; * } * &# ...