打廣告：java技術(shù)交流群：130031711，歡迎各位萌新大佬踴躍加入。

奇偶鏈表

題目：給定一個單鏈表，把所有的奇數(shù)節(jié)點和偶數(shù)節(jié)點分別排在一起。請注意，這里的奇數(shù)節(jié)點和偶數(shù)節(jié)點指的是節(jié)點編號的奇偶性，而不是節(jié)點的值的奇偶性。請嘗試使用原地算法完成。你的算法的空間復(fù)雜度應(yīng)為 O(1)，時間復(fù)雜度應(yīng)為 O(nodes)，nodes 為節(jié)點總數(shù)。

示例 1:
輸入: 1->2->3->4->5->NULL
輸出: 1->3->5->2->4->NULL
示例 2:
輸入: 2->1->3->5->6->4->7->NULL
輸出: 2->3->6->7->1->5->4->NULL
說明:
應(yīng)當保持奇數(shù)節(jié)點和偶數(shù)節(jié)點的相對順序。
鏈表的第一個節(jié)點視為奇數(shù)節(jié)點，第二個節(jié)點視為偶數(shù)節(jié)點，以此類推。

思路：暫時來說這個題的思路就是快慢指針。然后節(jié)點的取出和插入?？熘羔樏看沃赶虻目隙ㄊ瞧鏀?shù)節(jié)點，所以放在前面。我感覺我這個思路是沒問題的，時間空間復(fù)雜度都可以滿足，我去試試看吧。
一次ac，還是蠻簡單的題目。我直接貼代碼不多BB了：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode oddEvenList(ListNode head) {
        if(head==null || head.next==null || head.next.next==null) return head;
        //奇數(shù)
        ListNode slow = head;
        //偶數(shù)
        ListNode fast = head.next;
        //最后slow和fast都會指向最后，所以要記錄偶數(shù)的開始位置
        ListNode o = fast;
        while(fast != null && slow != null && fast.next!=null && slow.next!=null){
            //奇數(shù)節(jié)點放到slow后面
            slow.next = fast.next;  
            slow = slow.next;  
            //偶數(shù)節(jié)點放到fast后面       
            fast.next = slow.next;
            fast = fast.next;
        }
        slow.next = o; 
        return head;
    }
}

這個題我覺得是沒什么難點，可能稍微有點問題的就是剛接觸鏈表可能這個插入和取出會不太好一下子想出來。我也是做了好多類似的題才會一下子有思路的，反正就這樣吧，時間空間復(fù)雜度都合格，下一題了。

驗證二叉樹的前序序列化

題目：序列化二叉樹的一種方法是使用前序遍歷。當我們遇到一個非空節(jié)點時，我們可以記錄下這個節(jié)點的值。如果它是一個空節(jié)點，我們可以使用一個標記值記錄，例如 #。

     _9_
    /   \
   3     2
  / \   / \
 4   1  #  6
/ \ / \   / \
# # # #   # #

例如，上面的二叉樹可以被序列化為字符串 "9,3,4,#,#,1,#,#,2,#,6,#,#"，其中 # 代表一個空節(jié)點。給定一串以逗號分隔的序列，驗證它是否是正確的二叉樹的前序序列化。編寫一個在不重構(gòu)樹的條件下的可行算法。每個以逗號分隔的字符或為一個整數(shù)或為一個表示 null 指針的 '#' 你可以認為輸入格式總是有效的，例如它永遠不會包含兩個連續(xù)的逗號，比如 "1,,3" 。

示例 1:
輸入: "9,3,4,#,#,1,#,#,2,#,6,#,#"
輸出: true
示例 2:
輸入: "1,#"
輸出: false
示例 3:
輸入: "9,#,#,1"
輸出: false

思路：說個題外話，剛剛有個一起刷題的小姐姐邀請我4.25力扣編程大賽的組隊。。其實統(tǒng)共也報名了幾次leetcode的周賽，感覺自己現(xiàn)在的水平就是簡單的百分之九十沒問題，中等的要看運氣做出一兩道。最后困難的別說會不會了，大多數(shù)情況看的時間都莫得。。。然后這個一直攻略困難題目的小姐姐邀請我，有點小開心哈~！咱們繼續(xù)說這個題吧。這個題我覺得有一點：如果按照空位補0的情況，起碼這個數(shù)要是奇數(shù)的。因為根節(jié)點是一個，剩下都是成對出現(xiàn)，所以元素的個數(shù)一定是奇數(shù)個數(shù)。其次就是每一層個數(shù)，如果有一個#，則下一層在滿數(shù)的情況下少2個，依次判斷。我去實現(xiàn)看看。
思路沒問題，細節(jié)處理可能不太好，但是題目還是很清晰明了的，我直接貼代碼：

