leetcode Question 76: Regular Expression Matching

Regular Expression Matching

Implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

Analysis:

Note that this problem is NOT the same as Wildcard Matching.
The major difference is the meaning of  "*" in the string.
Here, "*" means 0 or more preceding element. For example, the last test case in the problem description:
    isMatch("aab",""c*a*b")
The pattern :  "c*a*b" means,  there can be 0 or more 'c', 0 or more 'a' and one b.
e.g., "ccaab", "aab", "ccb", "b" are all valid strings for this pattern, thus the correct answer for this test case is also true (0 'c', 2 'a' and 1 'b').

How to solve this question?  DFS!
Since we don't know how many "* element " is needed to get a match, one way is to search every possibilities. However in this problem, it is not complex because there are many restrictions, which seems even easier than the wildcard matching problem.

First of all, let's define "{x}" means 0 or more 'x' can be here in the string.
Using the above example, the problem can be rewritten as:
                             isMatch("aab" "{c}{a}b")

Then we can do the matching from the start of the two strings. The condition of a match between two elements s[i] and p[j] are:
(1) s[i]==p[j]
(2) s[i]!=p[j] but p[j]=='.'
Otherwise, 2 strings cannot have a match.

In the first case (s[i]==p[j]),
If p[j] is not a { }, (not followed by a *), we can just go to the next element (i++, j++).
If p[j] is a { } (followed by a *), zero or more p[j]s might be here.


How many time we need here to have multiple p[j]s?
Let's consider this problem in another way.
If it is zero p[j], then just search the next j (j++,i).
Otherwise, no matter how many we need, for the next element s[i+1], s[i+1] only knows it is now matching with {p[j]}. So, we can just search the current j with next i (j, i++).

For the end of the pattern, if all the remaining elements are { }, then it can all be empty so it is a match. Otherwise it is a false match.

To reduce the number of recursion, we know that, if p[j]==p[j+1] and they both are "{ }", then they can be considered as only one element with "{ }". Without this condition, your code might not pass the last test case in the OJ.

Code:

class Solution {
public:

    bool emp(int pm, vector<int> &vali){ //check if the remaining pattern can be empty or not
        if (pm==vali.size()){return true;}
        else{return vali[pm];}
    }

    bool match(string s,int sm, string p, int pm, vector<int> &stars, vector<int> &vali){
        if (sm<s.size() && pm==p.size()){ // if string is not ended but pattern is ended, it is a false
            return false;
        }
        if (sm>=s.size()){  //if the string is ended
            if (emp(pm,vali)){return true;} // if remaining pattern can be empty, it is a match
            else{return false;}
        }else{
            if (s[sm]!=p[pm] && p[pm]!='.'){ //if current elements not equal
                if (stars[pm]){ //if there can be zero p[pm].
                    return match(s,sm,p,pm+1,stars,vali); //search the next element
                }else{
                    return false;
                }
            }
            if (s[sm]==p[pm]||p[pm]=='.'){ //if current elements equal
                if (stars[pm]==1){ //if there can be 0 or more p[pm]
                    if(p[pm]==p[pm+1] && stars[pm+1]==1){ //if the next element is the same and also followed by *
                        return match(s,sm+1,p,pm+1,stars,vali);
                    }else{
                        ////////////////////search zero or more p[pm]///////////////////////
                        return match(s,sm,p,pm+1,stars,vali)||match(s,sm+1,p,pm,stars,vali); 
                        ////////////////////////////////////////////////////////////////////
                    }
                }else{
                    return match(s,sm+1,p,pm+1,stars,vali);
                }
            }
        }
    }

    bool isMatch(const char *s, const char *p) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        string str_s(s);
        string str_p(p);
        vector<int> stars;
        int i=0;
        while (i<=str_p.size()){  //rewrite the pattern string, store the elements followed with "*"
            if (str_p[i+1]=='*'){
                str_p.erase(i+1,1);
                stars.push_back(1);
            }else{
                stars.push_back(0);
            }
            i++;
        }
        
        vector<int> vali(str_p.size(),0); //if the remaining pattern are all with *, then vali[i]=1, otherwise 0
        i=str_p.size()-1;
        while(i>=0){
            if (stars[i]==1){vali[i--]=1;}
            else{break;}
        }
        
        return match(str_s,0,str_p,0,stars,vali);
    }

};

leetcode Question 107: Sudoku Solver

