成吉思（刷）: March 2016

Thursday, March 31, 2016

Implementation of pdist in Theano

There days I come cross a problem that need me to compute pairwise distance for two given matrix in theano. Such functionality is built as pdist() function in scipy. As far as I know there is no such equivalent function in theano for all of them at once. However, each specific distance, being a closed form mathematical expression, can be written down in Theano as such and then compiled.

Take as an example the minkowski p norm distance (wiki)

	import theano
	import theano.tensor as T
	X = T.fmatrix('X')
	Y = T.fmatrix('Y')
	P = T.scalar('P')
	translation_vectors = X.reshape((X.shape[0], 1, -1)) - Y.reshape((1, Y.shape[0], -1))
	minkowski_distances = (abs(translation_vectors) P).sum(2) (1. / P)
	f_minkowski = theano.function([X, Y, P], minkowski_distances)

view raw pdist_theano.py hosted with ❤ by GitHub

Note that abs calls the built-in __abs__, so abs is also a theano function. We can now compare this to pdist:

LeetCode Q200: Number of Islands

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

Answer: 1

Example 2:

Answer: 3

	class Solution {
	public:
	int numIslands(vector<vector<char>>& grid) {
	int res=0;
	if(grid.empty())
	return res;
	vector<vector<int> > accessed(grid.size(), vector<int>(grid[0].size(), 0));
	for(int i=0; i<grid.size(); i++){
	for(int j=0; j<grid[i].size(); j++){
	if(grid[i][j]=='0' \|\| accessed[i][j]==1)
	continue;

	queue<pair<int, int> > Q;
	Q.push(pair<int, int> (i, j));
	accessed[i][j]=1;

	while(!Q.empty()){
	pair<int, int> p=Q.front();
	Q.pop();

	if(p.first>0&&grid[p.first-1][p.second]=='1'&&accessed[p.first-1][p.second]==0){
	Q.push(pair<int, int> (p.first-1, p.second));
	accessed[p.first-1][p.second]=1;
	}
	if(p.first<grid.size()-1&&grid[p.first+1][p.second]=='1'&&accessed[p.first+1][p.second]==0){
	Q.push(pair<int, int> (p.first+1, p.second));
	accessed[p.first+1][p.second]=1;
	}
	if(p.second>0&&grid[p.first][p.second-1]=='1'&&accessed[p.first][p.second-1]==0){
	Q.push(pair<int, int> (p.first, p.second-1));
	accessed[p.first][p.second-1]=1;
	}
	if(p.second<grid[0].size()-1&&grid[p.first][p.second+1]=='1'&&accessed[p.first][p.second+1]==0){
	Q.push(pair<int, int> (p.first, p.second+1));
	accessed[p.first][p.second+1]=1;
	}
	}

	res++;
	}
	}
	return res;
	}
	};

view raw Q200NumberOfIslands.cpp hosted with ❤ by GitHub

Round 2 solution:
DFS

	class Solution {
	public:
	void helper(vector<vector<char> >& grid, vector<vector<bool> >& mark, int r, int c){
	if(r<0\|\|r>=grid.size()\|\|c<0\|\|c>=grid[0].size()\|\|grid[r][c]=='0'\|\|mark[r][c]==true)
	return;

	mark[r][c]=true;
	int steps[] = {0, 0, 0, -1, 0, 1, -1, 0, 1, 0};
	for(int i=0; i<5; i++)
	helper(grid, mark, r+steps[i2], c+steps[i2+1]);
	}

	int numIslands(vector<vector<char>>& grid) {
	int res = 0;
	if(grid.empty())
	return res;

	vector<vector<bool> > mark(grid.size(), vector<bool>(grid[0].size(), false));

	for(int i=0; i<grid.size(); i++){
	for(int j=0; j<grid[0].size(); j++){
	if(grid[i][j]=='1'&&mark[i][j]==false){
	res++;
	helper(grid, mark, i, j);
	}
	}
	}
	return res;
	}
	};

view raw Q200Rnd2.cpp hosted with ❤ by GitHub

Rnd3 sol:

	class Solution {
	public:
	void helper(vector<vector<char>>& grid, int row, int col){
	if(row<0\|\|col<0\|\|row>=grid.size()\|\|col>=grid[0].size()\|\|grid[row][col]=='0')
	return;

	grid[row][col]='0';
	helper(grid, row, col-1);
	helper(grid, row, col+1);
	helper(grid, row-1, col);
	helper(grid, row+1, col);
	}

	int numIslands(vector<vector<char>>& grid) {
	int res = 0;
	if(grid.empty())
	return res;
	for(int i=0; i<grid.size(); i++){
	for(int j=0; j<grid[0].size(); j++){
	if(grid[i][j]=='0')
	continue;

	helper(grid, i, j);
	res++;
	}
	}
	return res;
	}
	};

view raw Q200Rnd3.cpp hosted with ❤ by GitHub

LeetCode Q199: Binary Tree Right Side View

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

For example:
Given the following binary tree,

   1            <--- 2="" 3="" 4="" 5="" pre="">


You should return [1, 3, 4].



