LineIntersections(Redux)

 

LineIntersections

 

http://www.cs.toronto.edu/~robere/csc373h/files/A2-sol.pdf
search "3. Line Intersections (Redux)"

 

 

Decode Ways

Decode Ways
A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.
For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).
The number of ways decoding "12" is 2.

 

1. Dynamic Programming
class Solution {
public:
   
    int numDecodings(string s) {
       int n = s.length();
       if (n < 1) return 0;
       if (s[0] == '0') return 0;
       
       vector<int> ways(n+1, 0);
      
        ways[0] = 1, ways[1] = 1;
        
        for(int i = 2; i <= n; i++) {
            ways[i] = ways[i-1];
            if (s[i-1] == '0') {
                if (s[i-2] == '0' || s[i-2] > '2')
                  return 0;
                else
                  ways[i] = ways[i-2];
            }
            else {
                if ((s[i-2] == '1') || (s[i-2] == '2' && s[i-1] < '7')) ways[i] += ways[i-2];
            }
        }
       
        return ways[n];
    }
};

2. Notice we look up from no more than two previous result. We can use something similar to calculating Fibonacci series:
class Solution {
public:
    int numDecodings(string s) {
       int n = s.length();
       if (n < 1) return 0;
       int T_2 = 1, T_1 = 1;
        
       for(int i =0 ; i < n; i++) {
          int T = T_1;
          if (s[i] == '0') {
              if (i == 0 ||(s[i-1] == '0' || s[i-1] > '2'))
                return 0;
              else
                T = T_2;
          }
          else if (i > 0 && (s[i-1] == '1' || (s[i-1] == '2' && s[i] < '7')))
            T+= T_2;
         
          T_2 = T_1;
          T_1 = T;
       }
       
       return T_1;
    }
};

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

 
Solution 1, Recursion:

 bool isMatch(const char *s, const char *p) {
        if (!*p) return !*s;
       
        if (*(p+1) != '*') { return (*p == *s ||(*s && *p == '.')) && isMatch(s+1, p+1);}
       
        while(*s == *p || (*p == '.' && *s)) {
            if (isMatch(s, p+2)) return true;
            s++;
        }
        return isMatch(s, p+2);
    }

Solution 2. DP

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
       if (!*p) return !*s;
       int m = strlen(p);
       int n = strlen(s);
      
       vector<vector<bool>> match(m+1, vector<bool>(n+1, false));
      
       match[0][0] = 1;
       match[1][1] = s[0] == p[0] || p[0] == '.';
      
       // When s is empty, but p = '.*', p matches s
       for(int i = 2; i <=m; i++)
           match[i][0] = p[i-1] == '*'? match[i-2][0] : false;
       // starting from second char in p
       for(int i = 2; i <= m; i++)
           for(int j = 1; j <= n; j++)
              if (p[i-1]== '*')
                match[i][j] = isSame(s[j-1], p[i-2])? match[i-2][j] || match[i-2][j-1] || match[i-1][j-1] || match[i][j-1] : match[i-2][j];
             else 
                match[i][j] = isSame(s[j-1], p[i-1]) && match[i-1][j-1];
          
       
        return match[m][n];
    }
   
    bool isSame(char a, char b){
        return (a == b || b=='.');
    }
};

Edit Distance

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)
You have the following 3 operations permitted on a word:
a) Insert a character
b) Delete a character
c) Replace a character

 
//
//   D[i][j] = | D[i-1][j-1])  A[i] == A[j]
//             |
//             | 1 + min(D[i][j-1], D[i-1][j], D[i-1][j-1])   A[i] != A[j]
//
class Solution {
public:
    int minDistance(string A, string B) {
       
        int m = A.size();
        int n = B.size();
        vector<int> D(n + 1, 0);
       
        for(int j = 0; j <=n; j++)
           D[j] = j;
       
        for(int i = 1; i <= m; i++) {
          int D_i_1_j_1 = i-1; // D[i-1][0]
          D[0] = i;  // D[i][0]
         
          for(int j = 1; j <= n; j++) {
              int T = A[i-1] == B[j-1] ? D_i_1_j_1 : 1 + min(D[j-1], min(D[j], D_i_1_j_1));
              D_i_1_j_1 = D[j];
              D[j] = T;
          }
        }
        return D[n];
    } 
};

