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 printListFromTailToHead(ListNode listNode) {
    Stack temp = new Stack<>();//栈对象
    ArrayList 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;
    }
    }

    
    ```java
    /**
  • public class ListNode {
  • int val;
  • ListNode next = null;
  • ListNode(int val) {
  • this.val = val;
  • }
  • }
  • */
    import java.util.ArrayList;
    public class Solution {
    public ArrayList printListFromTailToHead(ListNode listNode) {
    ArrayList 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},则重建二叉树并返回。
`前序遍历:节点-左树-右树` `中序遍历:左树-节点-右树`--`在前序中第一个节点为根节点,根据根节点在中序中分出左树和右树`--`在左右树中按照前面的规则递归`
 ```java
/**
 * 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;
    }
}
  1. 用两个栈来实现一个队列,完成队列的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();
     }
    }