## Monday, November 30, 2015

### LeetCode OJ - Basic Calculator II

Problem:

Solution:

I could have extended the last solution for Basic Calculator to include the multiplication and division, but turn out the judge have a case that stress memory usage, and top down parser are just not good with respect to memory usage, so I hand written a shift reduce parser instead.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/basic-calculator-ii/

#include "LEET_BASIC_CALCULATOR_II.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <stack>

using namespace std;

namespace _LEET_BASIC_CALCULATOR_II
{
class Solution
{
public:
// Scanner states
unsigned int position;
char token;
string* expression;

void scan()
{
while (true)
{
if (position < (*expression).size())
{
token = (*expression)[position++];
}
else
{
token = '\0';
}
if (token != ' ')
{
break;
}
}
}

// A hand written shift-reduce parser!
// I could have adapted the previous top-down parsing solution
// But there is a test case in the judge to stress memory usage, and a top down parser necessarily use up the space because of the recursion
// A shift-reduce parser can save space by reducing early and not using the stack space
int calculate(string s)
{
const int PLUS = 0;
const int MINUS = 1;
const int MULTIPLY = 2;
const int DIVIDE = 3;

stack<int> numStack;
stack<int> sigStack;

position = 0;
expression = &s;

const int EXPECT_DIGIT = 0;
const int EXPECT_DIGIT_OR_OPERATOR = 1;
int state = EXPECT_DIGIT;

int currentNumber = 0;
while (true)
{
scan();
if (token >= '0' && token <= '9')
{
state = EXPECT_DIGIT_OR_OPERATOR;
currentNumber = currentNumber * 10 + (token - '0');
}
else
{
if (EXPECT_DIGIT)
{
throw 1;
}
numStack.push(currentNumber);
currentNumber = 0;
if (token == '*' || token == '/')
{
while (sigStack.size() > 0)
{
if (sigStack.top() >= MULTIPLY)
{
int operand2 = numStack.top(); numStack.pop();
int operand1 = numStack.top(); numStack.pop();
if (sigStack.top() == MULTIPLY)
{
numStack.push(operand1 * operand2);
}
else if (sigStack.top() == DIVIDE)
{
numStack.push(operand1 / operand2);
}
sigStack.pop();
}
else
{
break;
}
}

if (token == '*')
{
sigStack.push(MULTIPLY);
}
else if (token == '/')
{
sigStack.push(DIVIDE);
}

state = EXPECT_DIGIT;
}
else if (token == '+' || token == '-' || token == '\0')
{
while (sigStack.size() > 0)
{

int operand2 = numStack.top(); numStack.pop();
int operand1 = numStack.top(); numStack.pop();
if (sigStack.top() == PLUS)
{
numStack.push(operand1 + operand2);
}
else if (sigStack.top() == MINUS)
{
numStack.push(operand1 - operand2);
}
else if (sigStack.top() == MULTIPLY)
{
numStack.push(operand1 * operand2);
}
else if (sigStack.top() == DIVIDE)
{
numStack.push(operand1 / operand2);
}
sigStack.pop();
}
if (token == '+')
{
sigStack.push(PLUS);
}
else if (token == '-')
{
sigStack.push(MINUS);
}
else if (token == '\0')
{
return numStack.top();
}

state = EXPECT_DIGIT;
}
}
}

return 0;
}
};
};

using namespace _LEET_BASIC_CALCULATOR_II;

int LEET_BASIC_CALCULATOR_II()
{
Solution solution;
cout << (solution.calculate("3+2*2") == 7) << endl;
cout << (solution.calculate(" 3/2 ") == 1) << endl;
cout << (solution.calculate(" 3+5 / 2 ") == 5) << endl;
return 0;
}

### LeetCode OJ - Basic Calculator

Problem:

Solution:

For the purpose of this problem, I wrote a simple top down recursive parser for this grammar.

Expression = Value | Expression + Value | Expression - Value
Value = Number | (Expression)

Note the grammar has left recursion which mean top-down recursive parsing will run into infinite loop, eventually run out of stack, the innovative part of this solution, unlike traditional parsing, is to parse the string backwards, if we do that, then there is no right recursion, and now we are fine.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/basic-calculator/

