【剑指offer】

1、二维数组中的查找

//方法一：
        for(int i=0; i<array.length;i++){
            for(int j = 0;j<array[0].length;j++){
                if(array[i][j] == target){
                    return true;
                }
            }
        }
        return false;

//方法二：
        int x = 0;
        int y = array[0].length - 1;

        while(x < array.length && x >= 0 && y >= 0 && y < array[0].length ){
            if(target == array[x][y]){
                return true;
            }else if(target > array[x][y]){
                x++;
            }else{
                y--;
            }
        }
        return false;

2、替换空格

方法一：
        return  str.toString().replace(" ","%20");

方法二：
        StringBuffer s = new StringBuffer();
        for(int i =0;i<str.length();i++){
            if(str.charAt(i) == ' '){
                s.append("%20");
            }else{
                s.append(str.charAt(i));
            }
        }
        return s.toString();

3、从尾到头打印链表

//方法一：
        ArrayList<Integer> list = new ArrayList<>();
        Stack<Integer> statck = new Stack<>();

        while(listNode != null ){
            statck.add(listNode.val);
            listNode = listNode.next;
        }

        while(!statck.isEmpty()){
            list.add(statck.pop());
        }
        return list;

//方法二：
        ArrayList<Integer> list = new ArrayList<>();
        ListNode temp = listNode;
        while(temp != null){
            list.add(0,temp.val);
            temp = temp.next;
        }
        return list;

//方法三：
        ArrayList<Integer> list = new ArrayList<>();
        ListNode temp = listNode;
        while(temp != null){
            list.add(temp.val);
            temp = temp.next;
        }
        Collections.reverse(list);
        return list;

//方法四：递归
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> list = new ArrayList<>();
        if(listNode == null){
            return list;
        }
        return solve(list,listNode);
    }

    private static  ArrayList<Integer> solve(ArrayList<Integer> list,ListNode listNode){
        if(listNode.next != null){
            list = solve(list,listNode.next);
        }
        list.add(listNode.val);
        return list;
    }

//方法五：递归
public class Solution {
    ArrayList<Integer> list = new ArrayList<>();
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        if(listNode != null){
            printListFromTailToHead(listNode.next);
            list.add(listNode.val);
        }
        return list;
}

4、重建二叉树

import java.util.*;
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        Map<Integer,Integer> map = new HashMap<>();
        for(int i=0;i<pre.length;i++){
            map.put(in[i],i);
        }

        return buildTree(pre,0,pre.length-1,in,0,in.length-1,map);
    }

    private TreeNode buildTree(int[] preorder,int preLIndex,int preRIndex,int[] inorder,int inLIndex,int inRIndex,Map<Integer,Integer> map){
        if(preLIndex > preRIndex || inLIndex >inRIndex){
            return null;
        }
        int pIndex = map.get(preorder[preLIndex]);
        TreeNode root = new TreeNode(preorder[preLIndex]);
        root.left = buildTree(preorder,preLIndex+1,preLIndex+pIndex-inLIndex,inorder,inLIndex,pIndex-1,map);
        root.right = buildTree(preorder,pIndex-inLIndex+preLIndex+1,preRIndex,inorder,pIndex+1,inRIndex,map);
        return root;
    }
}

5、

6、