online advertising

Sunday, January 17, 2016

Monday, January 11, 2016

LeetCode OJ - Coin Change

Problem: 

Please find the problem here.

Solution:

A classic problem solved with dynamic programming. Depending on the denomination greedy algorithm may or may not work, so use dynamic programming here.

Assume you already know the minimal number of coin needed to solve any $ k < n $. To solve at least how many coins is need for $ n $, you pick any one of the coin in the list and use it as the first coin, then the rest is just recursively 'solving' for $ n - c $, where $ c $ is the first coin value. Within all choices, just pick the best one.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/coin-change/

#include "LEET_COIN_CHANGE.h"
#include <algorithm>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_COIN_CHANGE
{
    class Solution
    {
    public:
        int coinChange(vector<int>& coins, int amount)
        {
            vector<int> answer;
            answer.resize(amount + 1);
            answer[0] = 0;
            for (int i = 1; i <= amount; i++)
            {
                int goal = i;
                int count = -1;
                for (unsigned int j = 0; j < coins.size(); j++)
                {
                    int remainder = goal - coins[j];
                    if (remainder >= 0)
                    {
                        int recursive_solution = answer[remainder];
                        if (recursive_solution != -1)
                        {
                            if (count == -1)
                            {
                                count = recursive_solution + 1;
                            }
                            else
                            {
                                count = min(count, recursive_solution + 1);
                            }
                        }
                    }
                }

                answer[i] = count;
            }
            return answer[amount];
        }
    };
};

using namespace _LEET_COIN_CHANGE;

int LEET_COIN_CHANGE()
{
    Solution solution;
    vector<int> coin;
    coin.push_back(1);
    coin.push_back(2);
    coin.push_back(5);
    cout << solution.coinChange(coin, 11) << endl;
    return 0;
}

Saturday, January 9, 2016

LeetCode OJ - Power of Three

Problem: 

Please find the problem here.

Solution:

It is simple to check if it is a power of 3 with a loop. Not using a loop, the easiest method is just to check all possible numbers, after all there are only a few power of 3 in the whole range of signed 32 bit integer.

I wrote a code generator for this.

I am pleasantly surprised that this simple code's performance beats 99.57% of c++ code submission.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/power-of-three/

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

using namespace std;

namespace _LEET_POWER_OF_THREE
{
    class Solution
    {
    public:
        bool isPowerOfThree(int n)
        {
            if (n == 1) return true;
            if (n == 3) return true;
            if (n == 9) return true;
            if (n == 27) return true;
            if (n == 81) return true;
            if (n == 243) return true;
            if (n == 729) return true;
            if (n == 2187) return true;
            if (n == 6561) return true;
            if (n == 19683) return true;
            if (n == 59049) return true;
            if (n == 177147) return true;
            if (n == 531441) return true;
            if (n == 1594323) return true;
            if (n == 4782969) return true;
            if (n == 14348907) return true;
            if (n == 43046721) return true;
            if (n == 129140163) return true;
            if (n == 387420489) return true;
            if (n == 1162261467) return true;
            return false;
        }
    };
};

using namespace _LEET_POWER_OF_THREE;

int LEET_POWER_OF_THREE()
{
    Solution solution;
    for (int i = 0; i <= 9; i++)
    {
        cout << solution.isPowerOfThree(i) << endl;
    }
    return 0;
}

Thursday, January 7, 2016

LeetCode OJ - Maximum Product of Word Lengths

Problem: 

Please find the problem here.

Solution:

The problem is really about quickly determine if two words share a letter. Bitmask works great for the purpose.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/climbing-stairs/