// DP2
class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.length();
        int n = word2.length();
        if(m == 0) return n;
        if(n==0) return m;
       
        vector<vector<int>> map(m+1);
        for(int i = 0;i  < m+1; i++)
           map[i] = vector<int>(n+1, 0);
        for(int i = 0; i <=m; i++)
   map[i][0] =i;
  for(int i = 0; i <=n; i++)
   map[0][i] =i;
        for (int i = 1; i <=m; i++)
         for (int j = 1; j <=n; j++)   
          {
              if (word1[i-1] == word2[j-1])
                 map[i][j] = map[i-1][j-1];
              else {
                 map[i][j] = min(map[i-1][j], map[i][j-1]);
                 map[i][j] = min(map[i][j], map[i-1][j-1]);
                 map[i][j] +=1;
              }
          }
            
        return map[m][n];
   
    }
};

// DP 3

class Solution {
public:
    int minDistance(string word1, string word2) {
        int l1 = word1.size();
        int l2 = word2.size();
        vector<int> f(l2+1, 0);
        for (int j = 1; j <= l2; ++j)
            f[j] = j;
        for (int i = 1; i <= l1; ++i)
        {
            int prev = i;
            for (int j = 1; j <= l2; ++j)
            {
                int cur;
                if (word1[i-1] == word2[j-1]) {
                    cur = f[j-1];
                } else {
                    cur = min(min(f[j-1], prev), f[j]) + 1;
                }
                f[j-1] = prev;
                prev = cur;
            }
            f[l2] = prev;
        }
        return f[l2];
    } 
};

Valid Number

Valid Number
Validate if a given string is numeric.
Some examples:
"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true
Note: It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one.

 
// Sol1 http://www.mitbbs.com/article_t1/JobHunting/32787241_0_2.html
class Solution {
public:
    bool isNumber(const char *s) {
       if (!s) return false;
      
       while(*s == ' ')
         s++;
       
       // sign
       if (*s == '+' || *s == '-')
         s++;
        
       int n = getDigits(s);
      
       if (*s == '.') {
           s++;
           n += getDigits(s);
       }
      
       // digits before and after '.' must > 0, ".1" is valid
       if (n < 1) return false;
      
       if (*s == 'e') {
          s++;
          if (*s == '+' || *s == '-')
            s++;
          n = getDigits(s);
          if (n < 1) return false;
       }
      
       // trailing spaces is fine.
       while(*s == ' ') s++;
       return *s == NULL;
    }
   
    // count valid digits and move pointer
    int getDigits(const char *&s){
        int count = 0;
        while (*s >='0' && *s <='9'){
            count++;
            s++;
        }
        return count;
    }
};




// http://n00tc0d3r.blogspot.com/2013/06/valid-number.html
class Solution {
public:
    bool isNumber(const char *s) {
       int fsm[][9] = { 
                     {0, 8, -1, -1, 8, -1, -1, 8, 8}, 
                     {2, -1, -1, -1, -1, 6, -1, -1, -1}, 
                     {1, 1, 1, 4, 4, 7, 7, 7, -1}, 
                     {3, 4, 3, -1, -1, -1, -1, -1, -1}, 
                     {-1, 5, -1, -1, 5, -1, -1, -1, -1} 
                   }; 
        int state = 0;
        while(*s)
        {
            int in = getInput(s);
            if (in < 0) return false;
            state = fsm[in][state];
            if (state < 0) return false;
            s++;
        }
        return state == 1 || state == 4 || state == 7 || state == 8;
    }
   
    // Space(0), Sign(1), Digit(2), Dot(3), Exp(4), Else(-1); 
    int getInput(const char *s) {
        int out = -1;
        switch (*s) {
            case ' ': return 0;
            case '+':
            case '-': return 1;
            case '.': return 3;
            case 'e': return 4;
        }
       
        if (*s >='0' && *s <='9') return 2;
       
        return -1;
    }
};

Wildcard Matching

Wildcard Matching
Implement wildcard pattern matching with support for '?' and '*'.

'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).

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", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false

 
// Solution 1
class Solution {
public:
    bool isMatch( const char *s, const char *p) {
       while(*s && *p != '*') {
           if (*s != *p && *p != '?') return false;
           s++;
           p++;
       }
      
       const char *ps = NULL;
       const char *pp = NULL;
       while(*s) {
           if (*p == '*') {
               if (!*++p) return true;
               ps = s;
               pp = p;
           }
           else if (*s == *p || *p== '?') {
               s++; p++;
           }
           else {
               s = ++ps;
               p = pp;
           }
       }
      
       while(*p == '*') p++;
      
       return !*p;
    }
};




 


