byu_rself

LC.P2697[字典序最小回文串] 方法一：贪心+双指针123456789class Solution { public String makeSmallestPalindrome(String s) { char[] cs = s.toCharArray(); for (int i = 0, j = cs.length - 1; i < j; ++i, --j) { cs[i] = cs[j] = (char) Math.min(cs[i], cs[j]); } return new String(cs); }} 时间复杂度：$O(n)$ 空间复杂度：$O(n)$

LC.P2454[下一个更大元素IV] 方法一：排序+有序集合12345678910111213141516171819202122class Solution { public int[] secondGreaterElement(int[] nums) { int n = nums.length; int[] ans = new int[n]; Arrays.fill(ans, -1); int[][] arr = new int[n][2]; for (int i = 0; i < n; ++i) { arr[i] = new int[]{nums[i], i}; } Arrays.sort(arr, (a, b) -> b[0] - a[0]); TreeSet<Integer> ts = new TreeSet<>(); for ...

LC.P70[爬楼梯] 方法一：记忆化搜索1234567891011121314class Solution { int[] cache; public int climbStairs(int n) { cache = new int[n + 1]; return dfs(n); } private int dfs(int i) { if (i <= 1) return 1; if (cache[i] != 0) return cache[i]; return cache[i] = dfs(i - 1) + dfs(i - 2); }} 时间复杂度：$O(n)$ 空间复杂度：$O(n)$ 方法二：动态规划（1:1翻译成递推）1234567891011class Solution { public int climbStairs(int n) { int[] f = new in ...

LC.P1631[最小体力消耗路径] 方法一：并查集12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061class Solution { private static final int[][] dirs = new int[][]{{1, 0}, {0, 1}}; public int minimumEffortPath(int[][] heights) { int m = heights.length, n = heights[0].length; UnionFind p = new UnionFind(m * n); List<int[]> edges = new ArrayList<>(); for (int i = 0; i < ...

LC.P2008[出租车的最大盈利] 方法一：记忆化搜索1234567891011121314151617181920212223242526272829303132class Solution { List<int[]>[] group; long[] cache; public long maxTaxiEarnings(int n, int[][] rides) { cache = new long[n + 1]; Arrays.fill(cache, -1); group = new List[n + 1]; for (int[] r : rides) { int start = r[0], end = r[1], tip = r[2]; if (group[end] == null) { group[end] = new ArrayList<>(); ...

LC.P655[输出二叉树] 方法一：DFS123456789101112131415161718192021222324252627282930313233343536373839404142434445464748/** * 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 S ...

LC.P1609[奇偶树] 方法一：BFS1234567891011121314151617181920212223242526272829303132333435363738394041/** * 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 { ...

LC.P1466[重新规划路线] 方法一：DFS12345678910111213141516171819202122232425class Solution { List<int[]>[] g; public int minReorder(int n, int[][] connections) { g = new List[n]; Arrays.setAll(g, k -> new ArrayList<>()); for (int[] c : connections) { int a = c[0], b = c[1]; g[a].add(new int[]{b, 1}); g[b].add(new int[]{a, 0}); } return dfs(0, -1); } private int dfs(int ...

LC.P241[为运算表达式设计优先级] 方法一：DFS1234567891011121314151617181920212223242526272829303132333435class Solution { char[] cs; public List<Integer> diffWaysToCompute(String expression) { cs = expression.toCharArray(); return dfs(0, cs.length - 1); } private List<Integer> dfs(int left, int right) { List<Integer> ans = new ArrayList<>(); for (int i = left; i <= right; ++i) { if (cs[i] >= '0' & ...

LC.P2646[最小化旅行的价格总和] 方法一：DFS+动态规划123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051class Solution { List<Integer>[] g; int[] price, cnt; int end; public int minimumTotalPrice(int n, int[][] edges, int[] price, int[][] trips) { g = new ArrayList[n]; Arrays.setAll(g, k -> new ArrayList<>()); for (int[] e : edges) { int a = e[0], b = e[1]; g[a].add(b); g[b].add( ...