leetCode进阶算法题+解析（十三）

反正链表2

题目：反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明:
1 ≤ m ≤ n ≤ 链表长度。
示例:
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL

思路：说实话，这个题，感觉难点在一次扫描完成翻转吧。我现在的想法就是到了第m个元素开始，保存之前的链表，然后创建一个新链表，从后往前挂，挂到n个，直接把之前的链表接上这个新链表，然后后面的正常接。应该是一次扫描吧。我去实现下。
这个大体思路是对的，细节要不断的完善，反正我是改了好多版本（一开始的思路太笨了）。
实现思路 ：以1->2->3->4->5, m = 2, n=4 为例:

• 定位到要反转部分的头节点 2，head = 2；前驱结点 1，pre = 1；
• 当前节点的下一个节点3调整为前驱节点的下一个节点 1->3->2->4->5,
• 当前结点仍为2， 前驱结点依然是1，重复上一步操作。。。
• 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;
    }
}

要先设置一个头结点是以防从第一个元素开始反转。
首先nex=head.next. 其实这里主要就是为了保存插入元素的值，这句和下一句实现的一个功能：删除指到的节点并且保存节点值。
然后 head.next = nex.next;这句话讲head的下一个元素调过，其实换个角度就是 head.next = head.next.next。
继续nex.next = pre.next。到了这步就能看出来，nex其实保存的就是head的当前节点值。然后nex.next接上pre.next。
最后pre.next = nex;和上面的一行连起来，实现的操作就是把pre+nex+pre后面的值。相当于插入了一个节点而已。
我换种说法：
1,2,3,4,5想要倒转2，3，4。一种是倒转的理解，但是用插入的理解：
1，2，3，4，5
第一步：确定插入位置是1后面。定位1这个头结点
第二步：插入的元素的后面的元素同时把这个元素去掉：1后面是2，所以插入2.变成 1,2,3,4,5（这个2是后插入的而不是之前的2）
第三步：该插入的元素是3，把3本身删除。然后把3的值保存并插入到1后面。变成了1,3,2,4,5
第四步：该插入的元素是4，把4节点删除，4的值保存，并且插入到1后面，变成1,4,3,2,5
第五步：发现已经倒转完毕，直接返回。
这个题其实做出来不难，但是一次扫描还是很麻烦的。然后我觉得我解释的挺清楚了，这道题就这么过吧。

复原IP地址

题目：给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。

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

思路：简单来讲我做题生涯遇到了滑铁卢。。别说思路了，题目都看不懂了？？？想起一句话，力扣一大特点越简单的问题描述越不说人话。。好了好了，我去百度下什么是ip地址吧。如下如所示，要求三个“.”,四段数字，所以如果给定字符串长度小于4直接没有可能。还有0-256之间，所以每一段最多三个数，也就是说如果长度超过12也没有可能。最后的数字校准可以放到方法里面去做，其实这道题可以用回溯+剪枝来做。我去尝试写代码了。

ip格式

好了，做完回来了，很简单的题，就是性能一言难尽。我都奇了怪了，每次我觉得得心应手自信满满，性能总能打我脸，我先贴代码再说：

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){//一种可能完成了，直接添加到结果集
            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++){
                //因为这里是截取不包含后面，所以可以等于length和idx+3
                String ip = s.substring(idx,i);
                //大于255不能是ip段
                if(Integer.parseInt(ip)>255) continue;
                //如果大于一位数，0不是打头
                if(ip.length()>1 && ip.charAt(0)=='0') continue;
                list.add(ip);
                dfs(s,i,list,res);
                list.remove(list.size()-1);
            }
        }       
    }
}

首先是回溯，然后剪枝。
回溯就是标准三部曲：选择，递归，退回上一步。
剪枝条件：当前值大于255或者多位数0开头都直接pass。
然后这个题我觉得是很简单，但是问题性能
然后我这里为啥性能不好，，，讲真我还真没看出来。我特么还自以为我处理的挺好的呢，算了，我直接去看性能排行第一的代码吧。

image.png

好了，回来了，粗略的扫了几眼，逻辑不难，我这里字符串来字符串去的，还有list也是，来来回回size，get。人家用的char数组来表示这个字符串。还有用的数组表示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;
        }
    }
}

然后下次尽量吧，真的是字符串效率太低了，最近做题少，这个都没想到，我的我的。下一题。

二叉树的中序遍历

题目：给定一个二叉树，返回它的中序 遍历。

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

2
/
3
输出: [1,3,2]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？

思路:这道题题目都说了，递归算法很简单，要迭代完成。首先这个真的是基础的，二叉树前序中序后序。反正我就不多说了，然后迭代代替递归其实以前简单的题目就做过类似的。我记得当时是用了栈辅助（毕竟有那句话：栈就是隐式的递归
）。我先去敲代码了，两种都写一下。
首先是最无脑的递归：

/**
 * 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：如果前序中序后序不太理解的，其实就是递归中的三句话的顺序）
前序：

    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);  
    }

咱们继续说正题，用迭代代替递归：

/**
 * 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;
    }
}

这个题其实很简单，我这里用的栈stack这一数据结构（其实我怀疑用别的有序队列都可以。一会儿我去试试）、然后重点就是两个方法：一个是入栈，一个是出栈。
首先整个二叉树放进去。然后指针指向左树。下一个push进去的就是左树了。（因为是中序，所以先左后当前后右，举一反三，如果是后序则先放右边。前序则先把当前值add进去。随机应变吧）
等左边的都放完了，开始放右边的，因为后进下去，所以可以保证这个pop出来的右树是按照左树的存储顺序来获取的（这句话我不知道能不能理解，我想不出来更好的表述了），然后将值add进结果集。同时将root指向跟节点的右子树。
注意一下：通篇用的root，除了最开始push进去的是题目给的树，剩下的都是我用root来存储一个数对象的，不再是最开始的树了。

这样其实就是和 image.png
这三行代码一个意思，保证了中序遍历的顺序。
我感觉我表述的不太明白，大家对付看，实在脑补不出来我建议大家断点调试，一步一步走，看看是怎么存放的（好恨自己不会做动图）。
然后这道题就是怎么说呢，不懂的要慢慢理解，懂的很容易做出来，我就不多说了，刚刚我就说了，这里利用的是栈先入后出（也可以说后入先出）的特性。我感觉其实这个用list也是可以实现的。只不过把本来简单的操作变复杂了。每次取最后一个元素，然后删除最后一个元素。。我去试试吧，反正闲着。
卧槽！真的实现了，实现了是意料中的事，问题是用list性能居然比stack还要好。。。神奇了啊~~我直接贴代码：

/**
 * 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
有点神奇啊，哈哈。
今天的笔记就记到这里了，如果稍微帮到你了记得点个喜欢点个关注，也祝大家工作顺顺利利！生活健健康康！