online advertising

Monday, February 20, 2017

LeetCode OJ - Total Hamming Distance

Problem:

Please find the problem here.

Analysis:

The input could have 10,000 elements, we need to figure out a way to compute the total hamming distance without going through all pairs.

Solution:

Imagine for a bit they are all 1 bit number (i.e. either 0 or 1), then it is easy. Just count the number of zeros and number of ones and multiply them together.

For a full solution, just do this for all bits.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/total-hamming-distance

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

using namespace std;

namespace _LEET_TOTAL_HAMMING_DISTANCE
{
    class Solution
    {
    public:
        int totalHammingDistance(vector<int>& nums)
        {
            int dist = 0;
            int mask = 1;
            for (int i = 0; i < 32; i++)
            {
                int zero = 0;
                int ones = 0;
                for (size_t j = 0; j < nums.size(); j++)
                {
                    bool is_zero = (nums[j] & mask) == 0;
                    if (is_zero) { zero++; } else { ones++; }
                }
                dist += zero * ones;
                mask = mask << 1;
            }
            return dist;
        }
    };
};

using namespace _LEET_TOTAL_HAMMING_DISTANCE;

int LEET_TOTAL_HAMMING_DISTANCE()
{
    Solution solution;
    int input_array[] = { 4, 14, 2 };
    vector<int> input(input_array, input_array + _countof(input_array));
    cout << solution.totalHammingDistance(input) << endl;
    return 0;
}

Wednesday, February 15, 2017

LeetCode OJ - Most Frequent Subtree Sum

Problem:

Please find the problem here.

Analysis:

There are two subproblems, find the subtree sum and finding the ones with max frequency. Both of them are easy.

Solution:

We just need to combine them. In the unwinding phase of the tree traversal, we can get the subtree sums. We put them in a histogram, and finally we can get the ones with maximum frequency.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/most-frequent-subtree-sum/

#include "LEET_MOST_FREQUENT_SUBTREE_SUM.h"
#include <map>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

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

    class Solution
    {
    public:
        int findFrequentTreeSum(TreeNode* root, map<int, int>& histogram)
        {
            if (root == nullptr)
            {
                return 0;
            }
            int left = findFrequentTreeSum(root->left, histogram);
            int right = findFrequentTreeSum(root->right, histogram);
            int sum = left + right + root->val;
            auto probe = histogram.find(sum);
            if (probe == histogram.end())
            {
                histogram.insert(make_pair(sum, 1));
            }
            else
            {
                probe->second++;
            }

            return sum;
        }
        vector<int> findFrequentTreeSum(TreeNode* root)
        {
            map<int, int> histogram;
            findFrequentTreeSum(root, histogram);
            int max_freq = -1;
            for (auto pair : histogram)
            {
                max_freq = max(max_freq, pair.second);
            }
            vector<int> solution;
            for (auto pair : histogram)
            {
                if (pair.second == max_freq)
                {
                    solution.push_back(pair.first);
                }
            }

            return solution;
        }
    };
};

using namespace _LEET_MOST_FREQUENT_SUBTREE_SUM;

int LEET_MOST_FREQUENT_SUBTREE_SUM()
{
    Solution solution;
    TreeNode a(5);
    TreeNode b(2);
    TreeNode c(-3);
    a.left = &b;
    a.right = &c;
    auto test1 = solution.findFrequentTreeSum(&a);
    for (auto result : test1)
    {
        cout << result << " ";
    }
    cout << endl;

    TreeNode p(5);
    TreeNode q(2);
    TreeNode r(-5);
    p.left = &q;
    p.right = &r;
    auto test2 = solution.findFrequentTreeSum(&p);
    for (auto result : test2)
    {
        cout << result << " ";
    }
    cout << endl;
    return 0;
}

LeetCode OJ - Find Bottom Left Tree Value

Problem:

Please find the problem here.

Analysis:

This problem look very much like the previous one, with a twist. We need the leftmost entry. The easiest way to make sure we get the left most entry first is simply doing an in-order traversal.

Solution:

Just do an in-order traversal, keep track of the answer and update as necessary. As an aside, I hate pass by reference, that is so dangerous. I wouldn't use them in product code. But sometimes I do use it for competitive programming because it make the syntax so much simpler. A nice tool for a small problem could be a disaster used in scale ...

Code:

#include "stdafx.h"

// https://leetcode.com/problems/find-bottom-left-tree-value/

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

using namespace std;

namespace _LEET_FIND_BOTTOM_LEFT_TREE_VALUE
{
    struct TreeNode
    {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };
    class Solution
    {
    public:
        void findBottomLeftValue(TreeNode* root, int depth, int& max_layer, int& answer)
        {
            if (root == nullptr)
            {
                return;
            }
            findBottomLeftValue(root->left, depth + 1, max_layer, answer);
            if (depth > max_layer)
            {
                max_layer = depth;
                answer = root->val;
            }
            findBottomLeftValue(root->right, depth + 1, max_layer, answer);
        }
        int findBottomLeftValue(TreeNode* root)
        {
            int max_layer = -1;
            int answer = 0;
            findBottomLeftValue(root, 0, max_layer, answer);
            return answer;
        }
    };
};

