剑指offer第一天

2019-02-27 11:53:05来源：博客园阅读 ()

二维数组中的查找

数组-二分查找

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

public boolean Find(int target, int [][] array) {
            //思路：行遍历，对列做二分查找
 
            int i=0;
            while(i<=array.length-1){
                int left=0;
                int right=array[0].length-1;
                int temp=(left+right)/2;
                while(temp>=left&&temp<=right){
                    if(target<array[i][temp]){
                        right=temp-1;
                    }else if(target>array[i][temp]){
                        left=temp+1;
                    }else if(target==array[i][temp]){
                        return true;
                    }
                    temp=(left+right)/2;
                }
                i++;
            }
            return false;  

替换空格

字符串处理

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

public String replaceSpace(StringBuffer str) {
            //使用String类的replaceAll方法
            return str.toString().replaceAll(" ", "%20");
           //手写思路，首先遍历获取空格数目，然后从后往前插入%20
           
    }

从尾到头打印链表

单链表逆置-栈的应用

输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。

/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
//利用栈的性质
//先把listNode存进栈中，再从栈存入ArrayList
 
import java.util.Stack;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> arrayList=new ArrayList<>();
            Stack<Integer> at=new Stack<>();
            
           ListNode p=listNode;
           while(p!=null){
              at.push(p.val);
              p=p.next;
           }
           while(!at.isEmpty()){
               arrayList.add(at.pop());
           }
           return arrayList;
    }
}

重建二叉树

二叉树重建-递归

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{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 = fun(pre,0,pre.length - 1,in,0,in.length - 1);
        return root;
        
    }
        //preLeft和preRight为pre的首尾指针
       public static TreeNode fun(int[] pre,int preLeft,int preRight,int[] in,int inLeft,int inRight){
                //如果首尾指针反向则返回
               if(preLeft>preRight||inLeft>inRight){
                    return null;
                }
               //构造节点，按前序传值
                TreeNode treeNode=new TreeNode(pre[preLeft]);
                treeNode.left=null;
                treeNode.right=null;
               //找中序位置，建立父与左右子的连接
                for(int i=0;i<=inRight;i++){
                    //根据先序从前往后找到中序相同值的位置i
                    if(pre[preLeft]==in[i]){
                        //加入左子树，移动首尾指针，pre尾移到，指针in的尾指针到i前面一位
                        //pre的尾指针注意要左移（inleft-i）个位置
                        treeNode.left= fun(pre,preLeft + 1,preRight + i - inLeft,in,inLeft,i - 1);
                      //左边首指针注意右移i-inleft+1个位置
                        treeNode.right= fun(pre,preLeft+ i - inLeft + 1,preRight,in,i + 1,inRight);
                    }
                }
                return treeNode;
    }
}