Solution:

	/**
	* Definition for a binary tree node.
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class Solution {
	public:
	vector<int> rightSideView(TreeNode* root) {
	vector<int> res;
	if(root==NULL)
	return res;

	queue<TreeNode*> Q;
	int last=0;
	int cur=0;

	Q.push(root);
	last = 1;

	while(!Q.empty()){
	TreeNode* frontNode=Q.front();
	Q.pop();

	if(last==1)
	res.push_back(frontNode->val);

	if(frontNode->left!=NULL){
	Q.push(frontNode->left);
	cur++;
	}
	if(frontNode->right!=NULL){
	Q.push(frontNode->right);
	cur++;
	}

	last--;
	if(last==0){
	last=cur;
	cur=0;
	}
	}

	return res;
	}
	};

view raw Q199BinaryTreeRightSideView.cpp hosted with ❤ by GitHub

Rnd3

	/**
	* Definition for a binary tree node.
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class Solution {
	public:
	void helper(TreeNode* root, unordered_map<int, int>& myMap, int level){
	if(root==NULL)
	return;

	auto it = myMap.find(level);
	if(it==myMap.end()){
	myMap[level]=root->val;
	}
	helper(root->right, myMap, level+1);
	helper(root->left, myMap, level+1);
	}

	vector<int> rightSideView(TreeNode* root) {
	vector<int> res;
	if(root==NULL)
	return res;
	unordered_map<int, int> myMap;
	helper(root, myMap, 0);

	int i=0;
	auto it = myMap.find(i);
	while(it!=myMap.end()){
	res.push_back(it->second);
	it = myMap.find(++i);
	}

	return res;
	}
	};

view raw Q199Rnd3.cpp hosted with ❤ by GitHub

LeetCode Q198: House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Solution:

DP, if to decide whether to robber nums[i], we need to decide the maximum profit between following two options:

max ( profit( nums[0:i-1] ), profit( nums[0:i-2 ]+profit(nums[i]) )

	class Solution {
	public:
	int helper(vector<int> & nums, vector<int> & t, int n){
	if(n<=0){
	t[n]=n==0? 0:t[n];
	return 0;
	}

	int p0=t[n]==-1? helper(nums, t, n-1):t[n];
	int p1=t[n]==-1? helper(nums, t, n-2)+nums[n-1]:t[n];
	t[n]=max(p0, p1);
	}
	int rob(vector<int>& nums) {
	vector<int> t(nums.size()+1, -1);
	int res=helper(nums, t, nums.size());
	return res;
	}
	};

view raw Q198HouseRobber.cpp hosted with ❤ by GitHub

LooetCode Q191: Number of 1 Bits

Write a function that takes an unsigned integer and returns the number of ’1' bits it has (also known as the Hamming weight).

For example, the 32-bit integer ’11' has binary representation 00000000000000000000000000001011, so the function should return 3.

My solution: Time complexity O(1) it counts entire 32 bits.

	class Solution {
	public:
	int hammingWeight(uint32_t n) {
	int res=0;
	for(int i=0; i<32; i++)
	res+= (n>>i)&1;
	return res;
	}
	};

view raw Q191Numberof1Bits.cpp hosted with ❤ by GitHub

Optimal solution: Although the time complexity is also O(1), it takes k steps to finish, where k is the number of 1s in int. The idea is to remove an 1 at a time. The trick is: An elegant way to check is an integer has exactly one bit set to 1. Given integer say int i=k, we could check if (i & (i-1))==0, if true then only one bit is 1 in i. In the same time (i & (i-1))==0 actually check if number i is a power of 2.

	class Solution {
	public:
	int hammingWeight(uint32_t n){
	int res = 0;
	while(n)
	{
	n &= n - 1;
	++ res;
	}
	return res;
	}
	};

view raw Q191-2.cpp hosted with ❤ by GitHub

LeetCode Q190 Reverse Bits

Reverse bits of a given 32 bits unsigned integer.

For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as00111001011110000010100101000000).

Follow up:
If this function is called many times, how would you optimize it?

My solution:

	class Solution {
	public:
	uint32_t reverseBits(uint32_t _n) {
	int p0=0;
	int p1=31;
	uint32_t n = _n;
	while(p0<=p1){
	int b0 = n>>p0 & 1;
	int b1 = n>>p1 & 1;

	if(b0==1)
	n = n \| b0<<p1;
	else
	n = n & ~(1<<p1);

	if(b1==1)
	n = n \| b1<<p0;
	else
	n = n & ~(1<<p0);

	p0++;
	p1--;
	}
	return n;
	}
	};

view raw Q190ReverseBits.cpp hosted with ❤ by GitHub

A cool solution using divide and conquer you should not miss!

	class Solution {
	public:
	uint32_t reverseBits(uint32_t n) {
	n = (n >> 16) \| (n << 16);
	n = ((n & 0xff00ff00) >> 8) \| ((n & 0x00ff00ff) << 8);
	n = ((n & 0xf0f0f0f0) >> 4) \| ((n & 0x0f0f0f0f) << 4);
	n = ((n & 0xcccccccc) >> 2) \| ((n & 0x33333333) << 2);
	n = ((n & 0xaaaaaaaa) >> 1) \| ((n & 0x55555555) << 1);
	return n;
	}
	};

view raw Q190-2.cpp hosted with ❤ by GitHub

Another solution you have to know !

	uint32_t reverseBits(uint32_t n) {
	uint32_t m = 0;
	for (int i = 0; i < 32; i++, n >>= 1) {
	m <<= 1;
	m \|= n & 1;
	}
	return m;
	}

view raw Q190-2.cpp hosted with ❤ by GitHub

Round 2 solution:

	class Solution {
	public:
	uint32_t reverseBits(uint32_t n) {
	for(int i=0; i<=15; i++){
	int p0 = i;
	int p1 = 31-i;

	if(((n>>p0)&1)^((n>>p1)&1)){
	n = (1<<p0)^n;
	n = (1<<p1)^n;
	}
	}
	return n;
	}
	};

view raw Q190Rnd2.cpp hosted with ❤ by GitHub

LeetCode Q189: Rotate Array

Rotate an array of n elements to the right by k steps.

For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].

Note:
Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.

More solutions are shown in https://leetcode.com/discuss/27387/summary-of-c-solutions

My Solution:

	class Solution {
	public:
	void rotate(vector<int>& nums, int k) {
	k=k%nums.size();
	reverse(nums.begin(), nums.end());
	reverse(nums.begin(), nums.begin()+k);
	reverse(nums.begin()+k, nums.end());
	}
	};

view raw Q189RotateArray.cpp hosted with ❤ by GitHub

Wednesday, March 30, 2016

LeetCode Q188: Best Time to Buy and Sell Stock IV (hard)

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most k transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Solution:

Using DP. Iinspired buy solution of Sell Stock III, we keep track the price and profit at current transaction.

	class Solution {
	public:
	int maxProfit(int k, vector<int>& prices) {
	int maxProfit=0;

	if(prices.size()<2)
	return 0;
	if(k>prices.size()/2){
	for(int i=1; i<prices.size(); i++)
	maxProfit += max(prices[i]-prices[i-1], 0);
	return maxProfit;
	}

	int hold[k+1];
	int rele[k+1];
	for (int i=0;i<=k;++i){
	hold[i] = INT_MAX;
	rele[i] = 0;
	}

	for(int i=0; i<prices.size(); i++){
	for(int j=k; j>=1; j--){
	rele[j] = max(rele[j], prices[i]-hold[j]);
	hold[j] = min(hold[j], prices[i]-rele[j-1]);
	maxProfit=max(maxProfit, rele[j]);
	}
	}
	return maxProfit;
	}
	};

view raw Q188SellStockIV.cpp hosted with ❤ by GitHub

LeetCode Q187: Repeated DNA Sequences

All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.

Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.

For example,

Given s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT",

Return:
["AAAAACCCCC", "CCCCCAAAAA"].

Solution 1:
Using unordered_map to save substring.

	class Solution {
	public:
	vector<string> findRepeatedDnaSequences(string s) {
	unordered_map<string, int> myMap;
	vector<string> res;
	if(s.length()<=10)
	return res;

	for(int i=0; i<=s.length()-10; i++){
	string substring = s.substr(i, 10);
	if(myMap[substring]==0){
	myMap[substring]=1;
	}else{
	if(myMap[substring]==1){
	res.push_back(substring);
	myMap[substring]++;
	}
	else{
	if(myMap[substring]>1)
	continue;
	}
	}
	}
	return res;
	}
	};

view raw Q187-1.cpp hosted with ❤ by GitHub

Solution 2:
Converting substring to integer and hash integer instead of substring. Need to use different code for 'A', 'C', 'G', 'T'.

	class Solution {
	public:
	int str2int(string s){
	int str=0;
	for(int i=0; i<s.length(); i++){
	if(s[i]=='A')
	str = str<<2 \| 0;
	if(s[i]=='C')
	str = str<<2 \| 1;
	if(s[i]=='G')
	str = str<<2 \| 2;
	if(s[i]=='T')
	str = str<<2 \| 3;
	}
	return str;
	}
	vector<string> findRepeatedDnaSequences(string s) {
	unordered_map<int, int> myMap;
	vector<string> res;
	for(int i=0; i+10<=s.size(); i++){
	if(myMap[str2int(s.substr(i, 10))]++==1)
	res.push_back(s.substr(i, 10));
	}
	return res;
	}
	};

view raw Q187-2.cpp hosted with ❤ by GitHub

Tuesday, March 29, 2016

A blog for reviewing system design in about 1 month, highly recommended.

System Design Study Group

LeetCode Q186: Reverse Words in a String II

Given an input string, reverse the string word by word. A word is defined as a sequence of non-space characters.

The input string does not contain leading or trailing spaces and the words are always separated by a single space.

For example,
Given s = "the sky is blue",
return "blue is sky the".

	class Solution {
	public:
	void reverseWords(string &s){
	reverse(s.begin(), s.end());

	auto l=s.begin();
	auto r=s.begin();

	while(l!=s.end()){
	while(*r!=' '&& r!=s.end())
	r++;
	reverse(l, r);
	l=r+1;
	if(r==s.end())
	break;
	else
	r++;
	}
	}
	};

view raw Q186ReverseWordsinaStringII.cpp hosted with ❤ by GitHub

LeetCode Q179: Largest Number

Given a list of non negative integers, arrange them such that they form the largest number.

For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.

Note: The result may be very large, so you need to return a string instead of an integer.

Solution:

Since we need to decide which number is in front of another for each pair of numbers, we could come up a new rule for comparison in sort function.

	class Solution {
	public:
	string largestNumber(vector<int>& num) {
	sort(num.begin(), num.end(), [](int a, int b) { return to_string(a)+to_string(b) > to_string(b)+to_string(a); });
	string res;
	for(int i=0; i<num.size(); i++)
	res=res+to_string(num[i]);
	return res[0]=='0' ? "0":res;
	}
	};

view raw Q179LargestNumber.cpp hosted with ❤ by GitHub

LeetCode Q174: Dungeon Game (hard)

The demons had captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight (K) was initially positioned in the top-left room and must fight his way through the dungeon to rescue the princess.

The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately.

Some of the rooms are guarded by demons, so the knight loses health (negative integers) upon entering these rooms; other rooms are either empty (0's) or contain magic orbs that increase the knight's health (positive integers).

In order to reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step.

Write a function to determine the knight's minimum initial health so that he is able to rescue the princess.

For example, given the dungeon below, the initial health of the knight must be at least 7 if he follows the optimal path RIGHT-> RIGHT -> DOWN -> DOWN.

-2 (K)	-3	3
-5	-10	1
10	30	-5 (P)

Notes:

The knight's health has no upper bound.
Any room can contain threats or power-ups, even the first room the knight enters and the bottom-right room where the princess is imprisoned.

Solution:

Use hp[i][j] to store the min hp needed at position (i, j), then do the calculation from right-bottom to left-up.

Note: adding dummy row and column would make the code cleaner.

Q: Why do we start from the bottom right corner?

A: Because it is known that the knight has to reach the end with at least one health point and the health point with which the knight should start with is not known.

	class Solution {
	public:
	int calculateMinimumHP(vector<vector<int> > &dungeon) {
	int M = dungeon.size();
	int N = dungeon[0].size();
	// hp[i][j] represents the min hp needed at position (i, j)
	// Add dummy row and column at bottom and right side
	vector<vector<int> > hp(M + 1, vector<int>(N + 1, INT_MAX));
	hp[M][N - 1] = 1;
	hp[M - 1][N] = 1;
	for (int i = M - 1; i >= 0; i--) {
	for (int j = N - 1; j >= 0; j--) {
	int need = min(hp[i + 1][j], hp[i][j + 1]) - dungeon[i][j];
	hp[i][j] = need <= 0 ? 1 : need; // at least 1 blood needed at each slot.
	}
	}
	return hp[0][0];
	}
	};

view raw Q174DungeonGame.cpp hosted with ❤ by GitHub

LeetCode Q173: Binary Search Tree Iterator

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

	/**
	* Definition for binary tree
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class BSTIterator {
	public:
	BSTIterator(TreeNode *root) {
	if(root==NULL)
	return;

	inorderTraverse(root, sorted);
	idx=0;
	}

	/** @return whether we have a next smallest number */
	bool hasNext() {
	if(sorted.empty())
	return false;
	return idx<=sorted.size()-1;
	}

	/** @return the next smallest number */
	int next() {
	int res=sorted[idx]->val;
	idx++;
	return res;
	}

	void inorderTraverse(TreeNode* root, vector<TreeNode*>& sorted){
	if(root==NULL)
	return;

	inorderTraverse(root->left, sorted);
	sorted.push_back(root);
	inorderTraverse(root->right, sorted);
	}

	vector<TreeNode*> sorted;
	int idx;
	};

	/**
	* Your BSTIterator will be called like this:
	* BSTIterator i = BSTIterator(root);
	* while (i.hasNext()) cout << i.next();
	*/

