online advertising

Monday, August 31, 2015

LeetCode OJ - Sqrt(x)

Problem:

Please find the problem here.

Solution:

Let's solve the problem using Newton's method, a fairly standard solution.

Newton's method can be used to find zero of functions.


The function is $ f(y) = y^2 - x = 0 $, the function has a zero at $ \sqrt{x} $ and $ -\sqrt{x} $, we will ignore the negative one.


The Newton's iteration is based on an initial estimate of the root, and then iterate as follow:

$ \begin{eqnarray*} x_{n+1} &=& x_n - \frac{f(x_n)}{f'(x_n)} \\ &=& x_n - \frac{x_n^2 - x}{2x_n} \\ &=& x_n - \frac{x_n^2}{2x_n} + \frac{x}{2x_n} \\ &=& x_n - \frac{x_n}{2} + \frac{x}{2x_n} \\ &=& \frac{x_n}{2} + \frac{x}{2x_n} \\ &=& \frac{x_n + \frac{x}{x_n}}{2} \\ \end{eqnarray*} $

Therefore, we can simply implement the equation, but when do we stop?

By doing a simple experiment with the largest possible integer, it takes around 13 iterations to converge to the answer. To play safe, I just run 20 iterations.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/sqrtx/

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

using namespace std;

namespace _LEET_SQRTX
{
    class Solution
    {
    public:
        
        int mySqrt(int x)
        {
            if (x == 0)
            {
                return 0;
            }
            else if (x < 0)
            {
                throw 1;
            }
            double estimate = 1;
            for (int i = 0; i < 20; i++)
            {
                estimate = (estimate + x / estimate) / 2;
            }
            return (int)estimate;
        }
    };
};

using namespace _LEET_SQRTX;

int LEET_SQRTX()
{
    Solution s;
    cout << s.mySqrt(289) << endl;
    return 0;
}

Thursday, August 27, 2015

LeetCode OJ - Divide Two Integers

Problem:

Please find the problem here.

Solution:

This is more complicated than I thought.

At the heart of the algorithm is grade school division, but do it in binary.

The great thing about binary is that the quotient is either one or zero, so when you shift to the point where you can divide, that's what we will need.

The algorithm is not optimal in two sense.

  • It uses 64 bit arithmetic to circumvent issue with overflows, and
  • It always shift from 1, resulting in a lot of repeated shifts.

Anyway, the performance isn't bad at all, so let's just live with that.

One funny fact I learnt in this programming exercise is that division can lead to overflow, in particular.

$ \frac{2^{-32}}{-1} = 2^{32} $ cannot be represented as a signed int32.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/divide-two-integers/

#include "LEET_DIVIDE_TWO_INTEGERS.h"
#include <map>
#include <iostream>
#include <vector>

using namespace std;

namespace _LEET_DIVIDE_TWO_INTEGERS
{
    typedef long long int64;

    class Solution {
    public:
        int64 divideHelper(int64 dividend, int64 divisor)
        {
            if (dividend < divisor)
            {
                // dividend is the remainder, if wished
                return 0;
            }
            else
            {
                int64 subtractor = divisor;
                int64 quotient = 1;
                while ((subtractor << 1) > 0 && dividend >(subtractor << 1))
                {
                    subtractor = (subtractor << 1);
                    quotient = (quotient << 1);
                }

                // At this point, we know dividend < divisor * 2
                // But in the previous iteration, we have dividend > (divisor / 2) * 2 
                // Overall, we have  divisor <= dividend < divisor * 2
                return quotient + divideHelper(dividend - subtractor, divisor);
            }
        }

        int divide(int dividend, int divisor)
        {
            int64 dividendLong = dividend;
            int64 divisorLong = divisor;

            int sign = 1;
            if (dividendLong < 0)
            { 
                sign = -sign;
                dividendLong = -dividendLong;
            }
            if (divisorLong < 0)
            {
                sign = -sign;
                divisorLong = -divisorLong;
            }
            int64 result = sign * this->divideHelper(dividendLong, divisorLong);

            int64 intMax64 = 1;
            intMax64 = intMax64 << 31;
            intMax64--;
            int intMax = (int)intMax64;

            int64 intMin64 = 1;
            intMin64 = intMin64 << 31;
            intMin64 = -intMin64;
            int intMin = (int)intMin64;

            if (result > 0)
            {
                if (result > intMax64)
                {
                    return intMax;
                }
                else
                {
                    return (int)result;
                }
            }
            else
            {
                if (result < intMin64)
                {
                    return intMin;
                }
                else
                {
                    return (int)result;
                }
            }
        }
    };
};

using namespace _LEET_DIVIDE_TWO_INTEGERS;

int LEET_DIVIDE_TWO_INTEGERS()
{
    Solution s;
    cout << s.divide(2147483647, 1) << endl;
    cout << s.divide(2147483647, 2) << endl;
    cout << s.divide(-1010369383, (1 << 31)) << endl;
    cout << s.divide((1 << 31), -1) << endl;
    return 0;
}

Monday, August 24, 2015

LeetCode OJ - Missing Number

Problem:

Please find the problem here.

Solution:

Classic interview question. Just compare the sum and the expected sum for all numbers would solve the problem. To generalize it, any group would work just as well (e.g. xor), it is just harder to compute the expected value, but with the advantage that we can forget about overflows.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/missing-number/

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

using namespace std;

namespace _LEET_MISSING_NUMBER
{
    class Solution
    {
    public:
        int missingNumber(vector<int>& nums)
        {
            int expected_sum = (nums.size()) * (nums.size() + 1 ) / 2;
            int actual_sum = 0;
            for (int i = 0; i < nums.size(); i++)
            {
                actual_sum += nums[i];
            }
            return expected_sum - actual_sum;
        }
    };
};

using namespace _LEET_MISSING_NUMBER;

int LEET_MISSING_NUMBER()
{
    Solution solution;
    int case1[] = { 0, 1, 3 };
    cout << (solution.missingNumber(vector<int>(case1, case1 + _countof(case1))) == 2) << endl;
    return 0;
}

Sunday, August 23, 2015

LeetCode OJ - Compare Version Numbers

Problem:

Please find the problem here.

Solution:

The solution first find the delimiter by moving forward, then it compares the number by moving backwards. The code compares the characters from MSB to LSB one by one, leading zeroes are added if required.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/compare-version-numbers/

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

using namespace std;

namespace _LEET_COMPARE_VERSION_NUMBERS
{
    class Solution
    {
    public:
        int compareVersion(string version1, string version2)
        {
            int v1s = 0;
            int v2s = 0;
            int v1e = 0;
            int v2e = 0;
            while (true)
            {
                while (v1e < (int)version1.size() && version1[v1e] != '.')
                {
                    v1e++;
                }

                while (v2e < (int)version2.size() && version2[v2e] != '.')
                {
                    v2e++;
                }

                int len1 = v1e - v1s;
                int len2 = v2e - v2s;

                int length = max(len1, len2);

                if (length == 0)
                {
                    return 0;
                }

                for (int i = 0; i < length; i++)
                {
                    int v1ci = v1e - length + i;
                    int v2ci = v2e - length + i;
                    char v1c = v1ci < v1s ? '0' : version1[v1ci];
                    char v2c = v2ci < v2s ? '0' : version2[v2ci];
                    if (v1c > v2c)
                    {
                        return 1;
                    }
                    else if (v2c > v1c)
                    {
                        return -1;
                    }
                }

                v1e = v1s = v1e + 1;
                v2e = v2s = v2e + 1;
            }
        }
    };
};

using namespace _LEET_COMPARE_VERSION_NUMBERS;

int LEET_COMPARE_VERSION_NUMBERS()
{
    Solution s;
    cout << (s.compareVersion("1.0.1", "1.01") == -1) << endl;
    return 0;
}

LeetCode OJ - Valid Sudoku

Problem:

Please find the problem here.

Solution:

Just check the required rules.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/valid-sudoku/

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

using namespace std;

namespace _LEET_VALID_SUDOKU
{
    class Solution {
    private:
        bool found[9];
        void reset()
        {
            for (int i = 0; i < 9; i++)
            {
                found[i] = false;
            }
        }
        bool seen(char i)
        {
            if (i == '.')
            {
                return false;
            }
            i = i - '0';
            if (found[i - 1] == true)
            {
                return true;
            }
            else
            {
                found[i - 1] = true;
                return false;
            }
        }
    public:
        bool isValidSudoku(vector<vector<char>>& board)
        {
            // Rows 
            for (int row = 0; row < 9; row++)
            {
                reset();
                for (int col = 0; col < 9; col++)
                {
                    if (seen(board[row][col]))
                    {
                        return false;
                    }
                }
            }

            // Cols
            for (int col = 0; col < 9; col++)
            {
                reset();
                for (int row = 0; row < 9; row++)
                {
                    if (seen(board[row][col]))
                    {
                        return false;
                    }
                }
            }

            // Blocks
            for (int blockRow = 0; blockRow < 3; blockRow++)
            {
                for (int blockCol = 0; blockCol < 3; blockCol++)
                {
                    reset();
                    for (int row = blockRow * 3; row < blockRow * 3 + 3; row++)
                    {
                        for (int col = blockCol * 3; col < blockCol * 3 + 3; col++)
                        {
                            if (seen(board[row][col]))
                            {
                                return false;
                            }
                        }
                    }
                }
            }

            return true;

        }
    };
};

using namespace _LEET_VALID_SUDOKU;

int LEET_VALID_SUDOKU()
{
    Solution solution;
    vector<vector<char>> input;
    input.resize(9);
    for (int i = 0; i < 9; i++)
    {
        input[i].resize(9);
        for (int j = 0; j < 9; j++)
        {
            input[i][j] = '.';
        }
    }
    input[0][0] = '5';
    input[0][1] = '3';
    input[0][4] = '7';

    input[1][0] = '6';
    input[1][3] = '1';
    input[1][4] = '9';
    input[1][5] = '5';

    input[2][1] = '9';
    input[2][2] = '8';
    input[2][7] = '6';

    input[3][0] = '8';
    input[3][4] = '6';
    input[3][8] = '3';

    input[4][0] = '4';
    input[4][3] = '8';
    input[4][5] = '3';
    input[4][8] = '1';

    input[5][0] = '7';
    input[5][4] = '2';
    input[5][8] = '6';

    input[6][1] = '6';
    input[6][6] = '2';
    input[6][7] = '8';

    input[7][3] = '4';
    input[7][4] = '1';
    input[7][5] = '9';
    input[7][8] = '5';

    input[8][4] = '8';
    input[8][7] = '7';
    input[8][8] = '9';

    cout << solution.isValidSudoku(input) << endl;

    return 0;
}

Saturday, August 22, 2015

LeetCode OJ - Implement strStr()

Problem:

Please find the problem here.

Solution:

This is a substring match algorithm and in general many algorithms works for this. In this post, I used the Z-box algorithm described in Algorithms on Strings, Trees and Sequences.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/implement-strstr/

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

using namespace std;

namespace _LEET_IMPLEMENT_STRSTR
{
    class Solution
    {
    public:
        int strStr(string haystack, string needle)
        {
            // Special case - searching for empty string.
            if (needle == "")
            {
                return 0;
            }

            // Step 1: concatenate the strings
            unsigned int concatenated_length = needle.size() + 1 + haystack.size();
            char* concatenated = new char[concatenated_length];
            unsigned int i = 0;
            for (unsigned int j = 0; j < needle.size(); i++, j++)
            {
                concatenated[i] = needle[j];
            }
            concatenated[i++] = '\0';
            for (unsigned int j = 0; j < haystack.size(); i++, j++)
            {
                concatenated[i] = haystack[j];
            }

            // Step 2: Fundamental preprocessing
            int* z = new int[concatenated_length];
            z[0] = 0; // We do NOT compute the length of the Z-box for this one
            unsigned int l = 0; // Inclusive index of the rightmost Z-box
            unsigned int r = 0; // Exclusive index of the rightmost Z-box
            for (unsigned int k = 1; k < concatenated_length; k++)
            {
                if (k >= r)
                {
                    // The easy (but hard work) case - the current character is not in a Z-box
                    unsigned int start_head = 0;
                    unsigned int start_here = k;
                    unsigned int matching_length = 0;
                    while (start_here < concatenated_length)
                    {
                        if (concatenated[start_head] == concatenated[start_here])
                        {
                            start_head++;
                            start_here++;
                            matching_length++;
                        }
                        else
                        {
                            break;
                        }
                    }

                    z[k] = matching_length;
                    if (matching_length > 0)
                    {
                        l = k;
                        r = k + matching_length;
                    }
                }
                else
                {
                    // Denoting S[a, b) to means S[a ... b - 1]
                    // Denoting S[a -> b] to means S[a, a + b) = S[a ... a + b - 1]

                    // We are sure we know S[L, R) = S[0, R - L)
                    // We also know that L < k < R, so the current character is in a Z-box
                    // Therefore we know S[k, R) = S[k - L -> R - k]

                    int matching_length = r - k; // This is the length of S[k, R), the length of the string that we know must match

                    // We also know S[k - L -> z[k - L]] matches with S[0, z[k - L])
                    int reference_box_length = z[k - l];

                    
                    if (reference_box_length < matching_length)
                    {
                        // We know S[k, R) = S[k - L -> R - k]
                        // We also know z[k - L] < R - k, as we just checked
                        // 
                        // Therefore S[k -> z[k - L]] = S[k - L -> z[k - L]]    [ That is because if you match a string, you match a substring too]
                        // 
                        // We also know S[k - L -> z[k - L]] = S[0, z[k - L])
                        //
                        // Last but not least, we know for sure that the next character does not match
                        // 
                        // Therefore we know this:
                        //
                        z[k] = z[k - l];
                    }
                    else
                    {
                        // TODO
                        unsigned int start_head = matching_length;
                        unsigned int start_here = k + matching_length;
                        unsigned int actual_matching_length = matching_length;
                        while (start_here < concatenated_length)
                        {
                            if (concatenated[start_head] == concatenated[start_here])
                            {
                                start_head++;
                                start_here++;
                                actual_matching_length++;
                            }
                            else
                            {
                                break;
                            }
                        }

                        z[k] = actual_matching_length;
                        if (actual_matching_length > 0)
                        {
                            l = k;
                            r = k + actual_matching_length;
                        }
                    }
                }

                // If we found a match, returns right away
                if (z[k] == needle.size())
                {
                    // Skip the needle$ prefix
                    return k - needle.size() - 1;
                }
            }

            return -1;
        }
    };
};

using namespace _LEET_IMPLEMENT_STRSTR;

int LEET_IMPLEMENT_STRSTR()
{
    Solution s;
    cout << s.strStr("haystack", "sta") << endl;
    return 0;
}

Friday, August 21, 2015

LeetCode OJ - Valid Palindrome

Problem:

Please find the problem here.

Solution:

Keep two pointers at the first and the last character of the string, skip through any non-alphanumeric characters, and compare.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/valid-palindrome/

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

using namespace std;

namespace _LEET_VALID_PALINDROME
{
    class Solution {
    private:

        bool isAlphaNumeric(char c)
        {
            if ('A' <= c && c <= 'Z')
            {
                return true;
            }
            if ('a' <= c && c <= 'z')
            {
                return true;
            }
            if ('0' <= c && c <= '9')
            {
                return true;
            }
            return false;
        }
        char toLower(char x)
        {
            if (x >= 'A' && x <= 'Z')
            {
                return x + 'a' - 'A';
            }
            else
            {
                return x;
            }
        }
    public:
        bool isPalindrome(string s)
        {
            int b = 0;
            int e = s.size() - 1;
            while (b < e)
            {
                if (!isAlphaNumeric(s[b]))
                {
                    b++;
                }
                else if (!isAlphaNumeric(s[e]))
                {
                    e--;
                }
                else if (toLower(s[b]) == toLower(s[e]))
                {
                    b++;
                    e--;
                }
                else
                {
                    return false;
                }
            }

            return true;
        }
    };
};

using namespace _LEET_VALID_PALINDROME;

int LEET_VALID_PALINDROME()
{
    Solution s;
    cout << s.isPalindrome("A man, a plan, a canal: Panama") << endl;
    cout << !s.isPalindrome("race a car") << endl;
    cout << !s.isPalindrome("1a2") << endl;
    cout << s.isPalindrome("Zeus was deified, saw Suez.") << endl;
    return 0;
}