online advertising

Sunday, May 28, 2017

LeetCode OJ - Subtree of Another Tree

Problem:

Please find the problem here.

Analysis:

In this problem, I didn't spend much time to optimize the solution. It is a simple dirty yet $ O(n) $ solution. I simply computed the in-order traversal of both trees, and I claim that if the string representation matches, it must be an identical sub-tree.

Solution:

The key thing that we need to worry about is whether or not a substring match is due to reason other than a complete sub-tree matches, for example, the substring match was due to taking some data in the earlier subtrees or some later subtrees. It is made impossible by adding the brackets. The bracket helped us to make sure in the parent string the substring is properly parenthesized, so it has to be a subtree and a subtree alone. The commas are also important, it make sure we cannot concatenate numbers differently to yield the same string.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/subtree-of-another-tree

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

using namespace std;

namespace _LEET_SUBTREE_OF_ANOTHER_TREE
{
    struct TreeNode
    {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };
    class Solution
    {
    public:
        void ToString(TreeNode* s, ostringstream& sout)
        {
            if (s == nullptr)
            {
                sout << "#" << ",";
            }
            else
            {
                sout << "(";
                ToString(s->left, sout);
                sout << s->val;
                sout << ",";
                ToString(s->right, sout);
                sout << ")";
            }
        }
        bool isSubtree(TreeNode* s, TreeNode* t)
        {
            ostringstream sout;
            ostringstream tout;
            ToString(s, sout);
            ToString(t, tout);
            string sstr = sout.str();
            string tstr = tout.str();
            const char* x = strstr(sstr.c_str(), tstr.c_str());
            return (x != nullptr);
        }
    };
};

using namespace _LEET_SUBTREE_OF_ANOTHER_TREE;

int LEET_SUBTREE_OF_ANOTHER_TREE()
{
    TreeNode a(3);
    TreeNode b(4);
    TreeNode c(5);
    TreeNode d(1);
    TreeNode e(2);
    a.left = &b;
    a.right = &c;
    b.left = &d;
    b.right = &e;
    c.left = nullptr;
    c.right = nullptr;
    d.left = nullptr;
    d.right = nullptr;
    e.left = nullptr;
    e.right = nullptr;

    TreeNode p(4);
    TreeNode q(1);
    TreeNode r(2);
    p.left = &q;
    p.right = &r;
    q.left = nullptr;
    q.right = nullptr;
    r.left = nullptr;
    r.right = nullptr;

    Solution s;
    cout << (s.isSubtree(&a, &p) ? "True" : "False") << endl;
    return 0;
}

LeetCode OJ - Permutation in String

Problem:

Please find the problem here.

Analysis:

The idea is that we can check if two strings are equal to each other by comparing their histogram.

Solution:

We can easily compute the histogram of the s2, but for s1, we need a sliding histogram. Fortunately, computing a sliding histogram is pretty easy and simply take $ O(1) $ time to slide it. It is also $ O(1) $ time to compare two histograms since the strings only has lower case letters.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/permutation-in-string

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

using namespace std;

namespace _LEET_PERMUTATION_IN_STRING
{
    class Solution {
    public:
        bool checkInclusion(string s1, string s2)
        {
            if (s1.length() > s2.length())
            {
                return false;
            }
            char fixed_histogram[26];
            char slide_histogram[26];
            for (int i = 0; i < 26; i++)
            {
                fixed_histogram[i] = slide_histogram[i] = 0;
            }
            for (size_t i = 0; i < s1.length(); i++)
            {
                fixed_histogram[s1[i] - 'a']++;
                slide_histogram[s2[i] - 'a']++;
            }
            bool match = true;
            for (int i = 0; match && i < 26; i++)
            {
                match = fixed_histogram[i] == slide_histogram[i];
            }
            if (match)
            {
                return true;
            }
            for (size_t i = s1.length(); i < s2.length(); i++)
            {
                slide_histogram[s2[i - s1.length()] - 'a']--;
                slide_histogram[s2[i] - 'a']++;
                match = true;
                for (int i = 0; match && i < 26; i++)
                {
                    match = fixed_histogram[i] == slide_histogram[i];
                }
                if (match)
                {
                    return true;
                }
            }
            return false;
        }
    };
};