view raw Q173BinarySearchTreeIterator.cpp hosted with ❤ by GitHub

Round 2 solution:

	/**
	* Definition for binary tree
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class BSTIterator {
	public:
	BSTIterator(TreeNode *root) {
	if(root!=NULL){
	myStack.push(root);
	curNode=root->left;
	}else{
	curNode=NULL;
	}
	}

	/** @return whether we have a next smallest number */
	bool hasNext() {
	return !(curNode==NULL&&myStack.empty());
	}

	/** @return the next smallest number */
	int next() {
	int res = 0;
	while(true){
	if(curNode==NULL&&!myStack.empty()){
	TreeNode* top = myStack.top();
	res = top->val;
	myStack.pop();
	curNode=top->right;
	return res;
	}else{
	while(curNode!=NULL){
	myStack.push(curNode);
	curNode=curNode->left;
	}
	}
	}
	}

	stack<TreeNode*> myStack;
	TreeNode* curNode;
	};

	/**
	* Your BSTIterator will be called like this:
	* BSTIterator i = BSTIterator(root);
	* while (i.hasNext()) cout << i.next();
	*/

view raw Q173Rnd2.cpp hosted with ❤ by GitHub

LeetCode Q172: Factorial Trailing Zeros

Given an integer n, return the number of trailing zeroes in n!.

Note: Your solution should be in logarithmic time complexity.

Solution:

Zeros is produced by "5 x even number", so count how many 5s in each number.

	class Solution {
	public:
	int trailingZeroes(int n) {
	int ans=0;
	while (n>=5) {
	n/=5;
	ans+=n;
	}
	return ans;
	}
	};

view raw Q172FactorialTrailingZeros.cpp hosted with ❤ by GitHub

Monday, March 28, 2016

LeetCode Q171: Excel Sheet Coumn Numer

Related to question Excel Sheet Column Title

Given a column title as appear in an Excel sheet, return its corresponding column number.

For example:

    A -> 1
    B -> 2
    C -> 3
    ...
    Z -> 26
    AA -> 27
    AB -> 28

	class Solution {
	public:
	int titleToNumber(string s) {
	int base=0;
	int res=0;
	for(int i=s.length()-1; i>=0; i--){
	int t=s[i]-'A'+1;
	res = res+t*pow(26, base++);
	}
	return res;
	}
	};

view raw Q171ExcelSheetColumnNumber.cpp hosted with ❤ by GitHub

LeetCode Q170: Two Sum III - Data structure desing

Design and implement a TwoSum class. It should support the following operations: add and find.

add - Add the number to an internal data structure.
find - Find if there exists any pair of numbers which sum is equal to the value.

For example,

add(1); add(3); add(5);
find(4) -> true
find(7) -> false

Solution:
O(1) add
O(n) find: using hash table.

Need to care about when two numbers are equal. In this case, this number has to be added at least twice.

By using unordered_map::count() is much faster than unordered_map::find().

	class TwoSum {
	public:

	// Add the number to an internal data structure.
	void add(int number) {
	myMap[number]=myMap[number]+1;
	}

	// Find if there exists any pair of numbers which sum is equal to the value.
	bool find(int value) {
	for(auto it: myMap){
	int p0=it.first;
	int p1=value-p0;
	if(p1==p0){
	if(myMap[p1]>1)
	return true;
	continue;
	}

	if(myMap.count(p1))
	return true;
	}
	return false;
	}

	unordered_map<int, int> myMap;
	};

	// Your TwoSum object will be instantiated and called as such:
	// TwoSum twoSum;
	// twoSum.add(number);
	// twoSum.find(value);

view raw Q170TwoSumIII.cpp hosted with ❤ by GitHub

LeetCode Q169: Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Solution 1:
Using hash table:

	class Solution {
	public:
	int majorityElement(vector<int>& nums) {
	unordered_map<int, int> myMap;

	for(int i=0; i<nums.size(); i++){
	myMap[nums[i]]=myMap[nums[i]]+1;
	if(myMap[nums[i]]>int(nums.size())/2)
	return nums[i];
	}
	}
	};

view raw Q169MajorityElement.cpp hosted with ❤ by GitHub

Solution 2:

	public class Solution {
	public int majorityElement(int[] num) {

	int major=num[0], count = 1;
	for(int i=1; i<num.length;i++){
	if(count==0){
	count++;
	major=num[i];
	}else if(major==num[i]){
	count++;
	}else count--;

	}
	return major;
	}
	}

view raw Q169-2.cpp hosted with ❤ by GitHub

Actually there are many other solutoins, please see: Here

Round 2 solution:

	class Solution {
	public:
	int majorityElement(vector<int>& nums) {
	int cnt=1;
	int num=nums[0];

	for(int i=1; i<nums.size(); i++){
	if(nums[i]==num)
	cnt++;
	else
	if(--cnt==0){
	num=nums[i];
	cnt=1;
	}
	}
	return num;
	}
	};

view raw Q169Rnd2.cpp hosted with ❤ by GitHub

LeetCode Q168: Excel Sheet Column Title

Given a positive integer, return its corresponding column title as appear in an Excel sheet.

For example:

    1 -> A
    2 -> B
    3 -> C
    ...
    26 -> Z
    27 -> AA
    28 -> AB

Solution:
At the first glimpse, one may think this question as an one that convert decimal number to number with base 26. Unfortunately, it is not. the difference here is, there is no number represent 0 !!! The range here for each character is from [1, 26], not [0, 25].

	class Solution {
	public:
	string convertToTitle(int _n) {
	long n=_n;
	string res;
	int i=0;
	while(n!=0){
	int r = n%26;
	r=r==0? 26:r;
	char c = 'A'+r-1;
	res = string(1, c)+res;
	n = (n-r)/26;
	}

	return res;
	}
	};

view raw Q168ExcelSheetColumnTitle.cpp hosted with ❤ by GitHub

Round 2 solution:

	class Solution {
	public:
	string convertToTitle(int n) {
	string res;

	while(n!=0){
	n=n-1;
	res = string(1, (n%26 +'A')) + res;
	n = n/26;
	}

	return res;
	}
	};

view raw Q168Rnd2.cpp hosted with ❤ by GitHub

LeetCode Q167: Two Sum II - Input array is sorted

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

	class Solution {
	public:
	vector<int> twoSum(vector<int>& numbers, int target) {
	int p1=0;
	int p2=numbers.size()-1;
	vector<int> res;

	while(true){
	if(numbers[p1]+numbers[p2]>target){
	p2--; continue;
	}
	if(numbers[p1]+numbers[p2]<target){
	p1++; continue;
	}
	if(numbers[p1]+numbers[p2]==target){
	res.push_back(p1+1);
	res.push_back(p2+1);
	break;
	}
	}
	return res;
	}
	};

view raw Q167TwoSumII.cpp hosted with ❤ by GitHub

LeetCode Q166: Fraction to Recurring Decimal

Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.

If the fractional part is repeating, enclose the repeating part in parentheses.

For example,

Given numerator = 1, denominator = 2, return "0.5".
Given numerator = 2, denominator = 1, return "2".
Given numerator = 2, denominator = 3, return "0.(6)".

Solution:

Consider how the long division is done. Compute residual and result of division in each iteration. In the meantime keep track the residual using hash map in order to detect repeating pattern. Basically, the repetition happens when the same residual value appears again. Need to consider some boundary case such as "-2147483648", "-1"

	class Solution {
	public:
	string fractionToDecimal(int _nu, int _de) {
	long nu=long(_nu);
	long de=long(_de);
	string res;
	bool pts=false;
	bool repeat=false;
	unordered_map<int, int> myMap;

	if((nu<0&&de>0) \|\| (nu>0&&de<0)){
	res=res+string("-");
	}

	nu=abs(nu);
	de=abs(de);
	long residual=nu;

	if(nu==0)
	return string("0");

	while(residual!=0){
	long s = residual/de;
	residual=residual-s*de;
	res=res+to_string(s);
	if(!pts&&residual!=0){
	res=res+string(".");
	pts=true;
	}
	if(residual==0)
	break;
	if(myMap[residual]!=0&&s!=0){
	repeat=true;
	break;
	}
	myMap[residual]=res.length();
	residual*=10;
	}

	if(repeat){
	res.insert(myMap[residual], "(");
	res=res+string(")");
	}

	return res;
	}
	};

