Posts

Showing posts from August, 2018

reverse int

Given a 32-bit signed integer, reverse digits of an integer. Example 1: Input: 123 Output: 321 Example 2: Input: -123 Output: -321 Example 3: Input: 120 Output: 21 Note: Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−2 31 ,  2 31  − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows. class Solution { public: int reverse( int x) { // edge case // 对于integer的操作,要考虑其overflow的情况。 // max, numeric_limits<int>::max() .. min() .. if (x == numeric_limits< int >::max() || x == numeric_limits< int >::min()) { return 0 ; } if (x >= 0 ) { return reverseUtil(x); } else { return 0 - reverseUtil(abs(x)); } } int reverseUtil( int x) { long reverse = 0 ; while

Tree的遍历

今天一个朋友来帮我mock interview. 感觉自信心又收到了打击。看来我真的是自我认知不够正确外加过于乐观不知轻重。好吧,让我在打击中继续前行! 今天就来总结一下朋友问我的问题。 How to write a TreeIterator? 具体分析: 1. TreeIterator, 通过名字就该知道,这个题目是考察 tree的iterative traversal. 然后发现自己给出的答案的确开始没有注意到这点,这种感觉就像明明告诉你了,前方左转,我却依然右转一样。哎。。 2. Problem Definition. 问清楚题目的要求,input, output, 要handle的情景。 interface,  precondition, 树的traversal的方式. 3. 问题归一化。 在c++ stl里面有iterator 对于 iterator, 可能包括的函数有, a. construct Iterator b. next -> return value. Node?or value? error handling c. hasNext -> return bool d. single direction of bi-direction 4. Tree的traversal 分为三种,pre-order, in-order and post-order. Pre-order:  recursive void preOrder (TreeNode * root) { if (root == nullptr) { return ; } cout << root -> val; preOrder(root -> left); preOrder(root -> right); } iterative stack<TreeNode*> m_nodeStack; 只要stack不是empty的时候,就可以继续,直到stack is empty循环结束。 void preOrder2 (TreeNode * root) { stack < Tree