online advertising

Tuesday, March 31, 2015

LeetCode OJ - Excel Sheet Column Title

Problem:

Please find the problem here.

Solution:

With the previous problem done, this one is relatively simpler.

The previous one appears to be base-26 number, but it isn't. None of 'A' - 'Z' represents 0 (and there is no 0). In fact, the representation is a base 27 number with all number with 0 removed. But this observation doesn't helped much.

The key insight comes from mapping 'Z'. 'Z' = 26, so if the number % 26 == 0, we should generate a 'Z', and therefore the number should subtract 26 and then divided by 26 to move on.

That's how the code is written.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/excel-sheet-column-title/

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

using namespace std;

namespace _LEET_EXCEL_SHEET_COLUMN_TITLE
{
    class Solution
    {
    public:
        string convertToTitle(int n)
        {
            stringstream result_builder;
            vector<char> result;
            while (n > 0)
            {
                int d = n % 26;
                if (d == 0)
                {
                    d = 26;
                }
                n -= d;
                n /= 26;
                result.push_back(d + 'A' - 1);
            }

            for (vector<char>::const_reverse_iterator ri = result.rbegin(); ri != result.rend(); ri++)
            {
                result_builder << *ri;
            }
            
            return result_builder.str();
        }
    };
};

using namespace _LEET_EXCEL_SHEET_COLUMN_TITLE;

int LEET_EXCEL_SHEET_COLUMN_TITLE()
{
    Solution solution;
    cout << solution.convertToTitle(1) << endl;
    cout << solution.convertToTitle(26) << endl;
    cout << solution.convertToTitle(27) << endl;
    cout << solution.convertToTitle(52) << endl;
    cout << solution.convertToTitle(53) << endl;
    cout << solution.convertToTitle(702) << endl;
    cout << solution.convertToTitle(703) << endl;
    return 0;
}

LeetCode OJ - Excel Sheet Column Number

Problem:

Please find the problem here.

Solution:

As you will be able to read from the code - the algorithm is pretty simple. The key idea is to understand how did I get there (i.e. the thought process).

If it is possible at all, I would start any problem from its simplest case. In this particular example, a single letter problem is quite simple, isn't it? So all we need to do is to have s[0] - 'A' + 1 and we are done.

Now we start with the second letter. I knew if I know how to do "AA", it is simply the next of "Z", which is 27. "AZ" is 52, therefore "BA" is 53. I conjectured that it is just the second digit times 26 + the first digit, and it is indeed the case, because for the second character to advance, the first character must have gone through 'A' - 'Z', which is 26 characters.

The rest follows.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/excel-sheet-column-number/

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

using namespace std;

namespace _LEET_EXCEL_SHEET_COLUMN_NUMBER
{
    class Solution
    {
    public:
        int titleToNumber(string s)
        {
            int result = 0;
            int digitFactor = 1;
            for (int i = s.length() - 1; i >= 0; i--)
            {
                result += (s[i] - 'A' + 1) * digitFactor;
                digitFactor *= 26;
            }

            return result;
        }
    };
};

using namespace _LEET_EXCEL_SHEET_COLUMN_NUMBER;

int LEET_EXCEL_SHEET_COLUMN_NUMBER()
{
    Solution solution;
    cout << solution.titleToNumber("A") << endl;
    cout << solution.titleToNumber("Z") << endl;
    cout << solution.titleToNumber("AA") << endl;
    cout << solution.titleToNumber("AZ") << endl;
    cout << solution.titleToNumber("BA") << endl;
    cout << solution.titleToNumber("ZZ") << endl;
    cout << solution.titleToNumber("AAA") << endl;
    cout << solution.titleToNumber("AAZ") << endl;
    cout << solution.titleToNumber("ABA") << endl;
    cout << solution.titleToNumber("AZZ") << endl;
    cout << solution.titleToNumber("BAA") << endl;
    return 0;
}

LeetCode OJ - Length of Last Word

Problem:

Please find the problem here.

Solution:

Standard problem on scanning and state machine for it, just that it goes from backward, so be it.

Code:


#include "stdafx.h"

// https://leetcode.com/problems/length-of-last-word/

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

using namespace std;