view raw Q166FractiontoRecurringDecimal.cpp hosted with ❤ by GitHub

Round 2 solution:

	class Solution {
	public:
	string fractionToDecimal(int _numerator, int _denominator) {
	string res;
	long numerator = _numerator;
	long denominator = _denominator;
	res=numerator*denominator<0? string("-"):res;
	numerator=abs(numerator);
	denominator=abs(denominator);

	if(numerator>denominator){
	long r = numerator/denominator;
	res = res+to_string(r);
	numerator = numerator - denominator*r;
	}else
	res = res+string("0");

	if(numerator!=0)
	res+=string(".");

	unordered_map<long, long> myHash;
	vector<long> tmpR;
	vector<long> tmpNu;
	while(numerator!=0){
	int r = numerator*10/denominator;
	if(myHash[numerator]!=0){
	for(int i=0; i<tmpR.size(); i++){
	if(tmpNu[i]==numerator)
	res = res + string("(")+to_string(tmpR[i]);
	else
	res = res + to_string(tmpR[i]);
	}
	res = res + string(")");
	return res;
	}else{
	myHash[numerator] = 1;
	tmpR.push_back(r);
	tmpNu.push_back(numerator);
	}
	numerator = numerator10 - denominatorr;
	}
	for(int i=0; i<tmpR.size(); i++)
	res = res+to_string(tmpR[i]);

	return res;
	}
	};

view raw Q166Rnd2.cpp hosted with ❤ by GitHub

Saturday, March 26, 2016

LeetCode Q165: Compare Version Number

Compare two version numbers version1 and version2.
If version1 > version2 return 1, if version1 < version2 return -1, otherwise return 0.

You may assume that the version strings are non-empty and contain only digits and the . character.
The . character does not represent a decimal point and is used to separate number sequences.
For instance, 2.5 is not "two and a half" or "half way to version three", it is the fifth second-level revision of the second first-level revision.

Here is an example of version numbers ordering:

0.1 < 1.1 < 1.2 < 13.37

	class Solution {
	public:
	int compareVersion(string v1, string v2) {
	if(v1.empty()&&v2.empty())
	return 0;
	string s1;
	int i1;
	int p1=0;
	while(v1[p1]!='.'&&p1<v1.length())
	s1=s1+string(1, v1[p1++]);
	p1=p1<v1.length()? p1+1:p1;
	i1=s1.empty()? 0:stoi(s1);

	string s2;
	int i2;
	int p2=0;
	while(v2[p2]!='.'&&p2<v2.length())
	s2=s2+string(1, v2[p2++]);
	p2=p2<v2.length()? p2+1:p2;
	i2=s2.empty()? 0:stoi(s2);

	if(i1==i2){
	return compareVersion(v1.substr(p1, v1.length()-p1), v2.substr(p2, v2.length()-p2));
	}

	if(i1>i2)
	return 1;
	if(i1<i2)
	return -1;
	}

	};

view raw Q165.cpp hosted with ❤ by GitHub

Round 2 solution:

	class Solution {
	public:
	int compareVersion(string version1, string version2) {
	int p1=0, p2=0;

	while(p1<version1.length()\|\|p2<version2.length()){
	string d1, d2;
	while(version1[p1]!='.'&&p1<version1.length())
	d1=d1+version1[p1++];
	while(version2[p2]!='.'&&p2<version2.length())
	d2=d2+version2[p2++];
	int n1=d1.empty()? 0:stoi(d1);
	int n2=d2.empty()? 0:stoi(d2);

	if(n1>n2) return 1;
	if(n2>n1) return -1;

	p1++; p2++;
	}

	return 0;
	}
	};

view raw Q165Rnd2.cpp hosted with ❤ by GitHub

Friday, March 25, 2016

LeetCode Q164: Maximum Gap (hard)

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

Try to solve it in linear time/space.

Return 0 if the array contains less than 2 elements.

You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

Solution:
Radix sort!!!

	class Solution {
	public:
	int maximumGap(vector<int>& nums) {
	if(nums.size()<2)
	return 0;
	int maxv=nums[0];
	for(int i=0; i<nums.size(); i++)
	maxv=max(nums[i], maxv);
	int k=1; // total k digits in maxv.
	while(true)
	if(maxv/int(pow(10, k++))==0)
	break;
	k=k-1;
	vector<vector<int> > myBucketPre(10);
	vector<vector<int> > myBucketCur(10);

	for(int i=0; i<k; i++){
	for(int j=0; j<10; j++)
	myBucketCur[j].clear();

	if(i==0){
	for(int j=0; j<nums.size(); j++){
	myBucketPre[nums[j]%int(pow(10, i+1))].push_back(nums[j]);
	}
	continue;
	}else{
	for(int j=0; j<10; j++){
	for(int q=0; q<myBucketPre[j].size(); q++){
	int num=myBucketPre[j][q];
	int tmpnum=num/int(pow(10, i));
	myBucketCur[tmpnum%10].push_back(num);
	}
	}
	}
	myBucketPre=myBucketCur;
	}

	int gap=0;
	int pre=-1;
	int cur=-1;
	for(int j=0; j<10; j++){
	for(int q=0; q<myBucketPre[j].size(); q++){
	cur=myBucketPre[j][q];
	if(pre==-1){
	pre=cur;
	continue;
	}
	gap=max(gap, cur-pre);
	pre=cur;
	}
	}
	return gap;
	}
	};

view raw Q164.cpp hosted with ❤ by GitHub

Round 2 solution:

	class Solution {
	public:
	int maximumGap(vector<int>& nums) {
	if(nums.size()<2)
	return 0;
	vector<vector<int> > preBucket(10);
	vector<vector<int> > curBucket(10);
	vector<int> curNums;

	for(int i=0; i<32; i++){
	curNums.clear();
	if(i==0)
	curNums=nums;
	else{
	for(int j=0; j<10; j++){
	for(int k=0; k<preBucket[j].size(); k++)
	curNums.push_back(preBucket[j][k]);
	}
	}

	for(int j=0; j<curNums.size(); j++){
	int d = (curNums[j]/int(pow(10, i)))%10;
	curBucket[d].push_back(curNums[j]);
	}
	preBucket=curBucket;
	curBucket.clear();
	curBucket.resize(10);
	}

	int res=0;
	for(int j=1; j<curNums.size(); j++)
	res=max(res, curNums[j]-curNums[j-1]);

	return res;
	}
	};

view raw Q164Rnd2.cpp hosted with ❤ by GitHub

Rnd3 sol:

	class Solution {
	public:
	int maximumGap(vector<int>& nums) {
	if(nums.size()<2)
	return 0;
	vector<vector<int> > curBucket(10);
	vector<int> curNums=nums;

	for(int i=0; i<32; i++){
	for(int j=0; j<curNums.size(); j++){
	int d = (curNums[j]/int(pow(10, i)))%10;
	curBucket[d].push_back(curNums[j]);
	}
	curNums.clear();
	for(int j=0; j<10; j++){
	for(int k=0; k<curBucket[j].size(); k++)
	curNums.push_back(curBucket[j][k]);
	}

	curBucket.clear();
	curBucket.resize(10);
	}

	int res=0;
	for(int j=1; j<curNums.size(); j++)
	res=max(res, curNums[j]-curNums[j-1]);

	return res;
	}
	};

view raw Q164Rnd3.cpp hosted with ❤ by GitHub

LeetCode Q163: Missing Ranges

Given a sorted integer array where the range of elements are [lower, upper] inclusive, return its missing ranges.

For example, given [0, 1, 3, 50, 75], lower = 0 and upper = 99, return ["2", "4->49", "51->74", "76->99"].

	class Solution {
	public:
	vector<string> findMissingRanges(vector<int>& nums, int lower, int upper) {
	vector<string> res;
	if(nums.size()==0\|\|nums[0]!=lower)
	nums.insert(nums.begin(), lower-1);
	if(nums[nums.size()-1]!=upper)
	nums.insert(nums.end(), upper+1);

	for(int p=0;p<nums.size()-1; p++){
	if(nums[p+1]-nums[p]>2){
	string s(to_string(nums[p]+1)+string("->")+to_string(nums[p+1]-1));
	res.push_back(s);
	}
	if(nums[p+1]-nums[p]==2){
	string s(to_string(nums[p]+1));
	res.push_back(s);
	}
	}
	return res;
	}
	};

view raw Q163.cpp hosted with ❤ by GitHub

Round 2 solution:

	class Solution {
	public:
	vector<string> findMissingRanges(vector<int>& nums, int lower, int upper) {
	vector<string> res;

	if(nums.size()==0\|\|nums[0]!=lower)
	nums.insert(nums.begin(), lower-1);
	if(nums[nums.size()-1]!=upper)
	nums.insert(nums.end(), upper+1);

	for(int i=1; i<nums.size(); i++){
	int lb = nums[i-1]+1;
	int rb = nums[i]-1;
	if(lb==rb)
	res.push_back(to_string(lb));
	if(lb<rb)
	res.push_back(to_string(lb)+string("->")+to_string(rb));
	}

	return res;
	}
	};

