byu_rself

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[统计二叉树中好节点的数目] 方法一：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 ...

LC.P664[奇怪的打印机] 方法一：动态规划123456789101112131415161718class Solution { public int strangePrinter(String s) { int n = s.length(); int[][] f = new int[n + 1][n + 1]; for (int len = 1; len <= n; ++len) { for (int l = 0; l + len - 1 < n; ++l) { int r = l + len - 1; f[l][r] = f[l + 1][r] + 1; for (int k = l + 1; k <= r; ++k) { if (s.charAt(l) == s.charAt(k)) { ...

LC.P1267[统计参与通信的服务器] 方法一：模拟1234567891011121314151617181920212223class Solution { public int countServers(int[][] grid) { int m = grid.length, n = grid[0].length; int[] cntRow = new int[m], cntCol = new int[n]; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (grid[i][j] == 1) { ++cntRow[i]; ++cntCol[j]; } } } i ...

LC.P375[猜数字大小II] 方法一：记忆化搜索1234567891011121314151617181920class Solution { int[][] cache; public int getMoneyAmount(int n) { cache = new int[n + 1][n + 1]; return dfs(1, n); } private int dfs(int l, int r) { if (l >= r) return 0; if (cache[l][r] != 0) return cache[l][r]; int ans = Integer.MAX_VALUE; for (int x = l; x <= r; ++x) { int cur = Math.max(dfs(l, x - 1), dfs(x + 1, r)) + x; ans ...

LC.P1782[统计点对的数目] 方法一：排序+双指针+哈希表123456789101112131415161718192021222324252627282930313233343536373839404142434445class Solution { public int[] countPairs(int n, int[][] edges, int[] queries) { // degree[i] 表示与点 i 相连的边的数目 int[] degree = new int[n + 1]; // 节点编号从 1 到 n Map<Integer, Integer> cntE = new HashMap<>(); for (int[] e : edges) { int x = e[0], y = e[1]; if (x > y) { // 交换 x 和 y，因为 1-2 和 2- ...

LC.P849[到最近的人的最大距离] 方法一：贪心1234567891011121314class Solution { public int maxDistToClosest(int[] seats) { int last = -1, d = 0, n = seats.length, ans = 1; for (int i = 0; i < n; ++i) { if (seats[i] == 1) { if (last == -1) ans = Math.max(ans, i); // 坐左边 else ans = Math.max(ans, (i - last) / 2); // 坐中间 last = i; } } ans = Math.max(ans, n - last - 1); // 坐右边 retur ...

LC.P672[灯泡开关II] 方法一：找规律123456789101112class Solution { public int flipLights(int n, int presses) { // 不按开关 if (presses == 0) return 1; // 1个灯泡 if (n == 1) return 2; // 2个灯泡 else if (n == 2) return presses == 1 ? 3 : 4; // n >= 3 else return presses == 1 ? 4 : presses == 2 ? 7 : 8; }} 时间复杂度：$O(1)$ 空间复杂度：$O(1)$

LC.P667[优美的排列II] 方法一：脑筋急转弯1234567891011121314151617class Solution { public int[] constructArray(int n, int k) { int[] ans = new int[n]; int index = 0; // 前面部分相差为1 for (int i = 1; i < n - k; ++i) { ans[index++] = i; } for (int i = n - k, j = n; i <= j; ++i, --j) { ans[index++] = i; if (i != j) { ans[index++] = j; } } return ans;
...

LC.P2237[移动片段得到字符串] 方法一：双指针123456789101112class Solution { public boolean canChange(String start, String target) { int n = start.length(); for (int i = 0, j = 0; ; ++i, ++j) { while (i < n && start.charAt(i) == '_') ++i; while (j < n && target.charAt(j) == '_') ++j; if (i == n && j == n) return true; if (i == n || j == n || start.charAt(i) != target.charAt(j)) return fals ...