NO CODING NO LIFE: 六月 2015

2015年6月30日星期二

LeetCode: Binary Tree Level Order Traversal II

Almost same with Binary Tree Level Order Traversal
I used the standard DFS solution:
It can be easily realized based on tree methods in my previous article: http://codinggamestart.blogspot.com/2015/06/leetcode-binary-tree-level-order.html
for BFS with queue: change result.push_back(v) to result.insert(result.begin(), v);
for BFS with two queues: same with above;
for DFS the tricky solution: way 1 is to change it to standard solution like below
way 2 is to change push_back to insert, and notice the index change, become not straightforward.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
       int height=getHeight(root);
       vector<vector<int>> result(height);
       if(height==0) return result;
       preorder(root,height-1,result);
       return result;
    }
    int getHeight(TreeNode* node){
        int left=1;
        int right=1;
        if(node==NULL) return 0;
        if(node->left!=NULL) left+=getHeight(node->left);
        if(node->right!=NULL) right+=getHeight(node->right);
        return (left>right)?left:right;
    }
    void preorder(TreeNode* node, int n, vector<vector<int>>& result){
        if(node==NULL) return;
        result[n].push_back(node->val);
        if(node->left!=NULL) preorder(node->left, n-1, result);
        if(node->right!=NULL) preorder(node->right, n-1, result);
    }
};

Reference: http://siddontang.gitbooks.io/leetcode-solution/content/tree/binary_tree_level_order_traversal.html

Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

Have you met this question in a real interview?

Yes

Example

Given binary tree {3,9,20,#,#,15,7},

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

Challenge

Challenge 1: Using only 1 queue to implement it.

Challenge 2: Use DFS algorithm to do it.

It has two basic way: BFS and DFS.

For BFS, the typical way is to use pair to record the level of each node and store them in a queue.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        if(root==NULL) return result;
        queue<pair<TreeNode*,int>> Q;
        vector<int> tempresult;
        Q.push(make_pair(root,0));
        int pre_lev=0;
        while(!Q.empty()){
            TreeNode *cur=Q.front().first;
            int cur_lev=Q.front().second;
            if(cur_lev>pre_lev){
                result.push_back(tempresult);
                tempresult.clear();
                pre_lev=cur_lev;
            }
            tempresult.push_back(cur->val);
            if(cur->left!=NULL) {
                Q.push(make_pair(cur->left,cur_lev+1));
            
            }
            if(cur->right!=NULL) {
                Q.push(make_pair(cur->right,cur_lev+1));
            }
            Q.pop();
        }
        result.push_back(tempresult);
        return result;
    }
};

Since we don't need to know the exact level of each node in this problem, we can use two queues to record nodes of the same level.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        if(root==NULL) return result;
        queue<TreeNode*> q1, q2;
        q1.push(root);
        while(!q1.empty() || !q2.empty()){
            //if(q1.empty) 
            if(q1.empty()){
                q1=q2;
                while(!q2.empty()) q2.pop();
                //no clear() function in queue, has to use this way to clear
                //easy understanding, but cannot pass for time limit
                /*queue<TreeNode*> q3;  
                q3=q1;
                q1=q2;
                q2=q3;*/
            }
            int size=q1.size();
            vector<int> result_temp;
            for(int i=0;i<size;i++){
                TreeNode* cur=q1.front();
                q1.pop();
                result_temp.push_back(cur->val);
                if(cur->left!=NULL) q2.push(cur->left);
                if(cur->right!=NULL) q2.push(cur->right);
            }
            result.push_back(result_temp);
            result_temp.clear();
        }
        return result;
    }
};

For DFS, just do recursion in preorder, which makes it easy to write values in two dimensional vector.

My way is a little tricky. No initialization for two dimensional vector and no integer to record level. Here is a link to standard DFS solution: http://siddontang.gitbooks.io/leetcode-solution/content/tree/binary_tree_level_order_traversal.html
The main difference is that the standard way has two DFS process, one is used to calculate levels.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
       vector<vector<int>> result;
       if(root==NULL) return result;
       preorder(root,0,result);
       return result;
    }
    void preorder(TreeNode* node, int n, vector<vector<int>>& result){
        if(node==NULL) return;
        if(n<result.size()) result[n].push_back(node->val);
        else{
            vector<int> res_temp;
            res_temp.push_back(node->val);
            result.push_back(res_temp);
        }
        if(node->left!=NULL) preorder(node->left, n+1, result);
        if(node->right!=NULL) preorder(node->right, n+1, result);
    }
};