view raw Q163Rnd2.cpp hosted with ❤ by GitHub

LeetCode Q162: Find Peak Element

A peak element is an element that is greater than its neighbors.

Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that num[-1] = num[n] = -∞.

For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.

click to show spoilers.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

Soluton:

Binary search

	class Solution {
	public:
	int findPeakElement(vector<int>& nums) {
	if(nums.size()!=0&&(nums[0]>nums[1]))
	return 0;
	if(nums.size()!=0&&(nums[nums.size()-1]>nums[nums.size()-2]))
	return nums.size()-1;
	if(nums.size()==1)
	return 0;

	int l=1;
	int r=nums.size()-2;

	while(l<r){
	int mid=(l+r)/2;
	if(nums[mid]>nums[mid-1]&&nums[mid]>nums[mid+1])
	return mid;

	if(mid==l\|\|mid==r){
	mid = nums[l]>nums[r]? l:r;
	return mid;
	}

	if(nums[mid]>nums[mid-1])
	l=mid;
	else
	r=mid;
	}
	return l;
	}
	};

view raw Q162.cpp hosted with ❤ by GitHub

Round 2 Solution:

	class Solution {
	public:
	int findPeakElement(vector<int>& nums) {
	int l=0, r=nums.size()-1;

	while(l<r-1){
	int mid = (l+r)/2;
	int ml = mid==0? INT_MIN:nums[mid-1];

	if(nums[mid]>ml)
	l=mid;
	else
	r=mid;
	}

	return nums[l]<nums[r]? r:l;
	}
	};

view raw Q162Rnd2.cpp hosted with ❤ by GitHub

LeetCode Q161: One Edit Distance

Given two strings S and T, determine if they are both one edit distance apart.

	class Solution {
	public:
	bool isOneEditDistance(string s, string t) {
	if(t.length()<s.length())
	swap(s, t);

	if(t.length()-s.length()>1)
	return false;

	if(s.length()==0&&t.length()==0)
	return false;

	if(s.length()==t.length()){
	int diffMet=0;
	for(int i=0; i<s.length(); i++){
	if(s[i]!=t[i]){
	if(diffMet==0)
	diffMet=1;
	else
	return false;
	}
	}
	return diffMet==1;
	}

	if(t.length()<s.length())
	swap(s, t);

	int p0=0, p1=0;
	int diffMet=0;
	for(p0=0; p0<s.length(); ){
	if(s[p0]==t[p1]){
	p0++; p1++;
	continue;
	}else{
	if(diffMet==0){
	diffMet=1;
	p1++;
	}else
	return false;
	}
	}
	return true;
	}
	};

view raw Q161OneEditDistance.cpp hosted with ❤ by GitHub

Round 2 solution:

	class Solution {
	public:
	bool isOneEditDistance(string s, string t) {
	if(t.length()<s.length())
	return isOneEditDistance(t, s);

	if((s.length()==0&&t.length()==0)\|\|t.length()-s.length()>=2)
	return false;

	if(s.length()==t.length()){
	int diff=0;
	for(int i=0; i<s.length(); i++){
	if(s[i]!=t[i]){
	if(++diff>1)
	return false;
	}
	}
	if(diff!=1)
	return false;
	}else{
	int i=0, j=0;
	int diff=0;
	while(i<s.length()&&j<t.length()){
	if(s[i]==t[j]){
	i++; j++;
	}else{
	j++;
	if(diff++>1)
	return false;
	}
	}
	if(diff!=1&&j!=t.length()-1)
	return false;
	}

	return true;
	}
	};

view raw Q161Rnd2.cpp hosted with ❤ by GitHub

LeetCode Q160: Intersection of Two Linked Lists

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

begin to intersect at node c1.

Notes:

If the two linked lists have no intersection at all, return null.
The linked lists must retain their original structure after the function returns.
You may assume there are no cycles anywhere in the entire linked structure.
Your code should preferably run in O(n) time and use only O(1) memory.

Solution;

A hard question at the first glance, however, it is easy if you can figure out how many node each linkedlist has.

	/**
	* Definition for singly-linked list.
	* struct ListNode {
	* int val;
	* ListNode *next;
	* ListNode(int x) : val(x), next(NULL) {}
	* };
	*/
	class Solution {
	public:
	ListNode getIntersectionNode(ListNode headA, ListNode *headB) {
	int lenA=0;
	int lenB=0;
	ListNode* pA=headA;
	ListNode* pB=headB;

	while(pA!=NULL\|\|pB!=NULL){
	if(pA!=NULL){
	lenA++;
	pA=pA->next;
	}
	if(pB!=NULL){
	lenB++;
	pB=pB->next;
	}
	}

	pA=headA;
	pB=headB;

	if(lenB>lenA)
	for(int i=0; i<lenB-lenA; i++)
	pB=pB->next;
	if(lenA>lenB)
	for(int i=0; i<lenA-lenB; i++)
	pA=pA->next;

	while(pA!=NULL&&pB!=NULL){
	if(pA==pB)
	return pA;
	else{
	pA=pA->next;
	pB=pB->next;
	}
	}
	return NULL;
	}
	};

view raw Q160IntersectionofTwoLinkedList.cpp hosted with ❤ by GitHub

Thursday, March 24, 2016

LeetCode Q159: Longest Substring with At Most Two Distinct Characters (hard)

Given a string, find the length of the longest substring T that contains at most 2 distinct characters.

For example, Given s = “eceba”,

T is "ece" which its length is 3.

Solution:

To solve substring problem, could use following template:

	int findSubstring(string s){
	vector<int> map(128,0);
	int counter; // check whether the substring is valid
	int begin=0, end=0; //two pointers, one point to tail and one head
	int d; //the length of substring

	for() { /* initialize the hash map here */ }

	while(end<s.size()){

	if(map[s[end++]]-- ?){ /* modify counter here */ }

	while(/* counter condition */){

	/* update d here if finding minimum*/

	//increase begin to make it invalid/valid again

	if(map[s[begin++]]++ ?){ /modify counter here/ }
	}

	/* update d here if finding maximum*/
	}
	return d;
	}

view raw Q76-3.cpp hosted with ❤ by GitHub

My solution is:

	class Solution {
	public:
	int lengthOfLongestSubstringTwoDistinct(string s) {
	vector<int> map(128, 0);
	int counter=0;
	int start=0, end=0;
	int d=0;

	while(end<s.size()){
	if(map[s[end]]!=0){
	map[s[end]]+=1;
	end++;
	continue;
	}
	if(map[s[end]]==0){
	if(counter<2){
	map[s[end]]+=1;
	counter++;
	end++;
	continue;
	}
	if(counter==2){
	d=end-start>d? end-start:d;
	while(counter==2){
	map[s[start]]-=1;
	if(map[s[start]]==0)
	counter--;
	start++;
	}
	}
	}
	}
	return max(d, end-start);
	}
	};

view raw Q159.cpp hosted with ❤ by GitHub

A better solution is:

	int lengthOfLongestSubstringTwoDistinct(string s) {
	vector<int> map(128, 0);
	int counter=0, begin=0, end=0, d=0;
	while(end<s.size()){
	if(map[s[end++]]++==0) counter++;
	while(counter>2) if(map[s[begin++]]--==1) counter--;
	d=max(d, end-begin);
	}
	return d;
	}

view raw Q76-4.cpp hosted with ❤ by GitHub

Round 2 solution:

	class Solution {
	public:
	int lengthOfLongestSubstringTwoDistinct(string s) {
	int res=0;
	if(s.length()==0)
	return res;
	int p0=0, p1=0;
	vector<int> myHash(128, 0);
	int count=0;

	while(p1<s.length()){
	char c = s[p1];
	if(myHash[c]==0)
	count++;
	myHash[c]++;
	if(count>2){
	while(p0<s.length()){
	if(--myHash[s[p0++]]==0)
	break;
	}
	count--;
	}else
	res = max(res, p1-p0+1);

	p1++;
	}
	return res;
	}
	};

view raw Q159Rnd2.cpp hosted with ❤ by GitHub

Rnd3 sol:

	int lengthOfLongestSubstringTwoDistinct(string s) {
	int res=0;
	if(s.empty())
	return res;
	unordered_map<char, int> myMap;
	int p0=0, p1=0;
	int count = 0;
	while(p1<s.length()){
	char c = s[p1];
	myMap[c]++;
	count = myMap[c]==1? count+1:count;

	if(count>2){
	while(p0<s.length()-1&&--myMap[s[p0++]]!=0){}
	count--;
	}
	res = max(res, p1-p0+1);
	p1++;
	}
	return res;
	}

view raw Q159Rnd3.cpp hosted with ❤ by GitHub

LeetCode Q157: Read N Characters Given Read4

The API: int read4(char *buf) reads 4 characters at a time from a file.

The return value is the actual number of characters read. For example, it returns 3 if there is only 3 characters left in the file.

By using the read4 API, implement the function int read(char *buf, int n) that reads n characters from the file.