// Solution 2 similar to 1 but a little more concise
 bool isMatch( const char *s, const char *p) {
        const char *ps = NULL;
        const char *pp = NULL;
       
        while(*s) {
            if (*p == '*') {
                if (!*++p)  return true;
                ps = s + 1;
                pp = p;
            }
            else if (*s == *p || *p == '?') {
                s++;
                p++;
            }
            else if (ps)
            {
               s = ps++;
               p = pp;
            }
            else return false;
        }
       
        while(*p == '*') p++;
       
        return !*p;
    }




Binary Tree Postorder Traversal

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

    /*Method 1
    vector<int> postorderTraversal(TreeNode *root) {
      vector<int> output;
      if (!root) return output;
       
       TreeNode *prev = NULL;   
       stack<TreeNode *> st;
       st.push(root);
       while(!st.empty())
       {
           TreeNode *cur = st.top();
           if (!cur->left && !cur->right) {
               output.push_back(cur->val);
               st.pop();
           }
           if (cur->right) {
              st.push(cur->right);
              cur->right= NULL;
           }
           if (cur->left) {
              st.push(cur->left);
              cur->left = NULL;
           }
       }
       
       return output;
    } 
    
    // Method 2
    vector<int> postorderTraversal(TreeNode *root) {
      vector<int> output;
      if (!root) return output;
       
       TreeNode *prev = NULL;   
       stack<TreeNode *> st;
       stack<TreeNode *> st2;
       st.push(root);
       while(!st.empty())
       {
           TreeNode *cur = st.top();
           st.pop();
           st2.push(cur);
           if (cur->left) 
              st.push(cur->left);
           if (cur->right)
              st.push(cur->right);
       }
       
       while(!st2.empty()){
           TreeNode *cur = st2.top();
           st2.pop();
           output.push_back(cur->val);
       }
       return output;
    }
    
    // Method 3
    vector<int> postorderTraversal(TreeNode *root) {
      vector<int> output;
       stack<TreeNode *> st;
       while(!st.empty() || root)
       {
           if (!root)
           {
              while(!st.empty() && root==st.top()->right)
              {
                  root= st.top();
                  st.pop();
                  output.push_back(root->val);
              } 
              root= st.empty()? NULL : st.top()->right;
           }
           else 
           {
               st.push(root);
               root = root->left; 
           }
       }
       
       return output;
    }
    */
    
    // Simple coder's solution
    vector<int> postorderTraversal(TreeNode *root) {
        vector<int> output;
        stack<TreeNode*> st;
      
        TreeNode *prev = NULL;  
        pushLeft(root, st);
        while (!st.empty()) {
            root = st.top();
            if (prev == root->left && root->right)
            {
               pushLeft(root->right, st);
               prev = NULL;
            }
            else
            {
                output.push_back(root->val);
                st.pop();
                prev = root;
            }
        }

        return output;
    }
    
   void pushLeft(TreeNode *root, stack<TreeNode *> &st)
   {
       while(root) {
           st.push(root);
           root = root->left;
       }
   }
};

Clone Graph

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

OJ's undirected graph serialization: Nodes are labeled uniquely.
We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.
As an example, consider the serialized graph {0,1,2#1,2#2,2}.
The graph has a total of three nodes, and therefore contains three parts as separated by #.

1. First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
2. Second node is labeled as 1. Connect node 1 to node 2.
3. Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.

Visually, the graph looks like the following:

       1
      / \
     /   \
    0 --- 2
         / \
         \_/ 

/**
 * Definition for undirected graph.
 * struct UndirectedGraphNode {
 *     int label;
 *     vector<UndirectedGraphNode *> neighbors;
 *     UndirectedGraphNode(int x) : label(x) {};
 * };
 */

class Solution {
public:
    
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        if (!node) return NULL;
       
        unordered_map<UndirectedGraphNode *, UndirectedGraphNode *> map;
        queue<UndirectedGraphNode *> que;
        que.push(node);
        map[node] = new UndirectedGraphNode(node->label);
        while(!que.empty()) {
            UndirectedGraphNode *current = que.front();
            que.pop();
           
            for(auto iter : current->neighbors) {
                if (map.find(iter) == map.end()) {
                    map[iter] = new UndirectedGraphNode(iter->label);
                    que.push(iter);
                }

                map[current]->neighbors.push_back(map[iter]);
            }
        }
        return map[node];
    }
};

 
class Solution {
public:
    void BFS(UndirectedGraphNode *node, unordered_map<UndirectedGraphNode *, UndirectedGraphNode *> &map)
    { 
        if (map[node]) return;         map[node] = new UndirectedGraphNode(node->label);
        
        for(UndirectedGraphNode *child : node->neighbors)
            BFS(child, map);
    }
    
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        if (!node) return NULL;
        unordered_map<UndirectedGraphNode *, UndirectedGraphNode *> map;
        BFS(node, map); 
        
