online advertising

Thursday, December 7, 2017

LeetCode OJ - Sentence Similarity

Problem:

Please find the problem here.

Solution:

Because the relationship is not transitive, I cannot map them both into a single canonical representation. Therefore I simply iterate the map and try to map both and see if one and be mapped to another.

I could have index the pairs to avoid the inner loop, but turn out the mapping could be one to many, which means I need an unordered_map to and unordered_set. It is doable, I am just lazy since this work good enough.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/sentence-similarity

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

using namespace std;

namespace _LEET_SENTENCE_SIMILARITY
{
    class Solution
    {
    public:
        bool areSentencesSimilar(vector<string>& words1, vector<string>& words2, vector<pair<string, string>> pairs)
        {
            if (words1.size() != words2.size())
            {
                return false;
            }

            for (int i = 0; i < words1.size(); i++)
            {
                string& word1 = words1[i];
                string& word2 = words2[i];
                if (word1 == word2)
                {
                    continue;
                }
                bool found = false;
                for (int j = 0; j < pairs.size(); j++)
                {
                    if (pairs[j].first == word1 && pairs[j].second == word2)
                    {
                        found = true;
                        break;
                    }
                    if (pairs[j].first == word2 && pairs[j].second == word1)
                    {
                        found = true;
                        break;
                    }
                }
                if (!found)
                {
                    return false;
                }
            }
            return true;
        }
    };
};

using namespace _LEET_SENTENCE_SIMILARITY;

int LEET_SENTENCE_SIMILARITY()
{
    Solution s;
    vector<string> words1;
    words1.push_back("great");
    words1.push_back("acting");
    words1.push_back("skills");
    vector<string> words2;
    words2.push_back("fine");
    words2.push_back("drama");
    words2.push_back("talent");
    vector<pair<string, string>> pairs;
    pairs.push_back(make_pair("great", "fine"));
    pairs.push_back(make_pair("drama", "acting"));
    pairs.push_back(make_pair("skills", "talent"));
    cout << s.areSentencesSimilar(words1, words2, pairs) << endl;
    return 0;
}

Wednesday, November 29, 2017

LeetCode OJ - Split Linked List in Parts

Problem:

Please find the problem here.

Solution:

It is simple math, for the first $ n \mod k $ lists, there is one more item, otherwise we have $ \left\lfloor \frac{n}{k} \right\rfloor $ items.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/split-linked-list-in-parts

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

using namespace std;

namespace _LEET_SPLIT_LINKED_LIST_IN_PARTS
{
    struct ListNode
    {
        int val;
        ListNode *next;
        ListNode(int x) : val(x), next(NULL) {}
    };
    class Solution {
    public:
        vector<ListNode*> splitListToParts(ListNode* root, int k)
        {
            int size = 0;
            ListNode* cur = root;
            ListNode* prev = nullptr;
            while (cur != NULL)
            {
                size++;
                cur = cur->next;
            }
            int part_size = size / k;
            int part_excess = size % k;
            vector<ListNode*> result;
            result.resize(k);
            cur = root;
            for (int i = 0; i < k; i++)
            {
                result[i] = cur;
                for (int j = 0; j < part_size; j++)
                {
                    if (cur != nullptr)
                    {
                        prev = cur;
                        cur = cur->next;
                    }
                }
                if (part_excess > 0)
                {
                    if (cur != nullptr)
                    {
                        prev = cur;
                        cur = cur->next;
                    }
                    part_excess = part_excess - 1;
                }
                if (prev != nullptr)
                {
                    prev->next = nullptr;
                }
            }
            return result;
        }
    };
};

using namespace _LEET_SPLIT_LINKED_LIST_IN_PARTS;

int LEET_SPLIT_LINKED_LIST_IN_PARTS()
{
    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;
    Solution s;
    vector<ListNode*> result = s.splitListToParts(&a, 3);
    for (ListNode* r : result)
    {
        ListNode* u = r;
        while (u != nullptr)
        {
            cout << u->val << " -> ";
            u = u->next;
        }
        cout << "nullptr" << endl;
    }
    return 0;
}

Saturday, October 14, 2017

LeetCode OJ - Binary Number with Alternating Bits

Problem:

Please find the problem here.

Solution:

This one is easy, there are only so many numbers with alternating bits, just list them all.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/binary-number-with-alternating-bits

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

using namespace std;

namespace _LEET_BINARY_NUMBER_WITH_ALTERNATING_BITS
{
    class Solution
    {
    public:
        bool hasAlternatingBits(int n)
        {
            switch (n)
            {
            case 0x00:
            case 0x01:
            case 0x02:
            case 0x05:
            case 0x0A:
            case 0x15:
            case 0x2A:
            case 0x55:
            case 0xAA:
            case 0x155:
            case 0x2AA:
            case 0x555:
            case 0xAAA:
            case 0x1555:
            case 0x2AAA:
            case 0x5555:
            case 0xAAAA:
            case 0x15555:
            case 0x2AAAA:
            case 0x55555:
            case 0xAAAAA:
            case 0x155555:
            case 0x2AAAAA:
            case 0x555555:
            case 0xAAAAAA:
            case 0x1555555:
            case 0x2AAAAAA:
            case 0x5555555:
            case 0xAAAAAAA:
            case 0x15555555:
            case 0x2AAAAAAA:
            case 0x55555555:
            case 0xAAAAAAAA:
                return true;
            default:
                return false;
            }
        }
    };
};

