我的Weekly Contest 270戰況

參加周賽有7次了，1928/12931應該是目前最好一次排名了，上周的周賽和雙周賽也是只做對3道題，我也是LeetCode周賽“三道題選手”啦，當然，離4道全AC的大佬們還有距離，

什么是LeetCode周賽？

刷LeetCode兩年，我才發現leetcode上的演算法題一直在更新，而且更新的題目的來源就是周賽（每周4題）和雙周賽，

參加了幾次，我的心得體會是：簡單題不一定簡單，中等/難題也不一定難，掌味訓用常見套路，有了思路，再細心審題嚴謹分析，

show my code!

• 前三道都是新瓶裝舊酒，或許第一道medium應該為easy，easy應該為medium難度，
• 第一題dfs全排列（47），很經典的題，不以0開頭，偶數，三位數，加上去重，并不簡單，
• 第二題，洗掉鏈表的中間節點，鏈表歸并排序(https://leetcode.com/problems/sort-list/solution/)時就實作過，快慢指標，要洗掉中間節點，需要記錄前驅節點，
• 第三題（2096），二叉樹中兩個節點的最短路徑，依然可以從網上找到似曾相識的題，只不過題干有所改變，路徑不再是節點的串列，而是每一步方向組成的字串，
• 解法：
• 1、先求出兩個節點的最近公共祖先（236)
• 2、分別求出公共祖先到兩個節點的路徑
• 3、根據兩條路徑拼接出方向字串

2094. Finding 3-Digit Even Numbers

class Solution {
    private void dfs(int[] digits, boolean[] visited, int len, String cur, List<String> ans)
    {
        if(len == 1)
        {
            if(cur.charAt(0) == '0') return;
        }
        if(len == 3)
        {
            if(((cur.charAt(2) - '0') & 1) == 0)
            {
                ans.add(cur);
            }
            return;
        }
        
        for(int i = 0; i<digits.length; i++)
        {
            if(visited[i]) continue;
            if(i > 0 && digits[i] == digits[i-1] && !visited[i-1]) continue;
            visited[i] = true;
            dfs(digits, visited, len+1, cur+digits[i], ans);
            visited[i] = false; 
        }
    }
    
    public int[] findEvenNumbers(int[] digits) {
        Arrays.sort(digits);
        boolean[] visited = new boolean[digits.length];
        List<String> ans = new ArrayList<>();
        dfs(digits, visited, 0, "", ans);
        
        int[] nums = new int[ans.size()];
        for(int i=0; i<ans.size(); i++)
        {
            nums[i] = Integer.parseInt(ans.get(i));
        }
        return nums;
    }
}

2095. Delete the Middle Node of a Linked List

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteMiddle(ListNode head) {
        if(head == null || head.next == null) return null;
        ListNode p = head;
        ListNode midPrev = null;
        while (p != null && p.next != null) {
            midPrev = (midPrev == null) ? p : midPrev.next;
            p = p.next.next;
        }
        midPrev.next = midPrev.next.next;
        return head;
    }
}

2096. Step-By-Step Directions From a Binary Tree Node to Another
用例1：
用例2：

/**
 * 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 {
    public String getDirections(TreeNode root, int startValue, int destValue) {
        ArrayList<TreeNode> pathList1=new ArrayList<>();
        ArrayList<TreeNode> pathList2=new ArrayList<>();
        //求出兩個節點的最近公共祖先
        TreeNode ancestor=lowestCommonAncestor(root, startValue, destValue);
        //分別求出公共祖先到兩個節點的路經
        getPath(ancestor,startValue,pathList1);
        getPath(ancestor,destValue,pathList2);
        
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<pathList1.size()-1; i++)
        {
            sb.append("U");
        }
        for(int i=0; i<pathList2.size()-1; i++)
        {
            TreeNode pnt = pathList2.get(i);
            TreeNode cid = pathList2.get(i+1);
            if(pnt.left == cid) sb.append("L");
            else sb.append("R");
        }
        return sb.toString();
    }
    
    public TreeNode lowestCommonAncestor (TreeNode root, int node1, int node2){
        if (root==null || root.val==node1 || root.val==node2) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left,node1,node2);
        TreeNode right = lowestCommonAncestor(root.right, node1, node2);
        if(left != null && right != null) { 
            return root;
        }
        return left==null?right:left; 
    }

    /**
     *  獲取祖先節點到目標節點的路經（包含祖先節點和目標節點）
     */
    public boolean getPath(TreeNode root,int target,ArrayList<TreeNode> pathList){
        pathList.add(root);          
        if (root.val == target) {
            return true; 
        }         
        boolean hasFound=false;
        if (root.left!=null)
            hasFound=getPath(root.left,target,pathList);
        if (!hasFound && root.right!=null)
            hasFound=getPath(root.right,target,pathList);
        if (!hasFound)
            pathList.remove(pathList.size()-1);
        return hasFound; 
    }
}