#include "LEET_MAXIMUM_PRODUCT_OF_WORD_LENGTHS.h"
#include <algorithm>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_MAXIMUM_PRODUCT_OF_WORD_LENGTHS
{
    class Solution
    {
    public:
        int maxProduct(vector<string>& words)
        {
            vector<int> wordSummaries;
            wordSummaries.resize(words.size());
            for (unsigned int i = 0; i < words.size(); i++)
            {
                wordSummaries[i] = 0;
                for (unsigned int j = 0; j < words[i].length(); j++)
                {
                    wordSummaries[i] |= (1 << (words[i][j] - 'a'));
                }
            }

            int maxProduct = 0;
            for (unsigned int j = 0; j < words.size(); j++)
            {
                for (unsigned int k = j + 1; k < words.size(); k++)
                {
                    if ((wordSummaries[j] & wordSummaries[k]) == 0)
                    {
                        int product = words[j].length() * words[k].length();
                        maxProduct = max(maxProduct, product);
                    }
                }
            }

            return maxProduct;
        }
    };
};

using namespace _LEET_MAXIMUM_PRODUCT_OF_WORD_LENGTHS;

int LEET_MAXIMUM_PRODUCT_OF_WORD_LENGTHS()
{
    Solution solution;
    string case1_array[] = { "abcw", "baz", "foo", "bar", "xtfn", "abcdef" };
    vector<string> case1(case1_array, case1_array + _countof(case1_array));
    cout << solution.maxProduct(case1) << endl;

    string case2_array[] = { "a", "ab", "abc", "d", "cd", "bcd", "abcd" };
    vector<string> case2(case2_array, case2_array + _countof(case2_array));
    cout << solution.maxProduct(case2) << endl;

    string case3_array[] = { "a", "aa", "aaa", "aaaa" };
    vector<string> case3(case3_array, case3_array + _countof(case3_array));
    cout << solution.maxProduct(case3) << endl;

    return 0;
}

Wednesday, January 6, 2016

LeetCode OJ - Count Complete Tree Nodes

Problem: 

Please find the problem here.

Solution:

The problem is pretty simple, just counting the number of nodes.

The not so simple part is that we have a pretty tight bound for timing.

The key idea of the solution is that if the depth computed from going all the way left and going all the way right is identical, then we can skip the sub-tree.

If we have already computed the left depth, we can pass it on when we recurse into the left sub tree to optimize for performance.

The overall performance $ O(\log^2 n) $, and even constant matter for this problem's judge.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/count-complete-tree-nodes/

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

using namespace std;

namespace _LEET_COUNT_COMPLETE_TREE_NODES
{
    struct TreeNode
    {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x) : val(x), left(NULL), right(NULL)
        {
        }
    };

    class Solution
    {
    public:
        int leftDepth(TreeNode* node)
        {
            if (node == NULL)
            {
                return 0;
            }
            else
            {
                return 1 + leftDepth(node->left);
            }
        }

        int rightDepth(TreeNode* node)
        {
            if (node == NULL)
            {
                return 0;
            }
            else
            {
                return 1 + rightDepth(node->right);
            }
        }
        int countNodes(TreeNode* root, int leftDepthValue, int rightDepthValue)
        {
            int actualLeftDepthValue = leftDepthValue == -1 ? leftDepth(root) : leftDepthValue;
            int actualRightDepthValue = rightDepthValue == -1 ? rightDepth(root) : rightDepthValue;
            if (actualLeftDepthValue == actualRightDepthValue)
            {
                return (1 << actualLeftDepthValue) - 1;
            }
            else
            {
                return 1 + countNodes(root->left, actualLeftDepthValue - 1, -1) + countNodes(root->right, -1, actualRightDepthValue - 1);
            }
        }

        int countNodes(TreeNode* root)
        {
            return countNodes(root, -1, -1);
        }

    };

    TreeNode* BuildFullTree(int size)
    {
        if (size == 0)
        {
            return NULL;
        }
        else
        {
            TreeNode* leftSubTree = BuildFullTree(size - 1);
            TreeNode* rightSubTree = BuildFullTree(size - 1);
            TreeNode* result = new TreeNode(0);
            result->left = leftSubTree;
            result->right = rightSubTree;
            return result;
        }

    }
};