        for(auto iter:map)
            for(UndirectedGraphNode *child : iter.first->neighbors)
                iter.second->neighbors.push_back(map[child]);
        
        return map[node];
    }
};

 
class Solution {
public:
    UndirectedGraphNode *DFS(UndirectedGraphNode *node, unordered_map<UndirectedGraphNode *, UndirectedGraphNode *> &map)
    { 
        if (map[node]) return map[node]; 
        
        UndirectedGraphNode *nn = new UndirectedGraphNode(node->label);
        map[node] = nn;
        
        for(UndirectedGraphNode *child : node->neighbors)
            nn->neighbors.push_back(DFS(child, map));
            
        return nn;
    }
    
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        if (!node) return NULL;
        unordered_map<UndirectedGraphNode *, UndirectedGraphNode *> map;
        return DFS(node, map); 
    }
};

String to Integer (atoi)

Implement atoi to convert a string to an integer.
Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.
Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.

Requirements for atoi:
The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.
The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.
If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.
If no valid conversion could be performed, a zero value is returned. If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.

 
 
class Solution {
public:
    int atoi(const char *str) {
        while(*str && *str == ' ') str++;
        int sign = 1;
        if (*str == '+' || *str=='-') {
            sign = *str == '+'? 1 : -1;
            str++;
        }
       
        long val = 0;
        while(*str >= '0' && *str <='9') {
           if (sign == 1 && ((*str >= '8' && val == INT_MAX/10) || val > INT_MAX/10) ) return INT_MAX;
           if (sign == -1 && ((*str >= '8' && val == INT_MAX/10) || val > INT_MAX/10) ) return INT_MIN;
          
           val = val *10 + *str -'0';
           str++;
        }
       
        val *=sign;
        return val;
    }
};

ZigZag Conversion

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);

convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

 
class Solution {
public:
    string convert(string s, int nRows) {
        if (nRows < 2) return s;
        int n = s.length();
        int groupLen = 2*nRows-2;
        int groups = 1 + n / groupLen;
         
        string output;
        for(int i = 0; i < nRows; i++)
        {
            for(int j = 0; j < groups; j++ )
            {
                if (i == 0 || i == nRows-1)
                {
                    if (j * groupLen + i <n)
                       output.push_back(s[j * groupLen + i]);
                }
                else {
                    if (j * groupLen + i <n)
                       output.push_back(s[j * groupLen + i]);
                    if ((j+1) * groupLen - i <n)
                       output.push_back(s[(j+1) * groupLen - i]);
                }
            }
        }
        return output;
    }
};

class Solution {
public:
    string convert(string s, int nRows) {
        if (nRows < 2) return s;
       
        vector<string> map(nRows, "");
        int groupLen = 2*nRows-2;
       
        for(int i = 0; i < s.length(); i++)
        {
            int index = i % groupLen;
            if (index <nRows)
               map[index].push_back(s[i]);
            else
               map[groupLen-index].push_back(s[i]);
        }
       
        string output = "";
        for(string str:map)
           output += str;
        return output;
    }
};

StrStr: Find substring by using KMP algorithm

 
// http://www.mitbbs.com/article_t/JobHunting/32823417.html
// http://www.matrix67.com/blog/archives/115
class Solution {
public:
    vector<int> KMPpreprocessing(char *needle) {
         int m = strlen(needle);
         // assume j = match[i]: needle[i-j:i] == needle[0:j]
         vector<int> match(m,-1);
         int j = -1;
         for(int i=1; i<m; i++) {
             while(j>=0 && needle[i]!=needle[j+1]) j = match[j];
             if(needle[i]==needle[j+1]) j++;
             match[i] = j;
         }
         return match;
     }

