1. 在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数
    一个m*n有序的矩阵--找一个左下角或者右上角数,如果target比它小就行前移,如果target比它大就列下移
    public class Solution {
    //选取一个右上角的数,如果target比它小就左移(row--),,如果比它大就下移i++
    public boolean Find(int target, int [][] array) {
    //二维数组array.length代表行的长度,array[0].length代表列的长度
        int  row = array.length-1;
        int i = 0;
        while(row>=0&&i<array[0].length) {
            if(array[row][i]>target) {//选取右上角的数比较,目标比当前数小就(行)前移
                row--;
            }else if(array[row][i]<target){//目标比当前数大就(行)下移
                i++;
            }else {
                return true;
            }
        }
        return false;
    }
    }
  2. 请实现一个函数,将一个字符串中的空格替换成“%20”。例如,当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy
    是在原来的字符串上替换or新开一个字符串替换--在当前字符串替换,考虑从前往后移动还是从后往前移动--如果从前往后移动每遇到一个空格就需要移动一次后面的数据--而从后往前移动 在知道所需空间后则只要移动一次就行
    public class Solution{
    public String replaceSpace(StringBuffer str){
        int spaceNum = 0;       
        for(int i=0;i<str.length();i++){
            if(str.charAt(i)==' ')
                spaceNum++;    //计算str中的空格数量--计算数组需要的长度
        }
        int indexOld = str.length()-1;
        int newLength = str.length()+spaceNum*2;   //%20需要3个字符--除了空格占一个字符外还需要额外占两个字符空间,才能写入三个字符(每个空格都需要三个空间)
        int indexNew = newLength-1;
        str.setLength(newLength);    //扩充一下数组长度--准备写入
    //从后往前插入,遇到空格就替换--indexOld<newLength作用:当相等时就会退出循环
        for(;indexOld>=0&&indexOld<newLength;--indexOld){
            if(str.charAt(indexOld)==' '){
                str.setCharAt(indexOld--,'0');
                str.setCharAt(indexOld--,'2');
                str.setCharAt(indexOld--,'%');
            }else{
                str.setCharAt(indexNew--,str.charAt(indexOld));
            }
        }
        return str.toString();
    }
    }
    public class Solution {
    public String replaceSpace(StringBuffer str) {
        return str.toString().replaceAll("\\s","%20");
    }
    }
  3. 输入一个链表,从尾到头打印链表每个节点的值
    利用栈-先进后出,利用递归

    /**
    *    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) {
        Stack<Integer> temp = new Stack<>();//栈对象
        ArrayList<Integer> newList = new ArrayList<>();
        ListNode t = listNode;
        while(t != null) {
            temp.push(t.val);//进栈
            t = t.next;
        }
        while(!temp.empty()) {
            newList.add(temp.pop());//出栈值添加到list中返回
        }
        return newList;
    }
    }
    /**
    *    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> list = nnew ArrayList<>();
        ListNode pNode = listNOde;
        if(pNode != null) {
            if(pNode.next != null) {
                list = printListFromTailToHead(pNode.next);
            }
            list.add(pNode.val);
        }
    
    }
    }
  4. 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。
    前序遍历:节点-左树-右树 中序遍历:左树-节点-右树--在前序中第一个节点为根节点,根据根节点在中序中分出左树和右树--在左右树中按照前面的规则递归
    /**
    * 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) {
        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,startIn,int endIn) {
         if(startPre > endPre || startIn > endIn) {
             return null;
         }
         TreeNode root = TreeNode(pre[startPre]);//父节点
         for(int i=startIn;i<=endIn;i++){//在中序列表中找到根节点
             if(in[i] == pre[startPre] {
    //对比startPre=startPre+1;(作用:选出父节点,前序列表--父节点在前)
    //endPre=startPre+i-startIn;()
    //startIn=startIn;
    //endIn=i-1
                 root.left = reConstructBinaryTree(pre,startPre+1,startPre+i-startIn,in,startIn,i-1);
                 root.right = reConstructBinaryTree(pre,startPre+i-startIn+1,endPre,in,i+1,endIn);
    //startPre=startPre+i-startIn+1;
    //endPre=endPre;
    //startIn=i+1;
    //endIn=endIn
             }
         }
         return root;
    }
    }
  5. 用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。

    import java.util.Stack;
    //队列:先进先出
    //栈:先进后出
    //思想:先进stack1再进stack2然后pop()
    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(stack1.empty()&&stack2.empty()){
            throw new RuntimeException("Queue is empty!");
        }
        if(stack2.empty()){
            while(!stack1.empty()){
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
    }