byu_rself

LC.P215[数组中的第K个最大元素] 方法一：大根堆12345678910class Solution { public int findKthLargest(int[] nums, int k) { PriorityQueue<Integer> q = new PriorityQueue<>((a, b) -> b - a); for (int num : nums) q.offer(num); while (k-- > 1) { q.poll(); } return q.peek(); }} 时间复杂度：$O(nlogn)$ 空间复杂度：$O(n)$ 方法二：小根堆1234567891011121314class Solution { public int findKthLargest(int[] nums, int k) { Prio ...

LC.P1170[比较字符串最小字母出现频次] 方法一：后缀和12345678910111213141516171819202122232425262728293031class Solution { public int[] numSmallerByFrequency(String[] queries, String[] words) { int n = queries.length; int[] cnt = new int[12]; for (String word : words) ++cnt[f(word)]; for (int i = 9; i >= 1; --i) { cnt[i] += cnt[i + 1]; } int[] ans = new int[n]; for (int i = 0; i < n; ++i) { String s = queries[i]; ...

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<>(); ...