online advertising

Tuesday, December 29, 2015

LeetCode OJ - Bulb Switcher

Problem: 

Please find the problem here.

Solution:

A bulb $ b $ is going to be flipped whenever the current round number $ a $ is a factor of $ b $.
Therefore, a bulb is left on only if it is a perfect square (any other number has even number of factors)

With that, the code is trivial.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/bulb-switcher/

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

using namespace std;

namespace _LEET_BULB_SWITCHER
{
    /*
     * Analysis:
     * For the general mth bulb, it is toggled in the nth round if n is a factor of m
     * For example, the 3 bulb is on after round 1 and off after round 3 and will never turn on again (no matter what n is)
     * That applies for all prime
     * That actually also apply for all composite with even number of factors
     * What number has odd number of factors? Squares
     * So it is really just asking how many squares are there
     */
    class Solution {
    public:
        int bulbSwitch(int n)
        {
            int count = 0;
            int k = 3;
            int s = 1;
            while (n >= s)
            {
                count++;
                s += k;
                k += 2;
            }

            return count;
        }
    };
};

using namespace _LEET_BULB_SWITCHER;

int LEET_BULB_SWITCHER()
{
    Solution solution;
    for (int i = 1; i <= 10; i++)
    {
        cout << solution.bulbSwitch(i) << endl;
    }
    return 0;
}

Friday, December 4, 2015

LeetCode OJ - Game of Life

Problem: 

Please find the problem here.

Solution:

This is a relatively trivial programming exercise except we need to do it in-place. Technically, it isn't really in-place, it is just to leverage we used more spaces in the input representation than it would have to.

The key idea of the code involve carefully encoding the states.

0 represent it was dead
1 represent it was alive

and this encoding is dictated by the problem statement.

Now I have the freedom to choose the temp states, at minimal I need two temp states,

now_dead_was_live (?)
now_live_was_dead (?)

The encoding should be chosen to maximize computational speed for accessing its old state and new state. There could be multiple ways of doing that, but I chose to do this.

Step 1) Keep the LSB unchanged, so LSB represents old state

Now we can choose the second bit, notice if we do not want to change an array entry if the cell stay the same. then we cannot use the second bit to represent the new state, so we simply set the second bit on when it is changed, so overall, LSB is the old state, and second bit means change or not.

now_dead_was_live 3
now_live_was_dead 2

Last but not least, we need to map (1, 2) -> 1 and also (0, 3) -> 0. At a glance, seems no easy way. Here is the cleverness, if we look at the number + 1, then we find something interesting

0 + 1 -> 1 -> 001 need to map to 0
1 + 1 -> 2 -> 010 need to map to 1
2 + 1 -> 3 -> 011 need to map to 1
3 + 1 -> 4 -> 100 need to map to 0

See, it is simply the second bit of the binary representation, so we saved ourselves from doing conditionals in the mapping process.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/game-of-life/

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

using namespace std;

namespace _LEET_GAME_OF_LIFE
{
    class Solution
    {
    public:
        void gameOfLife(vector<vector<int>>& board)
        {
            // Note the design of the NOW variant
            // the least significant bit indicate the old state, so we just read the LSB for old state
            const int DEAD = 0;
            const int LIVE = 1;
            const int NOW_LIVE_WAS_DEAD = 2;
            const int NOW_DEAD_WAS_LIVE = 3;

            int height = board.size();
            if (height == 0)
            {
                return;
            }
            int width = board[0].size();
            if (width == 0)
            {
                return;
            }
            for (int r = 0; r < height; r++)
            {
                for (int c = 0; c < width; c++)
                {
                    int living_neighbor_count = 0;
                    for (int rd = -1; rd <= 1; rd++)
                    {
                        for (int cd = -1; cd <= 1; cd++)
                        {
                            int nr = r + rd;
                            int nc = c + cd;
                            if (nr >= 0 && nr < height && nc >= 0 && nc < width)
                            {
                                if ((board[nr][nc] & 1) == 1)
                                {
                                    living_neighbor_count++;
                                }
                            }
                        }
                    }
                    if ((board[r][c] & 1) == 1)
                    {
                        // For living cell, we need to discount itself.
                        living_neighbor_count--;
                        if (living_neighbor_count < 2 || living_neighbor_count > 3)
                        {
                            board[r][c] = NOW_DEAD_WAS_LIVE;
                        }
                    }
                    else
                    {
                        if (living_neighbor_count == 3)
                        {
                            board[r][c] = NOW_LIVE_WAS_DEAD;
                        }
                    }
                }
            }
            // Clear temp flags
            for (int r = 0; r < height; r++)
            {
                for (int c = 0; c < width; c++)
                {
                    // Now we need a function that maps
                    // DEAD (0) and NOW_DEAD_WAS_LIVE (3) to 0
                    // LIVE (1) and NOW_LIVE_WAS_DEAD (2) to 1
                    // The problem is easier if we look at the number + 1
                    // 0 + 1 = 1 (001) -> 0
                    // 3 + 1 = 4 (100) -> 0
                    // 1 + 1 = 2 (010) => 1
                    // 2 + 1 = 3 (011) => 1
                    // Note the answer is simply the second bit
                    board[r][c] = ((board[r][c] + 1) & 2) >> 1;
                }
            }
        }
    };
};

