Leetcode -- Maximum Product Subarray

Made a really complicated and ugly solution, will refactor later:

public class Solution {
    public int maxProduct(int[] A) {
         List B = new ArrayList();
        for(int i = A.length - 1; i >= 0; --i) {
            B.add(A[i]);
        }

        int[] BB = new int[A.length];
        for(int i = 0; i < A.length; ++i) {
            BB[i] = B.get(i);
        }
        return Math.max(maxProductHelper(A), maxProductHelper(BB));
    }
    public int maxProductHelper(int[] A) {
  int currentMax = A[0];
        int product = A[0];
        int grandproduct = A[0];

        for(int i = 1; i < A.length; ++i) {
            grandproduct *= A[i];

            if(A[i] == 0) {
                currentMax = Math.max(currentMax, 0);
                currentMax = Math.max(currentMax, product);
                product = 0;
                grandproduct = 1;
            } else if(A[i] < 0) {
                  currentMax = Math.max(currentMax, product);
                if(grandproduct > 0) {
                    product = grandproduct;
                    currentMax = Math.max(currentMax, product);
                }
                else if (grandproduct == 0) {
                    grandproduct = A[i];
                        product = A[i];
                } else {
                    product = 0;
                }
            } else {
                  if(grandproduct == 0) {
                    grandproduct = A[i];
                }
                if(product == 0) {
                    product = 1;
                }
                product *= A[i];
                currentMax = Math.max(currentMax, product);
            }
        }
        return currentMax;
    }
}

Evaluate Math Expression

A hacky way with python is quite simple
print eval('1+ 2*3 - 5', {'__builtins__' : None})

Otherwise, we assume there is not brackets

 #include <iostream>  
 #include <stack>  
 using namespace std;  
 class Eval {  
 public:  
  int operator()(string s) {  
   stack<int> operands;  
   stack<char> operators;  
   int num = 0;  
   for(int i = 0; i < s.length(); ++i) {  
    if(s[i] >= '0' && s[i] <= '9') {  
     num = num * 10 + s[i] - '0';  
    } else if(s[i] == '+' || s[i] == '-') {  
     if(operands.empty()) {  
      operands.push(num);  
     } else {  
      if(!operators.empty() && (operators.top() == '*' || operators.top()=='/')) {  
       if(operators.top() == '*') {  
        operands.top() *= num;  
       } else if(operators.top() == '/') {  
        operands.top() /= num;  
       }  
       operators.pop();  
      }  
     }  
     operators.push(s[i]);  
     num = 0;  
    } else if(s[i] == '*' || s[i] == '/') {  
     operands.push(num);  
     operators.push(s[i]);  
     num = 0;  
    }  
   }  
   operands.push(num);  
   while(operands.size() > 1) {  
    int right = operands.top();  
    operands.pop();  
    int left = operands.top();  
    operands.pop();  
    char op = operators.top();  
    operators.pop();  
    if(op=='+') {  
     left += right;  
    } else if(op=='-') {  
     left -= right;  
    } else if(op=='*') {  
     left *= right;  
    } else if (op=='/') {  
     left /= right;  
    }  
    operands.push(left);  
   }  
   return operands.top();  
  }  
 };  
 int main(int argc, char *argv[])  
 {  
  Eval eval;  
  std::cout << eval("1+2*3 + 5 * 10") << std::endl;  
  return 0;  
 }  

Leetcode -- Interleaving String

class Solution {  
 public:  
   bool isInterleave(string s1, string s2, string s3) {  
     int n1 = s1.size();  
     int n2 = s2.size();  
     int n3 = s3.size();  
     if(n1 + n2 != n3) {  
       return false;  
     }  
     vector<vector<bool> > dp(n1 + 1, vector<bool>(n2 + 1, 0));  
     dp[0][0] = 1;  
     for(int i = 1; i <=n1; ++i) {  
       if(s1[i - 1] == s3[i - 1] && dp[i - 1][0]) {  
         dp[i][0] = 1;  
       }  
     }  
     for(int j = 1; j <= n2; ++j) {  
       if(s2[j - 1] == s3[j - 1] && dp[0][j - 1]) {  
         dp[0][j] = 1;  
       }  
     }  
     for(int i = 1; i <= n1; ++i) {  
       for(int j = 1; j <= n2; ++j) {  
         dp[i][j] = dp[i - 1][j] && s1[i - 1] == s3[i + j - 1] || dp[i][j - 1] && s2[j - 1] == s3[i + j - 1];  
       }  
     }  
     return dp[n1][n2];  
   }  
 };  

Leetcode -- Recover Binary Search Tree

 /**  
  * Definition for binary tree  
  * struct TreeNode {  
  *   int val;  
  *   TreeNode *left;  
  *   TreeNode *right;  
  *   TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
  * };  
  */  
 class Solution {  
 public:  
   void recoverTree(TreeNode *root) {  
     TreeNode * n1 = NULL;  
     TreeNode * n2 = NULL;  
     TreeNode * prev = NULL;  
     recoverTree(root, n1, n2, prev);  
     if(n1 && n2) {  
     int temp = n1->val;  
     n1->val = n2->val;  
     n2->val = temp;  
     }  
   }  
   void recoverTree(TreeNode * root, TreeNode *& n1, TreeNode *& n2, TreeNode *& prev) {  
     if(!root) {  
       return;  
     }  
      recoverTree(root->left, n1, n2, prev );  
     if(prev && prev->val > root->val) {  
       n2 = root;  
       if(!n1) {  
         n1 = prev;  
       }  
     }  
     prev = root;  
     recoverTree(root->right, n1, n2, prev );  
   }  
 };  