Sudoku Solver:

Write a program to solve a Sudoku puzzle by filling the empty cells.

Empty cells are indicated by the character '.'.

You may assume that there will be only one unique solution.

A sudoku puzzle...

Analysis:

I was running this program on the old OJ and always failed because of the "time limit exceeded".
On the new OJ, it seems there are only 6 test samples and my code below passed it using 2304ms.

The idea of this problem is just the searching (either DFS or BFS). In my code below I used BFS, tried to use more space less time. BFS is conducted according to each blank ('.' in this problem) cell, assign a valid number (char actually) satisfying no duplicates in the same row, column, as well as the local block. Then push the new status of the board into the BFS queue, keep searching until no blank cell exists.

Code:

class Solution {
public:
    bool find(vector<vector<char> > &cur, int &i, int &j){
        for (int ii=0;ii<9;ii++){
            for (int jj=0;jj<9;jj++){
                if (cur[ii][jj]=='.'){
                    i=ii;
                    j=jj;
                    return true;
                }
            }
        }
        return false;
    }
    
    unordered_set<char> valid(int i, int j, vector<vector<char> > &cur){
        unordered_set<char> se({'1','2','3','4','5','6','7','8','9'});
        for (int ii=0;ii<9;ii++){
            se.erase(cur[ii][j]);
            se.erase(cur[i][ii]);
        }
        
        for (int ii=0;ii<3;ii++){
            for (int jj=0;jj<3;jj++){
                se.erase(cur[(i/3)*3+ii][(j/3)*3+jj]);
            }
        }
        
        return se;
        
    }
    void solveSudoku(vector<vector<char> > &board) {
        queue<vector<vector<char> > > que;
        que.push(board);
        vector<vector<char> > cur;
        unordered_set<char> se;
        int i=0;
        int j=0;
        while (!que.empty()){
            cur = que.front();
            que.pop();
            if (find(cur,i,j)==false){
                board = cur;
                return;
            }else{
                se = valid(i,j,cur);
                for (const char& x: se){
                    cur[i][j]=x;
                    que.push(cur);  
                }
            }
        }
    }
};

leetcode Question: Word Break I

Word Break I

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

For example, given
s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

Analysis:

First thought is DFS (depth first search), searching every dict elements, if matched go to next position of s, until find the last match. Consider a very long s has a bunch of "a" and other letters, and the dict has "a", the searching will be pretty slow then.

Note that the problem asked for "if or not", which means we don't need to know which dicts compose string s, but only a "true/false" result.

Instead of search each element in the dict, search every position of the string is another way:
Say mp[i][j]=true if S[i to j] can be found in dict, mp[i][j]=false otherwise.  In this way, we now have a matrix (actually upper triangle of the matrix) which shows the initial matching of string S.

Next step, the question becomes:  find the value of mp[0][s.size()-1]. How to determine mp[i][j]?
We can see that, for all the mp[i][j]=false, if there exists a k (i<=k<j), mp[i][k]==true and mp[k+1][j]==true, then mp[i][j]=true. This means, if s[i to k] can be found in the dict, and, s[k+1 to j] can also be found in the dict, then s[i to j] is a valid match. In the code, just set mp[i][j]=mp[i][k]&&mp[k+1][j] will work well.

The complexity of this problem is O(n^3), where n is the length of the original string. The code below has been tested and passed all the test cases in the OJ.

Code:

class Solution {
public:
bool wordBreak(string s, unordered_set<string> &dict) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        if (s.empty()){return false;}
        vector<vector<bool> > mp(s.size(),vector<bool>(s.size(),false));
        
        for (int i=0;i<s.size();i++){
            for (int j=i;j<s.size();j++){
                if (dict.find(s.substr(i,j-i+1))!=dict.end()){
                    mp[i][j]=true;
                }
            }
        }
        
        for (int i=0;i<s.size();i++){
            for (int j=i;j<s.size();j++){
                for(int k=i;k<j;k++){
                    if (!mp[i][j]){
                        mp[i][j]=mp[i][k]&&mp[k+1][j];
                    }
                }
            }
        }
        
        return mp[0][s.size()-1];
    }
};

leetcode Question: LRU Cache

LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

Analysis:

This a more likely a design question other than a algorithm question, which requires us to choose the proper data structure and implement the "get", "set" methods.