using namespace _LEET_COUNT_COMPLETE_TREE_NODES;

int LEET_COUNT_COMPLETE_TREE_NODES()
{
    Solution solution;
    int size = 3;
    TreeNode* test = BuildFullTree(size);
    TreeNode* left = test;
    for (int i = 0; i < size - 1; i++)
    {
        left = left->left;
    }
    left->left = new TreeNode(0);
    cout << solution.countNodes(test) << endl;
    return 0;
}

Monday, January 4, 2016

LeetCode OJ - Burst Balloons

Problem: 

Please find the problem here.

Solution:

I learn this new idea of interval dynamic programming. As of any dynamic programming, the key idea is to find out what are the sub-problems.

Originally, I was struggled after picking the first one to burst, bursting the leftmost balloon on the right hand side is going to have impact on the left hand side sub-problem, so we have many sub-problems, not good.

The key idea is, instead of picking the first one to burst, pick the last one. The last one fix the boundary of the both sub-problems so we can divide and conquer.

In particular, define $ f[i,j] $ as the optimal number of coins one can collect in the closed interval $ [i, j] $ subject to the constraint that $ [i-1] $ and $ [j + 1] $ is not bursted until $ [i,j] $ is bursted.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/burst-balloons/

#include "LEET_BURST_BALLOONS.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <algorithm>

using namespace std;

namespace _LEET_BURST_BALLOONS
{
    class Solution
    {
    public:
        int maxCoins(vector<int>& nums)
        {
            if (nums.size() == 0)
            {
                return 0;
            }

            // interval_solution[i][j] represents the maximum number of coins one can collect 
            // in the range [i, j] subject to the constraint that the (i-1)th and the (j+1)th 
            // balloon is not bursted until all balloons in [i, j] are bursted.
            vector<vector<int>> interval_solution;
            unsigned int n = nums.size();
            interval_solution.resize(n);
            for (unsigned int i = 0; i < n; i++)
            {
                interval_solution[i].resize(n);
            }

            // We build the solution from short interval to long ones
            for (int interval_length = 1; interval_length <= n; interval_length++)
            {
                int interval_src = 0;
                while (true)
                {
                    int interval_dst = interval_src + interval_length - 1; // the inclusive end index
                    if (interval_dst == n)
                    {
                        break;
                    }

                    int best = -1;
                    for (int last_balloon = interval_src; last_balloon <= interval_dst; last_balloon++)
                    {
                        // Since this is the last balloon to burst, all other balloons within the interval are bursted
                        // So at the time the last balloon is bursted, the last balloon is between the boundary of the interval
                        int last_balloon_prev_value = interval_src == 0 ? 1 : nums[interval_src - 1];
                        int last_balloon_next_value = interval_dst == n - 1 ? 1 : nums[interval_dst + 1];
                        int burst_value = last_balloon_prev_value * nums[last_balloon] * last_balloon_next_value;

                        // The total value of bursting all balloon is divided into three parts, the 
                        // portion before the last balloon, the last balloon itself, and the portion after the last balloon.
                        // In actual bursting, one could interleave bursting balloon is the left hand side or right hand side.
                        // The optimal bursting value is unchanged
                        int prev_value = last_balloon == interval_src ? 0 : interval_solution[interval_src][last_balloon - 1];
                        int next_value = last_balloon == interval_dst ? 0 : interval_solution[last_balloon + 1][interval_dst];

                        int total_value = prev_value + burst_value + next_value;

                        best = max(best, total_value);
                    }
                    interval_solution[interval_src][interval_dst] = best;

                    interval_src++;
                }
            }
            return interval_solution[0][n - 1];
        }
    };
};

using namespace _LEET_BURST_BALLOONS;

int LEET_BURST_BALLOONS()
{
    int case1[] = { 3, 1, 5, 8 };
    Solution solution;
    cout << solution.maxCoins(vector<int>(case1, case1 + _countof(case1))) << endl;
    return 0;
}