Note:
The read function will only be called once for each test case.

	// Forward declaration of the read4 API.
	int read4(char *buf);

	class Solution {
	public:
	/**
	* @param buf Destination buffer
	* @param n Maximum number of characters to read
	* @return The number of characters read
	*/
	int read(char *buf, int n) {
	int p=0;
	int count=0;
	while(true){
	char _buf[4];
	int _n=read4(_buf);

	for(int i=0; i<_n; i++){
	if(count==n)
	return n;
	buf[p++]=_buf[i];
	count++;
	}

	if(_n<4)
	return count;
	}
	}
	};

view raw Q157ReadCharGivenRead4.cpp hosted with ❤ by GitHub

Round 2 solution:

	// Forward declaration of the read4 API.
	int read4(char *buf);

	class Solution {
	public:
	/**
	* @param buf Destination buffer
	* @param n Maximum number of characters to read
	* @return The number of characters read
	*/
	int read(char *buf, int n) {
	int res=0;
	int local=4;

	while(res<n&&local==4){
	local=read4(buf);
	res+=local;
	buf+=local;
	}
	return min(n, res);
	}
	};

view raw Q157Rnd2.cpp hosted with ❤ by GitHub

LeetCode Q156: Binary Tree Upside Down

Given a binary tree where all the right nodes are either leaf nodes with a sibling (a left node that shares the same parent node) or empty, flip it upside down and turn it into a tree where the original right nodes turned into left leaf nodes. Return the new root.

For example:
Given a binary tree {1,2,3,4,5},

return the root of the binary tree [4,5,2,#,#,3,1].

Solution:
The most bottom left node will serve as a root in new tree. Using post-traversal. Remember that the right not will not have any children, so the recursion only apply to left node.

	/**
	* Definition for a binary tree node.
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class Solution {
	public:
	void helper(TreeNode* l, TreeNode* r, TreeNode*& newroot){
	if(l->left==NULL&&l->right==NULL){
	newroot=l;
	l->left=r;
	return;
	}

	helper(l->left, l->right, newroot);
	l->left->right=l;
	l->left=r;
	}

	TreeNode* upsideDownBinaryTree(TreeNode* root) {
	TreeNode* newroot=NULL;
	if(root==NULL)
	return newroot;

	if(root->left==NULL&&root->right==NULL){
	newroot=root;
	return newroot;
	}

	helper(root->left, root->right, newroot);
	root->left->right=root;
	root->left=NULL;
	root->right=NULL;
	return newroot;

	}
	};

view raw Q156BinaryTreeUpsideDown.cpp hosted with ❤ by GitHub

Round 2 solution:

	/**
	* Definition for a binary tree node.
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class Solution {
	public:
	TreeNode* helper(TreeNode* root){
	if(root->left==NULL&&root->right==NULL)
	return root;

	TreeNode* l = helper(root->left);
	l->left = root->right;
	l->right = root;
	root->left=NULL;
	root->right=NULL;
	return root;
	}

	TreeNode* upsideDownBinaryTree(TreeNode* root) {
	if(root==NULL)
	return root;

	TreeNode* newRoot=root;
	while(newRoot->left!=NULL)
	newRoot=newRoot->left;

	helper(root);
	return newRoot;
	}
	};

view raw Q156Rnd2.cpp hosted with ❤ by GitHub

LeetCode Q155: Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
getMin() -- Retrieve the minimum element in the stack.

Solution:

The essence of this question is to solve the problem of getting minimum element in remaining stack. To solve it we need to keep track the min in current stack. So, each entry in the stack have to domains, first one is used to save value of current element. the second domain contains the min value under the current element in the stack.

	class MinStack {
	public:
	void push(int x) {
	if(myStack.size()==0){
	pair<int, int> e(x, x);
	myStack.push(e);
	}else{
	if(x<getMin()){
	pair<int, int> e(x, x);
	myStack.push(e);
	}else{
	pair<int, int> e(x, getMin());
	myStack.push(e);
	}
	}
	}

	void pop() {
	myStack.pop();
	}

	int top() {
	pair<int, int> e = myStack.top();
	return e.first;
	}

	int getMin() {
	pair<int, int> top=myStack.top();
	return top.second;
	}
	stack<pair<int, int> > myStack;
	};

view raw Q155MinStack.cpp hosted with ❤ by GitHub

Round 2 solution: Anther way to track minimum element in current array is to use another stack. Similar to sliding window problem, the element inserted to the stack has to be strictly smaller or equal to current top element of the stack.

	class MinStack {
	public:
	/** initialize your data structure here. */
	MinStack() {

	}

	void push(int x) {
	myStack.push(x);
	update(x);
	}

	void pop() {
	if(myStack.top()==helpStack.top())
	helpStack.pop();
	myStack.pop();
	}

	int top() {
	return myStack.top();
	}

	int getMin() {
	return helpStack.top();
	}

	void update(int x){
	if(helpStack.empty()\|\|x<=helpStack.top())
	helpStack.push(x);
	}

	stack<int> myStack;
	stack<int> helpStack;
	};

	/**
	* Your MinStack object will be instantiated and called as such:
	* MinStack obj = new MinStack();
	* obj.push(x);
	* obj.pop();
	* int param_3 = obj.top();
	* int param_4 = obj.getMin();
	*/

view raw Q155Rnd2.cpp hosted with ❤ by GitHub

LeetCode Q154: Find Minimum in Rotated Sorted Array II (hard)

Follow up for "Find Minimum in Rotated Sorted Array":
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

The array may contain duplicates.

Solution:

The solution is basically the same to the question in which there is no duplicate element. Basically, for questions like this one which allows duplicate elements when doing binary search, we need to shrink the range by moving either left or right pointer when meeting duplicate element.

	class Solution {
	public:
	int findMin(vector<int>& nums) {
	int l=0;
	int r=nums.size()-1;

	while(l<r){
	int mid=(l+r)/2;
	if(l==mid\|\|r==mid)
	return min(nums[l], nums[r]);
	if(nums[mid]>nums[r]){
	l=mid;
	continue;
	}
	if(nums[mid]<nums[l]){
	r=mid;
	continue;
	}
	if(nums[l]<nums[r])
	break;
	if(nums[l]==nums[r])
	r--;
	}
	return nums[l];
	}
	};

view raw Q154MinInRotatedSortedArray.cpp hosted with ❤ by GitHub

Round 2 solution: For all rotated array questions with duplicates, we can compare middle elements with left/right boundary, if identical, we can shrink the boundary.

	class Solution {
	public:
	int findMin(vector<int>& nums) {
	int res;
	if(nums.empty())
	return 0;

	int l = 0;
	int r = nums.size()-1;

	while(l<r-1){
	int mid = (l+r)/2;

	if(nums[mid]==nums[r]){
	r--;
	continue;
	}

	if(nums[mid]==nums[l]){
	l++;
	continue;
	}

	if(nums[l]<nums[mid])
	if(nums[mid]<nums[r])
	r=mid;
	else
	l=mid;
	else
	r=mid;
	}

	res = min(nums[l], nums[r]);
	return res;
	}
	};

view raw Q154Rnd2.cpp hosted with ❤ by GitHub

Wednesday, March 23, 2016

LeetCode Q153: Find Minimum in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

You may assume no duplicate exists in the array.

Solution:

Binary search, each step move to branch where numbers are not in order. Need to consider the case where the given array is already sorted.

	class Solution {
	public:
	int findMin(vector<int>& nums) {
	int l=0;
	int r=nums.size()-1;

	while(l<r){
	int mid=(l+r)/2;
	if(l==mid\|\|r==mid)
	return min(nums[l], nums[r]);
	if(nums[mid]>nums[r]){
	l=mid;
	continue;
	}
	if(nums[mid]<nums[l]){
	r=mid;
	continue;
	}
	if(nums[l]<nums[r])
	break;
	}
	return nums[l];
	}
	};

view raw Q153MinInRotatedArray.cpp hosted with ❤ by GitHub

Round 2 solution: Questions like this, remember to illustrate all possible cases on paper first. It is easier to separate all cases from those examples.
For this question, find the middle element, and drop half of elements every iteration.

	class Solution {
	public:
	int findMin(vector<int>& nums) {
	int res;
	if(nums.empty())
	return 0;

	int l = 0;
	int r = nums.size()-1;

	while(l<r-1){
	int mid = (l+r)/2;
	if(nums[l]<nums[mid])
	if(nums[mid]<nums[r])
	r=mid;
	else
	l=mid;
	else
	r=mid;
	}

	res = min(nums[l], nums[r]);
	return res;
	}
	};

view raw Q153Rnd2.cpp hosted with ❤ by GitHub

Round 2 solution: For questions like this one, first list all examples on paper. It is easier to separate all cases from those examples.
For this question, we find middle element every time and we decide which type of order the current array is. Then we can drop half of elements depends on the pattern we get from examples we listed on the paper.

	class Solution {
	public:
	int findMin(vector<int>& nums) {
	int res;
	if(nums.empty())
	return 0;

	int l = 0;
	int r = nums.size()-1;

	while(l<r-1){
	int mid = (l+r)/2;
	if(nums[l]<nums[mid])
	if(nums[mid]<nums[r])
	r=mid;
	else
	l=mid;
	else
	r=mid;
	}

	res = min(nums[l], nums[r]);
	return res;
	}
	};