At the first glance, a queue seems enough for this problem, because of its FIFO property. However,  the questions also requires "Recently", which means both "input" and "visit" are "recent actions" for the data. If you have the data "<1,1>"  the least recently used element in the queue <1,1> <2,2><3,3>, if method "get(1)" is called, "<1,1>" is now becoming the last (recently used) element in the queue. (<2,2,><3,3,><1,1>)

Consider the basic operations we need:
(1) Insert a new <key, value> pair to the end of the list.
(2) delete a <key, value> pair (if the cache is full).
(3) move a <key, value> pair to the end. (when it is used)
(3) change the value in a <key, value> pair and move it to the end.

Therefore,  a double linked list can handle the above methods well. A map<key, node*>  is a good way tracking the position of the node according to its key.

Be careful with the following cases:
(1) List is empty
(2) List has one node
(3) Initialization
(4) Don't forget delete the element in the map when it is removed from list.

Code:

class LRUCache{
  
//define the double linked list, each node stores both the key and value.
struct Node{
  Node* next;
  Node* prev;
  int value;
  int key;
  Node(Node* p, Node* n, int k, int val):prev(p),next(n),key(k),value(val){};
  Node(int k, int val):prev(NULL),next(NULL),key(k),value(val){};
};


map<int,Node*>mp; //map the key to the node in the linked list
int cp;  //capacity
Node* tail; // double linked list tail pointer
Node* head; // double linked list head pointer



public:
    //constructor
    LRUCache(int capacity) {
        cp = capacity;
        mp.clear();
        head=NULL;
        tail=NULL;
    }
    
    //insert node to the tail of the linked list
    void insertNode(Node* node){
        if (!head){
            head = node;
            tail = node;
        }else{
            tail->next = node;
            node->prev = tail;
            tail = tail->next;
        }
    }

    //remove current node
    void rmNode(Node* node){
        if (node==head){
            head = head->next;
            if (head){head->prev = NULL;}
        }else{
            if (node==tail){
                tail =tail->prev;
                tail->next = NULL;
            }else{
                node->next->prev = node->prev;
                node->prev->next = node->next;
            }
        }
    }

    // move current node to the tail of the linked list
    void moveNode(Node* node){
        if (tail==node){
            return;
        }else{
            if (node==head){
                node->next->prev = NULL;
                head = node->next;
                tail->next = node;
                node->prev = tail;
                tail=tail->next;
            }else{
                node->prev->next = node->next;
                node->next->prev = node->prev;
                tail->next = node;
                node->prev = tail;
                tail=tail->next;
            }
        }
    }


    ///////////////////////////////////////////////////////////////////////
    // get method
    ///////////////////////////////////////////////////////////////////////
    int get(int key) {
        if (mp.find(key)==mp.end()){
            return -1;
        }else{
            Node *tmp = mp[key];
            moveNode(tmp);
            return mp[key]->value;
        }
    }

    ///////////////////////////////////////////////////////////////////////
    // set method
    ///////////////////////////////////////////////////////////////////////
    void set(int key, int value) {
        if (mp.find(key)!=mp.end()){
            moveNode(mp[key]);
            mp[key]->value = value;
        }else{
            if (mp.size()==cp){
                mp.erase(head->key);
                rmNode(head);
            }
            Node * node = new Node(key,value);
            mp[key] = node;
            insertNode(node);
        }
    }
};

leetcode Question: Gas Station

Gas Station

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].
You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.
Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.
Note:
The solution is guaranteed to be unique.

Analysis:

The key to this problem is "Don't make it too complex!"

Yes, after trying loop(which works but with high complexity), recursion, and DP, I failed at first. After reading the problem carefully, I forget the condition "unlimited gas tank"! Actually given this condition, this problem can be solved in one loop.

The idea is: consider the case that, if started at station i, and when goes to the station j, there is not enough gas to go the j+1 station. What happened now? For the brutal force method, we go back to the sataion i+1 and do the same thing. But, actually, if the accumutive gas cannot make it from j to j+1, then the stations from i to j are all not the start station. That is because, (1)the tank is unlimited, every time arrive to the station, the tank will fuel the max gas here, and comsume the cost to go to the next. (2)There can not be negative tank when arriving a station, at least the tank is empty. So, if i to j cannot go to j+1, then i+1 to j still cannot go to j+1... In this way, the next starting station we will try is not i+1, but the j+1. And after a single loop from i to j, we can find the result!

Code:

class Solution {
public:
    int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
        int n = gas.size();
        if (n==0){return -1;}
        int i=0;
        int j=0;
        int tank=0;
        while (true){
            if (j>=n){return i;}
            int net;
            if (i+j>=n){
                net = gas[i+j-n]-cost[i+j-n];
            }else{
                net = gas[i+j]-cost[i+j];
            }
            if (tank+net<0){
                j++;
                i=i+j;
                if (i>=n){return -1;}
                tank=0;
                j=0;
            }else{
                tank+=net;
                j++;
            }
        }
    }
};

leetcode Question: Copy List with Random Pointer

Copy List with Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

Analysis:

This problem returns a new linked list, which has the same value and structure of the original one. First we can create a new linked list without considering the Random pointer, which is straight forward:  Scan every node in the original list and create the new list (line 21- 27 in the code below).

But how to keep the random pointer also correct ? If we only point the new random pointer to the original random pointer, which is not a deep copy (since the deletion of nodes in original list will delete the new one as well).  So, how to memorize the relative position of the random node to the current node? Firstly I think to use the length from head node to the random node. For each node, I stored the position of its random node, same position node in the new list is the random node for the node in the new list. This idea can work, but is not efficient. For every node you have to search from the start to the end to find the random, the total complexity is O(n^2). Can we quickly locate the position of the node?  Yes!  Hash map!  A map with the node as key and node as the value can finish the job! We can use the original list node as the key, and the same node in the new list as the value.  Now the map[node_old] = node_new, therefore the node_new->random = map[node_old->random]. In this way, the complexity decreases to O(n).

Code:

/**
 * Definition for singly-linked list with a random pointer.
 * struct RandomListNode {
 *     int label;
 *     RandomListNode *next, *random;
 *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
 * };
 */
class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        if (!head){return NULL;}
        map<RandomListNode*,RandomListNode*> mp; //map <originalNode, newNode>
        mp.clear();
        RandomListNode *res=new RandomListNode(0);
        RandomListNode *p=head;
        RandomListNode *q=res;
        
        while (p){
            RandomListNode *tmp = new RandomListNode(p->label);
            q->next = tmp;
            mp[p]=tmp;
            p=p->next;
            q=q->next;
        }
        p=head;
        q=res->next;
        while (p){
            if (p->random==NULL){
                q->random==NULL;
            }else{
                q->random = mp[p->random];
            }
            p=p->next;
            q=q->next;
        }
        return res->next;
    }
};

leetcode Question: Reorder List

Reorder List

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You must do this in-place without altering the nodes' values.

For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.

Analysis:

Let's see some examples:

{1,2,3,4,5,6} ---> {1,6,2,5,3,4}
{1,2,3,4,5,6,7} ---> {1,7,2,6,3,5,4}

One straightforward middle step of such reordering is:
{1,2,3,4,5,6}  --> {1,2,3,6,5,4} --> {1,6,2,5,3,4}
{1,2,3,4,5,6,7}---> {1,2,3,4,7,6,5} ---> {1,7,2,6,3,5,4}

By reversing the last part of the linked list, we do not need to worried about the "parent" pointer anymore. The final step is just insert the each element in the last part into the first part (every two element).

So the algorithm implemented below can be summarized as:
Step 1  Find the middle pointer of the linked list (you can use the slow/fast pointers)
Step 2  Reverse the second part of the linked list (from middle->next to the end)
Step 3  Do the reordering. (inset every element in the second part in between the elements in the first part)

Code:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode *head) {
        if (!head){return;}
        if (head->next==NULL){return;}
        ListNode *p=head; 
        ListNode *q=head; 
        
        //find the midddle pointer
        while (q->next && q->next->next){
            p=p->next;
            q=q->next->next;
        }
        
        //now p is middle pointer
        //reverse p->next to end
        q = p->next;
        while (q->next){
            ListNode* tmp = p->next;
            p->next = q->next;
            q->next = q->next->next;
            p->next->next = tmp;
        }
        
        //reorder
        q = head;
        while (p!=q && p->next){
            ListNode* tmp = q->next;
            q->next = p->next;
            p->next = p->next->next;
            q->next->next = tmp;
            q=q->next->next;
        }
        return;
    }
};

leetcode Question: Insertion Sort List

Insertion Sort List

Sort a linked list using insertion sort.

Analysis:

The insertion sorting on array can be found in my previous post (here).
The general idea is insert the current element A[i] into the proper position from A[0]...A[i-1], and A[0]...A[i-1] is already sorted.

In this problem, we can use the same idea and linked list provides a more efficient way for insertion.  Details can be found in the code below. Note that after the insertion, the position of P is unchanged but should not provide another p=p->next operation.

Code:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *insertionSortList(ListNode *head) {
        if (!head){return NULL;}
        ListNode *p=new ListNode(0);
        p->next = head;
        head = p;
        ListNode *q;
        
        while (p->next!=NULL){
            q = head;
            bool flag = false;
            while (q!=p){
                if (q->next->val>p->next->val){
                    ListNode* tmp1=p->next;
                    p->next =p->next->next;
                    tmp1->next = q->next;
                    q->next = tmp1;
                    flag =true;
                    break;
                }else{
                    q=q->next;    
                }
            }
            if (!flag){
                p=p->next;
            }
        }
        return head->next;
    }
};

leetcode Question: Max Points on a Line

Max Points on a Line

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

Analysis:

First of all, how to know the points are on the same line?  The slope!
The slope of a line can be computed using any two points (x1,y1) (x2,y2) on the line:
 slop = (y2-y1)/(x2-x1) , x2!=x1.

In this problem, we want to know the max number of points on one line. We can think in this way: for every single point, all the possible lines (slopes) which goes across this point and any other point in the plane can be easily computed. Why? Because at least two points can determine a line, if one point is now fixed, use every other point can get all the lines.  For all these lines, they have the same starting point, so if two lines La--Lb and La--Lc have same slope, points a,b and c are actually on the same line. See figure below:

So, we can have a loop from the 1st point to the last point. Within this loop, we compute the slopes from this point to every other point. Then find the max number of points, which has the same slope. e.g., in the figure above, for point 1 (p1), the slops computed are
S:[s11,s12,s13,s14,s15,s16].
Say, s11 to s16 are six lines connecting p1 and p2,3,4,5,6 respectively. If s1i==s1j, i!=j, then p1, pi and pj are on the same line. The maximum number of points on the same line here in this one iteration is the max number of same slopes in S. Once we have this number in one iteration, the max number of all the iterations is what we want.

The algorithm goes like this:
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
for each point i in the plane:
    for each point j in the plane:
          if i!=j,
             Compute and store the slop
    Sort the slop array
    Count how many slops are the same
    Store the max number

Output the max number
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


Note:

(1) The slop is computed using "/", if (x2-x1)==0, there will be an error, but in the 2D plane it is a valid line (vertical line). So, store the vertical line as a specific slope is needed.

(2) Remember to consider the input points have duplicates. In my code, I only consider the duplicates with the starting point in each loop, the slop is not computed then but the number of duplicates are stored instead. Also be careful with all the input points are the same case.

See code for more details.


The complexity of this problem is :   O(n*nlgn).    n is the big loop i, nlgn is the sorting complexity (O(nlgn)>O(n))

Code(C++):

/**
 * Definition for a point.
 * struct Point {
 *     int x;
 *     int y;
 *     Point() : x(0), y(0) {}
 *     Point(int a, int b) : x(a), y(b) {}
 * };
 */
class Solution {
public:
    int maxPoints(vector<Point> &points) {
        int n = points.size(); //number of the points
        if (n<=2){return n;}   
        vector<double> k; //vector to store the slops for one point with all the other points
        int res = 0;
        
        for (int i=0;i<n;i++){ // for each point in the 2d plane
            k.clear();
            int dup = 1; // number of the duplicates with currrent point
            for (int j=0;j<n;j++){ 
                if (i!=j){ // for every other point
                    if (points[i].x-points[j].x==0){ // if the slope is a vertical line
                        if (points[i].y-points[j].y==0){ // if the point j is the same as point i
                            dup++;  
                        }else{
                            k.push_back(99999); //store the vertical line to a specific slope
                        }
                    }else{ // if it is the regular slop between point i and j
                        k.push_back(10000*(points[i].y-points[j].y)/(points[i].x-points[j].x)); // store the slope
                    }
                }
            }
            
            sort(k.begin(),k.end()); //sort the slopes for counting
            
            int pp = 1; //number of points in the same line of the point i
            if (k.size()==0){pp=0;} 

            for (int jj=1;jj<k.size();jj++){ //count pp
                if (k[jj]==k[jj-1]){
                    pp++;
                }else{
                    if (pp+dup>res){res=pp+dup;} // res = pp + the number of duplicates
                    pp = 1;
                }
            }
            if (pp+dup>res){res = pp+dup;}
        }

        return res;
    }
};