using namespace _LEET_GAME_OF_LIFE;

int LEET_GAME_OF_LIFE()
{
    Solution solution;
    vector<vector<int>> board;
    board.resize(3);
    board[0].push_back(1);    board[0].push_back(1); board[0].push_back(0);
    board[1].push_back(1);    board[1].push_back(1); board[1].push_back(0);
    board[2].push_back(1);    board[2].push_back(1); board[2].push_back(0);
    solution.gameOfLife(board);
    cout << board[0][0] << board[0][1] << board[0][2] << endl;
    cout << board[1][0] << board[1][1] << board[1][2] << endl;
    cout << board[2][0] << board[2][1] << board[2][2] << endl;
    return 0;
}

LeetCode OJ - Combinations

Problem: 

Please find the problem here.

Solution:

Building up the combination recursively.

The set of combinations involving [a .. n] of size k can be computed by:

For each number p in [a...n]
Generate all combinations R of size k - 1 in [p + 1 ... n]
Prepend R with p, output all combinations.

First, notice all the combination outputted are generated with size k, which is good.
Second, notice any valid combination will eventually be generated in some execution path.
Finally, the combination outputted can never have duplicates.

All of these statements need to be proved, but I will skip that, it is trivial despite it will involve lots of notations.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/combinations/

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

using namespace std;

namespace _LEET_COMBINATIONS
{
    class Solution
    {
    private:
        void generate_combinations(vector<bool>& used, int start, int k, vector<vector<int>>& result)
        {
            if (k == 0)
            {
                vector<int> found_combination;
                for (unsigned int i = 0; i < used.size(); i++)
                {
                    if (used[i])
                    {
                        found_combination.push_back(i + 1);
                    }
                }
                result.push_back(found_combination);
            }
            else
            {
                for (unsigned int i = start; i < used.size(); i++)
                {
                    if (!used[i])
                    {
                        used[i] = true;
                        generate_combinations(used, i + 1, k - 1, result);
                        used[i] = false;
                    }
                }
            }
        }
    public:
        vector<vector<int>> combine(int n, int k)
        {
            vector<vector<int>> result;
            vector<bool> used;
            used.resize(n);
            for (int i = 0; i < n; i++)
            {
                used[i] = false;
            }
            generate_combinations(used, 0, k, result);
            return result;
        }
    };
};

using namespace _LEET_COMBINATIONS;