Reference:
Yu's coding garden--great explanation for BFS
YouTube video: Great basic concepts explanation

Lintcode second:
BFS
use a queue store nodes and an integer record level size
Time: O(n)
Space: O(n)

class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: Level order a list of lists of integer
     */
public:
    vector<vector<int>> levelOrder(TreeNode *root) {
        vector<vector<int> > res;
        vector<int> temp;
        queue<TreeNode *> q;
        if(root) q.push(root);
        int levelsize= 1;
        while(!q.empty()){
            TreeNode *cur = q.front();
            q.pop();
            levelsize--;
            temp.push_back(cur->val);
            if(cur->left) q.push(cur->left);
            if(cur->right) q.push(cur->right);
            
            if(levelsize == 0){
                levelsize = q.size();
                res.push_back(temp);
                temp.clear();
            }
        }
        return res;
    }
};

2015年6月10日星期三

LeetCode: Factorial Trailing Zeroes

Reference algorithm from Wiki: http://en.wikipedia.org/wiki/Trailing_zero

class Solution {
public:
    int trailingZeroes(int n) {
        if(n<5) return 0;
        int q=n;
        int sum=0;
        while(q){
            q=q/5;
            sum+=q;
        }
        return sum;
    }
};

2015年6月9日星期二

LeetCode: House Robber

Dynamic programming.
Let rec[i] keep recording the maxim money with (i+1) houses.
Key is rec[i]=max(rec[i-1],rec[i-2]+nums[i]).

TIP: Make sure allocate memory for vector, or in leetcode test will display runtime error which equals to core dump in c++ compiler.

Debugging for too long time, not happy...

class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.size()==0) return 0;
        if(nums.size()==1) return nums[0];
        vector<int> rec(nums.size());
        rec[0]=nums[0];
        rec[1]=max(nums[0],nums[1]);
        for(int i=2;i<nums.size();i++){
            rec[i]=max(rec[i-1],rec[i-2]+nums[i]);
        }
        return rec[nums.size()-1];
    }
};

There is another solution that recording money based on odd and even.

Reference:
http://binwu.net/leetcode/2015/04/25/Leetcode-House-Robber/
3 solutions

LeetCode: Happy Number

Key is how to test the number loops endlessly. Test loop by a hashmap recording all sums appeared. If same sum appear again, it's easy to see the sum of the squares of its digits will loop.

class Solution {
public:
    int getSum(int n){
        int sum=0;
        while(n){
            sum+=(n%10)*(n%10);
            n=n/10;
        }
        return sum;
    }
    bool isHappy(int n) {
        unordered_set<int> record;
        while(n!=1){
            if(record.count(n)) return false;
            else record.insert(n);
            n=getSum(n);
        }
        return true;
    }
};

2015年6月7日星期日

LeetCode: Remove Linked List Elements

At first, I tried for loop to remove, but the logics become a mess. Maybe try for loop in the future.
Difficulty: how to deal with head point; Considering one node, two node, and last node.

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* cur=head;
        ListNode* pre=NULL;
        //if(!head) return NULL;
        while(head && head->val==val ) {
            ListNode* temp=head;
            head=head->next;
            delete temp;
        }
        if(!head) return NULL;
        cur=head->next;
        pre=head;
        while(cur ){
            if(cur->val==val){
                pre->next=cur->next;
                delete cur;
                cur=pre->next;
            }
            else{
                cur=cur->next;
                pre=pre->next;
            }   
        }
        return head;
        //bug codes:
        /*for( ; cur&&cur->next ; pre=cur,cur=cur->next){
            if(cur->val==val){
                //ListNode* temp=cur->next;
                pre->next=cur->next;
                delete cur;
                cur=pre;
            }
            //pre=cur;
            //cur=cur->next;
        }*/
    }
};

Another way to deal with head point is creating a fake head pointer which can refer to
http://www.bubuko.com/infodetail-761875.html
http://yucoding.blogspot.com/2015/06/leetcode-question-remove-linked-list.html

