天天看點
傳回

算法 | 一周刷完《劍指Offer》 Day2：第17~26題

寫在前面

  • 本系列包含《劍指Offer》66道算法題，預計一周刷完，這是第二篇。

    系列彙總：劍指Offer 66題 Java 刷題筆記彙總

  • 所有題目均可在牛客網線上程式設計平台進行調試。

    網址：https://www.nowcoder.com/ta/coding-interviews

  • 本系列包含題目，解題思路及代碼（Java）。

    代碼同步釋出在GitHub：https://github.com/JohnnyJYWu/offer-Java

上一篇：算法 | 一周刷完《劍指Offer》 Day1：第1~16題

下一篇：算法 | 一周刷完《劍指Offer》 Day3：第27~37題

Day2：第17~26題

今天的題涉及遞歸及二叉樹較多，需要深入了解其邏輯和原理。

  • T17. 樹的子結構
  • T18. 二叉樹的鏡像
  • T19. 順時針列印矩陣
  • T20. 包含 min 函數的棧
  • T21. 棧的壓入、彈出序列
  • T22. 從上往下列印二叉樹
  • T23. 二叉搜尋樹的後序周遊序列
  • T24. 二叉樹中和為某一值的路徑
  • T25. 複雜連結清單的複制
  • T26. 二叉搜尋樹與雙向連結清單

T17. 樹的子結構

題目描述

輸入兩棵二叉樹A，B，判斷B是不是A的子結構。（ps：我們約定空樹不是任意一個樹的子結構）

解題思路

設定終止條件進行判斷，将B樹與A樹，A樹左子樹，A樹右子樹進行比較，遞歸進行即可。

public boolean HasSubtree(TreeNode root1, TreeNode root2) {
		if(root1 == null || root2 == null) return false;
	    return isSubtree(root1, root2) //root2與root1比較
	    		|| HasSubtree(root1.left, root2) //root2與root1左子樹比較，遞歸邏輯
	    		|| HasSubtree(root1.right, root2); //root2與root1右比較，遞歸邏輯
	    //以上三種情況任一為true，即證明root2是root1的子結構
    }
	
	private boolean isSubtree(TreeNode root1, TreeNode root2) {
		//終止判定
		if(root1 == null && root2 == null) return true;//為null，能執行到此步且相同，為子結構
	    if(root1 == null) return false;//root1為null，root2不為null，不同，不為子結構
	    if(root2 == null) return true;//root1不為null，root2為null，能執行到此步說明相同，為子結構
	    if(root1.val != root2.val) return false;//root1，root2都不為null，val不同，不為子結構
	    
	    //能執行到此步，說明未判定完，繼續對root1，root2的左右子樹分别遞歸此方法進行判斷，均為true則為子結構
	    return isSubtree(root1.left, root2.left) && isSubtree(root1.right, root2.right);
	}

T18. 二叉樹的鏡像

題目描述

操作給定的二叉樹，将其變換為源二叉樹的鏡像。
算法 | 一周刷完《劍指Offer》 Day2：第17~26題

解題思路

交換每個結點的左右子樹，并對該結點的左右子結點分别進行此操作，遞歸進行即可。

public void Mirror(TreeNode root) {
        if(root == null) return;
        
        //交換左右子樹
        swap(root);
        //分别對root左右子樹進行交換，遞歸調用此方法即可
        Mirror(root.left);
        Mirror(root.right);
    }
	
	private void swap(TreeNode root) {
		TreeNode tmp = root.left;
		root.left = root.right;
		root.right = tmp;
	}

T19. 順時針列印矩陣

題目描述

輸入一個矩陣，按照從外向裡以順時針的順序依次列印出每一個數字，例如，如果輸入如下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.

解題思路

順時針繞圈列印即可，從外向裡每次循環繞一圈。

注意：一定細心，出錯基本都是馬虎造成的。

