online advertising

Tuesday, July 28, 2015

LeetCode OJ - Search a 2D Matrix II

Problem:

Please find the problem here.

Solution:

The trivial answer is to do binary search per row/column, and it is in fact the most efficient algorithm when the larger dimension is big.

In this problem I challenge myself to find the $ O(m + n) $ algorithm. The key insight for this solution is that after we testing the upper right corner, either the top row or the rightmost column can be excluded.

I thought about the same direction - but never actually get the key idea. The idea is what I grok from a forum post. Thanks xianrenb.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/search-a-2d-matrix-ii/

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

using namespace std;

namespace _LEET_SEARCH_A_2D_MATRIX_II
{
    class Solution
    {
    public:
        bool searchMatrix(vector<vector<int>>& matrix, int target)
        {
            unsigned int matrix_height = matrix.size();

            if (matrix_height == 0)
            {
                // There is no element in the matrix
                return false;
            }

            unsigned int matrix_width = matrix[0].size();

            int x1 = 0;
            int y1 = 0;
            int x2 = matrix_width - 1;
            int y2 = matrix_height - 1;

            while (true)
            {
                if (x2 < x1)
                {
                    return false;
                }
                if (y2 < y1)
                {
                    return false;
                }
                if (target < matrix[y1][x1])
                {
                    return false;
                }
                else if (target > matrix[y2][x2])
                {
                    return false;
                }
                else
                {
                    int corner = matrix[y1][x2];
                    if (target == corner)
                    {
                        return true;
                    }
                    else if (target < corner)
                    {
                        x2--;
                    }
                    else
                    {
                        y1++;
                    }
                }
            }
        }
    };
};

using namespace _LEET_SEARCH_A_2D_MATRIX_II;

int LEET_SEARCH_A_2D_MATRIX_II()
{
    Solution solution;
    vector<vector<int>> matrix;
    int row1[] = { 1, 4, 7, 11, 15 };
    int row2[] = { 2, 5, 8, 12, 19 };
    int row3[] = { 3, 6, 9, 16, 22 };
    int row4[] = { 10, 13, 14, 17, 24 };
    int row5[] = { 18, 21, 23, 26, 30 };
    matrix.push_back(vector<int>(row1, row1 + _countof(row1)));
    matrix.push_back(vector<int>(row2, row2 + _countof(row2)));
    matrix.push_back(vector<int>(row3, row3 + _countof(row3)));
    matrix.push_back(vector<int>(row4, row4 + _countof(row4)));
    matrix.push_back(vector<int>(row5, row5 + _countof(row5)));
    cout << (solution.searchMatrix(matrix, 5) == true) << endl;
    cout << (solution.searchMatrix(matrix, 20) == false) << endl;
    return 0;
}


Tuesday, July 21, 2015

LeetCode OJ - Rectangle Area

Problem:

Please find the problem here.

Solution:

This is a tricky problem, if not properly think through, it is really easy to fall trap into many of the cases that might arise.

The key idea of solving this problem is that


  1. Two line segments, if intersect at all, intersect as a line segment.
  2. We can compute the x-intersection and y-intersection separately.
  3. A line sweep can be used to compute the 1 dimensional line segment intersection problem.
Without using the sort in the intersection routine, the cases can grow like crazy. 4! = 24 cases. The sorting is what make things easy!


Code:

#include "stdafx.h"

// https://leetcode.com/problems/rectangle-area/

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

using namespace std;

namespace _LEET_RECTANGLE_AREA
{
    class Solution
    {
    private:
        // Do a simple line sweep
        int intersection_length(int p1, int p2, int q1, int q2)
        {
            // Step 1: Sorting
            int coord[4] = { p1, p2, q1, q2 };
            int event[4] = { 1, 1, 2, 2};
            for (int i = 0; i < 4; i++)
            {
                for (int j = i + 1; j < 4; j++)
                {
                    if (coord[j] < coord[i])
                    {
                        swap(coord[j], coord[i]);
                        swap(event[j], event[i]);
                    }
                }
            }
            bool inOne = false;
            bool inTwo = false;
            bool hasIntersection = false;
            int start = 0;
            int end = 0;
            for (int i = 0; i < 4; i++)
            {
                if (event[i] == 1) { inOne = !inOne; }
                if (event[i] == 2) { inTwo = !inTwo; }
                if (inOne && inTwo)
                {
                    hasIntersection = true;
                    start = coord[i];
                }
                else if (hasIntersection)
                {
                    end = coord[i];
                    break;
                }
            }
            if (hasIntersection)
            {
                return end - start;
            }
            else
            {
                return 0;
            }
        }