Leetcode -- Convert Sorted List to Binary Search Tree

 /**  
  * Definition for singly-linked list.  
  * struct ListNode {  
  *   int val;  
  *   ListNode *next;  
  *   ListNode(int x) : val(x), next(NULL) {}  
  * };  
  */  
 /**  
  * Definition for binary tree  
  * struct TreeNode {  
  *   int val;  
  *   TreeNode *left;  
  *   TreeNode *right;  
  *   TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
  * };  
  */  
 class Solution {  
 public:  
   TreeNode *sortedListToBST(ListNode *head) {  
     if(head == NULL) {  
       return NULL;  
     }  
     // check the length of the list node  
     ListNode * p = head;  
     int length = 0;  
     while(p != NULL) {  
       length++;  
       p = p->next;  
     }  
     return sortedListToBST(head, 0, length - 1);  
   }  
   TreeNode * sortedListToBST(ListNode *& head, int start, int end) {  
     if(start > end) {  
       return NULL;  
     }  
     int mid = start + (end - start) / 2;  
     TreeNode * left = sortedListToBST(head, start, mid - 1);  
     TreeNode * parent = new TreeNode(head->val);  
     parent->left = left;  
     head = head->next;  
     parent->right = sortedListToBST(head, mid + 1, end);  
     return parent;  
   }  
 };  

Leetcode -- Surrounding Regions

Basically just copied from Internet.

 class Solution {  
 public:  
   void solve(vector<vector<char>> &board) {  
     if(board.empty()) {  
       return;  
     }  
     vector<int> xIndex;  
     vector<int> yIndex;  
     int row = board.size();  
     int column = board[0].size();  
     for(int i = 0; i < row; ++i) {  
       if(board[i][0] == 'O') {  
         xIndex.push_back(i);  
         yIndex.push_back(0);  
       }  
       if(board[i][column - 1] == 'O') {  
         xIndex.push_back(i);  
         yIndex.push_back(column - 1);  
       }  
     }  
     for(int i = 1; i < column; ++i) {  
       if(board[0][i] == 'O') {  
         xIndex.push_back(0);  
         yIndex.push_back(i);  
       }  
       if(board[row - 1][i] == 'O') {  
         xIndex.push_back(row - 1);  
         yIndex.push_back(i);  
       }  
     }  
     int k = 0;  
     for(int i = 0; i < xIndex.size(); ++i) {  
       int x = xIndex[i];  
       int y = yIndex[i];  
       board[x][y] = 'Y';  
       if(x > 0 && board[x-1][y] == 'O') {  
         xIndex.push_back(x-1);  
         yIndex.push_back(y);  
       }  
       if(x < row - 1 && board[x+1][y] == 'O') {  
         xIndex.push_back(x + 1);  
         yIndex.push_back(y);  
       }  
       if(y > 0 && board[x][y - 1] == 'O') {  
         xIndex.push_back(x);  
         yIndex.push_back(y- 1);  
       }  
       if(y < column - 1 && board[x][y + 1] == 'O') {  
         xIndex.push_back(x);  
         yIndex.push_back(y+ 1);  
       }  
     }  
     for(int i = 0; i < row; ++i) {  
       for(int j = 0; j < column; ++j) {  
         if(board[i][j] == 'Y') {  
           board[i][j] = 'O';  
         } else {  
           board[i][j] = 'X';  
         }  
       }  
     }  
   }  
 };  

Leetcode -- Candy

Scan from both beginning and back, catch the strictly increasing and strictly decreasing ratings. When do the backward scan, be careful that if the current candy at location j is already greater than the expected candy, do not change it.

#include <iostream>  
 #include <vector>  
 using namespace std;  
 class Solution {  
 public:  
  int candy(vector<int> &ratings) {  
   int last = 0;  
   vector<int> candies(ratings.size(), 1);  
   for(int i = 1; i < ratings.size(); ++i) {  
    if(ratings[i] <= ratings[i - 1]) {  
     int num = 1;  
     for(int j = last; j < i; ++j) {  
      candies[j] = num++;  
     }  
     last = i;  
    }  
   }  
   int num = 1;  
   for(int j = last; j < ratings.size(); ++j) {  
    candies[j] = num++;  
   }  
   last = ratings.size() - 1;  
   for(int i = ratings.size() - 2; i >= 0; --i) {  
    if(ratings[i] <= ratings[i+ 1]) {  
     int num = 1;  
     for(int j = last; j > i; --j) {  
      candies[j] = candies[j] > num ? candies[j] : num++;  
     }  
     last = i;  
    }  
   }  
   num = 1;  
   for(int j = last; j >=0; --j) {  
    candies[j] = candies[j] > num ? candies[j] : num++;  
   }  
   int sum = 0;  
   for(int i = 0; i < candies.size(); ++i) {  
    sum+= candies[i];  
   }  
   return sum;  
  }  
 };  
 int main(int argc, char *argv[])  
 {  
  Solution s;  
  vector<int> ratings{2,2,1};  
  std::cout << s.candy(ratings) << std::endl;  
  return 0;  
 }