byu_rself

LC.P74[搜索二维矩阵] 方法一：二分123456789101112class Solution { public boolean searchMatrix(int[][] matrix, int target) { int m = matrix.length, n = matrix[0].length; int left = 0, right = m * n - 1; while (left < right) { int mid = left + right >> 1; if (matrix[mid / n][mid % n] >= target) right = mid; else left = mid + 1; } return matrix[left / n][left % n] == target; }} 时间复杂度：$O(log(mn)) ...

LC.P653[两数之和IV-输入二叉搜索树] 方法一：哈希表+DFS1234567891011121314151617181920212223242526/** * 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 { Set<In ...

LC.P337[打家劫舍III] 方法一：树形DP1234567891011121314151617181920212223242526272829303132/** * 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 ...

LC.P213[打家劫舍II] 方法一：动态规划12345678910111213141516171819class Solution { public int rob(int[] nums) { int n = nums.length; // 1.偷 nums[0]，那么 nums[1] 和 nums[n - 1] 不能偷，问题变成从 nums[2] 到 nums[n - 2] 的非环形版本 // 2.不偷 nums[0]，那么问题变成 nums[1] 到nums[n - 1] 的非环形版本 return Math.max(nums[0] + rob1(nums, 2, n - 1), rob1(nums, 1, n)); } // LC.P198 打家劫舍 private int rob1(int[] nums, int start, int end) { // [start,end) 左闭右开 int f0 = 0, f1 = 0; ...

LCP.P50[宝石补给] 方法一：模拟123456789101112131415class Solution { public int giveGem(int[] gem, int[][] operations) { int max = 0, min = Integer.MAX_VALUE; for (int[] op : operations) { int x = op[0], y = op[1], val = gem[x] >> 1; gem[y] += val; gem[x] -= val; } for (int x : gem) { max = Math.max(max, x); min = Math.min(min, x); } return max - min; }} 时间复 ...

LC.P331[验证二叉树的前序序列化] 方法一：找规律12345678910111213class Solution { public boolean isValidSerialization(String s) { String[] ss = s.split(","); int n = ss.length; int in = 0, out = 0; for (int i = 0; i < n; ++i) { if (!ss[i].equals("#")) out += 2; if (i != 0) ++in; if (i != n - 1 && out <= in) return false; } return in == out; }} 时间复杂度：$O(n)$ 空间复杂度：$O(n)$

LC.P173[二叉搜索树迭代器] 方法一：DFS1234567891011121314151617181920212223242526272829303132333435363738394041424344454647/** * 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 ...

LC.P2596[检查骑士巡视方案] 方法一：模拟1234567891011121314151617181920class Solution { public boolean checkValidGrid(int[][] grid) { if (grid[0][0] != 0) return false; int n = grid.length; int[][] pos = new int[n * n][2]; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { pos[grid[i][j]] = new int[]{i, j}; } } for (int i = 1; i < n * n; ++i) { int[] p1 = p ...

LC.P96[不同的二叉搜索树] 方法一：区间DP12345678910111213class Solution { public int numTrees(int n) { int[] f = new int[n + 1]; f[0] = 1; f[1] = 1; for (int i = 2; i <= n; ++i) { for (int j = 1; j <= i; ++j) { f[i] += f[j - 1] * f[i - j]; } } return f[n]; }} 时间复杂度：$O(n^2)$ 空间复杂度：$O(n)$ 方法二：数学—卡特兰数卡特兰数，公式为 $C_{n + 1} = \frac {C_{n} \times (4n + 2)} {n + 2} $ 1234567class So ...

LC.P1462[课程表IV] 方法一：拓扑排序12345678910111213141516171819202122232425262728293031323334class Solution { public List<Boolean> checkIfPrerequisite(int n, int[][] prerequisites, int[][] queries) { List<Integer>[] g = new List[n]; Arrays.setAll(g, k -> new ArrayList<>()); int[] in = new int[n]; for (int[] p : prerequisites) { int a = p[0], b = p[1]; g[a].add(b); ++in[b]; } Deque<Inte ...