    public:
        int computeArea(int A, int B, int C, int D, int E, int F, int G, int H)
        {
            int x_intersection = this->intersection_length(A, C, E, G);
            int y_intersection = this->intersection_length(B, D, F, H);
            int rect1_size = (C - A) * (D - B);
            int rect2_size = (G - E) * (H - F);
            int intersect_size = x_intersection * y_intersection;

            return rect1_size + rect2_size - intersect_size;
        }
    };
};

using namespace _LEET_RECTANGLE_AREA;

int LEET_RECTANGLE_AREA()
{
    Solution solution;
    cout << solution.computeArea(-3,0,3,4,0,-1,9,2) << endl;
    return 0;
}


Monday, July 20, 2015

LeetCode OJ - Remove Nth Node From End of List

Problem:

Please find the problem here.

Solution:

A rather trivial problem if we are to do this in two passes. The key to be able to do it in a single pass is to use the recursion rewind stack (I think I could do that with link inversion too, that gives constant space as well)

Code:

#include "stdafx.h"

// https://leetcode.com/problems/remove-nth-node-from-end-of-list/

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

using namespace std;

namespace _LEET_REMOVE_NTH_NODE_FROM_END_OF_LIST
{
    struct ListNode
    {
        int val;
        ListNode *next;
        ListNode(int x) : val(x), next(NULL) {}
    };

    class Solution
    {
    private:
        ListNode* removeNthFromEnd(ListNode* head, int n, int count, int& length)
        {
            if (head == NULL)
            {
                length = count;
            }
            else
            {
                head->next = removeNthFromEnd(head->next, n, count + 1, length);
            }

            if (count == length - n)
            {
                return head->next;
            }
            else
            {
                return head;
            }
        }
    public:
        ListNode* removeNthFromEnd(ListNode* head, int n)
        {
            int length = -1;
            return this->removeNthFromEnd(head, n, 0, length);
        }
    };
};

using namespace _LEET_REMOVE_NTH_NODE_FROM_END_OF_LIST;

int LEET_REMOVE_NTH_NODE_FROM_END_OF_LIST()
{
    Solution solution;
    ListNode a(1);
    ListNode b(2);
    ListNode c(3);
    ListNode d(4);
    ListNode e(5);
    a.next = &b;
    b.next = &c;
    c.next = &d;
    d.next = &e;
    ListNode* cursor = solution.removeNthFromEnd(&a, 2);
    while (cursor != NULL)
    {
        cout << cursor->val << ",";
        cursor = cursor->next;
    }
    cout << endl;
    return 0;
}

Sunday, July 19, 2015

LeetCode OJ - Summary Ranges

Problem:

Please find the problem here.

Solution:

Check forward, if the next integer is continuous, move on, output as appropriate.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/summary-ranges/

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

using namespace std;

namespace _LEET_SUMMARY_RANGES
{
    class Solution {
    private:
        void summaryRanges(vector<int>& nums, unsigned int i, vector<string>& append_to)
        {
            while (i < nums.size())
            {
                ostringstream os;
                unsigned int j = i;
                while (j < nums.size() - 1 && (nums[j + 1] == nums[j] + 1))
                {
                    j++;
                }
                if (i == j)
                {
                    os << nums[i];
                }
                else
                {
                    os << nums[i] << "->" << nums[j];
                }
                append_to.push_back(os.str());
                i = j + 1;
            }
        }
    public:
        vector<string> summaryRanges(vector<int>& nums)
        {
            vector<string> result;
            summaryRanges(nums, 0, result);
            return result;
        }
    };
};

using namespace _LEET_SUMMARY_RANGES;

int LEET_SUMMARY_RANGES()
{
    Solution solution;
    int case1[] = {0,1,2,4,5,7};
    vector<string> case1_solution = solution.summaryRanges(vector<int>(case1, case1 + _countof(case1)));
    for (unsigned int i = 0; i < case1_solution.size(); i++)
    {
        cout << case1_solution[i] << ",";
    }
    cout << endl;
    return 0;
}

LeetCode OJ - Remove Duplicates from Sorted List

Problem:

Please find the problem here.

Solution:

Check forward, if the next one is a duplicate delete it, otherwise move forward.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/remove-duplicates-from-sorted-list/

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

using namespace std;

namespace _LEET_REMOVE_DUPLICATES_FROM_SORTED_LIST
{
    struct ListNode
    {
        int val;
        ListNode *next;
        ListNode(int x) : val(x), next(NULL) {}
    };
    
    class Solution
    {
    public:
        ListNode* deleteDuplicates(ListNode* head)
        {
            ListNode* cursor = head;
            while (cursor != NULL)
            {
                if (cursor->next != NULL && cursor->next->val == cursor->val)
                {
                    cursor->next = cursor->next->next;
                }
                else
                {
                    cursor = cursor->next;
                }
            }
            return head;
        }
    };
};

using namespace _LEET_REMOVE_DUPLICATES_FROM_SORTED_LIST;

