NO CODING NO LIFE: 九月 2015

2015年9月30日星期三

Lintcode: Larget Rectangle in Histogram

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

Have you met this question in a real interview?

Yes

Example

Given height = [2,1,5,6,2,3],
return 10.

Tags Expand

Array Stack

Naive solution 1:
For each element, calculate largest area with the height of itself
Time limit for large data
Time: O(n*n)
Space: O(1)

class Solution {
public:
    /**
     * @param height: A list of integer
     * @return: The area of largest rectangle in the histogram
     */
    int largestRectangleArea(vector<int> &height) {
        // write your code here
        int res = 0;
        for(int i = 0; i < height.size(); i++){
            int cur = i;
            int left = 0, right = 0;
            while(cur >= 0){
                if(height[cur] < height[i]) break;
                left += height[i];
                cur--;
            }
            cur = i + 1;
            while(cur < height.size()){
                if(height[cur] < height[i]) break;
                right += height[i];
                cur++;
            }
            res = max(res, left + right);
        }
        return res;
    }
};

Naive solution 2
Similar solution in converse order: http://fisherlei.blogspot.com/2012/12/leetcode-largest-rectangle-in-histogram.html
We just get the minimum area between any possible two indexes:
Time: O(n*n)
Space: O(1)

class Solution {
public:
    /**
     * @param height: A list of integer
     * @return: The area of largest rectangle in the histogram
     */
    int largestRectangleArea(vector<int> &height) {
        // write your code here
        int maxArea = 0;
        for(int i = 0; i < height.size(); i++){
            int minH = height[i];
            for(int j = i; j < height.size(); j++){
                minH = min(minH, height[j]);
                maxArea = max(maxArea, minH * (j - i + 1));
            }
        }
        return maxArea;
    }
};

Optimized Naive solution 2 with Pruning
//thought: http://blog.csdn.net/abcbc/article/details/8943485
Whenever height[k] <= height[k - 1] rectangle formded by k - 1 is larger than k
So we look for the k that height[k] > height[k - 1]

Still cannot pass
Time: O(n*n)
Space: O(1)

class Solution {
public:
    /**
     * @param height: A list of integer
     * @return: The area of largest rectangle in the histogram
     */
    int largestRectangleArea(vector<int> &height) {
        // write your code here
        int maxArea = 0;
        //int lastH = -1;
        for(int i = 0; i < height.size(); i++){
            if(i > 0 && height[i] <= height[i - 1]) {
                continue;
            }
            int minH = height[i];
            for(int j = i; j < height.size(); j++){
                minH = min(minH, height[j]);
                maxArea = max(maxArea, minH * (j - i + 1));
            }
        }
        return maxArea;
    }
};

O(n) solution -- DP
http://www.acmerblog.com/largest-rectangle-in-histogram-6117.html

O(n) solution -- stack
//Great explanation, even though some problems in pictures
http://www.cnblogs.com/lichen782/p/leetcode_Largest_Rectangle_in_Histogram.html
//codes:
http://bangbingsyb.blogspot.com/2014/11/leetcode-largest-rectangle-in-histogram.html
Create a stack to store all increasing adjacent numbers, when new coming number is more than the top element is stack, just push it to stack; if not, pop elements bigger than new coming number and keep updating area.
Note: set -1 at the beginning and end of height vector:
The -1 at the begin is to help localize the possible maxArea in stack
The -1 at the end is to pop all elements in stack when finish iteration

class Solution {
public:
    /**
     * @param height: A list of integer
     * @return: The area of largest rectangle in the histogram
     */
    int largestRectangleArea(vector<int> &height) {
        if(height.empty()) return 0;
        height.push_back(-1);
        height.insert(height.begin(), -1);  //when elements 
        stack<int> s;
        int maxArea = 0;
        
        for(int i = 0; i < height.size(); i++){
            while(!s.empty() && height[i] < height[s.top()]){
                int h = height[s.top()];
                s.pop();
                maxArea = max(maxArea, h * (i - s.top() - 1));
            }
            s.push(i);
        }
        
        return maxArea;
    }
};