#include "LEET_BASIC_CALCULATOR.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_BASIC_CALCULATOR
{
class Solution
{
public:
// Scanner states
int position;
char token;
string* expression;

// Expression = Value
// Expression = Expression + Value
// Expression = Expression - Value
// Value = Number
// Value = ( Expression )

// The key innovation in this solution is parsing backward and thus eliminate the left recursion problem of the left associative grammar
void scan()
{
while (true)
{
if (position >= 0)
{
token = (*expression)[position--];
}
else
{
token = '\0';
}
if (token != ' ')
{
break;
}
}
}

bool ParseValue(int* result)
{
if (token >= '0' && token <= '9')
{
return ParseNumber(result);
}
else if (token == ')')
{
scan();
int bracketedExpression;
if (ParseExpression(&bracketedExpression))
{
*result = bracketedExpression;
if (token == '(')
{
scan();
return true;
}
else
{
return false;
}
}
else
{
return false;
}
}
else
{
return false;
}
}

bool ParseNumber(int* result)
{
int base = 1;
*result = 0;
while (true)
{
if (token >= '0' && token <= '9')
{
int digit = token - '0';
*result = *result + base * digit;
base *= 10;
scan();
}
else
{
return true;
}
}
return false;
}

bool ParseExpression(int* result)
{
if ((token >= '0' && token <= '9') || token == ')')
{
int tail;
if (ParseValue(&tail))
{
if (token == '+')
{
scan();
{
return true;
}
}
else if (token == '-')
{
scan();
{
return true;
}
}
else if (token == '\0' || token == '(')
{
*result = tail;
return true;
}
else
{
return false;
}
}
else
{
return false;
}
}

return false;
}

int calculate(string s)
{
position = s.size() - 1;
expression = &s;
scan();
int result;
if (ParseExpression(&result))
{
return result;
}
cout << "Parse error!" << endl;
return 0;
}
};
};

using namespace _LEET_BASIC_CALCULATOR;

int LEET_BASIC_CALCULATOR()
{
Solution solution;
cout << (solution.calculate("1 + 1") == 2) << endl;
cout << (solution.calculate(" 2-1 + 2 ") == 3) << endl;
cout << (solution.calculate("(1+(4+5+2)-3)+(6+8)") == 23) << endl;
return 0;
}

## Monday, November 23, 2015

### LeetCode OJ - Find Median from Data Stream

Problem:

Solution:

Two heaps solution. We maintain two heaps, one max heap that keep track of the smaller half of the numbers, and a min heap keep track of the larger half of the number, Having that we can find the median anytime we want with constant operation, and we can maintain the invariant of update in $O(\log n)$ time.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/find-median-from-data-stream/

#include "LEET_FIND_MEDIAN_FROM_DATA_STREAM.h"
#include <functional>
#include <queue>
#include <vector>
#include <iostream>

using namespace std;

namespace _LEET_FIND_MEDIAN_FROM_DATA_STREAM
{
class MedianFinder
{
private:
priority_queue<int> small;
priority_queue<int> large;
public:

// Adds a number into the data structure.
{
int size = small.size() + large.size();
if (size == 0)
{
small.push(num);
}
else if (size == 1)
{
int oldValue = small.top();
if (oldValue < num)
{
large.push(-num);
}
else
{
small.pop();
small.push(num);
large.push(-oldValue);
}
}
else
{
int maximal_small = small.top();
int minimal_large = -large.top();
if (size % 2 == 0)
{
if (num <= minimal_large)
{
small.push(num);
}
else
{
large.pop();
small.push(minimal_large);
large.push(-num);
}
}
else
{
if (num >= maximal_small)
{
large.push(-num);
}
else
{
small.pop();
small.push(num);
large.push(-maximal_small);
}
}
}
}

// Returns the median of current data stream
double findMedian()
{
int size = small.size() + large.size();
if (size % 2 == 0)
{
return (small.top() - large.top()) / 2.0;
}
else
{
return small.top();
}
return 0;
}
};
};

using namespace _LEET_FIND_MEDIAN_FROM_DATA_STREAM;

int LEET_FIND_MEDIAN_FROM_DATA_STREAM()
{
MedianFinder mf;
cout << (mf.findMedian() == 1.5) << endl;
cout << (mf.findMedian() == 2) << endl;
return 0;
}

### LeetCode OJ - Range Sum Query - Mutable

Problem:

Solution:

Cache the sums in a segment tree. Then we can do both query and update in $O(\log n)$ time.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/range-sum-query-mutable/

#include "LEET_RANGE_SUM_QUERY_MUTABLE.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_RANGE_SUM_QUERY_MUTABLE
{
class NumArray
{
struct SegmentTreeNode
{
int sum;
SegmentTreeNode* left;
SegmentTreeNode* right;
};

vector<int>& m_nums;
SegmentTreeNode* m_root;

SegmentTreeNode* build_segment_tree(int lower, int upper)
{
SegmentTreeNode* result = new SegmentTreeNode();
if (upper - lower == 1)
{
result->sum = this->m_nums[lower];
result->left = NULL;
result->right = NULL;
}
else
{
int mid = (lower + upper) / 2;
result->left = build_segment_tree(lower, mid);
result->right = build_segment_tree(mid, upper);
result->sum = result->left->sum + result->right->sum;
}

return result;
}

int get_sum(SegmentTreeNode* node, int treeLower, int treeUpper, int queryLower, int queryUpper)
{
if (queryLower <= treeLower && queryUpper >= treeUpper)
{
return node->sum;
}

int treeMid = (treeLower + treeUpper) / 2;
int result = 0;
if (queryLower < treeMid)
{
result += get_sum(node->left, treeLower, treeMid, queryLower, queryUpper);
}
if (queryUpper > treeMid)
{
result += get_sum(node->right, treeMid, treeUpper, queryLower, queryUpper);
}
return result;
}

void update_tree(SegmentTreeNode* node, int lower, int upper, int index, int delta)
{
node->sum += delta;
if (upper - lower != 1)
{
int mid = (lower + upper) / 2;
if (index < mid)
{
update_tree(node->left, lower, mid, index, delta);
}
else
{
update_tree(node->right, mid, upper, index, delta);
}
}
}
public:
NumArray(vector<int>& nums) : m_nums(nums), m_root(NULL)
{
if (nums.size() > 0)
{
m_root = build_segment_tree(0, nums.size());
}
}

~NumArray()
{
if (this->m_root != NULL)
{
delete this->m_root;
}
}

void update(int i, int val)
{
int delta = val - m_nums[i];
m_nums[i] = val;
return update_tree(this->m_root, 0, this->m_nums.size(), i, delta);
}

int sumRange(int i, int j)
{
// j + 1 so that we follow convention [)
return get_sum(this->m_root, 0, this->m_nums.size(), i, j + 1);
}
};
};

