leetcode solution

690 Employee Importance  This could be done either in DFS or BFS traversal of the graph.  Both need a define a map to save the id to employee object pointer, so that we could easily get the subordinate employee info while traversing. For BFS, we use a deque<Employee*> since it is a super version of queue allowing us insert at both end of the queue. (1) push_back the mp[id] info into the queue (2) while the queue is not empty, do the following:      pop_front the front element in the queue, add its importance to the the total importance of the employee id (either itself or its mangers'), push_back all its subordinate employee into the deque. (3) return the total importance in the end.    Tree 107 Binary Tree Level Order Traversal II        BFS: Define a queue (you could also use deque), push root in queue. loop each element while q is not empty, define a  nextLevelStarter to keep track of the beginn...

461 Hamming Distance (1) let z = x ^ y (2) count how many 1s in z's binary representation in a loop. 169 Majority Element The idea is to iterate each bit of all the numbers and try to get the statistics of each bit. If a given bit has more ones than zeros then set the result bit to 1, otherwise set it to zero. 187 Repeated DNA Sequences      Use a hash map to count each 10 character string frequency. In the second loop, loop each map element to check f its frequency is > 1, put it in the result array. Return the result array in the end. No need to calculate the hash key as binary number using bit manipulation. 231 Power of Two       return n <= 0 ? false : (n ^ (n - 1)) == 0; 342 Power of Four      Add one extra check based on 231:  (n & 0x55555555) != 0 191 Number of 1 Bits      Loop and count each 1 bit (n & (0x1 << 1)( in the 32-bit bin...

292   Nim Game     You can always win a Nim game if the number of stones n in the pile is not divisible by 4 4 . Second Time  ============================================= 319  Bulb Switcher  (N) A light will be toggled only during the round of its factors, e.g. number 6 light will be toggled at 1,2,3,6 and light 12 will be toggled at 1,2,3,4,6,12. The final state of a light is on and off only depends on if the number of its factor is odd or even. If odd, the light is on and if even the light is off. The number of one number’s factor is odd if and only if it is a perfect square! So we will only need to loop to find all the perfect squares that are smaller than n! Actually, the number of perfect square number within n is sqrt(n) 777  Swap Adjacent in LR String    题目要求根据给定的规则，判断能否从 start string 变换到 end string 。 给出了两种变换的规则，从“XL”到“LX”和从“RX”到“XR”。所以我们可以给出两条规律： 如果start能变换到end，那么除去两个字符串中的 "X" ，剩余的字符串一定相同。因为任意...

Second Time ========================================================================= 307  Range Sum Query - Mutable (1) A naive way is to do range sum query whenever needed, i.e: for loop the number between index i and j and sum all of them together, this takes O(N) time for the range sum query operation. (2) segment tree 1. Build segment tree We will use a very effective bottom-up approach to build segment tree. We already know from the above that if some node p p p holds the sum of [ i … j ] [i \ldots j] [ i … j ] range, its left and right children hold the sum for range [ i … i + j 2 ] [i \ldots \frac{i + j}{2}] [ i … ​ 2 ​ ​ i + j ​ ​ ] and [ i + j 2 + 1 , j ] [\frac{i + j}{2} + 1, j] [ ​ 2 ​ ​ i + j ​ ​ + 1 , j ] respectively. Therefore to find the sum of node p p p , we need to calculate the sum of its right and left child in advance. We begin from the leaves, initialize them with input array elements a [ 0 , 1 , … , n − 1 ] a[0, 1, \ldots, n-1] a [ 0 , 1 , ...

Tree 173 Binary Search Tree Iterator     This problem is actually Iterative inOrder traversal      maintain a  pushLeft function and a data member stack<TreeNode*> st. Call pushLeft in      the constructor BSTIterator. And hasNext() is just check the stack is not NULL. next() is      just visit st.top() element. But in order to visit the right child, we have to pushLeft(p->right)     before return p->val. It is a good idea to use pushLeft function in inOrder Traversal. 150 Evaluate Reverse Polish Notation Keep push the numbers onto the stack until see an operator, then pop two elements from stack top and do num2 op num1 and push the result back to the stack. Keep doing for all the strings in the input vector array. In the end return the stack top element, which is the final result calculated. 682 Baseball Game    Use stack to solve the problem, since all the operati...