上岸算法LeetCode Weekly Contest 270解题报告

上岸算法 · 发表于 2021-12-6 17:13:53

登录后可回复主题

您需要登录才可以下载或查看，没有帐号？注册账号

x

【 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[i] != 0 && digits[k] % 2 == 0) {
                     result.add(digits[i] * 100 + digits[j] * 10 + digits[k]);
               }
            }
      }
   }
   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[0])) {
            graph.put(p[0], new LinkedList<>());
      }
         graph.get(p[0]).add(p[1]);
         degree.put(p[0], degree.getOrDefault(p[0], 0) - 1);
         degree.put(p[1], degree.getOrDefault(p[1], 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[0][0], result, graph);
   }
   int[][] arr = new int[result.size()][];
   for (int i = 0; i < result.size(); i++) {
         arr[i] = 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});
   }
  }
}

帐号		自动登录	找回密码
密码			注册账号

[吹水聊天] 上岸算法LeetCode Weekly Contest 270解题报告

登录后可回复主题