using namespace _LEET_RANGE_SUM_QUERY_MUTABLE;

int LEET_RANGE_SUM_QUERY_MUTABLE()
{
int dataArray[] = { 7, 2, 7, 2, 0 };
vector<int> data(dataArray, dataArray + _countof(dataArray));
NumArray nums(data);
nums.update(4, 6);
nums.update(0, 2);
nums.update(0, 9);
cout << (nums.sumRange(4, 4) == 6) << endl;
nums.update(3, 8);
cout << (nums.sumRange(0, 4) == 32) << endl;
nums.update(4, 1);
cout << (nums.sumRange(0, 3) == 26) << endl;
cout << (nums.sumRange(0, 4) == 27) << endl;
return 0;
} 

## Tuesday, November 17, 2015

### LeetCode OJ - Range Sum Query 2D - Immutable

Problem:

Solution:

Using the running sum formula in the last post, and also the inclusive exclusive principle, we get this

$\begin{eqnarray*} & & \sum\limits_{r = r_1}^{r_2} {\sum\limits_{c = c_1}^{c_2} {f(r, c)}} \\ &=& \sum\limits_{r = 0}^{r_2} {\sum\limits_{c = 0}^{c_2} {f(r, c)}} - \sum\limits_{r = 0}^{r_1-1} {\sum\limits_{c = 0}^{c_2} {f(r, c)}} - \sum\limits_{r = 0}^{r_2} {\sum\limits_{c = 0}^{c_1-1} {f(r, c)}} + \sum\limits_{i = 0}^{r_1-1-1} {\sum\limits_{j = 0}^{c_1-1} {f(r, c)}} \end{eqnarray*}$

Code:

#include "stdafx.h"

// https://leetcode.com/problems/range-sum-query-2d-immutable/

#include "LEET_RANGE_SUM_QUERY_2D_IMMUTABLE.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_RANGE_SUM_QUERY_2D_IMMUTABLE
{
class NumMatrix
{
private:
vector<vector<int>> runningSums;
public:
NumMatrix(vector<vector<int>> &matrix)
{
int height = matrix.size();
if (height == 0)
{
return;
}

int width = matrix[0].size();
if (width == 0)
{
return;
}

// runningSum[i][j] = sum(r = 0 to i - 1) sum(c = 0 to j - 1) matrix[r][c]
runningSums.resize(height + 1);
for (int r = 0; r <= height; r++)
{
runningSums[r].resize(width + 1);
}

for (int i = 0; i <= height; i++)
{
for (int j = 0; j <= width; j++)
{
if (i == 0 || j == 0)
{
runningSums[i][j] = 0;
}
else
{
// Inclusive exclusive principle applies here
runningSums[i][j] = runningSums[i - 1][j] + runningSums[i][j - 1] - runningSums[i - 1][j - 1] + matrix[i - 1][j - 1];
}
}
}
}

int sumRegion(int row1, int col1, int row2, int col2)
{
// Inclusive exclusive principle applies here as well
return runningSums[row2 + 1][col2 + 1] - runningSums[row1][col2 + 1] - runningSums[row2 + 1][col1] + runningSums[row1][col1];
}
};
};

using namespace _LEET_RANGE_SUM_QUERY_2D_IMMUTABLE;

int LEET_RANGE_SUM_QUERY_2D_IMMUTABLE()
{
int row1[] = { 3, 0, 1, 4, 2 };
int row2[] = { 5, 6, 3, 2, 1 };
int row3[] = { 1, 2, 0, 1, 5 };
int row4[] = { 4, 1, 0, 1, 7 };
int row5[] = { 1, 0, 3, 0, 5 };
vector<vector<int>> nums;
nums.push_back(vector<int>(row1, row1 + _countof(row1)));
nums.push_back(vector<int>(row2, row2 + _countof(row2)));
nums.push_back(vector<int>(row3, row3 + _countof(row3)));
nums.push_back(vector<int>(row4, row4 + _countof(row4)));
nums.push_back(vector<int>(row5, row5 + _countof(row5)));
NumMatrix n(nums);
cout << (n.sumRegion(2, 1, 4, 3) == 8) << endl;
cout << (n.sumRegion(1, 1, 2, 2) == 11) << endl;
cout << (n.sumRegion(1, 2, 2, 4) == 12) << endl;
return 0;
}