public ArrayList<Integer> printMatrix(int[][] matrix) {
		ArrayList<Integer> list = new ArrayList<>();
		
		if(matrix == null || matrix[0] == null) return list;
		
		int rowTop = 0, rowBottom = matrix.length - 1;
		int colLeft = 0, colRight = matrix[0].length - 1;
		
		while(colLeft <= colRight && rowTop <= rowBottom) {//跳出條件
			for(int i = colLeft; i <= colRight; i ++) {//添加上邊一行，從左到右
				list.add(matrix[rowTop][i]);
			}
			for(int i = rowTop + 1; i <= rowBottom; i ++) {//添加右邊一列，從上到下，注意去掉已添加的【右上角】。
				list.add(matrix[i][colRight]);
			}
			if(rowTop != rowBottom) {//若相等則已到同一行，無可繼續添加的
				for(int i = colRight - 1; i >= colLeft; i --) {//添加下邊一行，從右到左，注意去掉已添加的【右下角】。
					list.add(matrix[rowBottom][i]);
				}
			}
			if(colLeft != colRight) {//若相等則已到同一列，無可繼續添加的
				for(int i = rowBottom - 1; i > rowTop; i --) {//添加左邊一列，從下到上，注意去掉已添加的【左下角】及【左上角】。
					list.add(matrix[i][colLeft]);
				}
			}
			
			colLeft ++;
			colRight --;
			rowTop ++;
			rowBottom --;
		}
		
		return list;
    }

T20. 包含 min 函數的棧

題目描述

定義棧的資料結構，請在該類型中實作一個能夠得到棧中所含最小元素的min函數（時間複雜度應為O(1)）。

解題思路

定義兩個棧，stack存入棧的數，minStack存該數入棧後棧内的最小數min。

注意：兩個棧大小是相同的，同步入棧及出棧。即哪怕入棧的數不是最小的，也把那個最小的再入一次minStack。

private Stack<Integer> stack = new Stack<>();
	private int min = Integer.MAX_VALUE;
	//minStack用于存儲任一進制素入棧時，目前棧内的最小值，與stack是同步入棧出棧的，即兩個棧内元素數目相同
	private Stack<Integer> minStack = new Stack<>();
	
	public void push(int node) {
        stack.push(node);
        if(min > node) {
        	min = node;
        }
    	minStack.push(min);
    }
    
    public void pop() {
        stack.pop();
        minStack.pop();
        min = minStack.peek();
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int min() {
        return min;
    }

T21. 棧的壓入、彈出序列

題目描述

輸入兩個整數序列，第一個序清單示棧的壓入順序，請判斷第二個序列是否可能為該棧的彈出順序。假設壓入棧的所有數字均不相等。例如序列1,2,3,4,5是某棧的壓入順序，序列4,5,3,2,1是該壓棧序列對應的一個彈出序列，但4,3,5,1,2就不可能是該壓棧序列的彈出序列。（注意：這兩個序列的長度是相等的）

解題思路

建個棧，模拟出入棧順序即可。

注意：每次入棧後，要對出棧順序的數組進行檢測，循環把該出棧的出了，再進行下次入棧。

public boolean IsPopOrder(int[] pushA, int[] popA) {//pushA和popA長度相同
		//建個棧，模拟入棧出棧操作即可
		Stack<Integer> stack = new Stack<>();
		int popIndex = 0;
		
		for(int pushIndex = 0; pushIndex < pushA.length; pushIndex ++) {
			stack.push(pushA[pushIndex]);//按pushA順序入棧
	    	  
			while(popIndex < popA.length && popA[popIndex] == stack.peek()) {//相同說明可出棧，即模拟popA順序進行出棧操作
				stack.pop();
				popIndex ++;
			}
		}

		//若棧空，說明pushA入棧能按popA順序出棧
		return stack.isEmpty();
    }

T22. 從上往下列印二叉樹

題目描述

從上往下列印出二叉樹的每個結點，同層結點從左至右列印。

解題思路

二叉樹層輸出，使用**廣度優先搜尋(BFS)**即可。

使用隊列實作，邊出隊邊輸出，同時将其左右子結點壓入隊列。

public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
		ArrayList<Integer> list = new ArrayList<>();
		
		if(root == null) return list;
		
		//使用隊列實作，不斷按層壓入及輸出
		Queue<TreeNode> queue = new LinkedList<>();
		queue.add(root);
		
		while(!queue.isEmpty()) {
			TreeNode tmp = queue.poll();
			//先左後右按順序壓入子結點
			if(tmp.left != null) queue.add(tmp.left);
			if(tmp.right != null) queue.add(tmp.right);
			
			list.add(tmp.val);
		}
		
		return list;
    }

