## Tuesday, December 29, 2015

### LeetCode OJ - Bulb Switcher

Problem:

Solution:

A bulb $b$ is going to be flipped whenever the current round number $a$ is a factor of $b$.
Therefore, a bulb is left on only if it is a perfect square (any other number has even number of factors)

With that, the code is trivial.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/bulb-switcher/

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

using namespace std;

namespace _LEET_BULB_SWITCHER
{
/*
* Analysis:
* For the general mth bulb, it is toggled in the nth round if n is a factor of m
* For example, the 3 bulb is on after round 1 and off after round 3 and will never turn on again (no matter what n is)
* That applies for all prime
* That actually also apply for all composite with even number of factors
* What number has odd number of factors? Squares
* So it is really just asking how many squares are there
*/
class Solution {
public:
int bulbSwitch(int n)
{
int count = 0;
int k = 3;
int s = 1;
while (n >= s)
{
count++;
s += k;
k += 2;
}

return count;
}
};
};

using namespace _LEET_BULB_SWITCHER;

int LEET_BULB_SWITCHER()
{
Solution solution;
for (int i = 1; i <= 10; i++)
{
cout << solution.bulbSwitch(i) << endl;
}
return 0;
}

## Friday, December 4, 2015

### LeetCode OJ - Game of Life

Problem:

Solution:

This is a relatively trivial programming exercise except we need to do it in-place. Technically, it isn't really in-place, it is just to leverage we used more spaces in the input representation than it would have to.

The key idea of the code involve carefully encoding the states.

1 represent it was alive

and this encoding is dictated by the problem statement.

Now I have the freedom to choose the temp states, at minimal I need two temp states,

The encoding should be chosen to maximize computational speed for accessing its old state and new state. There could be multiple ways of doing that, but I chose to do this.

Step 1) Keep the LSB unchanged, so LSB represents old state

Now we can choose the second bit, notice if we do not want to change an array entry if the cell stay the same. then we cannot use the second bit to represent the new state, so we simply set the second bit on when it is changed, so overall, LSB is the old state, and second bit means change or not.

Last but not least, we need to map (1, 2) -> 1 and also (0, 3) -> 0. At a glance, seems no easy way. Here is the cleverness, if we look at the number + 1, then we find something interesting

0 + 1 -> 1 -> 001 need to map to 0
1 + 1 -> 2 -> 010 need to map to 1
2 + 1 -> 3 -> 011 need to map to 1
3 + 1 -> 4 -> 100 need to map to 0

See, it is simply the second bit of the binary representation, so we saved ourselves from doing conditionals in the mapping process.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/game-of-life/

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

using namespace std;

namespace _LEET_GAME_OF_LIFE
{
class Solution
{
public:
void gameOfLife(vector<vector<int>>& board)
{
// Note the design of the NOW variant
// the least significant bit indicate the old state, so we just read the LSB for old state
const int LIVE = 1;

int height = board.size();
if (height == 0)
{
return;
}
int width = board[0].size();
if (width == 0)
{
return;
}
for (int r = 0; r < height; r++)
{
for (int c = 0; c < width; c++)
{
int living_neighbor_count = 0;
for (int rd = -1; rd <= 1; rd++)
{
for (int cd = -1; cd <= 1; cd++)
{
int nr = r + rd;
int nc = c + cd;
if (nr >= 0 && nr < height && nc >= 0 && nc < width)
{
if ((board[nr][nc] & 1) == 1)
{
living_neighbor_count++;
}
}
}
}
if ((board[r][c] & 1) == 1)
{
// For living cell, we need to discount itself.
living_neighbor_count--;
if (living_neighbor_count < 2 || living_neighbor_count > 3)
{
}
}
else
{
if (living_neighbor_count == 3)
{
}
}
}
}
// Clear temp flags
for (int r = 0; r < height; r++)
{
for (int c = 0; c < width; c++)
{
// Now we need a function that maps
// LIVE (1) and NOW_LIVE_WAS_DEAD (2) to 1
// The problem is easier if we look at the number + 1
// 0 + 1 = 1 (001) -> 0
// 3 + 1 = 4 (100) -> 0
// 1 + 1 = 2 (010) => 1
// 2 + 1 = 3 (011) => 1
// Note the answer is simply the second bit
board[r][c] = ((board[r][c] + 1) & 2) >> 1;
}
}
}
};
};