Code(Python):

# Definition for a point
# class Point:
#     def __init__(self, a=0, b=0):
#         self.x = a
#         self.y = b

class Solution:
    # @param points, a list of Points
    # @return an integer
    def maxPoints(self, points):
        if (len(points)<=2):
            return len(points)
        m = 0 #result value
        for i in range(0, len(points)):
            l = {}  #every time reset the dict
            dup = 1 #count the duplicates
            for j in range(0, len(points)):
                if (points[i].x==points[j].x and points[i].y==points[j].y and i!=j):        
                    dup+=1  #count duplicates
                elif i!=j :
                    if (points[i].x==points[j].x):  #vertical line
                        l['v'] = l.get('v',0) + 1
                    elif (points[i].y==points[j].y): # horizontal line
                        l['h'] = l.get('h',0) + 1
                    else:   #regular slope
                        slope = 1.0*(points[i].y-points[j].y)/(points[i].x-points[j].x)
                        l[slope] = l.get(slope,0)+1
            if (len(l)>0): 
                m = max(m,max(l.values())+dup)
            else: #if all points are duplicates, l is empty.
                m = max(m,dup)
        return m
                
        

leetcode Question: Binary Tree Postorder Traversal (iteration)

Binary Tree Postorder Traversal (iteration)

Given a binary tree, return the postorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [3,2,1].

Note: Recursive solution is trivial, could you do it iteratively?

Analysis:

Classical problem,  the recursion version of the solution can be easily found by modifying here. In this post, I solved it iteratively.  Which data structure do remind us ?  Yes! Still stack!

The algorithm has following steps, which is slight different from the previous question:
(1) Push the root node into the stack.
(2) while the stack is not empty, do:
       if 
          the top node is a leaf node (no left&right children), pop it.
          or if the top node has been visited, pop it. (here we use a sign head to show the latest popped node, if the top node's child = the latest popped node, either left or right, it must has been visited.)
       else
          b. push the right child of the top node (if exists)
          c. push the left child of the top node (if exists)

Code (C++):

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> postorderTraversal(TreeNode *root) {
        stack<TreeNode*> st;
        vector<int> res;
        if (!root){return res;}
        st.push(root);
        TreeNode* head=root;
        while (!st.empty()){
            TreeNode* top = st.top();
            if ((top->left==NULL && top->right==NULL)||top->right==head || top->left==head){
                res.push_back(top->val);
                st.pop();
                head = top;
            }else{
                if (top->right!=NULL){st.push(top->right);}
                if (top->left!=NULL){st.push(top->left);}
            }
        }
        return res;
    }
};

Code(Python):

# Definition for a  binary tree node
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    # @param root, a tree node
    # @return a list of integers
    def postorderTraversal(self, root):
        res = []
        st = []
        if root != None:
            st.append([root,False])
            while len(st) != 0:
                tmp = st[-1]
                if tmp[1] == True:
                    res.append(st.pop()[0].val)
                elif tmp[0].left == None and tmp[0].right == None:
                    res.append(st.pop()[0].val)
                else:
                    st[-1][1] = True
                    if tmp[0].right != None:
                        st.append([tmp[0].right, False])
                    if tmp[0].left != None:
                        st.append([tmp[0].left, False])
        return res
        
        

        

leetcode Question: Binary Tree Preorder Traversal (iteration)

Binary Tree Preorder Traversal (iteration)

Given a binary tree, return the preorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [1,2,3].

Note: Recursive solution is trivial, could you do it iteratively?

Analysis:

Classical problem,  the recursion version of the solution can be found here (you need do slight modification, can you do that?) . In this post, I solved it iteratively.  Which data structure do remind us ?  Yes! Stack!

The algorithm has following steps:
(1) Push the root node into the stack.
(2) while the stack is not empty, do:
       a. pop the top node and print it.
       b. push the right child of the top node (if exists)
       c. push the left child of the top node (if exists)

Code(C++):