T23. 二叉搜尋樹的後序周遊序列

題目描述

輸入一個整數數組，判斷該數組是不是某二叉搜尋樹的後序周遊的結果。如果是則輸出Yes,否則輸出No。假設輸入的數組的任意兩個數字都互不相同。

解題思路

二叉搜尋樹： 若它的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；若它的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值；它的左、右子樹也分别為二叉搜尋樹（二叉排序樹）。

後序周遊：左 -> 右 -> 根。

是以，後序周遊最後一個數為根結點。通過根結點可把後序周遊分為兩部分，前半部分為小于根結點的左子樹，後半部分為大于根結點的右子樹。然後根據此原理，遞歸對左右子樹分别用此方法進行驗證即可。

public boolean VerifySquenceOfBST(int [] sequence) {
		if(sequence == null || sequence.length == 0) return false;
		
		return verify(sequence, 0, sequence.length - 1);
    }
	
	private boolean verify(int[] sequence, int first, int last) {
    	//終止條件
		if(first >= last) return true;
		
		int rootValue = sequence[last];//後序周遊的根結點為最後一個
		int index = first;
		
		while(sequence[index] <= rootValue && index < last) {//比根結點小的為左子樹，大的為右子樹
			index ++;
		}
		//此時sequence[index]是第一個比根結點大的值
		//可将sequence[0]~sequence[index-1]認為是左子樹，sequence[index]~sequence[last-1]認為是右子樹
		for(int i = index; i < last; i ++) {
			if(sequence[i] < rootValue) {//若右子樹中存在比根結點小的，則不是二叉搜尋樹
				return false;
			}
		}
		
		//此時分别對根結點的左右子樹進行疊代判斷，全部為true則是後序周遊
		return verify(sequence, first, index - 1)
				&& verify(sequence, index, last - 1);//last為根結點
    }

T24. 二叉樹中和為某一值的路徑

題目描述

輸入一顆二叉樹的跟結點和一個整數，列印出二叉樹中結點值的和為輸入整數的所有路徑。路徑定義為從樹的根結點開始往下一直到葉結點所經過的結點形成一條路徑。(注意: 在傳回值的list中，數組長度大的數組靠前)

解題思路

深度優先搜尋(DFS)，通過減法的思想不斷用target減去目前結點值，能減為0則是一條路徑。

注意：路徑要求最後到達葉子結點。

疊代過程中需把目前值在path中移除以保證路徑正确，相當于回退到上一步的路徑。（詳見代碼）

private ArrayList<ArrayList<Integer>> result = new ArrayList<>();
	
	public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
        if(root == null) return result;
        
        ArrayList<Integer> path = new ArrayList<>();
        findPathDFS(root, target, path);
        
		return result;
    }
	
	private void findPathDFS(TreeNode node, int target, ArrayList<Integer> path) {
		if(node == null) return;
		
		path.add(node.val);
		target -= node.val;//減法的思想，目标值能減為0則是一條路徑
		if(target == 0 && node.left == null && node.right == null) {//已經到達葉子結點且targe正好減完
			result.add(new ArrayList<Integer>(path));
		} else if(target > 0) {//若>0則繼續對其左右子結點進行疊代判斷
			findPathDFS(node.left, target, path);
			findPathDFS(node.right, target, path);
		}
		
		path.remove(path.size() - 1);//此步重要，疊代過程中需把目前值在path中移除以保證路徑正确，相當于回退到上一步的路徑
	}

