## Monday, October 31, 2016

### LeetCode OJ - Evaluate Reverse Polish Notation

Problem:

Solution:

A stack machine work perfectly for this case! Be careful with subtraction/division case. Remember the stack pops the second argument first!

Code:

#include "stdafx.h"

// https://leetcode.com/problems/evaluate-reverse-polish-notation/

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

using namespace std;

namespace _LEET_EVALUATE_REVERSE_POLISH_NOTATION
{
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int> args;
for (int i = 0; i < tokens.size(); i++)
{
if (tokens[i] == "+")
{
int a = args.top(); args.pop();
int b = args.top(); args.pop();
args.push(a + b);
}
else if (tokens[i] == "-")
{
int a = args.top(); args.pop();
int b = args.top(); args.pop();
args.push(b - a);
}
else if (tokens[i] == "*")
{
int a = args.top(); args.pop();
int b = args.top(); args.pop();
args.push(a * b);
}
else if (tokens[i] == "/")
{
int a = args.top(); args.pop();
int b = args.top(); args.pop();
args.push(b / a);
}
else
{
args.push(stoi(tokens[i]));
}
}

return args.top();
}
};
};

using namespace _LEET_EVALUATE_REVERSE_POLISH_NOTATION;

int LEET_EVALUATE_REVERSE_POLISH_NOTATION()
{
Solution solution;
string input_array[5] = { "4", "13","5","/","+" };
vector<string> input(input_array, input_array + 5);
cout << solution.evalRPN(input) << endl;
return 0;
}

### LeetCode OJ - Next Permutation

Problem:

Analysis:

The next permutation is lexicographically larger than the current permutation, therefore, if a sequence is monotonic decreasing, there is no way we can have a next permutation, in this case, we simply reverse the permutation, that gives a monotonically increasing sequence, which is the 1st permutation.

If the sequence is not monotonically decreasing, there must be a increase in value. In particular, there must an increase that is least significant.

Look at this example, we have:

6, 3, 5, 4, 2, 1

The least significant increase happens here.

6, 3, 5, 4, 2, 1

Here is where we can try to increase it minimally lexicographically. 3 can be minimally increase to 4, so it becomes this:

6, 4, X, X, X, X

We do not know the 'X' yet, but because we wanted to increase it minimally, so it only make sense if we order the rest monotonically increasing like this:

6, 4, 1, 2, 3, 5

So that would be our answer, notice because the original 4 numbers are monotonically decreasing, to obtain this monotonic increasing sequence, we do not need to sort, all we have to do is to reverse it.

Solution:

The algorithm is as follow:

1. Scan the sequence from the back to find the last strictly increasing tuple (a[i] > a[i + 1])
2. If there is none, reverse the whole sequence, this is the case where the sequence is monotonically decreasing, no next permutation, so return the first one.
3. If there is one, search forward to find the last element a[j] that is strictly minimally larger than a[i]. (i.e a[j] > a[i], a[j] <= a[k] for all k in [i + 1, n), j maximal if multiple j exists)
4. Swap a[i] and a[j] (Here we increase the sequence minimally lexicographically)
5. Reverse a[i + 1] to a[n - 1] (Here we made the remaining list monotonically increasing)
6. Return;

Note the bold last above. This is an important detail. Swapping a[i] and a[j] will generally make the sequence smaller, therefore we need to make sure we find the last one to replace to ensure monotonicity (so that step 5 is valid).

Code:

#include "stdafx.h"

// https://leetcode.com/problems/next-permutation/

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

using namespace std;

namespace _LEET_NEXT_PERMUTATION
{
class Solution {
public:
void nextPermutation(vector<int>& nums)
{
if (nums.size() < 2)
{
return;
}
int i = nums.size() - 2;
while (i >= 0 && nums[i] >= nums[i + 1])
{
i--;
}
int s;
if (i == -1)
{
// This is a monotonically decreasing sequence!
s = 0;
}
else
{
s = i + 1;
// nums[i] < nums[i + 1]
for (int j = i + 2; j < nums.size(); j++)
{
// Finding the last occurrence of the least number larger than nums[i]
// and swap with it to ensure the suffix is still monotonically decreasing
if (nums[j] > nums[i] && nums[j] <= nums[s])
{
s = j;
}
}
int temp = nums[s];
nums[s] = nums[i];
nums[i] = temp;
s = i + 1;
}
int t = nums.size() - 1;
while (s < t)
{
int temp = nums[s];
nums[s] = nums[t];
nums[t] = temp;
s++;
t--;
}
}
};
};

using namespace _LEET_NEXT_PERMUTATION;

int LEET_NEXT_PERMUTATION()
{
Solution solution;
int input_array[5] = { 2, 3, 1, 3, 3 };
vector<int> input(input_array, input_array + 5);
solution.nextPermutation(input);
for (int i = 0; i < 5; i++)
{
cout << input[i] << ", ";
}
return 0;
}

## Sunday, October 30, 2016

### LeetCode OJ - Is Subsequence

Problem:

Analysis:

A greedy strategy would work, if 'aS' is a subsequence of 'BaC' where B does not contain any occurrence of 'a', then S must be a subsequence of C.

Solution:

We will simply march two strings with two pointers and advance the one pointing to s whenever we see a match.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/is-subsequence/

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

using namespace std;

namespace _LEET_IS_SUBSEQUENCE
{
class Solution
{
public:
bool isSubsequence(string s, string t)
{
if (s == "")
{
return true;
}
int i = 0;
for (int j = 0; j < t.length(); j++)
{
if (t[j] == s[i])
{
i++;
if (i == s.length())
{
return true;
}
}
}

return false;
}
};
};

using namespace _LEET_IS_SUBSEQUENCE;

int LEET_IS_SUBSEQUENCE()
{
Solution solution;
cout << solution.isSubsequence("abc", "ahbgdc") << endl;
return 0;
}

### LeetCode OJ - Path Sum II

Problem:

Analysis:

We need both the sum and the path at a leaf node to see if it is good.

Solution:

Therefore, give the sum and path to the target leaf node through recursive calls. In order to avoid copying the path during recursive calls, I used reference. A caveat is that we need to make sure the path is properly restored before the function returns.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/path-sum-ii/

#include "LEET_PATH_SUM_II.h"
#include <queue>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_PATH_SUM_II
{
struct TreeNode
{
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution
{
public:
vector<vector<int>> pathSum(TreeNode* root, int sum)
{
vector<vector<int>> result;
vector<int> path;
pathSum(root, sum, 0, path, result);
return result;
}
private:
void pathSum(TreeNode* root, int target, int sum, vector<int>& path, vector<vector<int>>& result)
{
if (root == nullptr)
{
return;
}

sum = sum + root->val;
path.push_back(root->val);
if (root->left == nullptr && root->right == nullptr && sum == target)
{
result.push_back(path);
}
this->pathSum(root->left, target, sum, path, result);
this->pathSum(root->right, target, sum, path, result);
path.pop_back();
}
};
};

using namespace _LEET_PATH_SUM_II;

int LEET_PATH_SUM_II()
{
Solution solution;
TreeNode a(5);
TreeNode b(4);
TreeNode c(8);
TreeNode d(11);
TreeNode e(13);
TreeNode f(4);
TreeNode g(7);
TreeNode h(2);
TreeNode i(5);
TreeNode j(1);
a.left = &b;
a.right = &c;
b.left = &d;
c.left = &e;
c.right = &f;
d.left = &g;
d.right = &h;
f.left = &i;
f.right = &j;
{
for (auto&& e : p)
{
cout << e << ",";
}
cout << endl;
}
return 0;
}

## Saturday, October 29, 2016

### Hacker Rank - New Year Chaos

Problem:

Analysis:

This is basically counting the number of swapping. This sound very familiar, like an insertion sort would have solved this, but the problem stretch me to find an $O(n)$ solution.

Solution:

In my solution, I maintain a sequence for what I expect, accounting for all the bribe I have seen so far. As an example, let's solve the problem for input 3,2,1,6,5,4

Initially, I expect the sequence simply be 1,2,3,4,5,6

I see 3, the expected position is 3, but the seen position is 1, therefore, there must be two bribes going on for 3 to get to the first position, therefore, the bribe count is 2, and my new expected sequence is:

3,1,2,4,5,6

Now I see 2, the expected position is 3, but the seen position is 1, therefore, there must be one bribe going on for 2 to get to the second position, therefore the bribe count is 3, and my new expected sequence is:

3,2,1,4,5,6

Now I see 1, the expected position is 3, and the seen position is 3, nothing need to be done for him.

The procedure moves on and calculate the final bribe count to be 6. In order to efficiently get the expected position for a person as well as the expected person at his previous position, I maintained a two way map for this sequence.

Code:

#include "stdafx.h"

// https://www.hackerrank.com/challenges/new-year-chaos

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int HACKER_RANK_NEW_YEAR_CHAOS()
{
int t;
cin >> t;
for (int i = 0; i < t; i++)
{
int n;
cin >> n;
vector<int> expect_person;
vector<int> expect_position;
vector<int> actual;
expect_person.resize(n);
expect_position.resize(n);
actual.resize(n);
for (int j = 0; j < n; j++)
{
expect_person[j] = j;
expect_position[j] = j;
cin >> actual[j];
actual[j]--;
}
bool good = true;
int bribe_count = 0;
for (int p = 0; p < n; p++)
{
int seen_person = actual[p];
int position_difference = expect_position[seen_person] - p;
if (position_difference > 2)
{
good = false;
break;
}
bribe_count += position_difference;
if (position_difference >= 1)
{
int current_position = expect_position[seen_person];
int previous_position = current_position - 1;
int previous_person = expect_person[previous_position];
expect_person[previous_position] = seen_person;
expect_position[seen_person] = previous_position;
expect_person[current_position] = previous_person;
expect_position[previous_person] = current_position;
}
if (position_difference == 2)
{
int current_position = expect_position[seen_person];
int previous_position = current_position - 1;
int previous_person = expect_person[previous_position];
expect_person[previous_position] = seen_person;
expect_position[seen_person] = previous_position;
expect_person[current_position] = previous_person;
expect_position[previous_person] = current_position;
}
}
if (!good)
{
cout << "Too chaotic" << endl;
}
else
{
cout << bribe_count << endl;
}
}
return 0;
}

### LeetCode OJ - Counting Bits

Problem:

Analysis:

The key to this problem is that I found this self repeating pattern.

Then we have 1,2 for [10,11]
Then we have 1,2,2,3 for [100,101,110,111]
And so on ...

Solution:

Basically, we found that the $2^{n}+1$ to $2^{n+1}$ is basically repeating $0$ to $2^n$ because the only difference between the two sequences is the most significant bit. We can basically construct the answer using this simple trick.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/counting-bits/

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

using namespace std;

namespace _LEET_COUNTING_BITS
{
class Solution
{
public:
vector<int> countBits(int num)
{
vector<int> result;
result.resize(num + 1);
result[0] = 0;
if (num == 0)
{
return result;
}
result[1] = 1;
int i = 0;
int j = 2;
int b = 1;
while (true)
{
for (i = 0; i < j; i++)
{
if (i + j > num)
{
break;
}
result[i + j] = result[i] + b;
}
if (i + j > num)
{
break;
}
j = i + j;
}

return result;
}
};
};

using namespace _LEET_COUNTING_BITS;

int LEET_COUNTING_BITS()
{
Solution solution;
vector<int> v = solution.countBits(13);
for (int i = 0; i < 14; i++)
{
cout << v[i] << ", ";
}
cout << endl;
return 0;
}

### LeetCode OJ - Battleships in a Board

Problem:

Analysis:

Ignoring the extra constraint that the battleship has special shape, this is basically a connected component problem.

Solution:

As with any connected component problem, one can solve it using disjoint set union find, so that I am doing for this problem.

Just a note for myself, be careful with union, always check if the two input is the same set before trying to do the union.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/battleships-in-a-board/

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

using namespace std;

namespace _LEET_BATTLESHIPS_IN_A_BOARD
{
class Solution
{
public:
int countBattleships(vector<vector<char>>& board)
{
int m = board.size();
if (m == 0)
{
return 0;
}
int n = board[0].size();
if (n == 0)
{
return 0;
}
vector<int> disjoint_sets;
disjoint_sets.resize(m * n);
for (int i = 0; i < m * n; i++)
{
disjoint_sets[i] = -1;
}
for (int r = 0; r < m - 1; r++)
{
for (int c = 0; c < n - 1; c++)
{
if (board[r][c] == 'X' && board[r + 1][c] == 'X')
{
union_sets(disjoint_sets, r * n + c, (r + 1) * n + c);
}
if (board[r][c] == 'X' && board[r][c + 1] == 'X')
{
union_sets(disjoint_sets, r * n + c, r * n + c + 1);
}
}
if (board[r][n - 1] == 'X' && board[r + 1][n - 1] == 'X')
{
union_sets(disjoint_sets, r * n + (n - 1), (r + 1) * n + (n - 1));
}
}
for (int c = 0; c < n - 1; c++)
{
if (board[m - 1][c] == 'X' && board[m - 1][c + 1] == 'X')
{
union_sets(disjoint_sets, (m - 1) * n + c, (m - 1) * n + c + 1);
}
}

int count = 0;
for (int r = 0; r < m; r++)
{
for (int c = 0; c < n; c++)
{
if (board[r][c] == 'X' && disjoint_sets[r * n + c] < 0)
{
count++;
}
}
}

return count;
}
private:
int find(vector<int>& disjoint_sets, int v)
{
if (disjoint_sets[v] < 0)
{
return v;
}
else
{
return disjoint_sets[v] = find(disjoint_sets, disjoint_sets[v]);
}
}
void union_sets(vector<int>& disjoint_sets, int u, int v)
{
int set1 = find(disjoint_sets, u);
int set2 = find(disjoint_sets, v);
if (set1 != set2)
{
int size1 = -disjoint_sets[set1];
int size2 = -disjoint_sets[set2];
if (size1 > size2)
{
disjoint_sets[set2] = set1;
disjoint_sets[set1] -= size2;
}
else
{
disjoint_sets[set1] = set2;
disjoint_sets[set2] -= size1;
}
}
}
};
};

using namespace _LEET_BATTLESHIPS_IN_A_BOARD;

int LEET_BATTLESHIPS_IN_A_BOARD()
{
Solution solution;
vector<vector<char>> board;
board.resize(3);
for (int i = 0; i < 3; i++)
{
board[i].resize(4);
}
board[0][0] = 'X';    board[0][1] = '.';    board[0][2] = '.';    board[0][3] = 'X';
board[1][0] = '.';    board[1][1] = '.';    board[1][2] = '.';    board[1][3] = 'X';
board[2][0] = '.';    board[2][1] = '.';    board[2][2] = '.';    board[2][3] = 'X';
cout << solution.countBattleships(board) << endl;
return 0;
}