反正鏈表2

題目：反轉(zhuǎn)從位置 m 到 n 的鏈表。請(qǐng)使用一趟掃描完成反轉(zhuǎn)。

說明:
1 ≤ m ≤ n ≤ 鏈表長(zhǎng)度。
示例:
輸入: 1->2->3->4->5->NULL, m = 2, n = 4
輸出: 1->4->3->2->5->NULL

思路：說實(shí)話，這個(gè)題，感覺難點(diǎn)在一次掃描完成翻轉(zhuǎn)吧。我現(xiàn)在的想法就是到了第m個(gè)元素開始，保存之前的鏈表，然后創(chuàng)建一個(gè)新鏈表，從后往前掛，掛到n個(gè)，直接把之前的鏈表接上這個(gè)新鏈表，然后后面的正常接。應(yīng)該是一次掃描吧。我去實(shí)現(xiàn)下。
這個(gè)大體思路是對(duì)的，細(xì)節(jié)要不斷的完善，反正我是改了好多版本（一開始的思路太笨了）。
實(shí)現(xiàn)思路 ：以1->2->3->4->5, m = 2, n=4 為例:

• 定位到要反轉(zhuǎn)部分的頭節(jié)點(diǎn) 2，head = 2；前驅(qū)結(jié)點(diǎn) 1，pre = 1；
• 當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)3調(diào)整為前驅(qū)節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn) 1->3->2->4->5,
• 當(dāng)前結(jié)點(diǎn)仍為2， 前驅(qū)結(jié)點(diǎn)依然是1，重復(fù)上一步操作。。。
• 1->4->3->2->5.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;
        for(int i = 1; i < m; i++){
            pre = pre.next;
        }
        head = pre.next;
        for(int i = m; i < n; i++){
            ListNode nex = head.next;
            head.next = nex.next;
            nex.next = pre.next;
            pre.next = nex;
        }
        return dummy.next;
    }
}

要先設(shè)置一個(gè)頭結(jié)點(diǎn)是以防從第一個(gè)元素開始反轉(zhuǎn)。
首先nex=head.next. 其實(shí)這里主要就是為了保存插入元素的值，這句和下一句實(shí)現(xiàn)的一個(gè)功能：刪除指到的節(jié)點(diǎn)并且保存節(jié)點(diǎn)值。
然后 head.next = nex.next;這句話講head的下一個(gè)元素調(diào)過，其實(shí)換個(gè)角度就是 head.next = head.next.next。
繼續(xù)nex.next = pre.next。到了這步就能看出來，nex其實(shí)保存的就是head的當(dāng)前節(jié)點(diǎn)值。然后nex.next接上pre.next。
最后pre.next = nex;和上面的一行連起來，實(shí)現(xiàn)的操作就是把pre+nex+pre后面的值。相當(dāng)于插入了一個(gè)節(jié)點(diǎn)而已。
我換種說法：
1,2,3,4,5想要倒轉(zhuǎn)2，3，4。一種是倒轉(zhuǎn)的理解，但是用插入的理解：
1，2，3，4，5
第一步：確定插入位置是1后面。定位1這個(gè)頭結(jié)點(diǎn)
第二步：插入的元素的后面的元素同時(shí)把這個(gè)元素去掉：1后面是2，所以插入2.變成 1,2,3,4,5（這個(gè)2是后插入的而不是之前的2）
第三步：該插入的元素是3，把3本身刪除。然后把3的值保存并插入到1后面。變成了1,3,2,4,5
第四步：該插入的元素是4，把4節(jié)點(diǎn)刪除，4的值保存，并且插入到1后面，變成1,4,3,2,5
第五步：發(fā)現(xiàn)已經(jīng)倒轉(zhuǎn)完畢，直接返回。
這個(gè)題其實(shí)做出來不難，但是一次掃描還是很麻煩的。然后我覺得我解釋的挺清楚了，這道題就這么過吧。