using namespace _LEET_PERMUTATION_IN_STRING;

int LEET_PERMUTATION_IN_STRING()
{
    Solution solution;
    cout << (solution.checkInclusion("ab", "eidbaooo") ? "True" : "False") << endl;
    return 0;
}

LeetCode OJ - Subarray Sum Equals K

Problem:

Please find the problem here.

Analysis:

We can use the running sum trick to reduce the problem of finding a sum to just do a subtraction. With that in mind, we are basically simply counting how many pairs of numbers in the running sum array such that when the right one subtracts the left one, yield $ k $.

Solution:

To find that count, we maintain a "wanted" list when we scan from left to right. The "wanted" list is basically a number such that if we encounter it in the future, it would make a right subtracted result. Building a wanted list is easy, and checking if it is wanted is also easy, so there we go.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/subarray-sum-equals-k

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

using namespace std;

namespace _LEET_SUBARRAY_SUM_EQUALS_K
{
    class Solution
    {
    public:
        int subarraySum(vector<int>& nums, int k)
        {
            int n = (int)nums.size();
            vector<int> running_sums;
            running_sums.resize(n + 1);
            running_sums[0] = 0;
            for (int i = 0; i < n; i++)
            {
                running_sums[i + 1] = nums[i] + running_sums[i];
            }
            map<int, int> wanted_count;
            int result = 0;
            for (int i = 0; i < (n + 1); i++)
            {
                auto probe1 = wanted_count.find(running_sums[i]);
                if (probe1 != wanted_count.end())
                {
                    result += probe1->second;
                }
                int wanted = k + running_sums[i];
                auto probe2 = wanted_count.find(wanted);
                if (probe2 == wanted_count.end())
                {
                    wanted_count.insert(make_pair(wanted, 1));
                }
                else
                {
                    probe2->second++;
                }
            }
            return result;
        }
    };
};

using namespace _LEET_SUBARRAY_SUM_EQUALS_K;

int LEET_SUBARRAY_SUM_EQUALS_K()
{
    Solution s;
    int input_array[] = { 1, 1, 1 };
    vector<int> input(input_array, input_array + _countof(input_array));
    cout << s.subarraySum(input, 2) << endl;
    return 0;
}

LeetCode OJ - Shortest Unsorted Continuous Subarray

Problem:

Please find the problem here.

Analysis:

Here is a simple observation, any element that is not the same as the sorted array need to be moved.

Solution:

Therefore the Shortest Unsorted Continuous Subarray must begin at the leftmost mismatch and ends with the rightmost mismatch.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/shortest-unsorted-continuous-subarray

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

using namespace std;

namespace _LEET_SHORTEST_UNSORTED_CONTINUOUS_SUBARRAY
{
    class Solution
    {
    public:
        int findUnsortedSubarray(vector<int>& nums)
        {
            vector<int> sorted(nums.begin(), nums.end());
            sort(sorted.begin(), sorted.end());
            int result = (int)nums.size();
            int s = 0;
            while (s < nums.size() && nums[s] == sorted[s])
            {
                s++;
                result--;
            }
            int e = (int)(nums.size() - 1);
            while (e >= s && nums[e] == sorted[e])
            {
                e--;
                result--;
            }
            return result;
        }
    };
};

using namespace _LEET_SHORTEST_UNSORTED_CONTINUOUS_SUBARRAY;

int LEET_SHORTEST_UNSORTED_CONTINUOUS_SUBARRAY()
{
    Solution s;
    int input_array[] = { 2, 6, 4, 8, 10, 9, 15 };
    vector<int> input(input_array, input_array + _countof(input_array));
    cout << s.findUnsortedSubarray(input) << endl;
    return 0;
}

LeetCode OJ - Kill Process

Problem:

Please find the problem here.

Analysis:

This is really just a problem of finding all the nodes in a sub-tree.

Solution:

We begin with building the tree, and then finding the sub-tree using BFS.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/kill-process