復盤解決Hard題

2097. Valid Arrangement of Pairs
比賽結束后，官網有解題提示，正好學習一波，

歐拉回路：從起點出發，每條邊走一遍，遍歷所有結點和邊后回到起點，這個路徑稱為歐拉回路，
找歐拉回路的Hierholzer演算法思路如下：

The algorithm assumes that the given graph has a Eulerian Circuit.

• Choose any starting vertex v, and follow a trail of edges from that vertex until returning to v. It is not possible to get stuck at any vertex other than v, because indegree and outdegree of every vertex must be same, when the trail enters another vertex w there must be an unused edge leaving w.
  The tour formed in this way is a closed tour, but may not cover all the vertices and edges of the initial graph.
• 上面的一段，大意是從結點v dfs直到回到v，但一次dfs可能不會遍歷完所有結點和邊，
• As long as there exists a vertex u that belongs to the current tour, but that has adjacent edges not part of the tour, start another trail from u, following unused edges until returning to u, and join the tour formed in this way to the previous tour.
• 回溯，上一步的路徑上存在結點u還有未訪問的邊, 從結點u出發，訪問所有未訪問的邊能回到u，和之前的路徑匯合形成歐拉回路，
• 演算法的具體實作可參照題解的dfs方法，其中ans是逆序的歐拉回路路徑，

private void dfs(int start)
{
     List<Integer> edges = graph.get(start);
     if(edges == null) return;
     while(edges.size() > 0)
     {
         int next = edges.get(edges.size()-1);
         edges.remove(edges.size()-1);
         dfs(next);
         //when next has not adjoin edge, 
         //add [start, next] to ans
         ans.add(new int[]{start, next});
     }
}

那么，這一題與歐拉回路稍許不同的是，遍歷完所有的邊不一定回到起點，
那么，dfs的起點就不能隨意指定，而是要找（出度>入度）的節點作為起點，如果不存在，則按照歐拉回路的解法隨意指定起點，如pairs[0][0]，

class Solution {
    Map<Integer, List<Integer>> graph;
    Map<Integer, Integer> degree;
    List<int[]> ans;
    
    public int[][] validArrangement(int[][] pairs) {
        graph = new HashMap<>();
        ans = new ArrayList<>();
        degree = new HashMap<>();
        
        //build graph
        buildGraph(pairs);
        
        //select a start
        int start = -1;
        for(Integer i : degree.keySet())
        {
            if(degree.get(i) > 0)
            {
                start = i;
                break;
            }
        }
        
        if(start == -1) start = pairs[0][0];
        
        //dfs Hierholzer
        dfs(start);
        
        int size = ans.size();
        int[][] range = new int[size][2];
        for(int i=0; i<size; i++)
        {
            range[i][0] = ans.get(size-1-i)[0];
            range[i][1] = ans.get(size-1-i)[1];
        }
        return range;
    }
    
    private void buildGraph(int[][] pairs)
    {
        for(int[] pair : pairs)
        {
            graph.putIfAbsent(pair[0], new ArrayList<>());
            List<Integer> edges = graph.get(pair[0]);
            edges.add(pair[1]);
            
            int cnt = degree.getOrDefault(pair[0], 0);
            degree.put(pair[0], cnt+1);
            cnt = degree.getOrDefault(pair[1], 0);
            degree.put(pair[1], cnt-1);
        }
    }
    
    private void dfs(int start)
    {
        List<Integer> edges = graph.get(start);
        if(edges == null) return;
        while(edges.size() > 0)
        {
            int next = edges.get(edges.size()-1);
            edges.remove(edges.size()-1);
            dfs(next);
            //when next has not adjoin edge, 
            //add [start, next] to ans
            ans.add(new int[]{start, next});
        }
    }
}