public class Solution { public int maxProduct(int[] A) { ListB = 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; } }
Roger Everett
10/02/2014
Leetcode -- Maximum Product Subarray
Made a really complicated and ugly solution, will refactor later:
6/15/2014
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
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;
}
6/08/2014
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 ); } };
6/07/2014
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; } };
6/03/2014
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';
}
}
}
}
};
6/01/2014
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; }
Subscribe to:
Posts (Atom)