Analysis:
However, codes above don't optimize the situation when there are many equal numbers in height, in this case, there are still some repetitive counts.
Below is how to optimize:
euqation in Line 1 avoid to store repetitive numbers in stack
The condition height[i] < h in line 4 avoid the TERMSIG case when height[i] = -1 and s.top() = -1

while(!s.empty() && height[i]<=height[s.top()]) {
                int h = height[s.top()];
                s.pop();
                if(height[i]<h) maxArea = max(maxArea, (i-s.top()-1)*h);
            }

2015年9月29日星期二

Lintcode: Ugly Number

Ugly number is a number that only have factors 3, 5 and 7.

Design an algorithm to find the Kth ugly number. The first 5 ugly numbers are 3, 5, 7, 9, 15 ...

Have you met this question in a real interview?

Yes

Example

If K=4, return 9.

Challenge

O(K log K) or O(K) time.

Thoughts:
http://blog.csdn.net/nisxiya/article/details/46767595

Naive solution:
Try every number and judge whether it is ugly until get the kth

Priority_queue solution:
Created a min heap and kept multiplying the minimum ugly number with 3, 5, 7 and put result into the heap. To avoid repetition, used a hashset to mark elements already in the heap
Time: O(klogk)
Space: O(k)

class Solution {
public:
    /*
     * @param k: The number k.
     * @return: The kth prime number as description.
     */
     struct compNode{
         bool operator()(long long a, long long b)const{
             return a > b;
         }
     };
    long long kthPrimeNumber(int k) {
        priority_queue<long long, vector<long long>, compNode> pq;
        long long cur;
        //vector<int> res;
        unordered_set<long long> hashset;
        pq.push(1);
        for(int i = 0; i <= k; i++){
            cur = pq.top();
            pq.pop();
            if(!hashset.count(cur * 3)) {
                pq.push(cur * 3);
                hashset.insert(cur * 3);
            }
            if(!hashset.count(cur * 5)){
                pq.push(cur * 5);
                hashset.insert(cur * 5);
            }
            if(!hashset.count(cur * 7)){
                pq.push(cur * 7);
                hashset.insert(cur * 7);
            }
        }
        return cur;
    }
};

Normal Solution:
Thought: http://www.cnblogs.com/EdwardLiu/p/4322664.html
Generate ugly number through competition:
Time: O(n)
Space: O(n)
There are repeatations like 15 = 3 * 5 = 5 * 3, in this case, the i3 and i5 will proceed at the same time. So no repetations in result array.

class Solution {
public:
    /*
     * @param k: The number k.
     * @return: The kth prime number as description.
     */
     
    long long kthPrimeNumber(int k) {
        vector<long long> res(k + 1);
        res[0] = 1;
        int i3 = 0, i5 = 0, i7 = 0;
        for(int i = 1; i <= k;i++){
            long long cur = min(min(res[i3] * 3, res[i5] * 5), res[i7] * 7);
            if(cur == res[i3] * 3) i3++;
            if(cur == res[i5] * 5) i5++;
            if(cur == res[i7] * 7) i7++;
            res[i] = cur;
        }
        return res[k];
    }
   
};

2015年9月28日星期一

Lintcode: Merge k sorted lists

Codes and Thoughts reference:
http://bangbingsyb.blogspot.com/2014/11/leetcode-merge-k-sorted-lists.html

Priority queue solution:

Introduction to data structure of priority_queue:
http://m.zgxue.com/197/1977189.html

Great Explanation of how to rewrite compare function of priority_queue
http://www.cnblogs.com/iammatthew/archive/2010/08/19/1803935.html

C++ operator overloading
http://c.biancheng.net/cpp/biancheng/view/215.html

Time: O(nk*logk)
Space: O(k)

class Solution {
public:
    struct compNode {
        bool operator()(ListNode *p, ListNode *q) const {
            return p->val>q->val;
        }  
    };