namespace _LEET_LENGTH_OF_LAST_WORD
{
    class Solution
    {
    public:
        int lengthOfLastWord(const char *s)
        {
            int length = strlen(s);
            int state = 0;
            int result = 0;
            for (int i = length - 1; i >= 0; i--)
            {
                if (state == 0)
                {
                    if (s[i] != ' ')
                    {
                        result = 1;
                        state = 1;
                    }
                }
                else if (state == 1)
                {
                    if (s[i] != ' ')
                    {
                        result++;
                    }
                    else
                    {
                        break;
                    }
                }
            }

            return result;
        }
    };
};

using namespace _LEET_LENGTH_OF_LAST_WORD;

int LEET_LENGTH_OF_LAST_WORD()
{
    Solution solution;
    cout << solution.lengthOfLastWord("Hello World") << endl;
    cout << solution.lengthOfLastWord("Hello World ") << endl;
    cout << solution.lengthOfLastWord(" ") << endl;
    cout << solution.lengthOfLastWord("Hello") << endl;
    cout << solution.lengthOfLastWord("Hello ") << endl;
    return 0;
}

LeetCode OJ - House Robber

Problem:

Please find the problem here.

Solution:

A simple application of dynamic programming.
The optimal way to rob all these homes is to either rob the last one and optimally rob the rest without the immediate neighbor, or not rob the last one and optimally rob all the ones before.

In equation, it is

OPT(n) = max(value[n] + OPT(n - 2), OPT(n-1))

With the initial conditions OPT(1) = value[1], and OPT(2) = max(value[1], value[2]).

Be careful with no home, one home or two home only, just special case them.

Could have reduce my memory to just two integers, just didn't bother, either is the judge.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/house-robber/

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

using namespace std;

namespace _LEET_HOUSE_ROBBER
{
    class Solution
    {
    public:
        int rob(vector<int> &num)
        {
            if (num.size() == 0)
            {
                return 0;
            }

            vector<int> best;
            best.resize(num.size());
            if (num.size() > 0)
            {
                best[0] = num[0];
            }
            if (num.size() > 1)
            {
                best[1] = max(num[0], num[1]);
            }

            for (unsigned int i = 2; i < num.size(); i++)
            {
                best[i] = max(num[i] + best[i - 2], best[i - 1]);
            }

            return best[num.size() - 1];
        }
    };
};

using namespace _LEET_HOUSE_ROBBER;

int LEET_HOUSE_ROBBER()
{
    Solution solution;
    vector<int> data;
    data.push_back(2);
    data.push_back(1);
    data.push_back(3);
    data.push_back(4);
    cout << solution.rob(data) << endl;
    return 0;
}

Monday, March 30, 2015

LeetCode OJ - Factorial Trailing Zeroes

Problem:

Please find the problem here.

Solution:

In order to have a trailing zero, there must be a factor of 10, there are plenty of 2 there, so the limiting factor is the number of 5 as a factor.

For all multiples of 5, we count 1.
For all multiples of 25, we should count two, but note that in the above step we already counted 1 for it, so just count 1.
For all multiples of 125, we should count three, but note that in the two above steps we already counted 2 for it, so again, just count 1.

Now we get the pattern, just count 1 for all multiples of all powers of 5, that's is.

Be careful with overflow, that's it.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/factorial-trailing-zeroes/

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

using namespace std;

namespace _LEET_FACTORIAL_TRAILING_ZEROES
{
    class Solution
    {
    public:
        int trailingZeroes(int n)
        {
            int numZeros = 0;
            long long p = 5;
            while (p <= n)
            {
                numZeros += n / p;
                p *= 5;
            }
            return numZeros;
        }
    };
};

using namespace _LEET_FACTORIAL_TRAILING_ZEROES;

int LEET_FACTORIAL_TRAILING_ZEROES()
{
    Solution solution;
    cout << solution.trailingZeroes(2147483647) << endl;
    return 0;
}

LeetCode OJ - Path Sum

Problem:

Please find the problem here.

Solution:

Recursively compute it - if we reach a leaf node with exactly the right sum value, return true. If we reach NULL, return false. Otherwise recursively call it and return if one of the branch works.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/path-sum/

#include "LEET_PATH_SUM.h"

#include <vector>
#include <set>
#include <map>
#include <iostream>
#include <algorithm>

using namespace std;