using namespace _LEET_BINARY_NUMBER_WITH_ALTERNATING_BITS;

int LEET_BINARY_NUMBER_WITH_ALTERNATING_BITS()
{
    Solution solution;
    cout << solution.hasAlternatingBits(5) << endl;
    return 0;
}

LeetCode OJ - Valid Parenthesis String

Problem:

Please find the problem here.

Analysis:

Without the star character, the problem can be solved simply by maintaining a counter represents the amount of open parenthesis. We require that it never go below zero and it reach zero at the end. With star, we do not know what to do with the counter.

Solution:

What we could do, instead of maintaining the counter value, maintain an upper bound and a lower bound on the possible values of the counter. We need to make sure the upper bound never goes below zero, if it does, the string cannot possibly be valid. We need to make sure the lower bound never goes below zero, and the range contains 0 at the end of the string.

Maintaining the bounds take only $ O(1) $ time per character, so overall it is an $ O(n) $ algorithm.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/valid-parenthesis-string

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

using namespace std;

namespace _LEET_VALID_PARENTHESIS_STRING
{
    class Solution
    {
    public:
        bool checkValidString(string s)
        {
            int u = 0;
            int l = 0;
            for (int i = 0; i < s.length(); i++)
            {
                char c = s[i];
                switch (c)
                {
                case '(':
                    u++;
                    l++;
                    break;
                case ')':
                    u--;
                    l--;
                    if (u < 0) { return false; }
                    if (l < 0) { l = 0; }
                    break;
                case '*':
                    u++;
                    l--;
                    if (l < 0) { l = 0; }
                    break;
                }
            }
            return u >= 0 && l <= 0;
        }
    };
};

using namespace _LEET_VALID_PARENTHESIS_STRING;

int LEET_VALID_PARENTHESIS_STRING()
{
    Solution solution;
    cout << solution.checkValidString("()") << endl;
    cout << solution.checkValidString("(*)") << endl;
    cout << solution.checkValidString("((*)") << endl;
    return 0;
}

LeetCode OJ - Max Area of Island

Problem:

Please find the problem here.

Solution:

We simply do a BFS on the graph and return the best tree size. As an optimization, instead of using a separate set to mark if the node is visited, we set the grid entry to be -1 instead.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/max-area-of-island

#include "LEET_MAX_AREA_OF_ISLAND.h"
#include <iostream>
#include <queue>
#include <map>
#include <string>

using namespace std;

namespace _LEET_MAX_AREA_OF_ISLAND
{
    class Solution
    {
    public:
        int maxAreaOfIsland(vector<vector<int>>& grid)
        {
            if (grid.size() == 0)
            {
                return 0;
            }
            int height = grid.size();
            int width = grid[0].size();
            int max_size = 0;
            for (int row = 0; row < height; row++)
            {
                if (grid[row].size() != width)
                {
                    throw 1;
                }
                for (int col = 0; col < width; col++)
                {
                    if (grid[row][col] == 1)
                    {
                        int size = 0;
                        queue<pair<int, int>> bfs;
                        bfs.push(make_pair(row, col));
                        grid[row][col] = -1;
                        while (bfs.size() > 0)
                        {
                            auto current = bfs.front();
                            int current_row = current.first;
                            int current_col = current.second;

                            size++;
                            bfs.pop();
                            if (current_row + 1 < height && grid[current_row + 1][current_col] == 1)
                            {
                                bfs.push(make_pair(current_row + 1, current_col));
                                grid[current_row + 1][current_col] = -1;
                            }
                            if (current_col + 1 < width && grid[current_row][current_col + 1] == 1)
                            {
                                bfs.push(make_pair(current_row, current_col + 1));
                                grid[current_row][current_col + 1] = -1;
                            }
                            if (current_row - 1 >= 0 && grid[current_row - 1][current_col] == 1)
                            {
                                bfs.push(make_pair(current_row - 1, current_col));
                                grid[current_row - 1][current_col] = -1;
                            }
                            if (current_col - 1 >= 0 && grid[current_row][current_col - 1] == 1)
                            {
                                bfs.push(make_pair(current_row, current_col - 1));
                                grid[current_row][current_col - 1] = -1;
                            }
                        }
                        max_size = max(size, max_size);
                    }
                }
            }
            return max_size;
        }
    };
};

using namespace _LEET_MAX_AREA_OF_ISLAND;