     int strStr(char *haystack, char *needle) {
         if(!*needle) return 0;
         if(!*haystack) return -1;  
         int n = strlen(haystack);
         int m = strlen(needle);
         vector<int> match = KMPpreprocessing(needle);
         int j = -1;
         for(int i=0; i<n; i++) {
             while(j>=0 && haystack[i]!=needle[j+1]) j = match[j];
             if(haystack[i]==needle[j+1]) j++;
             if(j==m-1) return i-m+1;
         }
         return -1;
     }
};

Jump Game

Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
For example:
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.

 
class Solution {
public:
    bool canJump(int A[], int n) {
        int current = 0;
        int reach = A[0];
       
        while(current <= reach) {
            if (reach >= n-1) return true;
            reach = max(reach, current+A[current]);
            current++;
        }
       
        return false;
    }
};

Jump Game II

Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.
For example:
Given array A = [2,3,1,1,4]
The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

 
class Solution {
public:
  int jump(int A[], int n) {
        if (n <= 1) return 0;
        int current = 0;
        int reach = A[0];
        int jumps = 1;
       
        while(reach < n-1)
        {
            int maxReach = 0;
            for(int i = current+1; i <=reach; i++)
               maxReach = max(maxReach, i+A[i]);
            current = reach;
            reach = maxReach;
            jumps++;
        }
        return jumps;
    }
};

class Solution {
public:
  int jump(vector<int>& nums) {
        int n = nums.size();
        if (n <= 1) return 0;
        int current = 1;
        int reach = nums[0];
        int jumps = 1;
       
        while(reach < n-1)
        {
            int maxReach = 0;
            while(current <=reach) {
               maxReach = max(maxReach, current+nums[current]); 
               current++;
            }
            reach = maxReach;
            jumps++;
        }
        return jumps;
    }
};

N-Queens II

Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.

 
class Solution {
public:
    bool canPlace(const vector<int> &placed, int row, int col)
    {
        for (int i = 0; i < row; i++)
        {
            if (placed[i] == col || abs(placed[i]-col) == row-i)
               return false;
        }
        return true;
    }
    
    int totalNQueens(int n) {
        int output = 0;
        vector<int> placed(n, 0);
       
        int row = 0, col = 0;
        while(true) {
            if (col == n) {
                if(row == 0) return output;
                else {
                    row--;
                    col = placed[row]+1;
                    continue;
                }
            }
           
            if (canPlace(placed, row, col)) {
                placed[row] = col;
                if (row == n-1) {
                    output++;
                    col++;
                }
                else {
                    row++;
                    col = 0;
                }
            }
            else
              col++;
        }
    }
}; 

N-Queens

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.
For example,
There exist two distinct solutions to the 4-queens puzzle:

[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

 
class Solution {
public:
    bool isValid(vector<int> placement, int row)
    {
        for(int i = 0; i< row; i++)
           if (placement[i] == placement[row] || row - i == abs(placement[i] - placement[row]))
                return false;
        return true;
    }
   
    vector<string> getBoard(const vector<int> &placed)
    {
        vector<string> output;
        for(int i = 0; i < placed.size(); i++)
        { 
           string temp;
           for(int j = 0; j < placed.size(); j++)
              temp.push_back(j==placed[i]?'Q':'.');
             
            output.push_back(temp);
        }
       
        return output;
    }
   
    void helper(int n, int row, vector<int>& placement, vector<vector<string>> &ans){
        if (row == n) {
            ans.push_back(getBoard(placement));
            return;
        }
        for(int i = 0;i < n; i++) {
            placement[row] = i;
            if (isValid(placement, row))
                helper(n, row+1, placement, ans);
        }
    }
   
    vector<vector<string> > solveNQueens(int n) {
       vector<vector<string>> ans;
       vector<int> placement(n);
       helper(n, 0, placement, ans);
       return ans;
    }   
};

 vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> output;
        vector<int> placed(n, 0);
        
        int row = 0, col = 0;
        while(true) {
            if (col == n) {
                if(row == 0) return output;
                else {
                    row--;
                    col = placed[row]+1;
                    continue;
                }
            }
            
            if (canPlace(placed, row, col)) {
                placed[row] = col;
                if (row == n-1) {
                    output.push_back(getBoard(placed));
                    col++;
                }
                else {
                    row++;
                    col = 0;
                }
            }
            else
              col++;
        }
        
        return output;
    }

Scheduling algorithm for a round-robin tournament

