online advertising

Monday, September 28, 2015

LeetCode OJ - Subsets II

Problem:

Please find the problem here.

Solution:

The odometer solution in this previous post worked just fine with one caveat. We should not double count some subsets, for example

Consider the input [1, 2, 2], for convenience, we mark it as [1, 2a, 2b], then

[1,2a] = [0, 1, 0]
[1,2b] = [0, 0, 1]

But they are really both just [1, 2], so we are double counting. The correct method would be

[1, 2a] = [0, 1]
[1, 2b] = [0, 1] // we will not double count this one as they have same odometer representation.
[1, 2a, 2b] = [0, 2] // and we will count this one!

Now we will not double count, we just need to make sure the digit overflow only when it overflow the number of occurrences of that number.

The blog posts in a row this morning, yay!

Code:

#include "stdafx.h"

// https://leetcode.com/problems/subsets-ii/

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

using namespace std;

namespace _LEET_SUBSETS_II
{
    class Solution
    {
    public:
        vector<vector<int>> subsetsWithDup(vector<int>& nums)
        {
            vector<vector<int>> result;
            if (nums.size() == 0)
            {
                return result;
            }

            sort(nums.begin(), nums.end());
            vector<int> distinct_nums;
            vector<int> distinct_nums_count;
            distinct_nums.push_back(nums[0]);
            distinct_nums_count.push_back(1);
            for (unsigned int i = 1; i < nums.size(); i++)
            {
                if (nums[i] == nums[i - 1])
                {
                    distinct_nums_count[distinct_nums_count.size() - 1]++;
                }
                else
                {
                    distinct_nums.push_back(nums[i]);
                    distinct_nums_count.push_back(1);
                }
            }

            int size = distinct_nums.size();
            vector<int> bits;
            bits.resize(size);
            for (int i = 0; i < size; i++)
            {
                bits[i] = 0;
            }
            while (true)
            {
                vector<int> subset;
                for (int i = 0; i < size; i++)
                {
                    for (int j = 0; j < bits[i]; j++)
                    {
                        subset.push_back(distinct_nums[i]);
                    }
                }
                result.push_back(subset);
                int digit = 0;
                while (true)
                {
                    if (bits[digit] == distinct_nums_count[digit])
                    {
                        bits[digit] = 0;
                        digit++;
                    }
                    else
                    {
                        bits[digit]++;
                        break;
                    }
                    if (digit == size)
                    {
                        return result;
                    }
                }
            }
        }
    };
};

using namespace _LEET_SUBSETS_II;

int LEET_SUBSETS_II()
{
    Solution solution;
    vector<int> nums;
    nums.push_back(1);
    nums.push_back(2);
    nums.push_back(2);
    vector<vector<int>> subsets = solution.subsetsWithDup(nums);
    for (unsigned int i = 0; i < subsets.size(); i++)
    {
        for (unsigned int j = 0; j < subsets[i].size(); j++)
        {
            cout << subsets[i][j];
        }
        cout << endl;
    }
    return 0;
}

LeetCode OJ - Subsets

Problem:

Please find the problem here.

Solution:

If we visualize the subset as a bit mask, we see this

[3]    = [1, 0, 0]
[1, 2] = [0, 1, 1]
...

So to iterate through all the subsets, simply run an odometer from 000 to 111, that's it.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/subsets/

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

using namespace std;

namespace _LEET_SUBSETS
{
    class Solution
    {
    public:
        vector<vector<int>> subsets(vector<int>& nums)
        {
            int size = nums.size();
            sort(nums.begin(), nums.end());
            vector<bool> bits;
            bits.resize(size);
            for (int i = 0; i < size; i++)
            {
                bits[i] = false;
            }
            vector<vector<int>> result;
            while (true)
            {
                vector<int> subset;
                for (int i = 0; i < size; i++)
                {
                    if (bits[i])
                    {
                        subset.push_back(nums[i]);
                    }
                }
                result.push_back(subset);
                int digit = 0;
                while (true)
                {
                    if (bits[digit])
                    {
                        bits[digit] = false;
                        digit++;
                    }
                    else
                    {
                        bits[digit] = true;
                        break;
                    }
                    if (digit == size)
                    {
                        return result;
                    }
                }
            }
        }
    };
};

using namespace _LEET_SUBSETS;

int LEET_SUBSETS()
{
    Solution solution;
    vector<int> nums;
    nums.push_back(1);
    nums.push_back(2);
    nums.push_back(3);
    vector<vector<int>> subsets = solution.subsets(nums);
    for (unsigned int i = 0; i < subsets.size(); i++)
    {
        for (unsigned int j = 0; j < subsets[i].size(); j++)
        {
            cout << subsets[i][j];
        }
        cout << endl;
    }
    return 0;
}

LeetCode OJ - Set Matrix Zeroes

Problem:

Please find the problem here.

Solution:

The key to this problem is to use constant space, to do that, we use the first row and first column of the matrix to store whether a column or a row need to set zero.