view raw Q153Rnd2.cpp hosted with ❤ by GitHub

LeetCode Q152: Maximum Product Subarray (hard)

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.

Solution:

Use DP. Given an array with N integers, we can create a Nx2 table. For each 1x2 entry in the table, we keep track the largest product (most of time for positive product) and smallest product (most of time for negative product so far) met so far. So, the idea is to save all valid product met so far including the negative ones, because we don't know whether there will be more negative integer in the remaining part of the array.

At the end of this design, we notice that, actually, there is no need to create a Nx2 table, all we need basically just two variables storing largest and smallest product obtained so far.

	class Solution {
	public:
	int maxProduct(vector<int>& nums) {
	int r=nums[0];

	for(int i=1, imax=r, imin=r; i<nums.size(); i++){
	if(nums[i]<0)
	swap(imax, imin);

	imax=max(nums[i], imax*nums[i]);
	imin=min(nums[i], imin*nums[i]);

	r=max(imax, r);
	}
	return r;
	}

	};

view raw Q152MaximumProductSubarray.cpp hosted with ❤ by GitHub

Round 2 solution:

	class Solution {
	public:
	int maxProduct(vector<int>& nums) {
	if(nums.empty())
	return 0;

	int minv = nums[0];
	int maxv= nums[0];
	int res = nums[0];

	for(int i=1; i<nums.size(); i++){
	int tmpmax = max(nums[i], max(nums[i]maxv, nums[i]minv));
	int tmpmin = min(nums[i], min(nums[i]maxv, nums[i]minv));
	maxv = tmpmax;
	minv = tmpmin;

	res = max(res, maxv);
	}

	return res;
	}
	};

view raw Q152Rnd2.cpp hosted with ❤ by GitHub

LeetCode Q151: Reverse Words in a String

Given an input string, reverse the string word by word.

For example,
Given s = "the sky is blue",
return "blue is sky the".

Update (2015-02-12):
For C programmers: Try to solve it in-place in O(1) space.

	class Solution {
	public:
	void reverseWords(string &s) {
	if(s.length()==0)
	return;

	int p0=0; while(s[p0]==' '){p0++;}
	int p1=s.length()-1; while(s[p1]==' '){p1--;}
	if(p0<=p1)
	s=s.substr(p0, p1-p0+1);
	else{
	s=s.substr(0, 0);
	return;
	}

	p0=0;
	p1=s.length()-1;
	while(p0<p1){
	char tmp=s[p0];
	s[p0]=s[p1];
	s[p1]=tmp;
	p0++;
	p1--;
	}

	p0=0; p1=0;
	while(p1<=s.length()-1){
	if(s[p1]!=' '){
	s[p0]=s[p1];
	p0++;
	p1++;
	continue;
	}

	s[p0]=s[p1];
	p0++;
	while(s[p1]==' '&&p1<=s.length()-1){p1++;}
	}
	s=s.substr(0, p0);

	p0=0; p1=0;
	while(p0<=s.length()-1){
	p1=p0;
	while(s[p1]!=' '&&p1<=s.length()-1){p1++;}
	int nextp=p1;
	p1--;

	while(p0<p1){
	char tmp=s[p0];
	s[p0]=s[p1];
	s[p1]=tmp;
	p0++;
	p1--;
	}

	p0=nextp+1;
	}
	}
	};

view raw Q151ReverseWordsinString.cpp hosted with ❤ by GitHub

Round 2 solution:

	class Solution {
	public:
	void reverseWords(string &s) {
	if(s.empty())
	return;

	int p0=0, p1=p0;
	string tmps;
	while(p0<s.length()){
	if(!isspace(s[p0])&&(p0==0 \|\| isspace(s[p0-1]))){
	p1 = p0;
	while(s[p1]!=' '&&p1!=s.length()) p1++;
	int tmp = p1--;
	string ss = s.substr(p0, p1-p0+1);
	int p00=0, p11=ss.length()-1;
	while(p00<p11) swap(ss[p00++], ss[p11--]);
	tmps = tmps.empty()? ss: tmps+string(" ")+ss;
	p0 = tmp;
	}
	p0++;
	}

	s=tmps;
	reverse(s.begin(), s.end());
	}
	};

view raw Q151Rnd2.cpp hosted with ❤ by GitHub

Tuesday, March 22, 2016

LeetCode Q150: Evaluate Reverse Polish Notation

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Some examples:

  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

Solution:
Not hard, but need to careful about some corner cases, such as when token has only 1 elements and the order of operators when popped from stack.

	class Solution {
	public:
	int evalRPN(vector<string>& tokens) {
	if(tokens.size()==1)
	return stoi(tokens[0]);
	int res=0;
	stack<int> myStack;
	int p=0;
	while(!myStack.empty()\|\|p!=tokens.size()){
	string s=tokens[p];
	if(s.compare("+")==0\|\|s.compare("-")==0\|\|s.compare("*")==0\|\|s.compare("/")==0){
	int op0=myStack.top(); myStack.pop();
	int op1=myStack.top(); myStack.pop();
	int r=0;
	switch(s[0]){
	case '+': r=(op1)+(op0); break;
	case '-': r=(op1)-(op0); break;
	case '': r=(op1)(op0); break;
	case '/': r=(op1)/(op0); break;
	}
	if(p!=tokens.size()-1\|\|!myStack.empty())
	myStack.push(r);
	res=r;
	}else{
	int i=stoi(s);
	myStack.push(i);
	}
	p++;
	}
	return res;
	}
	};

view raw Q150.cpp hosted with ❤ by GitHub

LeetCode Q149: Max Points on a Line (hard)

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

Solution:

Using hash, for each point, check the number of all other points that are co-linear with current point. The problem will encounter is how to represent a line in hash map. Directly using float/double as slope will have precision problem. So, here I represent a slope using x and y, where x=p1.x-p0.x, y=p1.y-p0.y. Then to ensure uniqueness of each slope, x and y are divided by their GCD.

	/**
	* Definition for a point.
	* struct Point {
	* int x;
	* int y;
	* Point() : x(0), y(0) {}
	* Point(int a, int b) : x(a), y(b) {}
	* };
	*/
	class Solution {
	public:
	int GCD(int a, int b){
	if(b==0) return a;
	return GCD(b, a%b);
	}
	int maxPoints(vector<Point>& points) {
	if(points.size()<2)
	return points.size();

	int globalMax=0;
	for(int i=0; i<points.size(); i++){
	int overlap=1;
	int localMax=0;
	unordered_map<string, int> myMap;
	for(int j=i+1; j<points.size(); j++){
	if(points[i].x==points[j].x&&points[i].y==points[j].y){
	overlap++;
	continue;
	}
	int a=points[j].y-points[i].y;
	int b=points[j].x-points[i].x;
	int gcd=GCD(a, b);
	a=gcd!=0? a/gcd:a;
	b=gcd!=0? b/gcd:b;
	myMap[string(to_string(a)+"_"+to_string(b))]=myMap[string(to_string(a)+"_"+to_string(b))]+1;
	}

	for(auto it=myMap.begin(); it!=myMap.end(); it++)
	localMax=max(localMax, it->second);
	localMax+=overlap;
	globalMax=max(globalMax, localMax);
	}
	return globalMax;
	}
	};

view raw Q149MaxPointsOnaLine.cpp hosted with ❤ by GitHub

LeetCode Q148: Sort List

Sort a linked list in O(n log n) time using constant space complexity.

Solution:
Using merge sort.

	/**
	* Definition for singly-linked list.
	* struct ListNode {
	* int val;
	* ListNode *next;
	* ListNode(int x) : val(x), next(NULL) {}
	* };
	*/
	class Solution {
	public:
	ListNode* merge(ListNode* head1, ListNode* head2){
	ListNode* p1=head1;
	ListNode* p2=head2;
	ListNode* newHead=NULL;
	ListNode* p=NULL;
	while(p1!=NULL&&p2!=NULL){
	ListNode* tmp=NULL;
	if(p1->val<p2->val){
	tmp=p1;
	p1=p1->next;
	}else{
	tmp=p2;
	p2=p2->next;
	}
	if(newHead==NULL){
	newHead=tmp;
	p=tmp;
	}else{
	p->next=tmp;
	p=tmp;
	}
	}
	if(p1==NULL)
	p->next=p2;
	else if(p2==NULL)
	p->next=p1;

	return newHead;
	}

	ListNode* sortList(ListNode* head){
	if(head==NULL\|\|head->next==NULL)
	return head;

	ListNode* head1=head;
	ListNode* head2=head->next;
	while(head2 && head2->next){
	head1=head1->next;
	head2=head2->next->next;
	}

	head2=head1->next;
	head1->next=NULL;
	head1=head;

	ListNode* newHead1=sortList(head1);
	ListNode* newHead2=sortList(head2);
	head=merge(newHead1, newHead2);
	return head;
	}
	};

view raw Q148SortList.cpp hosted with ❤ by GitHub