class Solution {
    int len;
    public boolean isValidSerialization(String preorder) {       
        String[] str = preorder.split(",");
        len = str.length;
        if(str.length%2!=1) return false;
        return dfs(str,1,0);
        
    }
    public boolean dfs(String[] str,int n,int start){
        if(len<(start+n))return false;//剩下元素數(shù)不夠了直接false
        int num = n;
        for(int i = 0;i<n;i++){
            if(str[start+i].equals("#")) num--;
        }
        //最后一層正好都是#則true
        if(num==0 && len == (start+n)) return true;
        //不應(yīng)該有下一層元素了，但是前序序列化中還有元素
        if(num==0) return false;
        return dfs(str,num*2,start+n);
    }
}

首先奇偶數(shù)的那個上面說了思路，其次最后一層肯定都是#才對。下一層是上一層數(shù)目的兩倍。反正我覺得條件啥的挺明確的。這道題就這樣吧。
我這個代碼是4ms，超過百分之八十七的人。我覺得大體思路沒錯。改進的話字符串equals這塊耽誤性能了可能，但是這里用char也不合適，畢竟數(shù)字有可能會好幾位數(shù)。。算了，我直接看題解吧。
性能排行第一的代碼：

class Solution {
    public boolean isValidSerialization(String preorder) {
        if (preorder == null || preorder.length() == 0) {
            return false;
        }
        int nodesNum = 0;
        char[] chars = preorder.toCharArray();
        int length = preorder.length();
        int i = 0;
        for (; i < length;) {
            if (chars[i] == ',') {
                ++i;
            } else if (chars[i] == '#') {
                if (nodesNum == 0) {
                    break;
                }
                ++i;
                --nodesNum;
            } else {
                ++nodesNum;
                ++i;
                while (i < length && chars[i] != '#' && chars[i] != ',') {
                    ++i;
                }
            }
        }
        return nodesNum == 0 && i == length - 1;
    }
}

怎么說呢，其實我覺得我已經(jīng)找到約束條件了，只不過和人家的一比，還是太年輕啊。我是看了人家的代碼反推回去才發(fā)現(xiàn)，如果都是空白補#，#的數(shù)量應(yīng)該比實際上的已有值的節(jié)點數(shù)多一個。另外因為是前序排列，所以不能只看最后總數(shù)結(jié)果，必須保證不會出現(xiàn)上一層都是#下一層還有元素的情況，所以一旦#數(shù)多了則直接return。
圖中性能第一的代碼是用正常節(jié)點數(shù)減去空節(jié)點數(shù)。如果出現(xiàn)不夠減的情況說明false。最后如果正常節(jié)點數(shù)沒了并且遍歷到序列的最后說明是對的，返回true不然就是false。
這道題只能說實現(xiàn)簡單，但是像人家這么思路清楚的實現(xiàn)我沒做到。下次記得了，下一趟吧。

重新安排行程

題目：給定一個機票的字符串二維數(shù)組 [from, to]，子數(shù)組中的兩個成員分別表示飛機出發(fā)和降落的機場地點，對該行程進行重新規(guī)劃排序。所有這些機票都屬于一個從JFK（肯尼迪國際機場）出發(fā)的先生，所以該行程必須從 JFK 出發(fā)。

