online advertising

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;
}

Tuesday, October 10, 2017

LeetCode OJ - Knight Probability in Chessboard

Problem:

Please find the problem here.

Analysis:

With the example, we understand that once is knight is out of the chess board, it cannot enter again. So it is really about making sure we keep track of the probability that the knight is still inside the board. There are only so many cells in the board but many paths, so we will count by the cell, not by the path. It looks very much like a path counting exercise.

Solution:

The code was carefully tuned so that it does not overflow - the number of paths grows very fast, instead of keeping track of the number of paths, we need to constantly reduce it, so we might as well simply keep track of the probability values.

Note that we could be emulated a one step move per cell, and make this a recurrence relation, which we can use the matrix exponentiation solution to reduce the algorithm complexity from $ O(k) $ to $ O(\log k) $, such an optimization would be meaningful if $ k $ is large. Even better, since there is only a limited number of $ k $, we can simply pre-compute all those matrices, if we wished. For simplicity, I skipped those.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/knight-probability-in-chessboard

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

using namespace std;

namespace _LEET_KNIGHT_PROBABILITY_IN_CHESSBOARD
{
    class Solution
    {
    public:
        double knightProbability(int N, int K, int r, int c) {
            double** board_old;
            double** board_new;
            board_old = new double*[N];
            board_new = new double*[N];
            for (int r = 0; r < N; r++)
            {
                board_new[r] = new double[N];
                board_old[r] = new double[N];
                for (int c = 0; c < N; c++)
                {
                    board_old[r][c] = board_new[r][c] = 0;
                }
            }
            double** current = (double**)board_old;
            double** next = (double**)board_new;
            current[r][c] = 1;
            for (int step = 0; step < K; step++)
            {
                for (int r = 0; r < N; r++)
                {
                    for (int c = 0; c < N; c++)
                    {
                        next[r][c] = 0;
                    }
                }

                for (int r = 0; r < N; r++)
                {
                    for (int c = 0; c < N; c++)
                    {
                        if (current[r][c] != 0)
                        {
                            vector<pair<int, int>> candidates;
                            candidates.push_back(make_pair(r + 2, c + 1));
                            candidates.push_back(make_pair(r + 1, c + 2));
                            candidates.push_back(make_pair(r + 2, c - 1));
                            candidates.push_back(make_pair(r + 1, c - 2));
                            candidates.push_back(make_pair(r - 2, c + 1));
                            candidates.push_back(make_pair(r - 1, c + 2));
                            candidates.push_back(make_pair(r - 2, c - 1));
                            candidates.push_back(make_pair(r - 1, c - 2));
                            for (auto&& candidate : candidates)
                            {
                                int pr = candidate.first;
                                int pc = candidate.second;
                                if (0 <= pr && pr < N && 0 <= pc && pc < N)
                                {
                                    next[pr][pc] += current[r][c] / 8.0;
                                }
                            }
                        }
                    }
                }

                swap(current, next);
            }
            double count = 0;
            for (int r = 0; r < N; r++)
            {
                for (int c = 0; c < N; c++)
                {
                    count += current[r][c];
                }
            }
            return count;
        }
    };
};

using namespace _LEET_KNIGHT_PROBABILITY_IN_CHESSBOARD;

int LEET_KNIGHT_PROBABILITY_IN_CHESSBOARD()
{
    Solution s;
    cout << s.knightProbability(3, 2, 0, 0) << endl;
    return 0;
}