Saturday, November 29, 2014
Sunday, November 23, 2014
Java consumer producers problem using mutex
http://java67.blogspot.com/2012/12/producer-consumer-problem-with-wait-and-notify-example.html?m=1
156. Binary Tree Upside Down ---M ~~~~做了3遍的, 竟然忘了~~~~
Given the root
of a binary tree, turn the tree upside down and return the new root.
You can turn a binary tree upside down with the following steps:
- The original left child becomes the new root.
- The original root becomes the new right child.
- The original right child becomes the new left child.
The mentioned steps are done level by level, it is guaranteed that every node in the given tree has either 0 or 2 children.
Example 1:
Input: root = [1,2,3,4,5] Output: [4,5,2,null,null,3,1]
Example 2:
Input: root = [] Output: []
Example 3:
Input: root = [1] Output: [1]
Constraints:
- The number of nodes in the tree will be in the range
[0, 10]
. 1 <= Node.val <= 10
Every node has either 0 or 2 children.
这个题目描述的很烂。
应该是: binary tree upside down along left most edge
Iterative bottom up.
就是先做左子树,再连接修改该节点。
就是先做左子树,再连接修改该节点。
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: TreeNode* upsideDownBinaryTree(TreeNode* root) { if(not root){ // if nullptr , or no child return root; } stack<TreeNode*> S; TreeNode *runner = root; while(runner->left ){ S.push(runner); runner = runner->left; } TreeNode * newRoot = runner; while(not S.empty()){ auto p = S.top(); S.pop(); runner->right = p; runner->left = p->right; p->left = nullptr; p->right = nullptr; runner = p; } return newRoot; } };
错误:
没有先把 p.right = nullptr; 这个题比较tricky的点就是,要事先找到return 的newRoot.
------------Recursive approach--------先找到 返回TreeNode, 这样就不需要在helper()中管了--------
这里利用了一个性质,就是指针指向的Node只做了child 指针的更改操作。原本的Object 位置并没有更改。
Mistakes:
1: base case中,忘了把root.left==null的情况加进来(否则会有null pointer的Exception)
------------Recursive approach--------先找到 返回TreeNode, 这样就不需要在helper()中管了--------
public class Solution { public TreeNode upsideDownBinaryTree(TreeNode root) { if(root == null) return null; TreeNode leftMost = root; while( leftMost.left != null) leftMost = leftMost.left; helper(root); return leftMost; } private void helper(TreeNode root){ if(root.left == null) return; upsideDownBinaryTree(root.left); TreeNode newRoot = root.left; newRoot.left = root.right; newRoot.right = root; root.left = null; root.right = null; } }
这里利用了一个性质,就是指针指向的Node只做了child 指针的更改操作。原本的Object 位置并没有更改。
Mistakes:
1: base case中,忘了把root.left==null的情况加进来(否则会有null pointer的Exception)
public class Solution { public TreeNode UpsideDownBinaryTree(TreeNode root) { if(root == null || root.left == null) return root; TreeNode newRoot = UpsideDownBinaryTree(root.left); TreeNode r= root.right; root.left =null; root.right = null; TreeNode runner = newRoot; while(runner!=null && runner.right!=null){ runner = runner.right; } if(runner!=null){ runner.left = r; runner.right = root; } return newRoot; } }
Saturday, November 22, 2014
155. Min Stack (easy)
Q:
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
- push(x) -- Push element x onto stack.
- pop() -- Removes the element on top of the stack.
- top() -- Get the top element.
- getMin() -- Retrieve the minimum element in the stack.
Example:
MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> Returns -3. minStack.pop(); minStack.top(); --> Returns 0. minStack.getMin(); --> Returns -2.
A:
思想很简单。后来出现memory out of limit, minStack中就没有存多余的最小值。
class MinStack { public: /** initialize your data structure here. */ vector<int> stack; vector<int> minStack; MinStack() { } void push(int x) { stack.push_back(x); if(minStack.empty() || minStack.back() > x) minStack.push_back(x); else minStack.push_back(minStack.back()); } void pop() { stack.pop_back(); minStack.pop_back(); } int top() { return stack.back(); } int getMin() { return minStack.back(); } }; /** * Your MinStack object will be instantiated and called as such: * MinStack* obj = new MinStack(); * obj->push(x); * obj->pop(); * int param_3 = obj->top(); * int param_4 = obj->getMin(); */
Learned:
1; minStack中,重复的最小值也要存。2:即使Stack<Integer>的返回值是一个对象,因此要用.equals()来比较大小
Subscribe to:
Posts (Atom)