    ListNode *mergeKLists(vector<ListNode *> &lists) {
        priority_queue<ListNode*, vector<ListNode*>, compNode> pq;
        ListNode *dummy = new ListNode(0), *tail = dummy;
        
        for(int i=0; i<lists.size(); i++) 
            if(lists[i]) pq.push(lists[i]);
            
        while(!pq.empty()) {
            tail->next = pq.top();
            tail = tail->next;
            pq.pop();
            if(tail->next) pq.push(tail->next);
        }
        
        return dummy->next;
    }
};

Merge two lists -- basic solution
n -- the maximum len of each list k -- the number of sorted lists
for merge two list O(m+n) ==> Portal to my leetcode Merge two sorted lists solution
here: n + 2n + 3n + ... + kn =((k+1)*k/2 - 1)*n

Time: O(nk^2)
Space: O(1)

/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param lists: a list of ListNode
     * @return: The head of one sorted list.
     */
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        ListNode *res = NULL;
        for(int i = 0; i < lists.size(); i++){
            res = merge(res, lists[i]);
        }
        return res;
    }
    ListNode* merge(ListNode *l1, ListNode *l2){
        ListNode* dummy = new ListNode(0);
        ListNode* cur = dummy;
        while(l1 && l2){
            if(l1->val < l2->val){
                cur->next = l1;
                l1 = l1->next;
            }
            else{
                cur->next = l2;
                l2 = l2->next;
            }
            cur = cur->next;
        }
        cur->next = l1 ? l1 : l2;
        return dummy->next;
    }
};

Bisection:
//thoughts
http://www.cnblogs.com/TenosDoIt/p/3673188.html

Time: O(nk*logk) ---- each level is O(nk) and there are logk levels
Space: O(1)

/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param lists: a list of ListNode
     * @return: The head of one sorted list.
     */
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        int end = lists.size() - 1;
        while(end){
            int begin = 0;
            while(begin < end){
                lists[begin] = merge(lists[begin], lists[end]);
                begin++;
                end--;
            }
        }
        return lists[0];
    }
    ListNode* merge(ListNode *l1, ListNode *l2){
        ListNode* dummy = new ListNode(0);
        ListNode* cur = dummy;
        while(l1 && l2){
            if(l1->val < l2->val){
                cur->next = l1;
                l1 = l1->next;
            }
            else{
                cur->next = l2;
                l2 = l2->next;
            }
            cur = cur->next;
        }
        cur->next = l1 ? l1 : l2;
        return dummy->next;
    }
};

Lintcode: Min Stack

Implement a stack with min() function, which will return the smallest number in the stack.

It should support push, pop and min operation all in O(1) cost.

Have you met this question in a real interview?

Yes

Example

Operations: push(1), pop(), push(2), push(3), min(), push(1), min() Return: 1, 2, 1

Note

min operation will never be called if there is no number in the stack

Reference my leetcode solution for the same problem:

class MinStack {
private:
    vector<int> data;
    int minV;
public:
    MinStack() {
        // do initialization if necessary
    }

    void push(int number) {
        // write your code here
        if(data.size() == 0) minV = number;
        else{
            int prev = minV + data.back();
            if(prev < minV) minV = prev;
        }
        data.push_back(number - minV);
    }

    int pop() {
        // write your code here
        int res = data.back() + minV;
        data.pop_back();
        if(data.back() < 0) minV = minV - data.back();
        return res;
    }

    int min() {
        // write your code here
        return ((data.back() + minV) < minV)?(data.back() + minV) : minV;
    }
};

Lintcode second:
Space: O(n)

class MinStack {
public:
    vector<int> data;
    vector<int> minData;
    MinStack() {
        // do initialization if necessary
    }

    void push(int number) {
        // write your code here
        data.push_back(number);
        if(minData.empty() || number <= minData.back()) minData.push_back(number);
    }

    int pop() {
        // write your code here
        if(data.back() == minData.back()) minData.pop_back();
        int res = data.back();
        data.pop_back();
        return res;
    }

    int min() {
        // write your code here
        return minData.back();
    }
};

Lintcode: longest consecutive sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

Have you met this question in a real interview?

Yes

