希望看起来没那么乱

牛客的发表博客想再次编辑，好像有点小问题，所以只好另起一篇，看看哪里需要更新或者有新的理解。本轮刷题是在leetcode上完成，因此有些名称和牛客oj不太一样。
这里是一刷的目录

03. 数组中重复的数字

参考原来的一刷的博客即可，在一刷的解法4，名字可以叫原地置换。该方法是时间复杂度和空间复杂度最佳，只是会改变原数组。
最优解如下:
Leetcode上是返回该数字，因此稍微有点不同

class Solution {
    public int findRepeatNumber(int[] nums) {
        int n=nums.length;
        for(int i=0;i<nums.length;i++){
            //例如5不在索引为5的位置上，就一直和后面的数做交换
            //直到出现两个相同，比如2位置上已经是2，而后面又出现了2
            //则描述该情况 nums[i]是后面的2  而nums[nums[i]]是前面的2，相同则找到了所求
            while(nums[i]!=i){
                if(nums[nums[i]] == nums[i]){
                    return nums[i];
                }
                int temp = nums[i];
                nums[i] = nums[temp];
                nums[temp] = temp;
            }
        }
        return -1;
    }
}

04.二维数组中的查找

参考原来的一刷的博客即可。时间复杂度O(n)，利用阶梯型走法。
提供一个Leetcode上通过的写法

class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if(matrix == null || matrix.length == 0) {
            return false;
        }
        //以右上角查找为例 则从最后一列开始，从第一行开始
        int m = matrix.length;//行
        int n= matrix[0].length;//列
        int row = 0;
        int col = n - 1;
         while(row < m && col >= 0) {
            if(matrix[row][col] > target) {
                col--;
            }else if(matrix[row][col] < target) {
                row++;
            }else {
                return true;
            }
        }
        return false;
    } 
}

05.替换空格

依旧参考一刷博客。最容易理解的写法是遇到空格在StringBuider或者StringBuffer上直接添加，而本题考察的是替换，因此，考虑如果给定的是一个字符数组，要求不适用额外的空间，在原数组上进行修改并替换空格，这样的假设下，最正统的方法就是从后往前慢慢加，也就是博客中记录的方法2。考虑本题给定的并不是一个字符数组，因此写法上会有些不同。
同样这里记录一个Leetcode上通过的正统写法。

class Solution {
    public String replaceSpace(String s) {
        if(s==null || "".equals(s)) return s;
        //统计空格数量
        int spaceCount = 0;
        for(int i = 0 ; i < s.length() ;i++){
            if(s.charAt(i) == ' ') {
                spaceCount++;
            }
        }
        //由于String是不可变的，为了容纳更多的字符，需要进行扩容
        int length1 = s.length();
        int length2 = length1+2*spaceCount;
        char[] result = new char[length2];
        //双指针
        int p1 = s.length()-1;
        int p2 = result.length-1;
        while(p1>=0){
            char c = s.charAt(p1);
            if(c ==' '){
                result[p2--] = '0';
                result[p2--] = '2';
                result[p2--] = '%';
            }else{
                result[p2--] = c;
            }
            p1--;
        }
        return new String(result);
      //return String.valueOf(result);
    }
}

06. 从尾到头打印链表（有补充）

这里要说明的是，有多种方法，递归，头插，栈，以及二刷要补充的反转链表，其他部分可以参考一刷博客，这里仅记录反转链表的写法。最优解可应该学习栈的写法，但是这个写法不需要额外空间，也是面试中的一个考点

class Solution {
    public int[] reversePrint(ListNode head) {

        ListNode temp = reverse(head);
        LinkedList<Integer> res = new LinkedList<>();
        while (temp != null) {
            res.add(temp.val);
            temp = temp.next;
        }
        int[] ans = new int[res.size()];
        for(int i=0;i<ans.length;i++){
            ans[i] = res.get(i);
        }
        return ans;
    }
    private ListNode reverse(ListNode node) {
        if (node == null || node.next == null ) {
            return node;
        }
        ListNode pre = null;
        ListNode cur = node;
        while (cur != null) {
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
}

07. 重建二叉树（有新的认识）

这题比较难，在一刷的写法中，我们每次都需要重新在中序中找到对应的值，但是这里可以用Map代替这一查找动作。思路其实一致，只是在找中序的节点时，一个重新找，一个用容器存了查找结果。如果要求不适用额外空间，那么显然是一刷的写法最好。
map中存放的是中序的某个值，以及该值的角标索引。

public class Solution {
    HashMap<Integer, Integer>  map = new HashMap<>();
    int[] arr;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        arr = preorder;
        for(int i = 0; i < inorder.length; i++)
            map.put(inorder[i], i);
        return recur(0, 0, inorder.length - 1);
    }
    public TreeNode recur(int pre_root, int in_left, int in_right) {
        if(in_left > in_right) return null;
        TreeNode root = new TreeNode(arr[pre_root]);
        int i = map.get(arr[pre_root]);//找到在中序中的位置
        //然后计算出各种偏移量。
        root.left = recur(pre_root + 1, in_left, i - 1);
        root.right = recur(pre_root + i - in_left + 1, i + 1, in_right);
        return root;
    }
}

有必要把原始写法也写出来，方便对比

public class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        TreeNode root=helper(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
        //传过去一个两个数组以及这个数组的首尾索引
        return root;
    }
    //前序遍历{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}
   public TreeNode helper(int[] pre,int leftP,int rightP,int[] in,int leftI,int rightI)
{
        //startPre和endpre以及startIn和endIn的缩写 分别代表传入数组的首尾位置的索引
        if(leftP>rightP||leftI>rightI)  //递归结束标志（也可加入其他健壮性语句）
            return null;

        TreeNode root=new TreeNode(pre[leftP]); //找到pre的首节点，就是传过来的树的根

        for(int i=leftI;i<=rightI;i++)   //遍历传过来的中序，找到根节点。
            if(in[i]==pre[leftP]){   //其左边的是子树，调用递归。右边的是右子树，调用递归
                root.left=helper(pre,leftP+1,leftP+i-leftI,in,leftI,i-1);
                root.right=helper(pre,i-leftI+leftP+1,rightP,in,i+1,rightI);
                break;//找到根节点在中序的位置就可以了，可以提前退出。
            }
        return root;
    }
}

08.二叉树的下一个节点（Leetcode的剑指offer部分暂无本题但有补充）

移步这里
上面的写法是在递归的过程中比较，显然我们还有一个思路，就是遍历出中序所有结果，然后去比较。但是整体上，一刷记录的写法是最优的，针对于各种情况讨论。因此建议掌握一刷中给出的方法。另外如果是找上一节点的话，我们用栈遍历的时候，可以记录上一个节点，但是下一个节点不好记录。

09.用两个栈实现队列

一刷博客中记录的方法，以下为Leetcode上ac代码

public class CQueue {

    Stack<Integer> stack1;
    Stack<Integer> stack2;
    public CQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }

    public void appendTail(int value) {
        stack1.push(value);//永远往栈1压元素
    }

    public int deleteHead() {
        if(stack1.empty()&&stack2.empty()){
            return -1;
        }
        if(stack2.isEmpty()){ //栈2为空，就需要倒一手，不为空就直接弹，跳到return进行弹
            while(!stack1.isEmpty()){
                //栈2已经空了想取元素，就得把元素全部倒给栈2，直到栈1是空
                stack2.push(stack1.pop()); //把栈1的弹出，全部放入栈2
            }
        }
        return stack2.pop();
    }
}