復(fù)原IP地址

題目：給定一個(gè)只包含數(shù)字的字符串，復(fù)原它并返回所有可能的 IP 地址格式。

示例:
輸入: "25525511135"
輸出: ["255.255.11.135", "255.255.111.35"]

思路：簡(jiǎn)單來講我做題生涯遇到了滑鐵盧。。別說思路了，題目都看不懂了？？？想起一句話，力扣一大特點(diǎn)越簡(jiǎn)單的問題描述越不說人話。。好了好了，我去百度下什么是ip地址吧。如下如所示，要求三個(gè)“.”,四段數(shù)字，所以如果給定字符串長(zhǎng)度小于4直接沒有可能。還有0-256之間，所以每一段最多三個(gè)數(shù)，也就是說如果長(zhǎng)度超過12也沒有可能。最后的數(shù)字校準(zhǔn)可以放到方法里面去做，其實(shí)這道題可以用回溯+剪枝來做。我去嘗試寫代碼了。

ip格式

好了，做完回來了，很簡(jiǎn)單的題，就是性能一言難盡。我都奇了怪了，每次我覺得得心應(yīng)手自信滿滿，性能總能打我臉，我先貼代碼再說：

class Solution {
    public List<String> restoreIpAddresses(String s) {
        if(s==null || s.length()>12 || s.length()<4) return new ArrayList<String>();
        List<String> res = new ArrayList<String>();
        dfs(s,0,new ArrayList<String>(),res);
        return res;

    }
    public void dfs(String s,int idx,List<String> list,List<String> res){
        if(list.size()==4 && s.length()==idx){//一種可能完成了，直接添加到結(jié)果集
            String result = list.get(0)+"."+list.get(1)+"."+list.get(2)+"."+list.get(3);
            res.add(result);
        }else{
            for(int i = idx+1;i<=s.length()&&i<=idx+3;i++){
                //因?yàn)檫@里是截取不包含后面，所以可以等于length和idx+3
                String ip = s.substring(idx,i);
                //大于255不能是ip段
                if(Integer.parseInt(ip)>255) continue;
                //如果大于一位數(shù)，0不是打頭
                if(ip.length()>1 && ip.charAt(0)=='0') continue;
                list.add(ip);
                dfs(s,i,list,res);
                list.remove(list.size()-1);
            }
        }       
    }
}

首先是回溯，然后剪枝。
回溯就是標(biāo)準(zhǔn)三部曲：選擇，遞歸，退回上一步。
剪枝條件：當(dāng)前值大于255或者多位數(shù)0開頭都直接pass。
然后這個(gè)題我覺得是很簡(jiǎn)單，但是問題性能
然后我這里為啥性能不好，，，講真我還真沒看出來。我特么還自以為我處理的挺好的呢，算了，我直接去看性能排行第一的代碼吧。

image.png

好了，回來了，粗略的掃了幾眼，邏輯不難，我這里字符串來字符串去的，還有l(wèi)ist也是，來來回回size，get。人家用的char數(shù)組來表示這個(gè)字符串。還有用的數(shù)組表示list的四段ip段。我直接貼代碼膜拜：

class Solution {
    List<String> res = new ArrayList();
    int[] nums = new int[4];
    char[] cs ;
    public List<String> restoreIpAddresses(String s) {
        cs = s.toCharArray();
        help(0,0);
        return res;
    }

    void help(int index,int size){
        if(size==4&&index==cs.length){
            StringBuilder sb = new StringBuilder();
            for(int i=0;i<size;++i){
                sb.append(nums[i]);
                if(i!=size-1) sb.append(".");
            }
            res.add(sb.toString());
            return ;
        }
        if(size>=4) return ;
        int num = 0;
        for(int i=index;i<cs.length&&i<index+3;++i){
            if(num==0&&i!=index) break;
            num = cs[i]-'0' + num*10;
            if(num>255){
                break;
            }
            
            nums[size] = num;
            help(i+1,size+1);
            nums[size] = 0;
        }
    }
}