Doing so ruined the first row and first column, so before doing that, we must also determine whether the first row or the first column need to zero out, and hence the code.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/set-matrix-zeroes/

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

using namespace std;

namespace _LEET_SET_MATRIX_ZEROES
{
    class Solution
    {
    public:
        void setZeroes(vector<vector<int>>& matrix)
        {
            int height = matrix.size();
            if (height > 0)
            {
                int width = matrix[0].size();
                if (width > 0)
                {
                    bool firstRowZero = false;
                    bool firstColumnZero = false;
                    for (int col = 0; col < width; col++)
                    {
                        if (matrix[0][col] == 0)
                        {
                            firstRowZero = true;
                            break;
                        }
                    }
                    for (int row = 0; row < height; row++)
                    {
                        if (matrix[row][0] == 0)
                        {
                            firstColumnZero = true;
                            break;
                        }
                    }
                    for (int row = 1; row < height; row++)
                    {
                        for (int col = 1; col < width; col++)
                        {
                            if (matrix[row][col] == 0)
                            {
                                matrix[row][0] = 0;
                                matrix[0][col] = 0;
                            }
                        }
                    }
                    for (int row = 1; row < height; row++)
                    {
                        for (int col = 1; col < width; col++)
                        {
                            if (matrix[row][0] == 0 || matrix[0][col] == 0)
                            {
                                matrix[row][col] = 0;
                            }
                        }
                    }
                    if (firstRowZero)
                    {
                        for (int col = 0; col < width; col++)
                        {
                            matrix[0][col] = 0;
                        }
                    }
                    if (firstColumnZero)
                    {
                        for (int row = 0; row < height; row++)
                        {
                            matrix[row][0] = 0;
                        }
                    }
                }
            }
        }
    };
};

using namespace _LEET_SET_MATRIX_ZEROES;

int LEET_SET_MATRIX_ZEROES()
{
    Solution solution;
    vector<vector<int>> matrix;
    matrix.resize(3);
    matrix[0].push_back(1);
    matrix[0].push_back(1);
    matrix[0].push_back(1);
    matrix[1].push_back(1);
    matrix[1].push_back(0);
    matrix[1].push_back(1);
    matrix[2].push_back(1);
    matrix[2].push_back(1);
    matrix[2].push_back(1);
    solution.setZeroes(matrix);
    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            cout << matrix[i][j];
        }
        cout << endl;
    }
    return 0;
}

LeetCode OJ - Flatten Binary Tree to Linked List

Problem:

Please find the problem here.

Solution:

I spent some time thinking about this one.

First, note that, the signature do not allow a return, which means the root of the tree node must be unchanged. That's calls for pre-order.

Next, if we do a pre-order traversal, and then modify the tree at the same time, we are done.

In order to stitch the list together, I need the end of the list, that's why I introduced a helper function for that purpose, it returns the end of the list of the subtree we are processing.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/flatten-binary-tree-to-linked-list/

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

using namespace std;

namespace _LEET_FLATTEN_BINARY_TREE_TO_LINKED_LIST
{
    struct TreeNode
    {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };
    class Solution
    {
        TreeNode* flattenWithLast(TreeNode* root)
        {
            TreeNode* left = root->left;
            TreeNode* right = root->right;
            root->left = NULL;
            root->right = NULL;
            TreeNode* last = root;
            if (left != NULL)
            {
                last->right = left;
                last = flattenWithLast(left);
            }
            if (right != NULL)
            {
                last->right = right;
                last = flattenWithLast(right);
            }
            return last;
        }
    public:
        void flatten(TreeNode* root) {
            if (root == NULL)
            {
                return;
            }
            flattenWithLast(root);
        }
    };
};

using namespace _LEET_FLATTEN_BINARY_TREE_TO_LINKED_LIST;

int LEET_FLATTEN_BINARY_TREE_TO_LINKED_LIST()
{
    Solution solution;
    TreeNode a(1);
    TreeNode b(2);
    TreeNode c(3);
    TreeNode d(4);
    TreeNode e(5);
    TreeNode f(6);
    a.left = &b;
    b.left = &c;
    b.right = &d;
    a.right = &e;
    e.right = &f;
    solution.flatten(&a);
    TreeNode* curr = &a;
    while (curr != NULL)
    {
        cout << curr->val;
        curr = curr->right;
    }
    cout << endl;
    return 0;
}

LeetCode OJ - Binary Tree Postorder Traversal

Problem:

Please find the problem here.

Solution:

As mentioned in the problem, recursive solution is trivial, so we will try to do it iteratively.

The recursive solution would look like this

  Function postorderTraversalImpl(TreeNode* root)
  {
0:  if (root == NULL)
    {
      return;
    }
    this->postorderTraversalImpl(root->left);
1:  this->postorderTraversalImpl(root->right);
2:  result.push_back(root->val);
    return;
}

In order to change this into an iterative algorithm, I simulated the call stack, in particular, I perform these rules:

A function call is replaced by pushing the parameter and return address to the stack, and jump to the function entry point.

