劍指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; } } 如有錯誤，歡迎指正