int LEET_COMBINATIONS()
{
    Solution solution;
    vector<vector<int>> result = solution.combine(4, 2);
    for (unsigned int i = 0; i < result.size(); i++)
    {
        for (unsigned int j = 0; j < result[i].size(); j++)
        {
            cout << result[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

Tuesday, December 1, 2015

LeetCode OJ - Word Pattern

Problem: 

Please find the problem here.

Solution:

A simple problem, just to be careful with the cases.


  • Too many patterns.
  • Too many tokens in the string.
  • One pattern match multiple tokens
  • One token match multiple patterns

Once the cases are carefully enumerated, the coding of it is rather trivial.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/word-pattern/

#include "LEET_WORD_PATTERN.h"
#include <map>
#include <string>
#include <iostream>

using namespace std;

namespace _LEET_WORD_PATTERN
{
    class Solution
    {
    private:
        bool match(map<char, string>& p_to_s, map<string, char>& s_to_p, char p, string s)
        {
            map<char, string>::iterator p_to_s_probe = p_to_s.find(p);
            map<string, char>::iterator s_to_p_probe = s_to_p.find(s);
            if (p_to_s_probe == p_to_s.end() && s_to_p_probe == s_to_p.end())
            {
                p_to_s.insert(pair<char, string>(p, s));
                s_to_p.insert(pair<string, char>(s, p));
                return true;
            }
            else if(p_to_s_probe != p_to_s.end() && s_to_p_probe != s_to_p.end())
            {
                return (p_to_s_probe->second == s) && (s_to_p_probe->second == p);
            }
            else
            {
                return false;
            }
        }
    public:
        bool wordPattern(string pattern, string str)
        {
            map<char, string> p_to_s;
            map<string, char> s_to_p;
            unsigned int s_i = 0;
            unsigned int p_i = 0;
            for (unsigned int s_e = 0; s_e < str.size(); s_e++)
            {
                if (str[s_e] == ' ')
                {
                    if (p_i < pattern.size())
                    {
                        if (match(p_to_s, s_to_p, pattern[p_i++], str.substr(s_i, s_e - s_i)))
                        {
                            s_i = s_e + 1;
                        }
                        else
                        {
                            return false;
                        }
                    }
                    else
                    {
                        return false;
                    }
                }
            }
            if (p_i < pattern.size())
            {
                if (!match(p_to_s, s_to_p, pattern[p_i++], str.substr(s_i, str.size() - s_i)))
                {
                    return false;
                }
            }
            else
            {
                return false;
            }
            if (p_i != pattern.size())
            {
                return false;
            }
            return true;
        }
    };
};

using namespace _LEET_WORD_PATTERN;

int LEET_WORD_PATTERN()
{
    Solution solution;
    cout << solution.wordPattern("abba", "dog cat cat dog") << endl;
    cout << !solution.wordPattern("abba", "dog cat cat fish") << endl;
    cout << !solution.wordPattern("aaaa", "dog cat cat dog") << endl;
    cout << !solution.wordPattern("abba", "dog dog dog dog") << endl;
    return 0;
}

LeetCode OJ - Populating Next Right Pointers in Each Node II

Problem: 

Please find the problem here.

Solution:

If we are allowed to use more space, then a simple BFS would have solved the problem, the twist in this problem is the requirement to use constant space.

Well, except the space we already occupied already! We have a free linked list to use, the next pointers of the visited nodes, and we have to populate them anyway as output!

Think like induction, layer by layer.

The next of the root is easy, it has to be NULL. The leftmost node on this layer is obviously root.

Now we are trying to build the next pointers of the $ n $ layer, assuming we know the leftmost node of the $ n - 1 $ layer, and that the next pointers are all set correctly there.

Then we just walk the $ n - 1 $ layer from left to right, if we see any child, we just set the child's next pointer correctly, keep track of the first node seen as the leftmost node, and that's it!

By induction we will be able to build the whole tree - a virtual node is conveniently used to reduce the number of cases to deal with when building the next layer nodes.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/

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

using namespace std;

namespace _LEET_POPULATING_NEXT_RIGHT_POINTERS_IN_EACH_NODE_II
{
    struct TreeLinkNode
    {
        int val;
        TreeLinkNode *left, *right, *next;
        TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
    };

    class Solution
    {
    public:
        void connect(TreeLinkNode *root)
        {
            if (root == NULL)
            {
                return;
            }

            root->next = NULL;

            TreeLinkNode virtualNode(10086);
            virtualNode.next = root;

            while (virtualNode.next != NULL)
            {
                TreeLinkNode* currentLayerCursor = virtualNode.next;
                TreeLinkNode* nextLayerEnds = &virtualNode;
                nextLayerEnds->next = NULL;
                while (currentLayerCursor != NULL)
                {
                    if (currentLayerCursor->left != NULL)
                    {
                        nextLayerEnds->next = currentLayerCursor->left;
                        nextLayerEnds = nextLayerEnds->next;
                    }
                    if (currentLayerCursor->right != NULL)
                    {
                        nextLayerEnds->next = currentLayerCursor->right;
                        nextLayerEnds = nextLayerEnds->next;
                    }
                    currentLayerCursor = currentLayerCursor->next;
                }
            }
        }
    };
};

using namespace _LEET_POPULATING_NEXT_RIGHT_POINTERS_IN_EACH_NODE_II;

int LEET_POPULATING_NEXT_RIGHT_POINTERS_IN_EACH_NODE_II()
{
    TreeLinkNode a(1);
    TreeLinkNode b(2);
    TreeLinkNode c(3);
    TreeLinkNode d(4);
    TreeLinkNode e(5);
    TreeLinkNode g(7);
    a.left = &b;
    a.right = &c;
    b.left = &d;
    b.right = &e;
    c.left = NULL;
    c.right = &g;
    d.left = NULL;
    d.right = NULL;
    e.left = NULL;
    e.right = NULL;
    g.left = NULL;
    g.right = NULL;
    Solution solution;
    solution.connect(&a);
    cout << ((a.next == NULL) ? "Yes" : "No") << endl;
    cout << ((b.next == &c) ? "Yes" : "No") << endl;
    cout << ((c.next == NULL) ? "Yes" : "No") << endl;
    cout << ((d.next == &e) ? "Yes" : "No") << endl;
    cout << ((e.next == &g) ? "Yes" : "No") << endl;
    cout << ((g.next == NULL) ? "Yes" : "No") << endl;
    return 0;
}

Monday, November 30, 2015

LeetCode OJ - Basic Calculator II

Problem: 

Please find the problem here.

Solution:

I could have extended the last solution for Basic Calculator to include the multiplication and division, but turn out the judge have a case that stress memory usage, and top down parser are just not good with respect to memory usage, so I hand written a shift reduce parser instead.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/basic-calculator-ii/

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

using namespace std;

namespace _LEET_BASIC_CALCULATOR_II
{
    class Solution
    {
    public:
        // Scanner states
        unsigned int position;
        char token;
        string* expression;

        void scan()
        {
            while (true)
            {
                if (position < (*expression).size())
                {
                    token = (*expression)[position++];
                }
                else
                {
                    token = '\0';
                }
                if (token != ' ')
                {
                    break;
                }
            }
        }

        // A hand written shift-reduce parser!
        // I could have adapted the previous top-down parsing solution
        // But there is a test case in the judge to stress memory usage, and a top down parser necessarily use up the space because of the recursion
        // A shift-reduce parser can save space by reducing early and not using the stack space
        int calculate(string s)
        {
            const int PLUS = 0;
            const int MINUS = 1;
            const int MULTIPLY = 2;
            const int DIVIDE = 3;

            stack<int> numStack;
            stack<int> sigStack;

            position = 0;
            expression = &s;

            const int EXPECT_DIGIT = 0;
            const int EXPECT_DIGIT_OR_OPERATOR = 1;
            int state = EXPECT_DIGIT;

            int currentNumber = 0;
            while (true)
            {
                scan();
                if (token >= '0' && token <= '9')
                {
                    state = EXPECT_DIGIT_OR_OPERATOR;
                    currentNumber = currentNumber * 10 + (token - '0');
                }
                else
                {
                    if (EXPECT_DIGIT)
                    {
                        throw 1;
                    }
                    numStack.push(currentNumber);
                    currentNumber = 0;
                    if (token == '*' || token == '/')
                    {
                        while (sigStack.size() > 0)
                        {
                            if (sigStack.top() >= MULTIPLY)
                            {
                                int operand2 = numStack.top(); numStack.pop();
                                int operand1 = numStack.top(); numStack.pop();
                                if (sigStack.top() == MULTIPLY)
                                {
                                    numStack.push(operand1 * operand2);
                                }
                                else if (sigStack.top() == DIVIDE)
                                {
                                    numStack.push(operand1 / operand2);
                                }
                                sigStack.pop();
                            }
                            else
                            {
                                break;
                            }
                        }

                        if (token == '*')
                        {
                            sigStack.push(MULTIPLY);
                        }
                        else if (token == '/')
                        {
                            sigStack.push(DIVIDE);
                        }

                        state = EXPECT_DIGIT;
                    }
                    else if (token == '+' || token == '-' || token == '\0')
                    {
                        while (sigStack.size() > 0)
                        {

                            int operand2 = numStack.top(); numStack.pop();
                            int operand1 = numStack.top(); numStack.pop();
                            if (sigStack.top() == PLUS)
                            {
                                numStack.push(operand1 + operand2);
                            }
                            else if (sigStack.top() == MINUS)
                            {
                                numStack.push(operand1 - operand2);
                            }
                            else if (sigStack.top() == MULTIPLY)
                            {
                                numStack.push(operand1 * operand2);
                            }
                            else if (sigStack.top() == DIVIDE)
                            {
                                numStack.push(operand1 / operand2);
                            }
                            sigStack.pop();
                        }
                        if (token == '+')
                        {
                            sigStack.push(PLUS);
                        }
                        else if (token == '-')
                        {
                            sigStack.push(MINUS);
                        }
                        else if (token == '\0')
                        {
                            return numStack.top();
                        }

                        state = EXPECT_DIGIT;
                    }
                }
            }

            return 0;
        }
    };
};

using namespace _LEET_BASIC_CALCULATOR_II;

int LEET_BASIC_CALCULATOR_II()
{
    Solution solution;
    cout << (solution.calculate("3+2*2") == 7) << endl;
    cout << (solution.calculate(" 3/2 ") == 1) << endl;
    cout << (solution.calculate(" 3+5 / 2 ") == 5) << endl;
    return 0;
}