Reference:
http://binwu.net/leetcode/2015/04/25/Leetcode-Remove-Linked-List-Elements/

LeetCode: Count Primes

Way 1: O(n^1.5) cannot pass leetcode test, too long time

class Solution {
public:
    static bool isPrime(int n){
        if(n<=1) return false;
        for(int i=2;i*i<=n;i++){ //Notice <=n when testing whether n is prime
            if(n%i==0) return false;
        }
        return true;
    }
    static int countPrimes(int n) {
        if(n<=1) return 0;
        int count=0;
        for(int i=2;i<n;i++){
            if(isPrime(i)) {
    count++;
             }
        }
        return count;
    }
};

Way 2: O(n*loglogn) Sieve of Eratostrenes

class Solution {
public:
    int countPrimes(int n) {
        bool* isPrime=new bool[n];
        for(int i=0;i<n;i++)
            isPrime[i]=true;
        //for(int i=2;i<=sqrt(n);i++){  
        for(int i=2;i*i<n;i++){  //since n is not included, condition equals i*i<=(n-1) 
            if(isPrime[i]) {
                for(int j=i*i;j<n;j=j+i){
                    isPrime[j]=false;
                } 
            }
        }
        int count=0;
        for(int i=2;i<n;i++){
            if(isPrime[i]) count++;
        }
        delete[] isPrime;
        return count;
    }
};

Reference: https://leetcode.com/problems/count-primes/

LeetCode: Contains Duplicate II

In Contains Duplicate problem, we just need to judge whether duplication exist, so set is enough.
Here, we need to search number to get index, so unordered_map(hashmap) will be first choice.

For each loop, if current number is in hashmap, this number appeared before. We calculate the index distance. If distance less or equal to k, return true. If distance is larger than k, we need to update index information in hashmap for current number.

Here is a point, there may be more than just two identical numbers in the array. So we need to update. If current number appears in the future, the future position to position now will be closer than to old position. So we just need to record the current position (corresponding to current number in Hashmap)

Complexity: O(nums.size)

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int,int> Map;
        for(int i=0;i<nums.size();i++){
            if(Map.find(nums[i])!=Map.end()) {
                int d=i-Map[nums[i]];
                if (d<=k) return true;
                else Map[nums[i]]=i;
            }
            else Map[nums[i]]=i;
        }
        return false;
    }
};

Reference:http://www.cnblogs.com/grandyang/p/4539680.html
//codes in this blog doesn't work, because array can have more than two identical numbers.

LeetCode: Rectangle Area

Difficulty: how to get dist_w/h.
At first I just got this distance with a difference from points ==!

dist_w/h ==> the distance between two farthest horizontal/vertical points of two rectangles
rep_w/h ==>repetition distance of width and height

class Solution {
public:
    int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
        int width1=abs(A-C);
        int width2=abs(E-G);
        int height1=abs(B-D);
        int height2=abs(F-H);
        
        int dist_w= ((C>G)?C:G) -  ((A<E)?A:E) ;
        int dist_h= ((D>H)?D:H) - ((B<F)?B:F);

        int rep_w=abs(width1+width2-dist_w);
        int rep_h=abs(height1+height2-dist_h);
        int area_sum=width1*height1+width2*height2;
        if(dist_w<(width1+width2) && dist_h<(height1+height2))
            return area_sum-rep_w*rep_h;
        return area_sum;
    }
};

LeetCode: Maximum Depth of Binary Tree

Iteration:

class Solution {
public:
    int maxDepth(TreeNode* root) {
        queue<pair<TreeNode*, int>> q;
        if(!root) return 0;
        q.push(make_pair(root,1));
        while(!q.empty()){
            pair<TreeNode*, int> cur=q.front();
            q.pop();
            if(cur.first->left !=NULL) 
                q.push(make_pair(cur.first->left,cur.second+1));
            if(cur.first->right !=NULL) 
                q.push(make_pair(cur.first->right,cur.second+1));
            if(cur.first->left==NULL && cur.first->right==NULL && q.empty())
                return cur.second;
        }       
    }
};

Recursion:

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(!root) return 0;
        int left=1;
        int right=1;
        if(root->left) left= maxDepth(root->left)+1;
        if(root->right) right= maxDepth(root->right)+1;
        return (left>right)?left:right;
    }
};

Lintcode second:

BFS: queue store pair

class Solution {
public:
    /**
     * @param root: The root of binary tree.
     * @return: An integer
     */
    int maxDepth(TreeNode *root) {
        // write your code here
        int res = 0;
        queue<pair<TreeNode*, int> > q;
        if(root) q.push(make_pair(root, 1));
        while(!q.empty()){
            TreeNode *curNode = q.front().first;
            int curLevel = q.front().second;
            res = max(res, curLevel);
            q.pop();
            if(curNode->left) q.push(make_pair(curNode->left, curLevel + 1));
            if(curNode->right) q.push(make_pair(curNode->right, curLevel + 1));
        }
        return res;
    }
};

BFS: two queues to track level
or use null or other special signal to track levels
or use a int count to track level

LeetCode: Isomorphic Strings

This problem is solve with key-value structure.
The smap stored key from char in s.
The tmap stroed key from char in t. The effect of tmap is just to make sure that values in tmap are not repeated. So I used a set replace the tmap. ( annotations are how to use tmap)
If changing map and set to unordered, speed will be better.

From the leetcode performance, there should be quicker way...

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        map<char, char> smap;
        //map<char, char> tmap;
        set<char> sset;
        for(int i=0;i<s.size();i++){
            if(!smap.count(s[i])) {
                //if( tmap.count(t[i])) return false;
                if( sset.count(t[i])) return false;
                smap[s[i]]=t[i];
                //tmap[t[i]]=s[i];
                sset.insert(t[i]);
            }
            else if(smap.find(s[i])->second!=t[i]) return false;
        }
        return true;
    }
};

Reference:
http://www.bkjia.com/cjjc/994501.html

LeetCode: Reverse Linked List

Two bad solutions, both are iterative
Solution 1: O(n), cannot pass test, need too much memory

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head==NULL) return NULL;
        if(head->next==NULL) return head;
        vector<ListNode*> Nodes;
        ListNode* cur=head;
        while(cur->next!=NULL){
            Nodes.push_back(cur);
        }
        //ListNode* newhead;
        //newhead=cur;
        head=cur;
        while(Nodes.size()!=0){
            cur->next=Nodes.back();
            cur=Nodes.back();
            Nodes.pop_back();
        }
        cur->next=NULL;
        //return newhead;
        return head;
    }
};

Solutions 2: O(n^2) speed is too low.
It took O(n) to get newest tail pointer in the input List which is unnecessary.

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head==NULL) return NULL;
        //if(head->next==NULL) return head;
        ListNode* pre;
        ListNode* cur=head;
        for(cur=head;cur->next!=NULL;pre=cur,cur=cur->next);
        ListNode* newhead=cur;
        cur->next=pre;
        pre->next=NULL;
        while(pre!=head){
            for(cur=head;cur->next!=NULL;pre=cur,cur=cur->next);
            cur->next=pre;
            pre->next=NULL;
        }
        return newhead;       
    }
};

Two final solutions:

Iterative Way:
Remember the point before current pointer, just reconnect from the beginning to the end of the linkedlist

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head==NULL) return NULL;
        //if(head->next==NULL) return head;
        ListNode* pre=NULL;
        ListNode* cur=head;
        while(cur!=NULL){
            ListNode* nextNode=cur->next;
            cur->next=pre;
            pre=cur;
            cur=nextNode;
        }
        return pre;
    }
};

Recursive way:

Reference:
http://articles.leetcode.com/2010/04/reversing-linked-list-iteratively-and.html

2015年6月6日星期六

LeetCode: Contains Duplicate

Stupid Way: Cannot pass testing, too long time

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        for(int i=0;i<nums.size();i++){
            int cur=nums[i];
            int comp=i+1;
            while(comp<nums.size()){
                if(cur==nums[comp]) return true;
                comp++;
            }
        }
        return false;
    }
};

RedBlack tree(set): n*O(log n)

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        set<int> s;
        for(int i=0;i<nums.size();i++){
            if(s.find(nums[i])!=s.end()) return true;
            s.insert(nums[i]);
        }
        return false;
    }
};

HashMap(unordered_set): n*O(1)
Tip: map element search O(log n), advantage compared to unordered_map: map is ordered
unordered_set has a convenient function count(): return 1 if key exists, 0 if not.
official definition: Count elements with a specific key

