byu_rself

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; * } * &# ...

LC.P847[访问所有节点的最短路径] 方法一：状态压缩+BFSclass Solution { private static final int INF = 0x3f3f3f3f; public int shortestPathLength(int[][] graph) { int n = graph.length; int mask = 1 << n; int[][] dist = new int[mask][n]; for (int i = 0; i < mask; ++i) Arrays.fill(dist[i], INF); Deque<int[]> queue = new ArrayDeque<>(); for (int i = 0; i < n; ++i) { dist[1 << i][i] = 0; queue.offe ...

什么时候用状态压缩？需要标记当前点的访问状态，且题目的数据长度比较短（最好小于32位）。满足以上条件，那么就可以使用二进制表示长度为 32 的 int 来代指点是否被访问过。 示例$(000…0101)_2$ 代表编号为 0 和编号为 2 的节点已经被访问过，而编号为 11 的节点尚未被访问。 常用操作检查编号为$x$的点是否被访问过使用位运算 1a = (state >> x) & 1 来获取$state$中第 $x$ 位的二进制表示，如果 $a$ 为 $1$ 代表编号为$x$的节点已被访问，如果为$0$则未被访问。 标记编号为$x$的点已经被访问过使用位运算 1state | (1 << x)