說明:
如果存在多種有效的行程，你可以按字符自然排序返回最小的行程組合。例如，行程 ["JFK", "LGA"] 與 ["JFK", "LGB"] 相比就更小，排序更靠前
所有的機場都用三個大寫字母表示（機場代碼）。
假定所有機票至少存在一種合理的行程。
示例 1:
輸入: [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
輸出: ["JFK", "MUC", "LHR", "SFO", "SJC"]
示例 2:
輸入: [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
輸出: ["JFK","ATL","JFK","SFO","ATL","SFO"]
解釋: 另一種有效的行程是 ["JFK","SFO","ATL","JFK","ATL","SFO"]。但是它自然排序更大更靠后。

思路：感覺這個題可以用鄰接鏈表實現(xiàn)？至于說的自然排序，我也沒太看明白排序的規(guī)則。反正先試試看吧。反正感覺這個題不難。jfk是0度的作為開始，剩下的因為確定是存在合理形成的，所以正常遍歷就好了吧？我去寫代碼試試。
好好一個題目讓我做的稀碎。中間改了n多次想法。本來想的入度，結(jié)果出來發(fā)現(xiàn)有的是死路。所以這個想法就破滅了，但是我覺得大方向還是不會錯的。所以換了回溯。主要是真的我覺得這種題麻煩的是數(shù)據(jù)格式，然后處理來處理去，最后用回溯+遞歸實現(xiàn)了，我直接貼下代碼：

class Solution {
    public List<String> findItinerary(List<List<String>> tickets) {
        Stack<String> stack = new Stack<String>();
        Map<String,List<String>> map = new HashMap<String,List<String>>();
        for (List<String> list : tickets) {
            String start = list.get(0);
            String end = list.get(1);
            if (!map.containsKey(start)) {
                map.put(start, new ArrayList<>());
            }
            map.get(start).add(end);
        }
        //排序
        for (String s : map.keySet()) {
            Collections.sort(map.get(s));
        }
        List<String> path = new ArrayList<>();
        DFS(map, "JFK", path, tickets.size() + 1);
        return path;
    }
    public boolean DFS(Map<String, List<String>> map, String s, List<String> path, int len){
        //整體是個大回溯、add——操作——remove，會回溯就說明此路不通，直接換成最近選擇的口換個選擇繼續(xù)試。
        path.add(s);
        //走到最后了
        if (path.size() == len) {
            return true;
        }
        
        List<String> next = map.get(s);
        if (next != null) {
            for (int i = 0; i < next.size(); ++i) {
                String nextS = next.get(i);
                //這個票往下走不下去了。
                if (nextS == null) {
                    continue;
                }
                //這個票正在走，所以下一個節(jié)點暫時為0.防止成環(huán)死遞歸
                next.set(i, null);
                if (DFS(map, nextS, path, len)) {
                    return true;
                } 
                next.set(i, nextS);
            }
        }
        path.remove(path.size() - 1);
        return false;
    }
}

然后因為代碼邏輯比較復(fù)雜，我注釋寫的很墨跡，說真的，一般我注釋都是給自己看的，怕坑著坑著不知道當時為啥這么寫代碼了。哈哈反正得品，細品。
做出來了發(fā)現(xiàn)邏輯其實不難，但是調(diào)試的時候真的心態(tài)炸。也可能是思路不清楚吧。
反正最終是實現(xiàn)了，大體邏輯：

• 首先變成map數(shù)組。然后互通關(guān)系要找好。稍微好點的是開始城市到結(jié)束城市不能互換。所以單向關(guān)系就好。
• 然后第二步是排序（因為說了按自然排序，我也不知道自然是誰，而且我覺得list也沒法自己排序，所以我用了sort，這個最自然了。）
• 第三步是找到一個途徑。找的過程是回溯+遞歸。中間有個注意點是遞歸過程中已經(jīng)用了的車次要暫時設(shè)置為null。不然可能就是過去回來過去回來陷入死循環(huán)。然后如果走到某條路不能走了說明不對，退到最近的岔路口，換條路。回溯也是這里用的。
  因為之前排序了，所以第一個到達終點（全都跑一遍就是到達終點了。而且是起始的，所以總長度+1。）就是最小自然排序的那個結(jié)果。
  總體來說思路就這樣，具體實現(xiàn)中的坑不自己試一遍容易記不住，千奇百怪的。
  看了下性能排行第一的代碼，思路是差不多的思路，只不過我是用list實現(xiàn)每個出發(fā)地對應(yīng)的目的地，而且還要單獨排序，但是人家用了一種自帶排序的隊列，處理起來比較優(yōu)雅吧。我直接貼代碼：

class Solution {
    public List<String> findItinerary(List<List<String>> tickets) {
        List<String> res = new ArrayList<>();
        if (tickets.size() == 0) {
            return res;
        }
        HashMap<String, PriorityQueue<String>> map = new HashMap<>();
        for (List<String> ticket : tickets) {
            String from = ticket.get(0);
            String to = ticket.get(1);
            if (map.get(from) == null) {
                map.put(from, new PriorityQueue<>());
            }
            map.get(from).offer(to);
        }

        findItineraryHelper(map, res, "JFK");
        return res;
    }

    public void findItineraryHelper(HashMap<String, PriorityQueue<String>> map, List<String> res, String from) {
        PriorityQueue<String> to = map.get(from);
        if (to != null) {
            while (!to.isEmpty()) {
                findItineraryHelper(map, res, to.poll());
            }
        }
        res.add(0, from);
    }
}

這個代碼我覺得利用數(shù)據(jù)結(jié)構(gòu)到極致了，其實這個PriorityQueue我是知道的，之前做題的時候也用過。不過可惜的是在這里沒想到用它。
而且還有一點，遞歸中是逆序插入的，就是每次都插入到第一個元素中。而且是每個元素?zé)o路可走了才會被插入到結(jié)果集。保證了最小的元素最后被插入到結(jié)果集，也就是到了最前面的位置。附上一個leetcode大佬的圖：

逆序插入