namespace _LEET_PATH_SUM
{
    struct TreeNode
    {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };
    class Solution
    {
    public:
        bool hasPathSum(TreeNode *root, int sum)
        {
            if (root == NULL)
            {
                return false;
            }
            else if (root->left == NULL && root->right == NULL && root->val == sum)
            {
                return true;
            }
            else
            {
                return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
            }
        }
    };
}

using namespace _LEET_PATH_SUM;

int LEET_PATH_SUM()
{
    TreeNode a(1);
    TreeNode b(2);
    TreeNode c(3);
    a.left = NULL;    a.right = &b;
    b.left = &c;  b.right = NULL;
    c.left = NULL;  c.right = NULL;
    Solution solution;
    cout << solution.hasPathSum(&a, 1) << endl;
    cout << solution.hasPathSum(&a, 2) << endl;
    cout << solution.hasPathSum(&a, 3) << endl;
    cout << solution.hasPathSum(&a, 4) << endl;
    cout << solution.hasPathSum(&a, 5) << endl;
    cout << solution.hasPathSum(&a, 6) << endl;
    return 0;
}

LeetCode OJ - Count and Say

Problem:

Please find the problem here.

Solution:

A straightforward implementation of the specification - note the use of stringstream to avoid conversion and the use of recursion to make life easy to code - performance wise it is not bad at all.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/count-and-say/

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

using namespace std;

namespace _LEET_COUNT_AND_SAY
{
    class Solution
    {
    public:
        string countAndSay(int n)
        {
            if (n < 1)
            {
                // Should be an error condition that is not clarified
                return "";
            }
            else if (n == 1)
            {
                return "1";
            }
            else
            {
                stringstream ss;
                string last = countAndSay(n - 1);
                for (unsigned int i = 0; i < last.length(); i++)
                {
                    int count = 1;
                    char value = last[i];
                    while (i < last.length())
                    {
                        if (last[i + 1] == value)
                        {
                            count++;
                            i++;
                        }
                        else
                        {
                            break;
                        }
                    }
                    
                    ss << count;
                    ss << value;
                }
                return ss.str();
            }
        }
    };
};

using namespace _LEET_COUNT_AND_SAY;

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

LeetCode OJ - Rotate Array

Problem:

Please find the problem here.

Solution:

It would be trivial if I allocate an array and just do the copy and copy back. To challenge myself, I decided to make this in-place with O(1) extra memory.

If I wanted to shift by 2, then I need to save the element that I will overwrite to, and then move on to shift the other as follow


CI = 0
V  = 'A'
NI = 2

0 1 2 3 4 6
A B C D E F

Here my current index is 0, and I wanted to shift by 2, so I wanted to move A to the position of C, let's save C first, and overwrite position 2 with A.

CI = 2
V  = 'C'
NI = 4

0 1 2 3 4 6
A B A D E F

Now we move further, we have

CI = 4
V  = 'E'
NI = 0

0 1 2 3 4 6
A B A D C F

But then we are reaching back to where we were, so after the writing, we stops.

CI = 0
V  = 'A'
NI = 2

0 1 2 3 4 6
E B A D C F

The interesting thing about this particular case is that although we are reaching back to where we were, but we moved only 3 elements, in general, that happens when n % k == 0. In this case, we need to help the algorithm by moving the next cycle as well, so we move the current index to 1 and start the loop again, by accounting the number of move, we can easily make sure we moved all elements.

This one is fun problem to crack, I would have a hard time without running the code and debugging it. I guess I could write it on a whiteboard, but much harder to get it all right.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/rotate-array/

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

using namespace std;

namespace _LEET_ROTATE_ARRAY
{
    class Solution {
    public:
        void rotate(int nums[], int n, int k) {
            int moved_element = 0;
            for (int start_index = 0; moved_element < n; start_index++)
            {
                int current_index = start_index;
                int next_index;
                int value_to_put = nums[start_index];
                do
                {
                    next_index = (current_index + k) % n;
                    int next_value = nums[next_index];
                    nums[next_index] = value_to_put;
                    value_to_put = next_value;
                    current_index = next_index;
                    moved_element++;
                } while (next_index != start_index);
            }
        }
    };
};

using namespace _LEET_ROTATE_ARRAY;