/**
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode *root) {
        stack<TreeNode*> st;
        vector<int> res;
        if (!root){return res;}
        st.push(root);
        TreeNode* head=root;
        while (!st.empty()){
            TreeNode* top = st.top();
            res.push_back(top->val);
            st.pop();
            if (top->right!=NULL){st.push(top->right);}
            if (top->left!=NULL){st.push(top->left);}
        }
        return res;
    }
};

Code(Python):

# Definition for a  binary tree node
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    # @param root, a tree node
    # @return a list of integers
    def preorderTraversal(self, root):
        res = [] 
        st = []
        if root != None:
            st.append(root)
            while len(st) != 0:
                tmp = st.pop()
                res.append(tmp.val)
                if (tmp.right != None):
                    st.append(tmp.right)
                if (tmp.left != None):
                    st.append(tmp.left)
        return res

 

leetcode Question: Evaluate Reverse Polish Notation

Evaluate Reverse Polish Notation

    Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Some examples:

  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

Analysis:

This is a classical algorithm question. The polish notation is the similar to the postorder traversal of the binary tree, and can be efficiently solved using the data structure-----stack.

The concept is:
When meeting the number, push into the stack.
When meeting the operator, pop the top 2 number and compute the value, then push the result back into the stack.
Until the end of the expression.
Output the top (last) value in the stack.

Details can be seen in the code below, there is some points need to be careful with, e.g. the order the the two numbers for the operator.

Code(C++):

class Solution {
public:
    int evalRPN(vector<string> &tokens) {
        stack<int> st;
        string op = "+-*/"; //to check the operator
        if (tokens.size()==0){return 0;}
        for (int i = 0; i<tokens.size();i++){
            string tok = tokens[i];
            int o =op.find(tok); //operator number
            if (o!=-1){
                if (st.size()<2){return -1;}
                else{
                    int a = st.top();
                    st.pop();
                    int b = st.top();
                    st.pop();
                    if (o==0){st.push(b+a);} //remember the order is b -> a
                    if (o==1){st.push(b-a);}
                    if (o==2){st.push(b*a);}
                    if (o==3){st.push(b/a);}
                }
            }else{
                st.push(atoi(tok.c_str()));
            }
        }
        return st.top();
    }
};

Code (Python):

class Solution:
    # @param tokens, a list of string
    # @return an integer
    def evalRPN(self, tokens):
        l=[]
        for str in tokens:
            if (str in ["+","-","*","/"]):
                a = l.pop()
                b = l.pop()
                if (str=="+"):
                    l.append(b+a)
                if (str=="-"):
                    l.append(b-a)
                if (str=="*"):
                    l.append(b*a)
                if (str=="/"):
                    #Be careful! "/" in python is different from C++ 
                    l.append(int(b/(a*1.0)))    
            else:
                l.append(int(str))
        return l[0]
                
            

How to use C++ STL heap? A toy example

How to use C++ STL heap?

In my previous post (click here), heap sort algorithm is presented You can also find the basic concept of the heap and how heap data structure is created and maintained. Generally speaking, heap is a tree structure where its parent node is the biggest(max heap) or smallest(min heap) of the values. Note that heap is NOT the BST, by traversing the tree cannot lead you to the sorted sequence as BST.


So, in our daily use or for the interview, sometime you don't have to implement the heap but using it is required. For example, let's see the toy example (this is also an interview question) below:

• How to find pair with kth largest sum? Given two sorted arrays of numbers, we want to find the pair with the kth largest possible sum. (A pair is one element from the first array and one element from the second array). For example, with arrays:

          A [2, 3, 5, 8, 13]
          B [4, 8, 12, 16]
          The pairs with largest sums are
          13 + 16 = 29
          13 + 12 = 25
          8 + 16 = 24
          13 + 8 = 21
          8 + 12 = 20
         So the pair with the 4th largest sum is (13, 8). How to find the pair with the kth largest    possible sum?



Analysis:
When the problem requires the largest, smallest, most frequent, etc. element in a big range of data, or the data is not 'static' but in stream, using heap is a good direction to try (always with the hashmap). For this problem, a max heap can be created according to the sum value, which is the sum of the two values in A and B array respectively. For better illustration, we consider the sorted arrays are in descending order (A[13,9,5,3,2], B[16,12,8,4]).

The algorithm is straightforward it you are familiar with the heap data structure:


(1) Push the A[0],B[0] into the heap.
(2) Do the following k times:
                 Pop the top node (A[i],B[j]) in the heap and output it.
                 Push the A[i+1],B[j] and A[i],B[j+1] into the heap.