T25. 複雜連結清單的複制

題目描述

輸入一個複雜連結清單（每個結點中有結點值，以及兩個指針，一個指向下一個結點，另一個特殊指針指向任意一個結點），傳回結果為複制後複雜連結清單的head。（注意，輸出結果中請不要傳回參數中的結點引用，否則判題程式會直接傳回空）

解題思路

算法 | 一周刷完《劍指Offer》 Day2：第17~26題

step1：在每個結點的後面（或者說每個結點與下一個結點中間）插入新結點。該新結點為克隆結點，這麼做是為了連接配接random結點。

step2：連接配接random結點。

step3：拆分連結清單，下邊為原連結清單，上邊為clone連結清單。

public RandomListNode Clone(RandomListNode pHead) {
		if(pHead == null) return null;
		
		//step1：在每個結點的後面（或者說每個結點與下一個結點中間）插入【新結點】
		//該新結點為克隆結點，這麼做是為了連接配接random結點
		RandomListNode tmp = pHead;
		while(tmp != null) {
			RandomListNode cloneNode = new RandomListNode(tmp.label);
			
			//插入clone結點
			cloneNode.next = tmp.next;
			tmp.next = cloneNode;
			//移到原連結清單的下一個結點
			tmp = cloneNode.next;
		}
		
		//step2：連接配接random結點
		tmp = pHead;
		while(tmp != null) {
			RandomListNode cloneNode = tmp.next;
			if(tmp.random != null) {
				cloneNode.random = tmp.random.next;//tmp.random是原連結清單的結點，tmp.random.next才是那個結點的clone結點
			}
			tmp = cloneNode.next;
		}
		
		//step3：拆分連結清單（詳見圖檔）
		tmp = pHead;
		RandomListNode cloneHead = tmp.next;
		while(tmp.next != null) {
			RandomListNode node = tmp.next;
			tmp.next = node.next;
			tmp = node;
		}
		
		return cloneHead;
    }

T26. 二叉搜尋樹與雙向連結清單

題目描述

輸入一棵二叉搜尋樹，将該二叉搜尋樹轉換成一個排序的雙向連結清單。要求不能建立任何新的結點，隻能調整樹中結點指針的指向。

解題思路

由于二叉搜尋樹左子結點 < 根結點 < 右子結點的性質，題目實質上是二叉搜尋樹的中序周遊，改結點的指針。left代表雙向連結清單的prev指針，right代表next指針。

private TreeNode pre = null;//用于記錄上一個結點
	private TreeNode head = null;
	
	public TreeNode Convert(TreeNode pRootOfTree) {
		if(pRootOfTree == null) return null;
		
		inOrder(pRootOfTree);
		
		return head;
    }
	
	private void inOrder(TreeNode node) {
		if(node == null) return;
		
		//實質上是中序周遊，改結點的指針。left代表雙向連結清單的prev指針，right代表next
		//左
		inOrder(node.left);
		
		//根
		//改指針的指向（隻需與上一個結點相連即可）
		node.left = pre;//連上一個
		if(pre != null) {//如果上一個不為null，連此時這個
			pre.right = node;
		}
		pre = node;//将pre移向此時這個結點，為下一次疊代做準備
		
		if(head == null) head = node;//隻在第一次找到最小結點時作為頭結點
		
		//右
		inOrder(node.right);
	}

項目位址：https://github.com/JohnnyJYWu/offer-Java

上一篇：算法 | 一周刷完《劍指Offer》 Day1：第1~16題

下一篇：算法 | 一周刷完《劍指Offer》 Day3：第27~37題

希望這篇文章對你有幫助~

劍指offer java 校招 算法
上一篇: 劍指offer java day17 排序
下一篇: java簡單題目day2

繼續閱讀