int LEET_MAX_AREA_OF_ISLAND()
{
    Solution solution;
    int row0[] = { 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0 };
    int row1[] = { 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0 };
    int row2[] = { 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0 };
    int row3[] = { 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0 };
    int row4[] = { 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0 };
    int row5[] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0 };
    int row6[] = { 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0 };
    int row7[] = { 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0 };
    vector<vector<int>> grid;
    grid.push_back(vector<int>(row0, row0 + _countof(row0)));
    grid.push_back(vector<int>(row1, row1 + _countof(row1)));
    grid.push_back(vector<int>(row2, row2 + _countof(row2)));
    grid.push_back(vector<int>(row3, row3 + _countof(row3)));
    grid.push_back(vector<int>(row4, row4 + _countof(row4)));
    grid.push_back(vector<int>(row5, row5 + _countof(row5)));
    grid.push_back(vector<int>(row6, row6 + _countof(row6)));
    grid.push_back(vector<int>(row7, row7 + _countof(row7)));
    cout << solution.maxAreaOfIsland(grid) << endl;
    return 0;
}

LeetCode OJ - Redundant Connection

Problem:

Please find the problem here.

Analysis:

A tree with an extra edge is guaranteed to have a cycle. Both BFS and DFS can detect the cycle, but DFS can be used to find the cycle as well as detecting the cycle, so I used DFS.

Solution:

I started with building an adjacency list so that each edge is associated with its edge index. I modified the standard DFS algorithm such that instead of returning nothing, each recursive call return a pair of integers (x, y) interpreted as follow:

If x == -1, it means we do not find a back edge in the sub-tree, otherwise it means we have already find the back-edge in the sub-tree.
If x != -1 and y == -1, it means the sub-tree contains the cycle and x is the best edge already.
If x != -1 and y != -1, it means that y is the beginning of the cycle, and x is the best edge so far considering all the downward edges as well as the back edge.

The algorithm is pretty simple, I just optimized it so that it use a compact encoding.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/redundant-connection

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

using namespace std;

namespace _LEET_REDUNDANT_CONNECTION
{
    class Solution
    {
    public:
        void add_edge(map<int, map<int, int>>& adjacency_list, int from, int to, int edge_index)
        {
            auto probe = adjacency_list.find(from);
            if (probe == adjacency_list.end())
            {
                adjacency_list.insert(make_pair(from, map<int, int>()));
            }
            adjacency_list[from].insert(make_pair(to, edge_index));
        }

        // best_edge_so_far, bad_node
        pair<int, int> findRedundantConnection(int edge, int parent, int current, map<int, map<int, int>>& adjacency_list, map<int, int>& associated_edge)
        {
            associated_edge[current] = edge;
            for (auto&& neighbor_node_edge_pair : adjacency_list[current])
            {
                int neighbor = neighbor_node_edge_pair.first;
                if (neighbor != parent)
                {
                    int edge = neighbor_node_edge_pair.second;
                    auto check = associated_edge.find(neighbor);
                    if (check == associated_edge.end())
                    {
                        pair<int, int> result = findRedundantConnection(edge, current, neighbor, adjacency_list, associated_edge);
                        int best_edge_so_far = result.first;
                        int bad_node = result.second;
                        if (best_edge_so_far != -1)
                        {
                            if (bad_node == -1)
                            {
                                return make_pair(best_edge_so_far, bad_node);
                            }
                            else if (neighbor == bad_node)
                            {
                                return make_pair(best_edge_so_far, -1);
                            }
                            else
                            {
                                return make_pair(max(edge, best_edge_so_far), bad_node);
                            }
                        }
                    }
                    else
                    {
                        return make_pair(edge, neighbor);
                    }
                }
            }
            return make_pair(-1, 0);
        }

        vector<int> findRedundantConnection(vector<vector<int>>& edges)
        {
            map<int, map<int, int>> adjacency_list;

            for (size_t i = 0; i < edges.size(); i++)
            {
                add_edge(adjacency_list, edges[i][0], edges[i][1], i);
                add_edge(adjacency_list, edges[i][1], edges[i][0], i);
            }

            map<int, int> associated_edge;
            return edges[findRedundantConnection(-1, 0, 1, adjacency_list, associated_edge).first];
        }
    };
};

using namespace _LEET_REDUNDANT_CONNECTION;

int LEET_REDUNDANT_CONNECTION()
{
    Solution solution;
    vector<vector<int>> graph;
    graph.resize(10);
    for (int i = 0; i < 10; i++)
    {
        graph[i].resize(2);
    }
    // [[2,7],[7,8],[3,6],[2,5],[6,8],[4,8],[2,8],[1,8],[7,10],[3,9]]
    graph[0][0] = 2;    graph[0][1] = 7;
    graph[1][0] = 7;    graph[1][1] = 8;
    graph[2][0] = 3;    graph[2][1] = 6;
    graph[3][0] = 2;    graph[3][1] = 5;
    graph[4][0] = 6;    graph[4][1] = 8;
    graph[5][0] = 4;    graph[5][1] = 8;
    graph[6][0] = 2;    graph[6][1] = 8;
    graph[7][0] = 1;    graph[7][1] = 8;
    graph[8][0] = 7;    graph[8][1] = 10;
    graph[9][0] = 3;    graph[9][1] = 9;
    
    vector<int> answer = solution.findRedundantConnection(graph);
    cout << answer[0] << "," << answer[1] << endl;
    return 0;
}