高强度学习训练第九天总结：5道剑指offer的题目

实在不想看JVM了。刷几道剑指Offer的题，今天就水一水吧，脑子迷糊。

1.二维数组中的查找

解题思路：从右上角开始搜索，从上到下为递增，从右到左为递减。根据这个思路来进行搜索，算法复杂度n+m

public class Solution {
    public boolean Find(int target, int [][] array) {
        int x=0,y=array[0].length-1;
        while(x<array.length&&y>-1){
            if(array[x][y]>target){
                y--;
            }else if(array[x][y]<target){
                x++;
            }else{
                return true;
            }
        }
        return false;
    }
}

---

2.替换空格

解题思路：不能一个一个插入，复杂度太高，要用空间来换取时间。一个一个赋值比较好。

public class Solution {
    public String replaceSpace(StringBuffer str) {
        StringBuffer sb = new StringBuffer();
        for(int i=0;i<str.length();i++) {
            if(str.charAt(i)==' ') {
                sb.append("%20");
            }else {
                sb.append(str.charAt(i));
            }
        }
        return sb.toString();
    }
}

---

3.从尾到头打印链表

解题思路：这题用C++的话可以直接把指针反转，不过Java传进来的是一个集合类。就算了吧。用傻瓜式解法。

/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> al = new ArrayList<Integer>();
        while(listNode!=null) {
            al.add(0,listNode.val);
            listNode = listNode.next;
        }
        return al;
    }
}

---

4.重建二叉树

解题思路：递归建树。基础题。

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if(pre.length==0) return null;
        TreeNode trn = new TreeNode(pre[0]);
        if(pre.length==1) return trn;
        else for(int i=0;i<in.length;i++) {
            if(in[i]==pre[0]) {
                int [] preleft = new int[i];
                int [] preright = new int[in.length-i-1];
                int [] inleft = new int[i];
                int [] inright = new int[in.length-i-1];
                System.arraycopy(pre,1,preleft,0,i);
                System.arraycopy(pre,i+1,preright,0,in.length-i-1);
                System.arraycopy(in,0, inleft, 0, i);
                System.arraycopy(in,i+1, inright, 0, in.length-i-1);
                trn.left = reConstructBinaryTree(preleft, inleft);
                trn.right = reConstructBinaryTree(preright,inright);
                return trn;
            }
        }
        return trn;
    }
}

---

5.用两个栈实现队列

解题思路：对先进后出和先进先出的基础理解即可想明白。

import java.util.Stack;

public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();

     public void push(int node) {
        stack1.push(node);
    }

    public int pop() {
        if(!stack2.empty()) {
            return stack2.pop();
        }
        else{
            while(!stack1.empty()) {
                stack2.push(stack1.pop());
            }
            return stack2.pop();
        }
    }
}