Round 2 solution:

	/**
	* Definition for singly-linked list.
	* struct ListNode {
	* int val;
	* ListNode *next;
	* ListNode(int x) : val(x), next(NULL) {}
	* };
	*/
	class Solution {
	public:
	ListNode* merge(ListNode* head1, ListNode* head2){
	ListNode* head = new ListNode(1);
	ListNode* p;

	if(head1==NULL\|\|head2==NULL)
	return head1==NULL? head2:head1;

	while(head1!=NULL\|\|head2!=NULL){
	if(head1==NULL\|\|head2==NULL){
	p->next = head1==NULL? head2:head1;
	break;
	}

	ListNode* curNode;
	if(head1->val<head2->val){
	curNode=head1;
	head1=head1->next;
	}else{
	curNode=head2;
	head2=head2->next;
	}

	if(head->next==NULL){
	head->next=curNode;
	p=curNode;
	p->next=NULL;
	}else{
	p->next=curNode;
	p=curNode;
	p->next=NULL;
	}
	}
	ListNode* tmp = head->next;
	delete head;
	return head->next;
	}

	ListNode* sortList(ListNode* head) {
	if(head->next==NULL)
	return head;

	ListNode* p0 = head;
	ListNode* p1 = head;

	while(p1->next!=NULL&&p1->next->next!=NULL){
	p0 = p0->next;
	p1 = p1->next->next;
	}

	p1 = p0->next;
	p0->next=NULL;
	p0 = head;

	p0 = sortList(p0);
	p1 = sortList(p1);
	head = merge(p0, p1);
	return head;
	}
	};

view raw Q148Rnd2.cpp hosted with ❤ by GitHub

Saturday, March 19, 2016

For God's sake, don't try sorting a linked list during the interview

Somebody gots some comments about his experience of interviewingin Google.

http://steve-yegge.blogspot.nl/2008/03/get-that-job-at-google.html
Might be helpful

LeetCode Q147: Insertioin Sort List

Sort a linked list using insertion sort.

	/**
	* Definition for singly-linked list.
	* struct ListNode {
	* int val;
	* ListNode *next;
	* ListNode(int x) : val(x), next(NULL) {}
	* };
	*/
	class Solution {
	public:
	ListNode* insertionSortList(ListNode* head) {
	if(head==NULL)
	return head;

	ListNode* myHead=new ListNode(-1);

	while(head!=NULL){
	ListNode* target=head;
	head=head->next;
	target->next=NULL;

	ListNode* p=myHead;

	while(true){
	if(p->next==NULL){
	p->next=target;
	break;
	}

	if(target->val<=p->next->val){
	target->next=p->next;
	p->next=target;
	break;
	}

	if(target->val>p->next->val){
	p=p->next;
	continue;
	}
	}
	}

	return myHead->next;

	}
	};

view raw Q147InsertionSortLinkedList.cpp hosted with ❤ by GitHub

Round 2 solution: I just aware that my 1st round solution is actually bubble sort. The insertion sort is given in below:

	/**
	* Definition for singly-linked list.
	* struct ListNode {
	* int val;
	* ListNode *next;
	* ListNode(int x) : val(x), next(NULL) {}
	* };
	*/
	class Solution {
	public:
	void sort(ListNode& head, ListNode node){
	node->next=NULL;
	ListNode* p=head;

	if(node->val<=head->val){
	node->next=p;
	head=node;
	return;
	}

	while(p->next!=NULL){
	if(node->val>p->val&&node->val<=p->next->val){
	ListNode* tmp = p->next;
	p->next=node;
	node->next=tmp;
	break;
	}
	p=p->next;
	}
	if(p->next==NULL)
	p->next=node;
	}

	ListNode* insertionSortList(ListNode* head) {
	if(head==NULL)
	return head;

	ListNode* p = head;
	ListNode* newHead=NULL;
	while(p!=NULL){
	if(newHead==NULL){
	newHead=p;
	p=p->next;
	newHead->next=NULL;
	}else{
	ListNode* tmp = p->next;
	sort(newHead, p);
	p=tmp;
	}
	}

	return newHead;
	}
	};

view raw Q147Rnd2.cpp hosted with ❤ by GitHub

LeetCode Q:146 LRU Cache (hard)

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

	class LRUCache {
	public:
	LRUCache(int capacity) : _capacity(capacity) {}

	int get(int key) {
	auto it = cache.find(key);
	if (it == cache.end()) return -1;
	touch(it);
	return it->second.first;
	}

	void set(int key, int value) {
	auto it = cache.find(key);
	if (it != cache.end()) touch(it);
	else {
	if (cache.size() == _capacity) {
	cache.erase(used.back());
	used.pop_back();
	}
	used.push_front(key);
	}
	cache[key] = { value, used.begin() };
	}

	private:
	typedef list<int> LI;
	typedef pair<int, LI::iterator> PII;
	typedef unordered_map<int, PII> HIPII;

	void touch(HIPII::iterator it) {
	int key = it->first;
	used.erase(it->second.second);
	used.push_front(key);
	it->second.second = used.begin();
	}

	HIPII cache; // < key, <value, list<key>::iterator> >
	LI used; // list<key>
	int _capacity;
	};

view raw Q146LRU.cpp hosted with ❤ by GitHub

Round 2 solution:
The key here is to keep a list iterator in hash map. We save a pair in list because we need know what key it is when we remove a value from list. So we can remove this key from hash map.

	class LRUCache {
	public:
	list<pair<int, int> > myList;
	unordered_map<int, list<pair<int, int> >::iterator> myMap;
	int capacity;

	LRUCache(int _capacity) : capacity(_capacity) {}

	void touch(list<pair<int, int> >::iterator& it){
	pair<int, int> p = *(it);
	myList.erase(it);
	myList.push_front(p);
	it = myList.begin();
	}

	int get(int key) {
	auto it = myMap.find(key);
	if(it==myMap.end())
	return -1;

	touch(it->second);
	return (*(it->second)).first;
	}

	void set(int key, int value) {
	auto it = myMap.find(key);
	if(it!=myMap.end()){
	(*(it->second)).first=value;
	touch(it->second);
	}else{
	if(myList.size()==capacity){
	pair<int, int> back = myList.back();
	myList.pop_back();
	myMap.erase(back.second);
	}
	pair<int, int> newPair(value, key);
	myList.push_front(newPair);
	list<pair<int, int> >:: iterator newit = myList.begin();
	myMap[key] = newit;
	}
	}
	};

view raw Q146Rnd2.cpp hosted with ❤ by GitHub

LeetCode Q145: Binary Tree Postorder Traversal

Given a binary tree, return the postorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

return [3,2,1].

Note: Recursive solution is trivial, could you do it iteratively?

	/**
	* Definition for a binary tree node.
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class Solution {
	public:
	vector<int> postorderTraversal(TreeNode* root) {
	vector<int> res;
	unordered_map<TreeNode*, int> myM;
	stack<TreeNode*> myS;

	if(root==NULL)
	return res;

	myS.push(root);
	myM[root]=2;

	while(!myS.empty()){
	TreeNode* cur=myS.top();

	if(myM[cur]==2){
	myM[cur]=myM[cur]-1;
	if(cur->left!=NULL){
	myS.push(cur->left);
	myM[cur->left]=2;
	}
	continue;
	}
	if(myM[cur]==1){
	myM[cur]=myM[cur]-1;
	if(cur->right!=NULL){
	myS.push(cur->right);
	myM[cur->right]=2;
	}
	continue;
	}
	if(myM[cur]==0){
	res.push_back(cur->val);
	myS.pop();
	continue;
	}
	}
	}
	};

view raw Q145.cpp hosted with ❤ by GitHub

Round 2 solution:

1.1 Create an empty stack
2.1 Do following while root is not NULL
    a) Push root's right child and then root to stack.
    b) Set root as root's left child.
2.2 Pop an item from stack and set it as root.
    a) If the popped item has a right child and the right child 
       is at top of stack, then remove the right child from stack,
       push the root back and set root as root's right child.
    b) Else print root's data and set root as NULL.
2.3 Repeat steps 2.1 and 2.2 while stack is not empty.

	/**
	* Definition for a binary tree node.
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class Solution {
	public:
	vector<int> postorderTraversal(TreeNode* root) {
	vector<int> res;
	if(root==NULL)
	return res;

	stack<TreeNode*> myStack;
	myStack.push(root->right); // push both current node and its right child to stack;
	myStack.push(root);

	TreeNode* cur = root->left;

	while(!myStack.empty()){
	if(cur!=NULL){
	myStack.push(cur->right);
	myStack.push(cur);
	cur = cur->left;
	}else{
	cur = myStack.top();
	myStack.pop();
	if(cur==NULL)
	continue;
	if(cur->right!=NULL&&myStack.size()!=0&&cur->right==myStack.top()){
	myStack.pop();
	myStack.push(cur);
	cur = cur->right;
	}else{
	res.push_back(cur->val);
	cur=NULL;
	}
	}
	}
	return res;
	}
	};

view raw Q145Rnd2.cpp hosted with ❤ by GitHub