The Problem We have a league with n players. every week they have a match with one other. in n-1 weeks every team fought against each other. there are n/2 matches a day. but one team can only fight once in a week. if we generate an (n/k) combination we get all of the combinations... (assuming k = 2) but i need to bring them in the right order.

The classic algorithm works like this:
Number the teams 1..n. (Here I'll take n=8.)
Write all the teams in two rows.

1 2 3 4
8 7 6 5

The columns show which teams will play in that round (1 vs 8, 2 vs 7, ...).
Now, keep 1 fixed, but rotate all the other teams. In week 2, you get

1 8 2 3
7 6 5 4

and in week 3, you get

1 7 8 2
6 5 4 3

This continues through week n-1, in this case,

1 3 4 5
2 8 7 6

If n is odd, do the same thing but add a dummy team. Whoever is matched against the dummy team gets a bye that week.


From: http://stackoverflow.com/questions/6648512/scheduling-algorithm-for-a-round-robin-tournament

Merge k Sorted Lists

 
// C++
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
typedef pair<int, int> PairInt;
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        priority_queue<PairInt, vector<PairInt>, greater<PairInt> > q;
        // initialize heap with first element from each list
        int k = lists.size();
        for (int i = 0; i < k; i++) {
            if (lists[i]) {
                q.push(PairInt(lists[i]->val, i));
            }
        }

        ListNode tmp(0);
        ListNode *p = &tmp;
       
        while (!q.empty()) {
            int i = q.top().second;
            q.pop();
            p->next = lists[i];
            p =p->next;
            lists[i] = lists[i]->next;
           
            if (lists[i]) {
                q.push(PairInt(lists[i]->val, i));
            }
        }
       
        return tmp.next;
    }
};


// Java
 public ListNode mergeKLists(ArrayList<ListNode> lists) {
        if (lists == null || lists.size() == 0) {  // this was missed.
            return null;
        }
        // PriorityQueue is the heap implementation in Java
        PriorityQueue<ListNode> pq = new PriorityQueue<ListNode>(lists.size(), new Comparator<ListNode>() {
            public int compare(ListNode l1, ListNode l2) {
                return l1.val - l2.val;
            }
        });
        for (ListNode head : lists) {
            if (head != null) {  // this was missed.
                pq.add(head);
            }
        }
        ListNode head = new ListNode(0);
        ListNode p = head;
        while (pq.size() > 0) {
            p.next = pq.poll();
            p = p.next; // this was missed.
            if (p.next != null) {
                pq.add(p.next);
            }
        }
        return head.next;
    }

Binary Tree InorderTraversal

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

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

   1
    \
     2
    /
   3

return [1,3,2].

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

LRU Cache

 
class DllNode
{
public:
    DllNode *prev;
    DllNode *next;
    int val;
    int key;
    DllNode(int key, int val)
    {
        this->key = key;
        this->val = val;
        this->prev = this;
        this->next = this;
    }
   
    void Detach()
    {
        prev->next = next;
        next->prev = prev;
    }
   
    void AddLeft(DllNode *node)
    {
       prev->next = node;
       node->prev = prev;
       node->next = this;
       prev = node;
    }
};

class LRUCache{
public:
    int m_cap;
    DllNode m_head;
    unordered_map<int, DllNode *> m_map;
  
    LRUCache(int capacity): m_head(0,0)
    {
        m_cap = capacity;
    }
   
    int get(int key) {
        if (m_map.count(key) ==0)
        return -1;
        DllNode *node = m_map[key];
        node->Detach();
        m_head.AddLeft(node);
        return node->val;
    }
   
    void set(int key, int value) {
       
        if (m_map.find(key) != m_map.end())
        {
            DllNode *node = m_map[key];
            node->Detach();
            delete node;
            m_map.erase(key);
        }
       
        if (m_map.size() == m_cap)
        {
           DllNode *oldest = m_head.next;
           oldest->Detach();
           m_map.erase(oldest->key);
           delete oldest;
        }
        DllNode *node = new DllNode(key, value);
        m_head.AddLeft(node);
        m_map[key] = node;
    }
};

Insertion Sort List

 
ListNode *insertionSortList(ListNode *head) {
        if (!head) return head;
        ListNode dummy(numeric_limits<int>::min());
       
        while(head) {
            ListNode *p = &dummy;   
            while(p->next && p->next->val <= head->val)
              p = p->next;
           
            ListNode *headNext = head->next;
            head->next = p->next;
            p->next = head;
            head = headNext;
        }
        return dummy.next;
    }