#include "LEET_KILL_PROCESS.h"
#include <map>
#include <iostream>
#include <queue>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_KILL_PROCESS
{
    struct Node
    {
        int data;
        Node* child;
        Node* sibling;
    };
    class Solution {
    public:
        vector<int> killProcess(vector<int>& pid, vector<int>& ppid, int kill)
        {
            map<int, Node*> nodes;
            Node* root = nullptr;
            size_t n = pid.size();
            for (size_t i = 0; i < n; i++)
            {
                Node* newNode = new Node();
                newNode->data = pid[i];
                newNode->child = newNode->sibling = nullptr;
                nodes.insert(make_pair(pid[i], newNode));
            }

            for (size_t i = 0; i < n; i++)
            {
                if (ppid[i] == 0)
                {
                    root = nodes[pid[i]];
                }
                else
                {
                    Node* curr = nodes[pid[i]];
                    Node* prev = nodes[ppid[i]];
                    curr->sibling = prev->child;
                    prev->child = curr;
                }
            }

            vector<int> result;
            queue<Node*> bfs;
            bfs.push(nodes[kill]);
            while (!bfs.empty())
            {
                Node* current = bfs.front();
                bfs.pop();
                result.push_back(current->data);
                Node* child = current->child;
                while (child != nullptr)
                {
                    bfs.push(child);
                    child = child->sibling;
                }
            }
            return result;
        }
    };
};

using namespace _LEET_KILL_PROCESS;

int LEET_KILL_PROCESS()
{
    Solution s;
    int pid_array[] = { 1,3,10,5 };
    int ppid_array[] = { 3,0,5,3 };
    vector<int> pid(pid_array, pid_array + _countof(pid_array));
    vector<int> ppid(ppid_array, ppid_array + _countof(ppid_array));
    vector<int> result = s.killProcess(pid, ppid, 5);
    for (size_t i = 0; i < result.size(); i++)
    {
        cout << result[i] << " ";
    }
    cout << endl;
    return 0;
}

LeetCode OJ - Longest Harmonious Subsequence

Problem:

Please find the problem here.

Analysis:

The key misleading word in the problem name is "subsequence". If we can pick non consecutive elements, and there is no requirement where the smallest and the largest is in the subsequence, the word subsequence can totally be replaced by subset. Once we have this realization, the rest is easy.

Solution:

To make calculation fast, we can build a histogram on counts of numbers by their value. Then we can search if there exists consecutive pairs. If we do, and have multiple of them, we can find the largest one.

I could have make this faster (e.g. $ O(n) $) by using a hash search instead, but this is simple and passes the judge.

Code:

#include "stdafx.h"

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

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

using namespace std;

namespace _LEET_LONGEST_HARMONIOUS_SUBSEQUENCE
{
    class Solution
    {
    public:
        int findLHS(vector<int>& nums)
        {
            map<int, int> m;
            for (auto&& n : nums)
            {
                auto probe = m.find(n);
                if (probe == m.end())
                {
                    m.insert(make_pair(n, 1));
                }
                else
                {
                    probe->second++;
                }
            }
            vector<pair<int, int>> freq;
            for (auto&& p : m)
            {
                freq.push_back(p);
            }
            if (freq.size() < 2)
            {
                return 0;
            }
            else
            {
                int result = 0;
                for (size_t i = 1; i < freq.size(); i++)
                {
                    if (freq[i - 1].first + 1 == freq[i].first)
                    {
                        result = max(result, freq[i - 1].second + freq[i].second);
                    }
                }
                return result;
            }
        }
    };
};

using namespace _LEET_LONGEST_HARMONIOUS_SUBSEQUENCE;

int LEET_LONGEST_HARMONIOUS_SUBSEQUENCE()
{
    Solution s;
    int input_array[] = { 1,3,2,2,5,2,3,7 };
    vector<int> input(input_array, input_array + _countof(input_array));
    cout << s.findLHS(input) << endl;
    return 0;
}

Monday, May 1, 2017

LeetCode OJ - Student Attendance Record II

Problem:

Please find the problem here.

Analysis:

The fun part of doing this problem is the analysis. Here is how I thought about the problem.

Let $ a[n] $ be the number of strings of length $ n $ with 0 absence and ends with 0 late records.
Let $ b[n] $ be the number of strings of length $ n $ with 0 absence and ends with 1 late records.
Let $ c[n] $ be the number of strings of length $ n $ with 0 absence and ends with 2 late records.
Let $ d[n] $ be the number of strings of length $ n $ with 1 absence and ends with 0 late records.
Let $ e[n] $ be the number of strings of length $ n $ with 1 absence and ends with 1 late records.
Let $ f[n] $ be the number of strings of length $ n $ with 1 absence and ends with 2 late records.

