剑指Offer（一）

题目一：二维数组中的查找

题目描述：
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

解题思路：
二维数组的矩形是有序的，且向右向下递增。从第一行最后一列开始比较，如果target小于该对象，则跳过该列向左比较，如果target大于该对象，则跳过该行向下比较。直到找到target相等或者找完整个二维数组。

  public boolean Find(int target, int [][] array) {
        if(array == null || array.length < 1 || array[0].length < 1){
            return false;
        }

        int rows = array.length;
        int cols = array[0].length;

        int row = 0;
        int col = cols - 1;

        while (row < rows && col < cols && row >=0 && col >= 0){
            if(array[row][col] == target){
                return true;
            }else if(array[row][col] > target){
                col--;
            }else{
                row++;
            }
        }

        return false;
    }

---

题目二：二维数组中的查找

题目描述：
请实现一个函数，将一个字符串中的空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

解题思路：
1.直接用replaceAll函数

  public String replaceSpace(StringBuffer str) {
        String string = str.toString();
        return string.replaceAll("\\s","%20");
  }

2.采用遍历的方式修改字符串

  public String replaceSpace(StringBuffer str) {
        StringBuffer out = new StringBuffer();
        for(int i = 0; i < str.toString().length(); i++){
            char b = str.charAt(i);
            if(String.valueOf(b).equals(" ")){
               out.append("%20");
            }else{
                out.append(b);
            }
        }
        return out.toString();
    }

---

题目三：从尾到头打印链表

题目描述：
输入一个链表，从尾到头打印链表每个节点的值。

  public class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }

解题思路：
1.遍历链表获得每个元素，采用栈结构实现先进后出。

 public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        
        ArrayList<Integer> arrayList = new ArrayList<>();

        if(listNode != null){
            arrayList.add(listNode.val);
            while (listNode.next != null){
                listNode = listNode.next;
                arrayList.add(0,listNode.val);
            }
        }
        return arrayList;
  }

2.采用递归的方式

  ArrayList<Integer> arrayList = new ArrayList<>();

  public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        if(listNode != null){
            this.printListFromTailToHead(listNode.next);
            arrayList.add(listNode.val);
        }
        return arrayList;
  }

---

题目四：重建二叉树

题目描述：
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

  public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

解题思路：
前序遍历序列得到根节点和左右两边的树结构，在使用递归方式得到整个二叉树

  public TreeNode reConstructBinaryTree(int [] pre,int [] in) {

        TreeNode root=reConstructBinaryTree(pre,0,pre.length-1,in,0,in.length-1);

        return root;

  }

  private TreeNode reConstructBinaryTree(int [] pre,int startPre,int endPre,int [] in,int startIn,int endIn) {

        if(startPre>endPre||startIn>endIn){
            return null;
        }

        TreeNode root=new TreeNode(pre[startPre]);
        //对中序数组进行输入边界的遍历
        for(int i = startIn; i <= endIn; i++){
            if(in[i]==pre[startPre]){
                //重构左子树，注意边界条件
                root.left=reConstructBinaryTree(pre,startPre+1,startPre+i-startIn,in,startIn,i-1);
                //重构右子树，注意边界条件
                root.right=reConstructBinaryTree(pre,i-startIn+startPre+1,endPre,in,i+1,endIn);
            }
        }
        return root;
  }

---

题目五：用两个栈实现队列

题目描述：
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

解题思路：
两个栈，一个栈为入栈，一个栈为出栈，加入队列则添加到入栈，踢出队列则在出栈中pop，如果出栈为空，则遍历清空入栈，将元素以相反顺序添加到出栈中。

    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()){
            while (!stack1.empty()){
                int i = stack1.pop();
                stack2.push(i);
            }
        }
       return stack2.pop();
    }