Sort List

 
ListNode *sortList(ListNode *head) {
        // Notice the second condition check, other wise, stack overflow.
        if (!head || !head->next) return head;
       
        ListNode *fast = head, *slow = head;
        while(fast->next && fast->next->next)
        {
            fast = fast->next->next;
            slow = slow->next;
        }
       
        fast = slow->next;
        slow->next = NULL;
        return merge(sortList(head), sortList(fast));
    }
   
    ListNode *merge(ListNode *left, ListNode *right)
    {
        ListNode dummy(0);
        ListNode *p = &dummy;   
        while(left && right)
        {
            if (left->val < right->val) {
                p->next = left;
                left = left->next;
            }
            else {
                p->next = right;
                right = right->next;
            }
            p = p->next;
        }
       
        p->next = left? left : right;
        return dummy.next;
    }

Max Points on a Line

Solution 1:

 int maxPoints(vector<Point> &points){
            int n = points.size();
            if (n < 3) return n;
            int ret = 0;
            for (int i = 0; i < n; i++) {
                unordered_map<double, int> slopes;
                int dup = 1;
                int localMax = 0;
                for(int j = i+1; j < n; j++) {
                    if (points[i].x == points[j].x && points[i].y == points[j].y)
                        dup++;
                    else {
                       double x = points[i].x - points[j].x;
                       double y = points[i].y - points[j].y;
                       double slop = x == 0? numeric_limits<double>::max() : y/x;
                       localMax = max(localMax, ++slopes[slop]);
                    }
                }
                ret = max(ret, dup+localMax);
            }
             return ret;
        }

Solution 2:

  int maxPoints(vector<Point> &points){
            int n = points.size();
            if (n < 3) return n;
            int ret = 0;
            for (int i = 0; i < n; i++)
            {
                unordered_map<int, unordered_map<int, int>> slopes;
                int dup = 1;
                int localMax = 0;
                for(int j = i+1; j < n; j++)
                {
                    if (points[i].x == points[j].x && points[i].y == points[j].y)
                        dup++;
                    else
                    {
                       int x = points[i].x - points[j].x;
                       int y = points[i].y - points[j].y;
                       int gcd = GCD(x, y);
                       if (gcd != 0)
                       {
                           x /= gcd;
                           y /= gcd;
                       }
                       localMax = max(localMax, ++slopes[x][y]);
                    }
                }
                ret = max(ret, dup+localMax);
            }
             return ret;
        }
       
        int GCD(int a, int b)
        {
            if (b == 0) return a;
            return GCD(b, a%b);
        }

Solution 3:

 bool equals(float a, float b)
    {
       return abs(a-b) <= 1.0e-9;
    }
   
    int LongestPoints(vector<float> &slopes)
    {
        sort(slopes.begin(), slopes.end());
        int n = slopes.size();
        int counter = 1;
        int start = 0;
        int output = 0;
        for(int i =1; i < n; i++)
        {
            if (!equals(slopes[i], slopes[i-1]))
            {
                output = max(output,  i-start);
                start = i;
            }
        }
        output = max(output, n-start);
        return output;
    }
    int maxPoints(vector<Point> &points)
    {
        int n = points.size();
        if (n < 3) return n;
        int maxPts = 2;
       
        for (int i = 0; i < n; i++)
        {
            vector<float> slopes;
            int dup = 1;
            for(int j = i+1; j < n; j++)
            {
                float slope = numeric_limits<float>::max();
                if (points[i].x == points[j].x && points[i].y == points[j].y)
                    dup++;
                else {
                    if (points[i].x != points[j].x)
                       slope = (float)(points[i].y-points[j].y)/(float)(points[i].x-points[j].x);
                    slopes.push_back(slope);
                }
            }
           
            int longestPoints = LongestPoints(slopes);
            maxPts = max(maxPts, dup + longestPoints);
        }
       
        return maxPts;
    }

Evaluate Reverse Polish Notation

 
Solution 1 (in Java):

  public int evalRPN(String[] tokens) {
         Stack<Integer> stack = new Stack<Integer>();
         for(String token : tokens)
         {
             if ("+".equals(token))
                stack.push(stack.pop() + stack.pop());
             else if("-".equals(token))
                stack.push(-stack.pop() + stack.pop());
             else if("*".equals(token))
                stack.push(stack.pop() * stack.pop());
             else if("/".equals(token))
             {
                 int d1 = stack.pop();
                 int d2 = stack.pop();
                 stack.push(d2/d1);
             }
             else stack.push(Integer.parseInt(token));
         }
         return stack.pop();
    }