Example

Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Clarification

Your algorithm should run in O(n) complexity.

Reference:
Thought:
http://yucoding.blogspot.com/2013/05/leetcode-question-129-longest.html
Codes:
http://bangbingsyb.blogspot.com/2014/11/leetcode-longest-consecutive-sequence.html

Time: O(n)
Space: O(n)

class Solution {
public:
    /**
     * @param nums: A list of integers
     * @return an integer
     */
    int longestConsecutive(vector<int> &num) {
        unordered_set<int> hash;
        for(int i = 0;i < num.size(); i++){
            hash.insert(num[i]);
        }
        int maxLen = 0;
        for(int i = 0; i < num.size(); i++){
            if(hash.empty()) break;
            int curLen = 0;
            int curNum = num[i];
            
            while(hash.count(curNum)){
                hash.erase(curNum);
                curLen++;
                curNum++;
            }
            curNum = num[i] - 1;
            while(hash.count(curNum)){
                hash.erase(curNum);
                curLen++;
                curNum--;
            }
            maxLen = max(maxLen, curLen);
        }
        return maxLen;
    }
};

Lintcode second:
Good codes
http://www.geeksforgeeks.org/longest-consecutive-subsequence/

Time: O(nlogn)
Space: O(1)

class Solution {
public:
    /**
     * @param nums: A list of integers
     * @return an integer
     */
    int longestConsecutive(vector<int> &num) {
        // write you code here
        if(num.size() == 0) return 0;
        //if(num.size() == 1) return 1;
        sort(num.begin(), num.end());
        int maxLen = 1;
        for(int i = 1; i < num.size(); i++){
            if(i == 0) continue;
            int tempLen = 1;
            while(i < num.size() && (num[i] == num[i - 1] + 1 || num[i] == num[i - 1])){
                if(num[i] == num[i - 1] + 1){
                    tempLen++;
                }
                i++;
            }
            maxLen = max(tempLen, maxLen);
        }
        return maxLen;
    }
};

Lintcode: Implement Queue by Two Stacks

As the title described, you should only use two stacks to implement a queue's actions.

The queue should support push(element), pop() and top() where pop is pop the first(a.k.a front) element in the queue.

Both pop and top methods should return the value of first element.

Have you met this question in a real interview?

Yes

Example

For push(1), pop(), push(2), push(3), top(), pop(), you should return 1, 2 and 2

Challenge

implement it by two stacks, do not use any other data structure and push, pop and top should be O(1) by AVERAGE.

class Queue {
   
public:
    stack<int> stack1;
    stack<int> stack2;
   
    Queue() {
        // do intialization if necessary
    }
 
    void push(int element) {
        // write your code here
        stack1.push(element);
    }
    
    int pop() {
        // write your code here
        move();
        int res;
        res = stack2.top();
        stack2.pop();
        return res;
    }

    int top() {
        // write your code here
        int res;
        move();
        res = stack2.top();
        return res;
    }
private:
    void move(){
        if(!stack2.empty()) return;
        while(!stack1.empty()){
            int temp;
            temp = stack1.top();
            stack1.pop();
            stack2.push(temp);
        }
    }
};

Lintcode: word break

Given a string s and a dictionary of words dict, determine if s can be break into a space-separated sequence of one or more dictionary words.

Have you met this question in a real interview?

Yes

Example

Given s = "lintcode", dict = ["lint", "code"].

Return true because "lintcode" can be break as "lint code".

Tags Expand

String Dynamic Programming

Reference:
http://bangbingsyb.blogspot.com/2014/11/leetcode-word-break-i-ii.html

s1: dp[i] -- can the beginning i char can be broken
s2: dp[i + 1] (0 <= i < s.size) ==> whether exists s[k--i] is in dictionary && dp[k] is true (whether s[0--k-1] is true)
s3: dp[0] = true

Time: O(n*n) -- n is len of string
Space: O(n)