(3) Update the heap

In C++ STL, heap can be created using the make_heap , which is in the <algorithm> lib.
And pop_heap, push_heap is used to add and remove element in the heap.
Below I show the code for this problem and you can see how to use the heap with STL:

Code:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;


bool _cmp(pair<pair<int,int>, int> a, pair<pair<int,int>, int> b){
    return a.second < b.second;
}

int main()
{
    //Initialize the data
    int a[5]= {13,2,3,8,5};
    int b[4] = {8,4,16,12};
    vector<int> A(a,a+5);
    vector<int> B(b,b+4);
    sort(A.rbegin(),A.rend());  // rbegin to get the descending order
    sort(B.rbegin(),B.rend());
    //Print the sorted array
    cout << "Original Arrays: "<< endl;
    for (int i=0;i<A.size();i++){cout << A[i] <<" ";}
    cout <<endl;
    for (int i=0;i<B.size();i++){cout << B[i] <<" ";}
    cout <<endl;

    //Use pair<<id_A,id_B>, A[id_A]+B[id_B]> as the node in the heap
    vector <pair<pair<int,int>, int> > C; // vector to maintain the heap.
    C.push_back(make_pair(make_pair(0,0),A[0]+B[0])); //push the first node
    make_heap(C.begin(),C.end(),_cmp); // make the heap

    int n =5; //get the first 5 biggest pairs
    for (int i=0;i<n;i++){
        pair<pair<int,int>, int> hroot = C.front(); // get the root of the heap (biggest sum)
        int maxi = hroot.first.first;
        int maxj = hroot.first.second;
        cout << "[" << A[maxi] << "," << B[maxj]<< "]," << hroot.second << endl;
        //pop the root node
        pop_heap(C.begin(),C.end(),_cmp);
        C.pop_back();

        //push the two new nodes
        C.push_back(make_pair(make_pair(maxi+1,maxj),A[maxi+1]+B[maxj]));
        push_heap(C.begin(),C.end(),_cmp);

        C.push_back(make_pair(make_pair(maxi,maxj+1),A[maxi]+B[maxj+1]));
        push_heap(C.begin(),C.end(),_cmp);

    }
    return 0;
}

leetcode Question: Linked List Cycle II

Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Follow up:
Can you solve it without using extra space?

Analysis:

This problem can be viewed as two major steps:
    (1) Detect whether the loop exists in the linked list.
    (2) Find the loop start node if loop exists.

The (1) step can be easily solved using the slow&fast pointers (see Linked List Cycle)
How to deal with step (2)?

Firstly let us assume the slow pointer (S) and fast pointer (F) start at the same place in a n node circle. S run t steps while F can run 2t steps, we want to know what is t (where they meet) , then
just solve:  t mod n = 2t mod n,  it is not hard to know that when t = n, they meet, that is the start of the circle.

For our problem, we can consider the time when S enter the loop for the 1st time, which we assume k step from the head. At this time, the F is already in k step ahead in the loop. When will they meet next time?
Still solve the function:    t mod n = (k + 2t) mod n
Finally, we can find out: t = (n-k), S and F will meet, this is k steps before the start of the loop.

So, the Step (2) can be easily solved after Step(1):
Note that here S and F are not slow or fast pointers, but only regular pointers.
1. Set S to the head.
2. S = S -> next, F = F->next
3. output either one of the pointer until they meet.

Here I show some figure for better illustration:
Note that, from step 5, p (slow pointer) firstly enter the loop, it will go (n-k) steps, and meet with fast pointer q. The rest of step is n-(n-k) = k, steps from current meet point, back to the start of the loop.

Code(C++):

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if (!head){return NULL;}
        ListNode *p=head;
        ListNode *q=head;
        while (1){
            if (p->next!=NULL){p=p->next;}else{return NULL;}
            if (q->next!=NULL && q->next->next!=NULL){q=q->next->next;}else{return NULL;}
            if (p==q){ //if find the loop, then looking for the loop start
                q=head;
                while (p!=q){
                    p=p->next;
                    q=q->next;
                }
                return p;
            }
        }
    }
};

Code(python):

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head:
            return None
        p = head
        q = head
        while True:
            if p.next:
                p = p.next
            else:
                return None
            if q.next and q.next.next:
                q = q.next.next
            else:
                return None
            if p == q:
                q = head
                while p!=q:
                    p = p.next
                    q = q.next
                return p