Solution 2 (in C++):

    bool isOperator(string &o)
    {
        return o == "+" || o == "-" || o == "*" || o == "/";
    }
   
    int atoi(const string &a)
    {
        int o = 0;
        int i = 0;
        int sign = 1;
        while(i < a.length())
        {
            if (i == 0 && a[i] == '-') {
              sign = -1;
              i++;
              continue;
            }
            o= o*10 + a[i]-'0';
            i++;
        }
       
        return o*sign;
    }
   
    int eval(int left, const string &op, int right)
    {
        int r = 0;
        if(op == "+")
               return left+ right;
        if(op == "-")
            return left - right;
        if(op == "*")
            return left * right;
         if(op == "/")
            return left / right;
            
        return 0;
    }
    int evalRPN(vector<string> &tokens) {
        stack<int> mystack;
        for(int i = 0; i < tokens.size(); i++)
        {
            if (isOperator(tokens[i]))
            {
               int right = mystack.top();
               mystack.pop();
               int left = mystack.top();
               mystack.pop();
               mystack.push(eval(left, tokens[i], right));
            }
            else
               mystack.push(atoi(tokens[i]));
        }
       
        return mystack.top();
    }

Reverse Words in a String

 
Solution 1:

void reverseWords(string &s) {
        string output = "";
        int len = 0;
        for(int i = s.length()-1; i >=0; i--)
        {
            if (s[i] != ' ')
              len++;
         
            if (len > 0 && (i==0 || s[i-1] == ' '))
            {
               if (output.length() >0) output += " ";
               output += s.substr(i, len);
               len = 0;
            }
        }
        s = output;
    }

Solution 2:

void reverseWords(string &s) {
        stack<string> st;
       
        string word = "";
        for(char c: s)
        {
            if (c == ' ')
            {
                if (word != "")
                {
                    st.push(word);
                    word = "";
                }
            }
            else
              word += c;
        }
       
        if (word != "") st.push(word);
      
        s ="";
        if (st.size() >= 1)
        {
            s = st.top();
            st.pop();
        }
           
        while(st.size() > 0)
        {
          s += " " + st.top();
          st.pop();
        }
    }

Maximum Product Subarray

 
Solution 1:

int maxProduct(int A[], int n) {
         int max=A[0], min = A[0], ans = A[0];
        
         for(int i = 1; i < n; i++) {
             int mx = max, mn = min;
             max = std::max(A[i], std::max(mx*A[i], mn*A[i]));
             min = std::min(A[i], std::min(mx*A[i], mn*A[i]));
            
             ans = std::max(ans, max);
         }
        
         return ans;
}

Solution 2:

 int maxProduct(int A[], int n) {
         int max = A[0];
         int maxPos = 1.0;
         int minNeg = 1.0;
        
         for(int i = 0; i < n; i++) {
             if (A[i] > 0) {
                 maxPos *= A[i];
                
                 minNeg = min(1, minNeg*A[i]);
                   
                 max = std::max(max,maxPos);
             }
             else if (A[i] < 0) {
                 int tmp = maxPos * A[i];
                
                 if (minNeg < 0) {
                    maxPos = std::max(1, minNeg * A[i]);
                    max = std::max(max,maxPos);
                 }
                 else
                    maxPos = 1;
                 minNeg = tmp;
             }
             else {
                 maxPos = 1.0;
                 minNeg = 1.0;
                
                 max = std::max(0, max);
             }
         }
        
         return max;
    }

Find Minimum in Rotated Sorted Array

 
 int findMin(vector<int> &num) {
        int l = 0, r = num.size()-1;
       
        while(l < r) {
            int m = l + (r-l) /2;
            if (num[m] < num[r])
              r = m;
            else
              l = m +1;
        }
        return num[r];
    }

Find Minimum in Rotated Sorted Array II

 
   int findMin(vector<int> &A) {
        int l = 0, r = A.size()-1;
        while(l < r) {
            if (A[l] < A[r])
              break;
            int m = l + (r-l)/2;
           
            if (A[m] < A[r])
                r = m;
            else if (A[m] > A[r])
                l = m+1;
            else {
               r--;
               l++;
            }
        }       
        return A[l];
    }