上岸算法LeetCode Weekly Contest 270解题报告
【 NO.1 找出 3 位偶数】解题思路
签到题，枚举所有组合即可。
代码展示
class Solution {
public int[] findEvenNumbers(int[] digits) {
Set<Integer> result = new HashSet<>();
for (int i = 0; i < digits.length; i++) {
for (int j = 0; j < digits.length; j++) {
for (int k = 0; k < digits.length; k++) {
if (i == j || j == k || i == k) {
continue;
}
if (digits != 0 && digits % 2 == 0) {
result.add(digits * 100 + digits * 10 + digits);
}
}
}
}
int[] arr = result.stream().mapToInt(i -> i).toArray();
Arrays.sort(arr);
return arr;
}
}
【 NO.2 删除链表的中间节点】
解题思路
快慢指针的经典题目。
代码展示
class Solution {
public ListNode deleteMiddle(ListNode head) {
if (head == null || head.next == null) {
return null;
}
ListNode slow = head;
ListNode fast = head.next;
while (fast != null) {
fast = fast.next;
if (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next;
}
}
slow.next = slow.next.next;
return head;
}
}
【 NO.3 从二叉树一个节点到另一个节点每一步的方向】
解题思路
分别求出从根节点到 startValue 和 destValue 的路径，然后删去公共的部分，再把走向 startValue 的部分全部替换为 U 即可。
代码展示
class Solution {
public String getDirections(TreeNode root, int startValue, int destValue) {
StringBuilder start = new StringBuilder();
StringBuilder dest = new StringBuilder();
getDirections(root, startValue, start);
getDirections(root, destValue, dest);
int common = 0;
while (common < Math.min(start.length(), dest.length()) && start.charAt(common) == dest.charAt(common)) {
common++;
}
if (common > 0) {
start.delete(0, common);
dest.delete(0, common);
}
for (int i = 0; i < start.length(); i++) {
start.setCharAt(i, 'U');
}
return start.append(dest).toString();
}
private boolean getDirections(TreeNode root, int value, StringBuilder sb) {
if (root == null) {
return false;
}
if (root.val == value) {
return true;
}
int len = sb.length();
sb.append('L');
if (getDirections(root.left, value, sb)) {
return true;
}
sb.delete(len, sb.length());
sb.append('R');
return getDirections(root.right, value, sb);
}
}
【 NO.4 合法重新排列数对】
解题思路
有向图求欧拉路径的模板题。
代码展示
class Solution {
public int[][] validArrangement(int[][] pairs) {
Map<Integer, LinkedList<Integer>> graph = new HashMap<>();
Map<Integer, Integer> degree = new HashMap<>();
for (var p : pairs) {
if (!graph.containsKey(p)) {
graph.put(p, new LinkedList<>());
}
graph.get(p).add(p);
degree.put(p, degree.getOrDefault(p, 0) - 1);
degree.put(p, degree.getOrDefault(p, 0) + 1);
}
List<int[]> result = new ArrayList<>();
for (var e : degree.entrySet()) {
if (e.getValue() < 0) {
dfs(e.getKey(), result, graph);
}
}
if (result.isEmpty()) {
dfs(pairs, result, graph);
}
int[][] arr = new int[];
for (int i = 0; i < result.size(); i++) {
arr = result.get(result.size() - i - 1);
}
return arr;
}
private void dfs(int start, List<int[]> result, Map<Integer, LinkedList<Integer>> graph) {
var next = graph.get(start);
while (next != null && !next.isEmpty()) {
int to = next.poll();
dfs(to, result, graph);
result.add(new int[]{start, to});
}
}
}
页:
[1]