using namespace _LEET_GAME_OF_LIFE;

int LEET_GAME_OF_LIFE()
{
Solution solution;
vector<vector<int>> board;
board.resize(3);
board[0].push_back(1);    board[0].push_back(1); board[0].push_back(0);
board[1].push_back(1);    board[1].push_back(1); board[1].push_back(0);
board[2].push_back(1);    board[2].push_back(1); board[2].push_back(0);
solution.gameOfLife(board);
cout << board[0][0] << board[0][1] << board[0][2] << endl;
cout << board[1][0] << board[1][1] << board[1][2] << endl;
cout << board[2][0] << board[2][1] << board[2][2] << endl;
return 0;
}

### LeetCode OJ - Combinations

Problem:

Solution:

Building up the combination recursively.

The set of combinations involving [a .. n] of size k can be computed by:

For each number p in [a...n]
Generate all combinations R of size k - 1 in [p + 1 ... n]
Prepend R with p, output all combinations.

First, notice all the combination outputted are generated with size k, which is good.
Second, notice any valid combination will eventually be generated in some execution path.
Finally, the combination outputted can never have duplicates.

All of these statements need to be proved, but I will skip that, it is trivial despite it will involve lots of notations.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/combinations/

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

using namespace std;

namespace _LEET_COMBINATIONS
{
class Solution
{
private:
void generate_combinations(vector<bool>& used, int start, int k, vector<vector<int>>& result)
{
if (k == 0)
{
vector<int> found_combination;
for (unsigned int i = 0; i < used.size(); i++)
{
if (used[i])
{
found_combination.push_back(i + 1);
}
}
result.push_back(found_combination);
}
else
{
for (unsigned int i = start; i < used.size(); i++)
{
if (!used[i])
{
used[i] = true;
generate_combinations(used, i + 1, k - 1, result);
used[i] = false;
}
}
}
}
public:
vector<vector<int>> combine(int n, int k)
{
vector<vector<int>> result;
vector<bool> used;
used.resize(n);
for (int i = 0; i < n; i++)
{
used[i] = false;
}
generate_combinations(used, 0, k, result);
return result;
}
};
};

using namespace _LEET_COMBINATIONS;

int LEET_COMBINATIONS()
{
Solution solution;
vector<vector<int>> result = solution.combine(4, 2);
for (unsigned int i = 0; i < result.size(); i++)
{
for (unsigned int j = 0; j < result[i].size(); j++)
{
cout << result[i][j] << " ";
}
cout << endl;
}
return 0;
}

## Tuesday, December 1, 2015

### LeetCode OJ - Word Pattern

Problem:

Solution:

A simple problem, just to be careful with the cases.

• Too many patterns.
• Too many tokens in the string.
• One pattern match multiple tokens
• One token match multiple patterns

Once the cases are carefully enumerated, the coding of it is rather trivial.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/word-pattern/

#include "LEET_WORD_PATTERN.h"
#include <map>
#include <string>
#include <iostream>

using namespace std;

