JZ21 堆疊的壓入、彈出序列(堆疊)
題目描述
輸入兩個整數序列，第一個序串列示堆疊的壓入順序，請判斷第二個序列是否可能為該堆疊的彈出順序，假設壓入堆疊的所有數字均不相等，例如序列1,2,3,4,5是某堆疊的壓入順序，序列4,5,3,2,1是該壓堆疊序列對應的一個彈出序列，但4,3,5,1,2就不可能是該壓堆疊序列的彈出序列，（注意：這兩個序列的長度是相等的）
解
模擬堆疊的壓入和彈出程序即可，按照入堆疊順序逐個壓入元素，如果當前堆疊頂元素與出堆疊順序的當前元素相等，則將堆疊中元素出堆疊，若最終能得到空堆疊，則出堆疊順序正確，否則可以判斷該順序不是一個正確的出堆疊順序，
import java.util.*;
public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
// 樸素模擬？
Stack<Integer> s = new Stack<>();
int i = 0, j = 0, n = pushA.length;
boolean flag = true;
while(i < n && j < n) {
if(s.isEmpty()) {
s.push(pushA[i]);
i++;
} else if(s.peek() == popA[j]) {
s.pop();
j++;
} else {
s.push(pushA[i]);
i++;
}
}
// 堆疊內剩下的元素如果不能匹配則說明這不是一個彈出序列
while(!s.isEmpty()) {
if(s.pop() != popA[j]) {
flag = false;
break;
}
j++;
}
return flag;
}
}
JZ22 從上往下列印二叉樹(樹，佇列)
題目描述
從上往下列印出二叉樹的每個節點，同層節點從左至右列印，
解
樹的層次遍歷法
import java.util.ArrayList;
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
// 層次遍歷
ArrayList<Integer> res = new ArrayList<>();
ArrayList<TreeNode> q = new ArrayList<>();
// ArrayList的remove(0)的時間復雜度是？
int head = -1;
if(root == null)
return res;
q.add(root);
TreeNode p = null;
while(head < q.size() - 1) {
p = q.get(++head);
res.add(p.val);
if(p.left != null)
q.add(p.left);
if(p.right != null)
q.add(p.right);
}
return res;
}
}
JZ23 二叉搜索樹的后序遍歷序列(樹，堆疊)
題目描述
輸入一個整數陣列，判斷該陣列是不是某二叉搜索樹的后序遍歷的結果，如果是則回傳true,否則回傳false，假設輸入的陣列的任意兩個數字都互不相同，
解
對于一個二叉搜索樹而言，當前節點的左子樹所有節點值都比當前節點值小，當前節點的右子樹所有節點值都比當前節點大，而根據“左-右-根”的遍歷順序，后序遍歷序列的前一部分為左子樹，中間一部分為右子樹，最后一個元素為根，前一部分的所有值都比最后一個元素小，后一部分的所有值都比最后一個元素大，而序列的左子樹部分和右子樹部分也滿足上述定義，可以看出這是一個遞回的定義，可以使用遞回方法和非遞回方法完成此題，
遞回做法
public class Solution {
public boolean VerifySquenceOfBST(int [] sequence) {
if(sequence.length <= 0)
return false;
return verify(sequence, 0, sequence.length - 1);
}
public boolean verify(int [] seq, int min, int max) {
if(min >= max)
return true;
int mid = 0;
int pivot = seq[max], i = min;
while(seq[i] < pivot) {
i++;
}
mid = i;
while(i < max) {
if(seq[i] < pivot) {
return false;
}
i++;
}
return verify(seq, min, mid - 1) && verify(seq, mid, max - 1);
}
}
非遞回做法
import java.util.*;
public class Solution {
public boolean VerifySquenceOfBST(int [] sequence) {
if(sequence.length <= 0)
return false;
Stack<Integer> s = new Stack<>();
s.push(0);
s.push(sequence.length - 1);
while(!s.isEmpty()) {
int max = s.pop(), min = s.pop();
int pivot = sequence[max], i = min, mid = min;
while(sequence[i] < pivot && i < max)
i++;
mid = i;
while(i < max) {
if(sequence[i] < pivot) {
return false;
}
i++;
}
if(min < mid - 1) {
s.push(min);
s.push(mid - 1);
}
if(mid < max - 1) {
s.push(mid);
s.push(max - 1);
}
}
return true;
}
}
需要注意的是，想要利用中序序列和后序序列之間的關系來完成本題是不正確的（雖然可以通過牛客的用例），以中序序列為入堆疊順序進行入堆疊的話，若某一序列是該樹的后序序列，那么這一序列屬于一種出堆疊序列，但是若某一序列是一種以中序序列為入堆疊順序的出堆疊序列，那么這一序列不一定是樹的后序序列，
JZ24 二叉樹中和為某一值的路徑(樹，DFS)
題目描述
輸入一顆二叉樹的根節點和一個整數，按字典序列印出二叉樹中結點值的和為輸入整數的所有路徑，路徑定義為從樹的根結點開始往下一直到葉結點所經過的結點形成一條路徑，
解
遞回地遍歷整棵樹，并用全域變數記錄根節點到當前節點的路徑，遇到葉子節點時判斷路徑上所有節點值之和是否為目標值，如果是，將當前的路徑資訊深拷貝后插入到結果集合中，如果使用非遞回演算法，需要對樹進行后序遍歷，
import java.util.ArrayList;
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> path = new ArrayList<>();
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
if(root == null) return res;
path.add(root.val);
if(root.left == null && root.right == null && target - root.val == 0) {
res.add(new ArrayList<Integer>(path));
}
FindPath(root.left, target - root.val);
FindPath(root.right, target - root.val);
// 回收當前節點
path.remove(path.size() - 1);
return res;
}
}
JZ25 復雜鏈表的復制(鏈表)
題目描述
輸入一個復雜鏈表（每個節點中有節點值，以及兩個指標，一個指向下一個節點，另一個特殊指標random指向一個隨機節點），請對此鏈表進行深拷貝，并回傳拷貝后的頭結點，（注意，輸出結果中請不要回傳引數中的節點參考，否則判題程式會直接回傳空）
解
3種解法，個人先想出的第一種，仔細想了想想出第二種，第三種是參考了牛客上的解法，
解1 暴力
先不處理特殊指標，使用next指標復制鏈表的所有節點，然后在原鏈表中為每一個節點使用next指標定位每一個隨機指標的指向，新鏈表和原鏈表的查找指標保持同步，找到后將隨機指標的指向同步反映到新鏈表中：如果原鏈表中第i個節點的隨機指標指向第j個節點，新鏈表的第i個節點的隨機指標也指向新鏈表的第j個節點，時間復雜度為\(O(n^2)\)
/*
public class RandomListNode {
int label;
RandomListNode next = null;
RandomListNode random = null;
RandomListNode(int label) {
this.label = label;
}
}
*/
public class Solution {
public RandomListNode Clone(RandomListNode pHead)
{
// 先不處理特殊指標
RandomListNode res = new RandomListNode(-1), p = pHead, q = res, r = null, s = null;
while(p != null) {
q.next = new RandomListNode(p.label);
q = q.next;
p = p.next;
}
// 暴力一點的話，時間復雜度就便乘了n^2: 在原鏈表中暴力尋找隨機指標的指向，同步反應到新鏈表中
res = res.next;
r = pHead;
s = res;
while(r != null) {
p = pHead;
q = res;
while(p != r.random) {
p = p.next;
q = q.next;
}
s.random = q;
s = s.next;
r = r.next;
}
return res;
}
}
解2 用HashMap儲存原鏈表節點和新鏈表節點的映射關系
解1為了在新鏈表中還原隨機指標，要在新鏈表中為每一個節點查找隨機指標的指向，而每次查找都要遍歷一遍整個鏈表，解2為了優化還原隨機指標的程序，在解1使用next指標復制鏈表節點時，使用HashMap保存了原鏈表節點和新鏈表節點的映射關系，這樣在新鏈表上還原第i個節點的隨機指標時，只需要找到原鏈表上第i個節點的random所指向的節點A，再通過HashMap就可以找到與節點A所對應的新鏈表節點A'，讓新鏈表上第i個節點指向A'即還原了新鏈表第i個節點的隨機指標，時間復雜度為\(O(n)\)，需要\(O(n)\)的輔助存盤空間，
/*
public class RandomListNode {
int label;
RandomListNode next = null;
RandomListNode random = null;
RandomListNode(int label) {
this.label = label;
}
}
*/
import java.util.*;
public class Solution {
public RandomListNode Clone(RandomListNode pHead)
{
// 先不處理隨機指標, 但是建立舊鏈表和新鏈表的映射關系，后續利用映射關系建表，需要使用輔助空間，復雜度為O(n)
// 時間復雜度為O(n)
RandomListNode res = new RandomListNode(-1), p = pHead, q = res, r = null, s = null;
HashMap<RandomListNode, RandomListNode> m = new HashMap<>();
while(p != null) {
q.next = new RandomListNode(p.label);
q = q.next;
m.put(p, q);
p = p.next;
}
// 使用HashMap重建隨機指標
res = res.next;
q = res;
p = pHead;
while(q != null) {
if(p.random != null) {
q.random = m.get(p.random);
}
q = q.next;
p = p.next;
}
return res;
}
}
解3 先原地復制復雜鏈表的節點，再進行拆分
首先將原鏈表的每個節點復制，將復制后的節點插入到原節點的后面，根據原鏈表節點p的隨機指標還原復制節點q的隨機指標：q.random = p.random.next（復制節點是原節點的后繼節點），最后將兩個鏈表進行拆分即可，時間復雜度為\(O(n)\)，并且輔助存盤空間復雜度為\(O(1)\)，
/*
public class RandomListNode {
int label;
RandomListNode next = null;
RandomListNode random = null;
RandomListNode(int label) {
this.label = label;
}
}
*/
import java.util.*;
public class Solution {
public RandomListNode Clone(RandomListNode pHead)
{
// 先原地復制復雜鏈表的每個節點，將復制后的節點插入到原節點后面
// 然后根據原鏈表在復制節點上還原隨機指標的指向關系
// 最后拆分
// 額外的存盤空間復雜度為O(1)，時間復雜度為O(n)
if(pHead == null) return null;
RandomListNode res = new RandomListNode(-1), p = pHead, q = null;
while(p != null) {
q = new RandomListNode(p.label);
q.next = p.next;
p.next = q;
p = q.next;
}
p = pHead;
while(p != null) {
q = p.next;
if(p.random != null)
q.random = p.random.next;
p = q.next;
}
p = pHead;
q = res;
// 注意：要將復制后的節點從原鏈表中解開（原鏈表不能有指標指向復制節點），否則會被判空
while(p != null) {
q.next = p.next;
p.next = (p.next).next;
q = q.next;
p = p.next;
}
return res.next;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/25937.html
標籤：其他