剑指offer刷题记录——Java学习实战（更新版记录）

1.题目描述

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

解题思路：

              1.外循环遍历每行元素
               2.如果每行第一个元素target，在该行找
               否则，退出该行，continue
               3.确定元素所在行后，查找该元素

简单做法是暴力遍历所有元素，但加一个判断语句会跳过不必要的查询比较。

public class Solution {
    public static void main(String[] args) {
        int arr[][]=new int[][]{{1,2,3},{2,4,6},{3,8,10},{4,9,12},{5,10,13}};
        int target=10;
        boolean t = Find(target, arr);
        System.out.println("查询结果为："+t);
    }

    public static boolean Find(int target, int array[][])
    {
        /*思路：1.外循环遍历每行元素
               2.如果每行第一个元素target，在该行找
               否则，退出该行，continue
               3.确定元素所在行后，查找该元素*/
      for(int i=0;i< array.length;i++)
          for(int j=0;j=target)
              {
                  if(array[i][j]==target)
                  {
                      return true;
                  }
              }
              else
                  continue;
          }
        //最后一个元素都没能找到

        return false;
    }

}

2.题目描述

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

        /*思路：
        1.找到首次出现" "的下标位置
        2.将该下标的元素进行替换
        3.下标位置+1，从新的下标开始往后找首次出现" "的位置*/

public class Solution {
    public static String replaceSpace(StringBuffer str) {
        //这题考察的是stringBuffer和string的相互转换
        /*思路：
        1.找到首次出现" "的下标位置
        2.将该下标的元素进行替换
        3.下标位置+1，从新的下标开始往后找首次出现" "的位置*/
        int ind = str.indexOf(" ");
        while (ind <= str.length()) {
            if (str.indexOf(" ") >= 0)
            //System.out.println("存在空字符串");
            {
                str = str.replace(ind, ind + 1, "%20");
                int ind2 = ind + 2;
                ind = str.indexOf(" ", ind2);
            } 
            else
                break;
        }
        return str.toString();
    }


    public static void main(String args[])
    {
        //创建一个string变量，转为stringBuffer，带入方法中，将返回值转为sting类型
        String str="We Are Happy!";
        StringBuffer str2=new StringBuffer();
        str2.append(str);
        str=replaceSpace(str2);
        System.out.println("新的字符串为："+str);
    }
}

 这个简单的题让我整复杂了，我用的是StringBuffer里的替换字符串方法需要传递三个参数，实际上调用str.toString()方法将StringBuffer类对象转为String类，在调用String类的replaceAll(" ","%20")方法即可。

本题考察的是String类不能直接赋值给StringBuffer类

3.题目描述：输入一个链表，按链表从尾到头的顺序返回一个ArrayList。

解题思路：
1.获取链表的长度
2.创建数组list依次存放这些元素
3.创建数组list1，将list数组反过来存放在list1数组中

这里它默认为你创建了ListNode类

public class ListNode{
    int val;
    ListNode next =null;
    ListNode(int val){
        this.val=val;
    }
}//相当于C语言的结构体

代码如下：带测试用例

/**
 *    public class ListNode {
 *        int val;
 *        ListNode next = null;
 *
 *        ListNode(int val) {
 *            this.val = val;
 *        }
 *    }
 *
 */
import java.util.ArrayList;
public class Solution {
    /*解题思路：
1.获取链表的长度
2.创建数组list依次存放这些元素
3.创建数组list1，将list数组反过来存放在list1数组中*/
    public static ArrayList printListFromTailToHead(ListNode listNode) {
        ListNode head=new ListNode(0);//头指针
        ArrayList list=new ArrayList();
        ArrayList list1=new ArrayList();
        head.next=listNode;
        int len=0;
        while(head.next!=null){
            list.add(len,head.next.val);
            len++;
            head=head.next;
        }
        for (int i=0;i

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

}

public class Solution {
    public static TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        if ((pre.length == 0) || (in.length == 0)) {
            return null;
        }
        TreeNode root = reConstructBinaryTreeCore(pre, in, 0, pre.length - 1, 0, in.length - 1);//调用Core方法真正实现二叉树重建
        return root;
    }
    public static TreeNode reConstructBinaryTreeCore(int[] pre, int[] in, int startPre, int endPre, int startIn, int endIn)
     {
           if(startPre>endPre||startIn>endIn)
           {
                return null;//设置终止条件，搜索开始点和结束点重合为止
            }
            //根据前序遍历数组首元素在中序遍历中找到，并记住步数
            TreeNode node=new TreeNode(pre[startPre]);
            int count=0;
            for(int i=startIn;i<=endIn;i++)
            {

                if(in[i]==pre[startPre])
                {
                    count = i - startIn;
                    break;
                }
            }
            
//用count做间隔比较容易理解，左子树的前序遍历的起始点为startPre+1,终止点为startPre+count
//count表示中序遍历找到当前根节点用的步数            node.left=reConstructBinaryTreeCore(pre,in,startPre+1,startPre+count,startIn,startIn+count-1);
            node.right=reConstructBinaryTreeCore(pre,in,startPre+count+1,endPre,startIn+count+1,endIn);
            return node;
     }
     public static void main(String[] args) {//主方法测试
        int[] pre=new int[] {1,2,4,7,3,5,6,8};
        int[] in=new int[] {4,7,2,1,5,3,8,6};
        TreeNode root=reConstructBinaryTree(pre,in);
        
    }

}