东莞网站seo推广优化,公司网站SEO优化哪个做得好,中国商标注册网,wordpress主题名称文章目录二叉树的锯齿形层序遍历#xff08;树、广度优先搜索#xff09;用栈实现队列#xff08;栈、设计#xff09;买卖股票的最佳时机 IV#xff08;数组、动态规划#xff09;二叉树的锯齿形层序遍历#xff08;树、广度优先搜索#xff09;
给定一个二叉树…
文章目录二叉树的锯齿形层序遍历树、广度优先搜索用栈实现队列栈、设计买卖股票的最佳时机 IV数组、动态规划二叉树的锯齿形层序遍历树、广度优先搜索
给定一个二叉树返回其节点值的锯齿形层序遍历。即先从左往右再从右往左进行下一层遍历以此类推层与层之间交替进行。 例如 给定二叉树 [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 ListListInteger zigzagLevelOrder(TreeNode root) {ListListInteger list new LinkedList();if (root null) {return list;}StackTreeNode stack1 new Stack();stack1.push(root);boolean postive true;while (!stack1.isEmpty()) {StackTreeNode stack2 new Stack();ListInteger 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;}
}用栈实现队列栈、设计
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作push、pop、peek、empty 实现 MyQueue 类
void push(int x) 将元素 x 推到队列的末尾int pop() 从队列的开头移除并返回元素int peek() 返回队列开头的元素boolean empty() 如果队列为空返回 true 否则返回 false
说明
你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。你所使用的语言也许不支持栈。你可以使用 list 或者 deque双端队列来模拟一个栈只要是标准的栈操作即可。
进阶
你能否实现每个操作均摊时间复杂度为 O(1) 的队列换句话说执行 n 个操作的总时间复杂度为 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最多调用 100 次 push、pop、peek 和 empty假设所有操作都是有效的 例如一个空的队列不会调用 pop 或者 peek 操作
解答
class MyQueue {StackInteger s1;StackInteger s2;/** Initialize your data structure here. */public MyQueue() {s1 new StackInteger();s2 new StackInteger();}/** 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数组、动态规划
给定一个整数数组 prices 它的第_ i 个元素 prices[i] 是一支给定的股票在第 i _天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 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 1000 prices.length 10000 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;}
}本文内容到此结束了 如有收获欢迎点赞收藏关注✔️您的鼓励是我最大的动力。 如有错误❌疑问欢迎各位指出。 主页共饮一杯无的博客汇总 保持热爱奔赴下一场山海。