A parameter access is replaced by accessing the parameter value of the top of the stack.

A return is replaced by popping the stack frame and jumping to the address

The jump operation could have been coded using goto, but instead I used status flag to redirect the jumps instead. There is a global while loop to jump backwards, and then an address to go flag to redirect to the right line.

With the addressToGo thing, the code look really ugly, sigh, but it works.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/binary-tree-postorder-traversal/

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

using namespace std;

namespace _LEET_BINARY_TREE_POSTORDER_TRAVERSAL
{
    struct TreeNode
    {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };
    class Solution {
    private:
        class Frame
        {
        public:
            TreeNode* root;
            int returnAddress;
        };

        vector<int> result;
        stack<Frame> callstack;

        void postorderTraversalImpl(TreeNode* root)
        {   
            int addressToGo = 0;
            while (true)
            {
                if (addressToGo == -1)
                {
                    break;
                }
                Frame current = callstack.top();
                if (addressToGo == 0)
                {
                    if (current.root == NULL)
                    {
                        // return;
                        addressToGo = current.returnAddress;
                        callstack.pop();
                    }
                    else
                    {
                        Frame newFrame;
                        newFrame.root = current.root->left;
                        newFrame.returnAddress = 1;
                        callstack.push(newFrame);
                        addressToGo = 0;
                        // this->postorderTraversalImpl(root->left);
                    }
                }
                else if (addressToGo == 1)
                {
                    Frame newFrame;
                    newFrame.root = current.root->right;
                    newFrame.returnAddress = 2;
                    callstack.push(newFrame);
                    addressToGo = 0;
                    // this->postorderTraversalImpl(root->right);
                }
                else if (addressToGo == 2)
                {
                    result.push_back(current.root->val);
                    // return
                    addressToGo = current.returnAddress;
                    callstack.pop();
                }
            }
        }
    public:
        vector<int> postorderTraversal(TreeNode* root)
        {
            this->result.clear();
            Frame initialFrame;
            initialFrame.root = root;
            initialFrame.returnAddress = -1;
            callstack.push(initialFrame);
            this->postorderTraversalImpl(root);
            return result;
        }
    };
};

using namespace _LEET_BINARY_TREE_POSTORDER_TRAVERSAL;

int LEET_BINARY_TREE_POSTORDER_TRAVERSAL()
{
    Solution solution;
    TreeNode a(1);
    TreeNode b(2);
    TreeNode c(3);
    a.right = &b;
    b.left = &c;
    vector<int> result = solution.postorderTraversal(&a);
    for (unsigned int i = 0; i < result.size(); i++)
    {
        cout << result[i] << " ";
    }
    cout << endl;
    return 0;
}

LeetCode OJ - Unique Paths II

Problem:

Please find the problem here.

Solution:

Unlike Unique Paths, this problem has no closed form solution. Instead, we will use the simple dynamic programming algorithm.

At each cell, we compute the number of ways to reach a certain cell. The initial case is trivial.

ways[0][0] = 1.

Next, we can reach a cell either from above our from left (if they exists), so we have these.

ways[row][col] = ways[row - 1][col] + ways[row][col -1] // Decay the number of zero if array index out of bound.

That's give the following dynamic programming algorithm.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/unique-paths-ii/

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

using namespace std;

namespace _LEET_UNIQUE_PATHS_II
{
    class Solution {
    public:
        int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid)
        {
            int height = obstacleGrid.size();
            if (height > 0)
            {
                int width = obstacleGrid[0].size();
                if (width > 0)
                {
                    vector<vector<int>> answer;
                    answer.resize(height);
                    for (int h = 0; h < height; h++)
                    {
                        answer[h].resize(width);
                    }
                    for (int h = 0; h < height; h++)
                    {
                        for (int w = 0; w < width; w++)
                        {
                            if (obstacleGrid[h][w] == 1)
                            {
                                answer[h][w] = 0;
                            }
                            else
                            {
                                int above = h == 0 ? 0 : answer[h - 1][w];
                                int left = w == 0 ? 0 : answer[h][w - 1];
                                int bonus = (h == 0 && w == 0) ? 1 : 0;
                                answer[h][w] = above + left + bonus;
                            }
                        }
                    }
                    return answer[height - 1][width - 1];
                }
            }
            return 0;
        }
    };
};

using namespace _LEET_UNIQUE_PATHS_II;

int LEET_UNIQUE_PATHS_II()
{
    Solution solution;
    vector<vector<int>> obstacleGrid;
    obstacleGrid.resize(3);
    obstacleGrid[0].push_back(0);
    obstacleGrid[0].push_back(0);
    obstacleGrid[0].push_back(0);
    obstacleGrid[1].push_back(0);
    obstacleGrid[1].push_back(1);
    obstacleGrid[1].push_back(0);
    obstacleGrid[2].push_back(0);
    obstacleGrid[2].push_back(0);
    obstacleGrid[2].push_back(0);
    cout << solution.uniquePathsWithObstacles(obstacleGrid) << endl;
    return 0;
}