It is easy to see these are all possibilities for any string that can be rewarded. Now let's take a look on how to compute the value of these for arbitrary $ n $.

It is also pretty obvious that the initial conditions works:

$ a[1] = 1 $, this is the string 'P'.
$ b[1] = 1 $, this is the string 'L'.
$ c[1] = 0 $, there cannot be any.
$ d[1] = 1 $, this is the string 'A'.
$ e[1] = 0 $, there cannot be any.
$ f[1] = 0 $, there cannot be any.

And here are the recurrence relations:

$ a[n + 1] = a[n] + b[n] + c[n] $.
$ b[n + 1] = a[n] $.
$ c[n + 1] = b[n] $.
$ d[n + 1] = a[n] + b[n] + c[n] + d[n] + e[n] + f[n] $.
$ e[n + 1] = d[n] $.
$ f[n + 1] = e[n] $.

Solution:

Given the recurrence it is pretty easy to write the code. Care is taken to make sure we never overflow by making sure we do the mod operation for every addition.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/student-attendance-record-ii

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

using namespace std;

namespace _LEET_STUDENT_ATTENDANCE_RECORD_II
{
    class Solution {
    public:
        int add(int x, int y)
        {
            return (x + y) % 1000000007;
        }

        int checkRecord(int n) {
            if (n == 0)
            {
                return 0;
            }

            int a = 1, b = 1, c = 0, d = 1, e = 0, f = 0;

            for (int i = 1; i < n; i++)
            {
                int ta = add(add(a, b), c);
                int tb = a;
                int tc = b;
                int td = add(add(add(add(add(a, b), c), d), e), f);
                int te = d;
                int tf = e;

                a = ta;
                b = tb;
                c = tc;
                d = td;
                e = te;
                f = tf;
            }

            return add(a, add(b, add(c, add(d, add(e, f)))));
        }
    };
};

using namespace _LEET_STUDENT_ATTENDANCE_RECORD_II;

int LEET_STUDENT_ATTENDANCE_RECORD_II()
{
    Solution solution;
    for (int i = 1; i <= 50; i++)
    {
        cout << solution.checkRecord(i) << endl;
    }
    return 0;
}

LeetCode OJ - Binary Tree Tilt

Problem:

Please find the problem here.

Analysis:

It is obvious there is no way we can compute the tilt without walking the whole tree. Is it possible to do that in one pass? The answer is yes.

Solution:

The key is to do the work in the stack unwind phase. Just do a normal recursive tree processing and return both the tilt and the sum of the subtree. That allows the unwind phase to compute the same two thing and return that back to the caller.

I hate passing by reference - that's why I insisted on using pointers - that notation make it blindingly obvious to the caller that the value will be changed. It would be much more implicit in the reference case.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/binary-tree-tilt

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

using namespace std;

namespace _LEET_BINARY_TREE_TILT
{
    struct TreeNode
    {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };
    class Solution {
    public:
        void findTiltSum(TreeNode* root, int* pTilt, int* pSum)
        {
            if (root == nullptr)
            {
                *pTilt = 0;
                *pSum = 0;
            }
            else
            {
                int leftTilt;
                int leftSum;
                int rightTilt;
                int rightSum;
                findTiltSum(root->left, &leftTilt, &leftSum);
                findTiltSum(root->right, &rightTilt, &rightSum);
                *pSum = leftSum + rightSum + root->val;
                *pTilt = abs(leftSum - rightSum) + leftTilt + rightTilt;
            }
        }

        int findTilt(TreeNode* root)
        {
            int tilt;
            int sum;
            findTiltSum(root, &tilt, &sum);
            return tilt;
        }
    };
};

using namespace _LEET_BINARY_TREE_TILT;

int LEET_BINARY_TREE_TILT()
{
    Solution solution;
    TreeNode a(1);
    TreeNode b(2);
    TreeNode c(3);
    a.left = &b;
    a.right = &c;
    b.left = nullptr;
    b.right = nullptr;
    c.left = nullptr;
    c.right = nullptr;
    cout << solution.findTilt(&a) << endl;
    return 0;
}