using namespace _LEET_FIND_BOTTOM_LEFT_TREE_VALUE;

int LEET_FIND_BOTTOM_LEFT_TREE_VALUE()
{
    Solution solution;
    TreeNode a(2);
    TreeNode b(1);
    TreeNode c(3);
    a.left = &b;
    a.right = &c;
    cout << solution.findBottomLeftValue(&a) << endl;

    TreeNode p(1);
    TreeNode q(2);
    TreeNode r(3);
    TreeNode s(4);
    TreeNode t(5);
    TreeNode u(6);
    TreeNode v(7);
    p.left = &q;
    p.right = &r;
    q.left = &s;
    r.left = &t;
    r.right = &u;
    t.left = &v;
    cout << solution.findBottomLeftValue(&p) << endl;
    return 0;
}

LeetCode OJ - Find Largest Value in Each Tree Row

Problem:

Please find the problem here.

Analysis:

Given only the root, there is no way I can tell which subtree have the largest element in a certain row, so I have to walk the whole tree anyway. To put it more technically, suppose there exist an algorithm that does not visit all nodes, in particular, it does not visit a node p. An adversary could put a huge number in the node p and therefore the algorithm output a wrong result. Therefore any algorithm must walk the whole tree.

Solution:

Now we know we have to walk the whole tree, then the solution is relatively simple. Suppose we use a tree traversal (any traversal would do) and also keep track of the current height, then we can maintain a vector of maximum values in the current row. That would be the final result.

The interesting thing about a (just about any) tree traversal is that it increase the depth only by 1. Therefore, the vector of maximum number can increase at most by 1. That make the implementation easy by a simple push_back to the vector.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/find-largest-value-in-each-tree-row/

#include "LEET_FIND_LARGEST_VALUE_IN_EACH_TREE_ROW.h"
#include <map>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_FIND_LARGEST_VALUE_IN_EACH_TREE_ROW
{
    struct TreeNode
    {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };
    class Solution
    {
    public:
        void largestValues(TreeNode* root, int depth, vector<int>& result)
        {
            if (root == nullptr)
            {
                return;
            }
            if (result.size() > depth)
            {
                result[depth] = max(result[depth], root->val);
            }
            else
            {
                result.push_back(root->val);
            }
            largestValues(root->left, depth + 1, result);
            largestValues(root->right, depth + 1, result);
        }
        vector<int> largestValues(TreeNode* root)
        {
            vector<int> result;
            largestValues(root, 0, result);
            return result;
        }
    };
};

using namespace _LEET_FIND_LARGEST_VALUE_IN_EACH_TREE_ROW;

int LEET_FIND_LARGEST_VALUE_IN_EACH_TREE_ROW()
{
    Solution solution;
    TreeNode a(1);
    TreeNode b(3);
    TreeNode c(2);
    TreeNode d(5);
    TreeNode e(3);
    TreeNode f(9);
    a.left = &b;
    a.right = &c;
    b.left = &d;
    b.right = &e;
    c.right = &f;
    auto result = solution.largestValues(&a);
    for (auto&& r : result)
    {
        cout << r << endl;
    }
    return 0;
}

LeetCode OJ - Longest Palindromic Subsequence

Problem:

Please find the problem here.

Analysis:

Recently I have been reading up about some algorithms on bioinformatics and this one does look similar. The idea is you use interval dynamic programming.

Suppose we know the answer (i.e. the length of the longest palindromic subsequence) of all substrings with length less than d. We can use that information to compute the answer for all substring with length d.

To make the description simpler, let's abbreviate the longest palindromic subsequence to just LPS

There are a few possibilities, for the LPS, one of the following must hold:

  • The first character is paired with the last character.
  • The first character is paired with some other character but not the last one.
  • The first character is not included in the LPS.

For the first one, of course, the first and last one must be equal, and then we take the
LPS on the inner d - 2 characters. The length is therefore 2 + LPS(the inner d-2 characters)

For the second one, the last character cannot be paired with anything since the first one is paired with something else and apparently there is nothing before the first one. So this case the LPS is really just the LPS of the beginning d -1 characters.

For the third one, the first character cannot be paired with anything by design, so this case the LPS is really just the LPS of the last d -1 characters.

That make a very simple recurrence relation, define lps(i, j) be the length of the LPS of the substring of S from i to j inclusive.

lps(i, j) = max(lps(i, j - 1), lps(i + 1, j), 2 + lps(i + 1, j - 1))

Of course, the last term apply only if S[i] == S[j].

Solution:

We define lps2(i, len) = lps(i, i + len - 1). With this transformation, we know that we only need the last two lengths when computing the current length values, therefore we can save memory by keeping only the last two rows.

To avoid copying, I used a simple circular buffer scheme, that should make reading the code a little easier to understand this.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/longest-palindromic-subsequence/

#include "LEET_LONGEST_PALINDROMIC_SUBSEQUENCE.h"
#include <map>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_LONGEST_PALINDROMIC_SUBSEQUENCE
{
    class Solution
    {
    public:
        int longestPalindromeSubseq(string s)
        {
            if (s.length() == 0)
            {
                return 0;
            }

            vector<int> result[3];
            result[0].resize(s.length());
            result[1].resize(s.length());
            result[2].resize(s.length());
            for (size_t i = 0; i < s.length(); i++)
            {
                // The maximum palindromic subsequence of a subsequence starting at i with length 0 is 0
                result[0][i] = 0;
                // The maximum palindromic subsequence of a subsequence starting at i with length 1 is 1
                result[1][i] = 1;
            }

            int current_row = 2;
            int last_row = 1;
            int last_last_row = 0;
            for (int length = 2; length <= s.length(); length++)
            {
                for (int i = 0; i + length <= s.length(); i++)
                {
                    int candidate = result[last_row][i];
                    candidate = max(candidate, result[last_row][i + 1]);
                    if (s[i] == s[i + length - 1])
                    {
                        candidate = max(candidate, 2 + result[last_last_row][i + 1]);
                    }
                    result[current_row][i] = candidate;
                }
                current_row = (current_row + 1) % 3;
                last_row = (last_row + 1) % 3;
                last_last_row = (last_last_row + 1) % 3;
            }
            return result[last_row][0];
        }
    };
};

using namespace _LEET_LONGEST_PALINDROMIC_SUBSEQUENCE;

int LEET_LONGEST_PALINDROMIC_SUBSEQUENCE()
{
    Solution solution;
    cout << solution.longestPalindromeSubseq("") << endl;
    cout << solution.longestPalindromeSubseq("bbbab") << endl;
    cout << solution.longestPalindromeSubseq("cbbd") << endl;
    return 0;
}

Friday, February 10, 2017

LeetCode OJ - Find Mode in Binary Search Tree

Problem:

Please find the problem here.

Analysis:

A standard idea is to build a frequency table. Once the table is built, we go through the table to find out who are the winners. In the worst case where the tree has all distinct elements, this will lead to an extra linear space.

Solution:

The key idea is that we can do an in-order traversal of the tree to get a sorted order. We build the tree as usual with a single difference - the table only contain two entries. The current best entry, and the last number entry. Suppose an element X doesn't have enough count, and in the in-order traversal we see Y now, X is never going to win, so we can get X out of the table. Now we have a constant extra space algorithm! (Of course, you still need to save all the answers to report them, which, in the worst case, linear)

Code:


#include "stdafx.h"

// https://leetcode.com/problems/find-mode-in-binary-search-tree/

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

using namespace std;

namespace _LEET_FIND_MODE_IN_BINARY_SEARCH_TREE
{
    struct TreeNode
    {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };
    class Solution {
    public:
        void findMode(TreeNode* root, vector<int>& result, int& max_count, int& last_node, int& last_count)
        {
            if (root == nullptr)
            {
                return;
            }

            if (root->left != nullptr)
            {
                findMode(root->left, result, max_count, last_node, last_count);
            }

            if (max_count == 0)
            {
                // This is possible only for the very first call
                result.push_back(root->val);
                max_count = 1;
                last_node = root->val;
                last_count = 1;
            }
            else
            {
                if (root->val == last_node)
                {
                    last_count++;
                }
                else
                {
                    last_node = root->val;
                    last_count = 1;
                }

                if (last_count == max_count)
                {
                    result.push_back(last_node);
                }
                else if (last_count > max_count)
                {
                    result.clear();
                    result.push_back(last_node);
                    max_count = last_count;
                }
            }

            if (root->right != nullptr)
            {
                findMode(root->right, result, max_count, last_node, last_count);
            }
        }

        vector<int> findMode(TreeNode* root)
        {
            vector<int> result;
            int max_count = 0;
            int last_node = 0;
            int last_count = 0;
            findMode(root, result, max_count, last_node, last_count);
            return result;
        }
    };
};

using namespace _LEET_FIND_MODE_IN_BINARY_SEARCH_TREE;

int LEET_FIND_MODE_IN_BINARY_SEARCH_TREE()
{
    Solution solution;
    TreeNode a(1);
    TreeNode b(2);
    TreeNode c(2);
    a.left = nullptr;
    a.right = &b;
    b.left = &c;
    b.right = nullptr;
    c.left = nullptr;
    c.right = nullptr;
    vector<int> result = solution.findMode(&a);
    for (int i = 0; i < result.size(); i++)
    {
        cout << result[i] << endl;
    }
    return 0;
}