Searches the container for elements whose key is k and returns the number of elements found. Because unordered_map containers do not allow for duplicate keys, this means that the function actually returns 1 if an element with that key exists in the container, and zero otherwise.

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_set<int> s;
        for(int i=0;i<nums.size();i++){
            if(s.count(nums[i])) return true;
            s.insert(nums[i]);
        }
        return false;
    }
};

SortingWay: update later
Reference:
http://www.bubuko.com/infodetail-827176.html
http://www.cplusplus.com/reference/unordered_map/unordered_map/count/

C++ Learning resources

Basics
pinter to get member in class and struct
http://c.biancheng.net/cpp/biancheng/view/188.html
http://c.biancheng.net/cpp/biancheng/view/173.html

library classes

c++11
http://www.oschina.net/news/28928/9-reasons-to-start-using-c11
http://blog.csdn.net/m6830098/article/details/17253057

pair:
http://www.cnblogs.com/cszlg/archive/2013/03/10/2952807.html

set:
O(logn) to find
best to insert and delete element
find()，若找到，返回该键值迭代器的位置，否则，返回最后一个元素后面一个位置。
http://www.cnblogs.com/BeyondAnyTime/archive/2012/08/13/2636375.html
http://www.cnblogs.com/youxin/p/3414015.html
STL常用vector,map,set,sort用法

stack, queue, vector
C++ STL stack、queue和vector的使用

unordered container turorial

vector赋值
http://zhidao.baidu.com/link?url=2ytPLBMlhGcfz3jH7lJfNl92TwlWKif5To75ylE0Gq8OSLv9EW-oCtBsf-7oP1OtEjcpgEvy4QR_AtT-xj172q
http://zhidao.baidu.com/question/36348703.html?qbl=relate_question_0&word=vector%20%B8%B3%D6%B5

Container adaptor and underlying container:
stack, queue and priority_queue are implemented as container adaptors. Container adaptors are not full container classes, but classes that provide a specific interface relying on an object of one of the container classes (such as dequeor list) to handle the elements. The underlying container is encapsulated in such a way that its elements are accessed by the members of the container adaptor independently of the underlying container class used.
http://www.cplusplus.com/reference/stl/

priority_queue
http://www.cplusplus.com/reference/queue/priority_queue/

rewrite comp function of sort()
http://fusharblog.com/3-ways-to-define-comparison-functions-in-cpp/

memory management

difference between stack and heap
http://my.oschina.net/u/1167799/blog/160086
http://www.cnblogs.com/wengzilin/p/3922022.html
http://boyishachang.blog.51cto.com/3485129/1275724

difference between malloc/free and new/delete
http://blog.sciencenet.cn/blog-591030-595189.html

对象创建 JAVA C++ 比较
http://developer.51cto.com/art/201305/395862.htm

LeetCode: Minimum Depth of Binary Tree

C++ Solution:

Queue approach:

struct DATA{
    TreeNode* node;
    int level;
    DATA(TreeNode* n, int l):node(n),level(l){}
};

class Solution {
public:
    int minDepth(TreeNode* root) {
        queue< DATA > que;
        if(!root) return 0;
        que.push(DATA(root,1));
        while(!que.empty()){
            DATA current=que.front();//in java, pop() will return element, in c++, not
            que.pop();
            if(!current.node->left && !current.node->right) return current.level;
            if(current.node->left) 
                //not sure whether DATA() is right for initialization an object
                que.push(DATA(current.node->left, current.level+1)); 
            if(current.node->right) 
                que.push(DATA(current.node->right, current.level+1));
        }      
    }
};

Reference:
1. recursion approach: https://helloacm.com/coding-exercise-minimum-depth-of-binary-tree-c-online-judge/
http://blog.theliuy.com/minimum-depth-of-binary-tree/
2. queues approach: http://yucoding.blogspot.com/2013/01/leetcode-question-55-minimum-depth-of.html

JAVA Solution:
Reference: http://gongxuns.blogspot.com/2012/12/leetcode-minimum-depth-of-binary-tree.html

Complexity of Recursion Function

Great explanations for Recursion Function Complexity Calculation:
http://www.cs.ucf.edu/~dmarino/ucf/cop3502/lec_biswas/

订阅：博文 (Atom)