byu_rself

LC.P494[目标和] 方法一：回溯12345678910111213141516171819202122class Solution { int ans, target, n; int[] nums; public int findTargetSumWays(int[] nums, int target) { this.nums = nums; this.n = nums.length; this.target = target; dfs(0, 0); return ans; } private void dfs(int index, int sum) { if (index == n) { if (sum == target) ++ans; } else { dfs(index + 1, sum + nums[index]); ...

LC.P437[路径总和III] 方法一：DFS12345678910111213141516171819202122232425262728293031323334353637/** * 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 { in ...

LC.P2699[修改图中的边权] 方法一：dijkstra1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071class Solution { public int[][] modifiedGraphEdges(int n, int[][] edges, int source, int destination, int target) { List<int[]>[] g = new ArrayList[n]; Arrays.setAll(g, e -> new ArrayList<>()); for (int i = 0; i < edges.length; ++i) { // 建图，额外记录边的编号 int x = ...

LC.P1240[铺瓷砖] 方法一：回溯12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758class Solution { int ans, n, m; boolean[][] rect; public int tilingRectangle(int n, int m) { ans = Math.max(n, m); rect = new boolean[n][m]; this.n = n; this.m = m; dfs(0, 0, 0); return ans; } public void dfs(int x, int y, int cnt) { if (cnt >= ans) return; if (x >= n) { ...

LC.P1802[有界数组中指定下标处的最大值] 方法一：贪心+二分查找123456789101112131415161718class Solution { public int maxValue(int n, int index, int maxSum) { int left = 1, right = maxSum; while (left < right) { int mid = left + right + 1 >> 1; if (sum(mid - 1, index) + sum(mid, n - index) <= maxSum) { left = mid; } else { right = mid - 1; } } return left; } ...

Offer.P37[序列化二叉树] 方法一：BFS123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */public class Codec { private static final String EMPTY = "null"; // Encodes a tree to a single string. public String serialize(TreeNode root) { ...

Offer.P32-III[从上到下打印二叉树III] 方法一：层序遍历12345678910111213141516171819202122232425262728293031/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> ans = new ArrayList<>(); Deque<TreeNode> queue = new ArrayDeque<> ...

Offer.P32-II[从上到下打印二叉树II] 方法一：层序遍历12345678910111213141516171819202122232425262728/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> ans = new ArrayList<>(); Deque<TreeNode> queue = new ArrayDeque<>(); ...

Offer.P32-I[从上到下打印二叉树] 方法一：层序遍历123456789101112131415161718192021222324252627/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { public int[] levelOrder(TreeNode root) { List<Integer> list = new ArrayList<>(); Deque<TreeNode> queue = new ArrayDeque<>(); if (root != null) queue.addLast(root); ...

LC.P2611[老鼠和奶酪] 方法一：贪心+排序1234567891011121314class Solution { public int miceAndCheese(int[] reward1, int[] reward2, int k) { int ans = 0, n = reward1.length; for (int i = 0; i < n; ++i) { ans += reward2[i]; reward1[i] -= reward2[i]; } Arrays.sort(reward1); for (int i = 0; i < k; ++i) { ans += reward1[n - i - 1]; } return ans; }} 时间复杂度：$O(nlogn)$ 空间复杂度：$O(n)$