int LEET_REMOVE_DUPLICATES_FROM_SORTED_LIST()
{
    ListNode a(1);
    ListNode b(1);
    ListNode c(2);
    ListNode d(2);
    ListNode e(3);
    a.next = &b;
    b.next = &c;
    c.next = &d;
    d.next = &e;
    Solution s;
    ListNode* soln = s.deleteDuplicates(&a);
    while (soln != NULL)
    {
        cout << soln->val << ",";
        soln = soln->next;
    }
    cout << endl;
    return 0;
}

LeetCode OJ - Add and Search Word - Data structure design

Problem:

Please find the problem here.

Solution:

Build a compressed trie and use DFS for the search in case of wild card at a node.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/add-and-search-word-data-structure-design/

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

using namespace std;

namespace _LEET_ADD_AND_SEARCH_WORD
{
    class WordDictionary 
    {
    private:
        class WordDictionaryNode
        {
        public:
            ~WordDictionaryNode()
            {
                for (map<char, WordDictionaryNode*>::iterator ci = this->children.begin(); ci != this->children.end(); ci++)
                {
                    delete ci->second;
                }
            }
            string label;
            map<char, WordDictionaryNode*> children;
        };
        WordDictionaryNode root;

        bool search_start(string& word, unsigned int i, WordDictionaryNode* current);
        bool search_child(string& word, unsigned int i, WordDictionaryNode* current);
    public:
        // Adds a word into the data structure.
        void addWord(string word)
        {
            word = word + '\0';
            int wordLength = word.length();
            WordDictionaryNode* current = &root;
            unsigned int i = 0;
            while (true)
            {
                map<char, WordDictionaryNode*>::iterator probe = current->children.find(word[i]);
                if (probe == current->children.end())
                {
                    WordDictionaryNode* newNode = new WordDictionaryNode();
                    current->children.insert(pair<char, WordDictionaryNode*>(word[i], newNode));
                    newNode->label = word.substr(i);
                    break;
                }
                else
                {
                    current = probe->second;
                    unsigned int j = 0;
                    for (;j < current->label.length() && i < word.length(); i++, j++)
                    {
                        if (word[i] != current->label[j])
                        {
                            break;
                        }
                    }
                    if (j != current->label.length())
                    {
                        // Split a node
                        string prefix = current->label.substr(0, j);
                        string old_suffix = current->label.substr(j);
                        string new_suffix = word.substr(i);

                        WordDictionaryNode* old_node = new WordDictionaryNode();
                        WordDictionaryNode* new_node = new WordDictionaryNode();

                        old_node->label = old_suffix;
                        new_node->label = new_suffix;
                        current->label = prefix;

                        for (map<char, WordDictionaryNode*>::iterator ci = current->children.begin(); ci != current->children.end(); ci++)
                        {
                            old_node->children.insert(*ci);
                        }
                        current->children.clear();
                        current->children.insert(pair<char, WordDictionaryNode*>(old_suffix[0], old_node));
                        current->children.insert(pair<char, WordDictionaryNode*>(new_suffix[0], new_node));
                        break;
                    }
                }
            }
        }

        // Returns if the word is in the data structure. A word could
        // contain the dot character '.' to represent any one letter.
        bool search(string word)
        {
            word = word + '\0';
            return search_child(word, 0, &root);
        }
    };

    bool WordDictionary::search_start(string& word, unsigned int i, WordDictionary::WordDictionaryNode* current)
    {
        for (unsigned int j = 0; i < word.length() && j < current->label.length(); i++, j++)
        {
            if (word[i] != '.' && word[i] != current->label[j])
            {
                return false;
            }
        }

        return search_child(word, i, current);
    }

    bool WordDictionary::search_child(string& word, unsigned int i, WordDictionary::WordDictionaryNode* current)
    {
        if (i == word.length())
        {
            return true;
        }

        if (word[i] == '.')
        {
            for (map<char, WordDictionary::WordDictionaryNode*>::iterator ci = current->children.begin(); ci != current->children.end(); ci++)
            {
                if (search_start(word, i, ci->second))
                {
                    return true;
                }
            }

            return false;
        }
        else
        {
            map<char, WordDictionary::WordDictionaryNode*>::iterator probe = current->children.find(word[i]);
            if (probe == current->children.end())
            {
                return false;
            }
            else
            {
                return search_start(word, i, probe->second);
            }
        }
    }
};

using namespace _LEET_ADD_AND_SEARCH_WORD;

int LEET_ADD_AND_SEARCH_WORD()
{
    WordDictionary dict;
    dict.addWord("bad");
    dict.addWord("dad");
    dict.addWord("mad");
    cout << (dict.search("pad") == 0) << endl;
    cout << (dict.search("bad") == 1) << endl;
    cout << (dict.search(".ad") == 1) << endl;
    cout << (dict.search("b..") == 1) << endl;
    return 0;
}