namespace _LEET_WORD_PATTERN
{
class Solution
{
private:
bool match(map<char, string>& p_to_s, map<string, char>& s_to_p, char p, string s)
{
map<char, string>::iterator p_to_s_probe = p_to_s.find(p);
map<string, char>::iterator s_to_p_probe = s_to_p.find(s);
if (p_to_s_probe == p_to_s.end() && s_to_p_probe == s_to_p.end())
{
p_to_s.insert(pair<char, string>(p, s));
s_to_p.insert(pair<string, char>(s, p));
return true;
}
else if(p_to_s_probe != p_to_s.end() && s_to_p_probe != s_to_p.end())
{
return (p_to_s_probe->second == s) && (s_to_p_probe->second == p);
}
else
{
return false;
}
}
public:
bool wordPattern(string pattern, string str)
{
map<char, string> p_to_s;
map<string, char> s_to_p;
unsigned int s_i = 0;
unsigned int p_i = 0;
for (unsigned int s_e = 0; s_e < str.size(); s_e++)
{
if (str[s_e] == ' ')
{
if (p_i < pattern.size())
{
if (match(p_to_s, s_to_p, pattern[p_i++], str.substr(s_i, s_e - s_i)))
{
s_i = s_e + 1;
}
else
{
return false;
}
}
else
{
return false;
}
}
}
if (p_i < pattern.size())
{
if (!match(p_to_s, s_to_p, pattern[p_i++], str.substr(s_i, str.size() - s_i)))
{
return false;
}
}
else
{
return false;
}
if (p_i != pattern.size())
{
return false;
}
return true;
}
};
};

using namespace _LEET_WORD_PATTERN;

int LEET_WORD_PATTERN()
{
Solution solution;
cout << solution.wordPattern("abba", "dog cat cat dog") << endl;
cout << !solution.wordPattern("abba", "dog cat cat fish") << endl;
cout << !solution.wordPattern("aaaa", "dog cat cat dog") << endl;
cout << !solution.wordPattern("abba", "dog dog dog dog") << endl;
return 0;
}

### LeetCode OJ - Populating Next Right Pointers in Each Node II

Problem:

Solution:

If we are allowed to use more space, then a simple BFS would have solved the problem, the twist in this problem is the requirement to use constant space.

Well, except the space we already occupied already! We have a free linked list to use, the next pointers of the visited nodes, and we have to populate them anyway as output!

Think like induction, layer by layer.

The next of the root is easy, it has to be NULL. The leftmost node on this layer is obviously root.

Now we are trying to build the next pointers of the $n$ layer, assuming we know the leftmost node of the $n - 1$ layer, and that the next pointers are all set correctly there.

Then we just walk the $n - 1$ layer from left to right, if we see any child, we just set the child's next pointer correctly, keep track of the first node seen as the leftmost node, and that's it!

By induction we will be able to build the whole tree - a virtual node is conveniently used to reduce the number of cases to deal with when building the next layer nodes.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/

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

using namespace std;

namespace _LEET_POPULATING_NEXT_RIGHT_POINTERS_IN_EACH_NODE_II
{
{
int val;
TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
};

class Solution
{
public:
{
if (root == NULL)
{
return;
}

root->next = NULL;

virtualNode.next = root;

while (virtualNode.next != NULL)
{
nextLayerEnds->next = NULL;
while (currentLayerCursor != NULL)
{
if (currentLayerCursor->left != NULL)
{
nextLayerEnds->next = currentLayerCursor->left;
nextLayerEnds = nextLayerEnds->next;
}
if (currentLayerCursor->right != NULL)
{
nextLayerEnds->next = currentLayerCursor->right;
nextLayerEnds = nextLayerEnds->next;
}
currentLayerCursor = currentLayerCursor->next;
}
}
}
};
};

using namespace _LEET_POPULATING_NEXT_RIGHT_POINTERS_IN_EACH_NODE_II;

int LEET_POPULATING_NEXT_RIGHT_POINTERS_IN_EACH_NODE_II()
{
a.left = &b;
a.right = &c;
b.left = &d;
b.right = &e;
c.left = NULL;
c.right = &g;
d.left = NULL;
d.right = NULL;
e.left = NULL;
e.right = NULL;
g.left = NULL;
g.right = NULL;
Solution solution;
solution.connect(&a);
cout << ((a.next == NULL) ? "Yes" : "No") << endl;
cout << ((b.next == &c) ? "Yes" : "No") << endl;
cout << ((c.next == NULL) ? "Yes" : "No") << endl;
cout << ((d.next == &e) ? "Yes" : "No") << endl;
cout << ((e.next == &g) ? "Yes" : "No") << endl;
cout << ((g.next == NULL) ? "Yes" : "No") << endl;
return 0;
}