int LEET_ROTATE_ARRAY()
{
    int A[] = { 1, 2, 3, 4, 5 };
    Solution solution;
    solution.rotate(A, 4, 2);
    for (int i = 0; i < 5; i++)
    {
        cout << A[i] << " ";
    }
    cout << endl;
    return 0;
}


LeetCode OJ - Reverse Bits

Problem:

Please find the problem here.

Solution:

Let's construct the result by pushing the bits into the result one by one from the least significant end, the most significant one (of the result) need to be push in first, which correspond to the least significant bit on the left end, so there is it.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/reverse-bits/

#include "LEET_REVERSE_BITS.h"

#include <vector>
#include <set>
#include <map>
#include <iostream>
#include <stdint.h>

using namespace std;

namespace _LEET_REVERSE_BITS
{
    class Solution
    {
    public:
        uint32_t reverseBits(uint32_t n)
        {
            uint32_t result = 0;
            for (int i = 0; i < 32; i++)
            {
                result = result << 1;
                result = result | (n & 1);
                n = n >> 1;
            }
            return result;
        }
    };
};

using namespace _LEET_REVERSE_BITS;

int LEET_REVERSE_BITS()
{
    Solution solution;
    cout << solution.reverseBits(43261596) << endl;
    return 0;
}

Saturday, March 28, 2015

LeetCode OJ - Majority Element

Problem:

Please find the problem here.

Solution:

Sort it, the majority element must be in the median element!

Code:

#include "stdafx.h"

// https://leetcode.com/problems/majority-element/

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

using namespace std;

namespace _LEET_MAJORITY_ELEMENT
{
    class Solution {
    public:
        int majorityElement(vector<int> &num) {
            sort(num.begin(), num.end());
            return num[num.size() / 2];
        }
    };
};

using namespace _LEET_MAJORITY_ELEMENT;

int LEET_MAJORITY_ELEMENT()
{
    vector<int> odd;
    odd.push_back(1);
    odd.push_back(2);
    odd.push_back(1);
    
    vector<int> even;
    even.push_back(1);
    even.push_back(2);
    even.push_back(1);
    even.push_back(1);
    Solution solution;
    cout << solution.majorityElement(odd) << endl;
    cout << solution.majorityElement(even) << endl;
    return 0;
}

LeetCode OJ - Plus One

Problem:

Please find the problem here.

Solution:

What do you expect? Plus one! So just do it! This one is really surprising me on how simple a problem can be.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/plus-one/

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

using namespace std;

namespace _LEET_PLUS_ONE
{
    class Solution
    {
    public:
        vector<int> plusOne(vector<int> &digits)
        {
            vector<int> result;
            int i = digits.size() - 1;
            int carry = 1;
            while (i >= 0 || carry == 1)
            {
                int digit = i < 0 ? 0 : digits[i];
                if (carry == 1)
                {
                    digit++;
                    if (digit == 10)
                    {
                        digit = 0;
                        carry =  1;
                    }
                    else
                    {
                        carry = 0;
                    }
                }
                result.push_back(digit);
                i--;
            }

            reverse(result.begin(), result.end());
            return result;
        }
    };
};

using namespace _LEET_PLUS_ONE;

int LEET_PLUS_ONE()
{
    vector<int> input;
    // input.push_back(1);
    input.push_back(9);
    input.push_back(9);
    Solution solution;
    vector<int> answer = solution.plusOne(input);
    for (unsigned int i = 0; i < answer.size(); i++)
    {
        cout << answer[i];
    }
    cout << endl;
    return 0;
}

LeetCode OJ - Single Number

Problem:

Please find the problem here.

Solution:

This one is a classic. XOR all the numbers will do the trick, as A xor A is 0 and xor is associative.

Code:

#include "stdafx.h"

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

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

using namespace std;

namespace _LEET_SINGLE_NUMBER
{
    class Solution
    {
    public:
        int singleNumber(int A[], int n)
        {
            int answer = 0;
            for (int i = 0 ; i < n; i++)
            {
                answer = answer ^ A[i];
            }

            return answer;
        }
    };
};

using namespace _LEET_SINGLE_NUMBER;

int LEET_SINGLE_NUMBER()
{
    int A[5];
    A[0] = 1;
    A[1] = 5;
    A[2] = 1;
    A[3] = 4;
    A[4] = 5;
    Solution solution;
    cout << solution.singleNumber(A, 5) << endl;
    return 0;
}