剑指Offer系列之题1~题5
- 2020 年 4 月 11 日
- 筆記
写在前面：本随笔中包含五道题：题目描述，题目思路以及对应解法。
1.二维数组的查找
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
找到最大或最小值，然后以此为界，进行查找。
1、暴力解：
public class Solution { public boolean Find(int target, int [][] array) { int n=array[0].length; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(array[i][j]==target){ return true; } } } return false; } } 2、从左下开始比较：
public class Solution { public boolean Find(int target, int [][] array) { int rowLen=array[0].length;//列数 int colLen=array.length;//行数 //从左下角开始，大于则向右找，小于则向上 int j=0; for(int i=colLen-1;i>=0;i--){ if(j<rowLen){ if(target>array[i][j]){ j++; i++;//右移，i不变，该步抵消i-- }else if(target==array[i][j]){ return true; } } } return false; } } 2.替换空格
请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
重点是考虑边界问题，全为空格；末尾有空格等情况
1、遍历：
public class Solution { public String replaceSpace(StringBuffer str) { String demo=str.toString(); String temp=""; for(int i=0;i<demo.length();i++){ if(demo.charAt(i)==' '){ temp+="%20"; }else{ temp+=demo.charAt(i); } } return temp; } } 2、如果要求在原字符串上进行操作。则先计算新字符串的长度进行扩展。然后从后向前依次替换空格。
public class Solution { public String replaceSpace(StringBuffer str) { int spaceNum=0; //计算空格数量， for(int i=0;i<str.length();i++){ if(str.charAt(i)==' '){ spaceNum++; } } int indexOld=str.length()-1; str.setLength(str.length()+spaceNum*2); int indexNew=str.length();//扩容后长度 for(int i=indexNew-1;i>=0 && indexOld>=0;i--){//从末尾开始 if(str.charAt(indexOld)==' '){ str.setCharAt(i,'0'); str.setCharAt(i-1,'2'); str.setCharAt(i-2,'%'); i=i-2; indexOld--; }else{ str.setCharAt(i,str.charAt(indexOld)); indexOld--; } } return str.toString(); } } 3.从尾到头打印链表
输入一个链表，按链表从尾到头的顺序返回一个ArrayList。
暴力解或递归
1、暴力解：
import java.util.ArrayList; public class Solution { public ArrayList<Integer> printListFromTailToHead(ListNode listNode) { ArrayList<Integer> al=new ArrayList<Integer>(); if(listNode==null){//判空 return al; } al.add(listNode.val); while(listNode.next!=null){ listNode=listNode.next; al.add(listNode.val); } ArrayList<Integer> result=new ArrayList<Integer>(); for(int i=al.size()-1;i>=0;--i){ result.add(al.get(i)); } return result; } } //注：ArrayList的add(int index,E element)方法在添加时会将index处元素后移 2、递归：
import java.util.*; 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.链表中环的入口节点
给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。
先判断是否有环（快慢指针，相遇则有环），若有环，则令两个指针，一个从头节点，一个从相遇点分别开始走，再次相遇的点即环的入口节点。
1、双指针：
public ListNode EntryNodeOfLoop(ListNode pHead) { if(pHead==null||pHead.next==null){ return null; } //判断有无环 ListNode slow=pHead; ListNode fast=pHead; boolean flag=false; while(fast!=null&&fast.next!=null){ fast=fast.next.next; slow=slow.next; if(fast==slow){ flag=true; } break; } //两者相遇时循环结束，此时开始计算环中结点的数目 int count=0; while(fast.next!=slow){ count++; fast=fast.next; } count++;//环的节点数 ListNode fir=pHead; ListNode sec=pHead; for(int i=0;i<count;i++){ fir=fir.next; }//第一个指针走了count步 //两者开始一起走，相遇的点即入口点。第二个指针与入口点的距离=总结点数-环中的结点数 //因为第一个指针走了环中结点数，所以两者必在入口点相遇。第二个指针到达入口节点时第一个指针走了一圈到达入口结点。 while(fir!=sec){ fir=fir.next; sec=sec.next; } return fir; } 5.重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
一般情况下树的题目都可以考虑递归方法，找到递归的退出条件（本题即：前序和中序序列只剩下一个节点），在完成的基础上对代码进行优化。
1、递归：
/** * 递归解决 * 跳出条件是只剩下一个节点，返回赋值给上一个根节点的左或右子树 * @param pre * @param in * @return */ public TreeNode reConstructBinaryTree(int [] pre,int [] in) { //前序：根左右；中序：左根右 /*if(pre==null || in == null ){ return null; }*/ TreeNode root=new TreeNode(pre[0]);//根节点 if(pre.length==in.length && pre.length==1){//若前序和中序遍历都只剩下一个节点则返回该节点 return root; } int mid=0; //找到中序遍历中根节点的位置 for(int i=0;i<in.length;i++){ if(in[i]==root.val){ mid=i; } } int left=mid;//左子树的节点个数 int right=in.length-mid-1;//右子树的节点个数 //递归 if(left>0){ int leftpre[]=new int[left]; int leftin[]=new int[left]; for(int i=0;i<left;i++){ leftpre[i]=pre[i+1]; leftin[i]=in[i]; } root.left=reConstructBinaryTree(leftpre,leftin);//左子树的前序遍历和左子树的中序遍历 } if(right>0){ int rightpre[]=new int[right]; int rightin[]=new int[right]; for(int i=0;i<right;i++){ rightpre[i]=pre[i+1+left]; rightin[i]=in[i+left+1]; } root.right=reConstructBinaryTree(rightpre,rightin);//右子树的前序遍历和左子树的中序遍历 } return root; } 2、递归精简版：
public TreeNode reConstructBinaryTree1(int [] pre,int [] in) { TreeNode root=reConstructBinaryTree1(pre,0,pre.length-1,in,0,in.length-1); return root; } //前序遍历{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6} private TreeNode reConstructBinaryTree1(int [] pre,int startPre,int endPre,int [] in,int startIn,int endIn) { if(startPre>endPre||startIn>endIn) return null; TreeNode root=new TreeNode(pre[startPre]); for(int i=startIn;i<=endIn;i++) if(in[i]==pre[startPre]){ /*startPre+i-startIn是startPre+左子树的节点个数 得到前序序列的末尾位置*/ root.left=reConstructBinaryTree1(pre,startPre+1,startPre+i-startIn,in,startIn,i-1); root.right=reConstructBinaryTree1(pre,i-startIn+startPre+1,endPre,in,i+1,endIn); break; } return root; } 如有错误，欢迎指正
