剑指Offer系列之题16~题20
- 2020 年 4 月 12 日
- 筆記
16.反转链表
输入一个链表，反转链表后，输出新链表的表头。
从前往后，依次将当前节点的next指向前结点。用多个变量存储当前节点，下一节点，前结点。
public class Solution { public ListNode ReverseList(ListNode head) { if(head==null) return null; //从头开始，依次将节点的next指向前一个结点 ListNode prev=null; ListNode cur=head; ListNode follow=null; while(cur.next!=null){ follow=cur.next;//获得当前结点的下个节点 cur.next=prev;//将当前节点的next指向前一个结点 prev=cur;//保存当前结点作为前结点 cur=follow; } cur.next=prev; return cur; } } 17.合并两个排序的链表
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
基本：遍历两链表，当l2中元素小于l1时，将其加入l1，直到末尾。或者新建一个链表，将小的依次加入该链表
1.暴力：
/*添加至list1*/ public class Solution { public ListNode Merge(ListNode list1,ListNode list2) { //结果要求是单调递增 //错误输入的判断 if(list1==null && list2 ==null) return null; if(list1== null) return list2; if(list2==null) return list1; ListNode p1=list1; ListNode p2=list2; ListNode temp1=null;//暂存两链表的结点 ListNode temp2=null; //依次从链表头开始判断 while(p1!=null && p2!=null ){ while(p1!=null && p1.val<p2.val){//当l1的结点小于l2时，将l1结点右移 temp1=p1;//记录当前结点，便于后续插入 p1=p1.next; }//直到p1.val >= p2.val或p1.next==null if(p1==null){//若l1已到末尾，则将l2的结点接到l1末尾后 temp1.next=p2; return list1; } temp2=new ListNode(p2.val);//list2的结点移到list1 temp2.next=p1; if(temp1!=null)//判断是否是添加到l1的头部 temp1.next=temp2; else{//是则让list1头节点变为temp2 list1=temp2; } p1=temp2;//该结点一定比l2的下一节点小，所以temp1下一步一定会切换 if(p2.next==null)//如果l2遍历完毕 break; p2=p2.next;//p2右移 } return list1; } } 2.递归：
/*相当于一个新链表*/ public class Solution { public ListNode Merge(ListNode list1,ListNode list2) { //结果要求是单调递增 //错误输入的判断 if(list1==null && list2 ==null) return null; if(list1== null) return list2; if(list2==null) return list1; //递归 if(list1.val <=list2.val){ list1.next=Merge(list1.next,list2); return list1; }else{ list2.next=Merge(list1,list2.next); return list2; } } } 3.新建链表存储：
public class Solution { public ListNode Merge(ListNode list1,ListNode list2) { //新建一个头节点，用来存合并的链表。 ListNode head=new ListNode(-1); head.next=null; ListNode root=head; while(list1!=null && list2!=null){ if(list1.val<list2.val){ head.next=list1; head=list1; list1=list1.next; }else{ head.next=list2; head=list2; list2=list2.next; } } //把未结束的链表连接到合并后的链表尾部 if(list1!=null){ head.next=list1; } if(list2!=null){ head.next=list2; } return root.next; } } 18.树的子结构 ?
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
先判断A中根节点是否等于B根节点，相等则对两者左右子树进行遍历判断是否相等；
若根节点不等，则从A的左右子树中寻找等于B中根节点的节点，然后判断。
递归
递归：
public class Solution { public boolean HasSubtree(TreeNode root1,TreeNode root2) { if(root1 ==null || root2 == null)//输入判断 return false; boolean flag=false; //查看2的前序和中序遍历是否属于1 if (root1.val == root2.val){//当A的根结点等于B的根节点时，对其子树进行遍历判断（递归） flag=judgeSub(root1,root2); } if(!flag)//当A的根节点不等于B的根节点时，从根节点的左子树中查找相等的节点 flag=HasSubtree(root1.left,root2); if(!flag)//从根节点的右子树中查找相等的节点 flag=HasSubtree(root1.right,root2); return flag; } //根节点相等时，判断其结构是否相等 public boolean judgeSub(TreeNode root1,TreeNode root2){ if(root2==null)//若B节点为空，则证明该节点前结构属于A，因为前面的已证过相等，不然不会走到该步 return true; if(root1==null)//若A节点为空，则两者结构不等 return false; if(root1.val != root2.val) return false; return judgeSub(root1.left,root2.left) && judgeSub(root1.right,root2.right);//递归判断左右子树是否相等 } } 19.二叉树的镜像
操作给定的二叉树，将其变换为源二叉树的镜像。
输入描述：
二叉树的镜像定义： 源二叉树 8 / 6 10 / / 5 7 9 11 镜像二叉树 8 / 10 6 / / 11 9 7 5 递归处理左右子树
递归：
public class Solution { public void Mirror(TreeNode root) { if(root!=null){ //根节点不变，左右子树交换位置 //递归 if(root.left!=null ){//若根节点左右子树非空，则将左右子树进行翻转 Mirror(root.left); } if(root.right!=null) Mirror(root.right); TreeNode temp=root.left; root.left=root.right; root.right=temp; } } } 20.顺时针打印矩阵
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10。
找到每次遍历的起始点，然后以此进行判断每次遍历的边界。（每次遍历前一定要判断前置条件）
1.暴力：
import java.util.ArrayList; public class Solution { private ArrayList<Integer> result=new ArrayList<>(); public ArrayList<Integer> printMatrix(int [][] matrix) { if(matrix==null || matrix.length==0) return null; int rows=matrix.length; int cols=matrix[0].length; int start=0; //找出每一圈的起始点。即左上角的点，(0,0) (1,1)等 while(rows>start*2 && cols>start*2){ int endCol=cols-1-start;//该次遍历时最右边列的坐标 int endRow=rows-1-start;//该次遍历时最下边行的坐标 for(int i=start;i<=endCol;++i){//打印第一行 result.add(matrix[start][i]); } if(start<endRow){//满足才有一列可以打印，否则一行直接打印完毕 for(int i=start+1;i<=endRow;++i){//打印最后一列 result.add(matrix[i][endCol]); } } if(start<endCol && start<endRow){//满足才有最后一行可以打印 for(int i=endCol-1;i>=start;--i){//打印最后一行 result.add(matrix[endRow][i]); } } if(start<endCol && start< endRow-1){//满足时才会在最后一行打印完毕后仍有上面的行 for(int i=endRow-1;i>start;--i){//打印第一列 result.add(matrix[i][start]); } } start++; } return result; } } 如有错误，欢迎指正