然后下次盡量吧，真的是字符串效率太低了，最近做題少，這個(gè)都沒想到，我的我的。下一題。

二叉樹的中序遍歷

題目：給定一個(gè)二叉樹，返回它的中序 遍歷。

示例:
輸入: [1,null,2,3]
1

2
/
3
輸出: [1,3,2]
進(jìn)階: 遞歸算法很簡(jiǎn)單，你可以通過迭代算法完成嗎？

思路:這道題題目都說了，遞歸算法很簡(jiǎn)單，要迭代完成。首先這個(gè)真的是基礎(chǔ)的，二叉樹前序中序后序。反正我就不多說了，然后迭代代替遞歸其實(shí)以前簡(jiǎn)單的題目就做過類似的。我記得當(dāng)時(shí)是用了棧輔助（畢竟有那句話：棧就是隱式的遞歸
）。我先去敲代碼了，兩種都寫一下。
首先是最無腦的遞歸：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    List<Integer> res;
    public List<Integer> inorderTraversal(TreeNode root) {
        res = new ArrayList<Integer>();
        df(root);
        return res;
    }
    public void df(TreeNode root){
        if(root==null) return;
        df(root.left);
        res.add(root.val);        
        df(root.right);
    }
}

（ps：如果前序中序后序不太理解的，其實(shí)就是遞歸中的三句話的順序）
前序：

    public void df(TreeNode root){
        if(root==null) return;
        res.add(root.val);    
        df(root.left);           
        df(root.right);
    }

中序如demo中的代碼。
后序：

public void df(TreeNode root){
        if(root==null) return;          
        df(root.left);           
        df(root.right);
        res.add(root.val);  
    }

咱們繼續(xù)說正題，用迭代代替遞歸：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        //root不是null或者棧沒空都說明沒遍歷完
        while(root!=null || !stack.isEmpty()){
           if(root!=null){
              stack.push(root);
               root = root.left;
           }else{
               root = stack.pop();
               res.add(root.val);
               root = root.right;
           }
        }
        return res;
    }
}

這個(gè)題其實(shí)很簡(jiǎn)單，我這里用的棧stack這一數(shù)據(jù)結(jié)構(gòu)（其實(shí)我懷疑用別的有序隊(duì)列都可以。一會(huì)兒我去試試）、然后重點(diǎn)就是兩個(gè)方法：一個(gè)是入棧，一個(gè)是出棧。
首先整個(gè)二叉樹放進(jìn)去。然后指針指向左樹。下一個(gè)push進(jìn)去的就是左樹了。（因?yàn)槭侵行颍韵茸蠛螽?dāng)前后右，舉一反三，如果是后序則先放右邊。前序則先把當(dāng)前值add進(jìn)去。隨機(jī)應(yīng)變吧）
等左邊的都放完了，開始放右邊的，因?yàn)楹筮M(jìn)下去，所以可以保證這個(gè)pop出來的右樹是按照左樹的存儲(chǔ)順序來獲取的（這句話我不知道能不能理解，我想不出來更好的表述了），然后將值add進(jìn)結(jié)果集。同時(shí)將root指向跟節(jié)點(diǎn)的右子樹。
注意一下：通篇用的root，除了最開始push進(jìn)去的是題目給的樹，剩下的都是我用root來存儲(chǔ)一個(gè)數(shù)對(duì)象的，不再是最開始的樹了。

image.png

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        List<TreeNode> list = new ArrayList<TreeNode>();
        //root不是null或者棧沒空都說明沒遍歷完
        while(root!=null || list.size()!=0){
           if(root!=null){
               list.add(root);
               root = root.left;
           }else{
               root = list.get(list.size()-1);
               list.remove(list.size()-1);
               res.add(root.val);
               root = root.right;
           }
        }
        return res;
    }
}

image.png