class Solution {
public:
    /**
     * @param s: A string s
     * @param dict: A dictionary of words dict
     */
    bool wordBreak(string s, unordered_set<string> &dict) {
        // write your code here
        vector<bool> dp(s.size() + 1, false);
        dp[0] = true;
        
        //annotation part is used to pass lintcode, not necessary for leetcode
        // Filter out impossible string which alphabet set is not covered by dict.
        /*
        unordered_set<char> chrs;
        for (const auto& word : dict) {
            for (const auto& c : word) {
                chrs.insert(c);
            }
        } 
        for (const auto& c : s) {
            if (chrs.find(c) == chrs.end())
                return false;
        }
        */
        for(int i = 0; i < s.size(); i++){
            //string str = "";
            for(int k = i; k >= 0; k--){
                //str = s[k] + str;
                if(dp[k] && dict.count(s.substr(k, i - k + 1)) ){
                    dp[i + 1] = true;
                    break;
                }
            }
        }
        return dp[s.size()];
    }
};

2015年9月27日星期日

Lintcode: Backpack

Given n items with size Ai, an integer m denotes the size of a backpack. How full you can fill this backpack?

Have you met this question in a real interview?

Yes

Example

If we have 4 items with size [2, 3, 5, 7], the backpack size is 11, we can select [2, 3, 5], so that the max size we can fill this backpack is 10. If the backpack size is 12. we can select [2, 3, 7] so that we can fulfill the backpack.

You function should return the max size we can fill in the given backpack.

Note

You can not divide any item into small pieces.

Challenge

O(n x m) time and O(m) memory.

O(n x m) memory is also acceptable if you do not know how to optimize memory.

Reference:
http://www.code123.cc/docs/leetcode-notes/dynamic_programming/backpack.html

s1: D[i][j]: bool array ---- whether the amount j can be filled with the beginning i items;
s2: If not put current item into backpack: D[i][j] = D[i-1][j]
if put it into backpack: D[i][j] = D[i-1][j - A[i]]
s3: Initial condition: 0 <= i <= A.size() 0 <= j <= m
D[0][0] = 1; D[0][j] = 0; D[i][0] = 1;

Time: O(m*n)
Space: O(m*n)

class Solution {
public:
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A: Given n items with size A[i]
     * @return: The maximum size
     */
    int backPack(int m, vector<int> A) {
        // write your code here
        vector<vector<bool> > dp(A.size() + 1,vector<bool>(m + 1, false));
        dp[0][0] = true;
        for(int i = 1; i <= A.size(); i++){
            dp[i][0] = true;
        }
        for(int j = 1; j <= m; j++){
            dp[0][j] = false;
        }
        for(int i = 1; i <= A.size(); i++){
            for(int j = 1; j <= m; j++){
                
                if(j < A[i - 1]) dp[i][j] = dp[i - 1][j];
                else dp[i][j] = dp[i - 1][j] || dp[i - 1][j - A[i - 1]];
                //anotation part are supposed to be optimization
                //however, time limit when test, strange
                /*
                dp[i][j] = dp[i - 1][j];
                if((j >= A[i - 1]) && (dp[i - 1][j - A[i - 1]] == true)){
                    dp[i][j] = dp[i - 1][j - A[i - 1]];
                }*/
            }
        }
        for(int j = m; j >= 0; j--){
            if(dp[A.size()][j] == true) return j;
        }
    }
};

Optimization of the space:
Time: O(m*n)
Space: O(m)

class Solution {
public:
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A: Given n items with size A[i]
     * @return: The maximum size
     */
    int backPack(int m, vector<int> A) {
        // write your code here
        vector<bool>  res(m + 1, false);
        res[0]= true; 
        
        for(int i = 1; i <= A.size(); i++){
            for(int j = m; j >= 1; j--){
                /*
                if(j < A[i - 1]) res[j] = res[j];
                else{
                    res[j] = res[j] || res[j - A[i - 1]];
                }*/
                //simplify
                if(j >= A[i - 1] && res[j - A[i - 1]]) res[j] = true;
            }
        }
        for(int j = m; j >= 0; j--){
            if(res[j] == true) return j;
        }
    }
};

订阅：博文 (Atom)