二叉樹的鋸齒形層序遍歷（樹、廣度優(yōu)先搜索）

給定一個二叉樹，返回其節(jié)點值的鋸齒形層序遍歷。（即先從左往右，再從右往左進行下一層遍歷，以此類推，層與層之間交替進行）。
例如：
給定二叉樹 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回鋸齒形層序遍歷如下：
[ [3], [20,9], [15,7] ]

解答：

public class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) {val = x;}
}
class Solution {public List<List<Integer>> zigzagLevelOrder(TreeNode root) {List<List<Integer>> list = new LinkedList<>();if (root == null) {return list;}Stack<TreeNode> stack1 = new Stack<>();stack1.push(root);boolean postive = true;while (!stack1.isEmpty()) {Stack<TreeNode> stack2 = new Stack<>();List<Integer> subList = new LinkedList<>();while (!stack1.isEmpty()) {TreeNode current = stack1.pop();subList.add(current.val);if (postive) {if (current.left != null) {stack2.push(current.left);}if (current.right != null) {stack2.push(current.right);}} else {if (current.right != null) {stack2.push(current.right);}if (current.left != null) {stack2.push(current.left);}}}postive = !postive;stack1 = stack2;list.add(subList);}return list;}
}

用棧實現(xiàn)隊列（棧、設(shè)計）

請你僅使用兩個棧實現(xiàn)先入先出隊列。隊列應(yīng)當(dāng)支持一般隊列支持的所有操作（push、pop、peek、empty）：
實現(xiàn) MyQueue 類：

• void push(int x) 將元素 x 推到隊列的末尾
• int pop() 從隊列的開頭移除并返回元素
• int peek() 返回隊列開頭的元素
• boolean empty() 如果隊列為空，返回 true ；否則，返回 false

說明：

• 你只能使用標(biāo)準(zhǔn)的棧操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
• 你所使用的語言也許不支持棧。你可以使用 list 或者 deque（雙端隊列）來模擬一個棧，只要是標(biāo)準(zhǔn)的棧操作即可。

進階：

• 你能否實現(xiàn)每個操作均攤時間復(fù)雜度為 O(1) 的隊列？換句話說，執(zhí)行 n 個操作的總時間復(fù)雜度為 O(n) ，即使其中一個操作可能花費較長時間。

示例：

輸入： ["MyQueue", "push", "push", "peek", "pop", "empty"] [[], [1], [2], [], [], []] 輸出： [null, null, null, 1, 1, false] 
解釋： MyQueue myQueue = new MyQueue(); myQueue.push(1); // queue is: [1] myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue) myQueue.peek(); // return 1 myQueue.pop(); // return 1, queue is [2] myQueue.empty(); // return false

提示：

• 1 <= x <= 9
• 最多調(diào)用 100 次 push、pop、peek 和 empty
• 假設(shè)所有操作都是有效的 （例如，一個空的隊列不會調(diào)用 pop 或者 peek 操作）

解答：

class MyQueue {Stack<Integer> s1;Stack<Integer> s2;/** Initialize your data structure here. */public MyQueue() {s1 = new Stack<Integer>();s2 = new Stack<Integer>();}/** Push element x to the back of queue. */public void push(int x) {while (!s1.empty())s2.push(s1.pop());s1.push(x);while (!s2.empty())s1.push(s2.pop());return;}/** Removes the element from in front of queue and returns that element. */public int pop() {return s1.pop();}/** Get the front element. */public int peek() {int ret = s1.pop();s1.push(ret);return ret;}/** Returns whether the queue is empty. */public boolean empty() {return s1.empty();}
}
/*** Your MyQueue object will be instantiated and called as such:* MyQueue obj = new MyQueue();* obj.push(x);* int param_2 = obj.pop();* int param_3 = obj.peek();* boolean param_4 = obj.empty();*/

買賣股票的最佳時機 IV（數(shù)組、動態(tài)規(guī)劃）

給定一個整數(shù)數(shù)組 prices ，它的第_ i 個元素 prices[i] 是一支給定的股票在第 i _天的價格。
設(shè)計一個算法來計算你所能獲取的最大利潤。你最多可以完成 k 筆交易。
**注意：**你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。

示例 1：
輸入：k = 2, prices = [2,4,1] 輸出：2 解釋：在第 1 天 (股票價格 = 2) 的時候買入，在第 2 天 (股票價格 = 4) 的時候賣出，這筆交易所能獲得利潤 = 4-2 = 2 。
示例 2：
輸入：k = 2, prices = [3,2,6,5,0,3] 輸出：7 解釋：在第 2 天 (股票價格 = 2) 的時候買入，在第 3 天 (股票價格 = 6) 的時候賣出, 這筆交易所能獲得利潤 = 6-2 = 4 。 隨后，在第 5 天 (股票價格 = 0) 的時候買入，在第 6 天 (股票價格 = 3) 的時候賣出, 這筆交易所能獲得利潤 = 3-0 = 3 。

提示：

• 0 <= k <= 100
• 0 <= prices.length <= 1000
• 0 <= prices[i] <= 1000

解答：

class Solution {public int maxProfit(int k, int[] prices) {if (k < 1)return 0;if (k >= prices.length / 2)return greedy(prices);int[][] t = new int[k][2];for (int i = 0; i < k; ++i)t[i][0] = Integer.MIN_VALUE;for (int p : prices) {t[0][0] = Math.max(t[0][0], -p);t[0][1] = Math.max(t[0][1], t[0][0] + p);for (int i = 1; i < k; ++i) {t[i][0] = Math.max(t[i][0], t[i - 1][1] - p);t[i][1] = Math.max(t[i][1], t[i][0] + p);}}return t[k - 1][1];}private int greedy(int[] prices) {int max = 0;for (int i = 1; i < prices.length; ++i) {if (prices[i] > prices[i - 1])max += prices[i] - prices[i - 1];}return max;}
}

本文內(nèi)容到此結(jié)束了，
如有收獲歡迎點贊👍收藏💖關(guān)注??，您的鼓勵是我最大的動力。
如有錯誤?疑問💬歡迎各位指出。
主頁：共飲一杯無的博客匯總👨?💻

保持熱愛，奔赴下一場山海。🏃🏃🏃