online advertising

Wednesday, January 11, 2017

LeetCode OJ - Hamming Distance

Problem:

Please find the problem here.

Solution:

This is an easy problem, just compute the hamming distance by a moving bit mask.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/hamming-distance/

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

using namespace std;

namespace _LEET_HAMMING_DISTANCE
{
    class Solution
    {
    public:
        int hammingDistance(int x, int y)
        {
            int mask = 1;
            int result = 0;
            for (int i = 0; i < 32; i++)
            {
                int mask_x = x & mask;
                int mask_y = y & mask;
                if (mask_x != mask_y)
                {
                    result++;
                }
                mask = mask << 1;
            }

            return result;
        }
    };
};

using namespace _LEET_HAMMING_DISTANCE;

int LEET_HAMMING_DISTANCE()
{
    Solution solution;
    cout << solution.hammingDistance(1, 4) << endl;
    return 0;
}

LeetCode OJ - Ones and Zeroes

Problem:

Please find the problem here.

Solution:

This problem look very similar to the 0-1 knapsack problem except instead of one weight, we have two weights.

Consider the last string, we can either pick it or not, this lead to the recurrence:

opt[w,m,n] = max(opt[w-1,m,n], 1 + opt[w-1,m-o(w),n-z(w)])

Of course, this deserves some explanation.

We denote:
opt as the optimal number of strings one can create.
w is the string being considered so far
m is the number of 1 we have
n is the number of 0 we have
o(w) is the number of 1 of the w string
z(w) is the number of 0 of the w string

With these notation, the explanation is obvious. The optimal number of strings we could create is either not picking the last one and optimally picking the rest, or picking the last one and optimally picking the rest with less 0 and 1 available.

The initial condition is simple, there is no way you can pick anything when considering no strings, regardless of the value of m and n.

Analysis:

We build the table bottom up. Note that we only require the table of the last w, so we can reduce the space requirement to $ O(m,n) $. The time complexity is still $ O(wmn) $, we also need to count the time required to pre-compute the o and z array, which is basically just a linear scan to the strings.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/ones-and-zeroes/

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

using namespace std;

namespace _LEET_ONES_AND_ZEROES
{
    int answer[2][101][101];

    class Solution
    {
    public:

        int findMaxForm(vector<string>& strs, int m, int n)
        {
            vector<int> o;
            vector<int> z;
            int num_items = strs.size();
            int num_ones = m;
            int num_zero = n;

            for (int w = 0; w < 2; w++)
            {
                for (int m = 0; m <= num_ones; m++)
                {
                    for (int n = 0; n <= num_zero; n++)
                    {
                        answer[w][m][n] = 0;
                    }
                }
            }

            o.resize(num_items);
            z.resize(num_items);
            for (int w = 0; w < num_items; w++)
            {
                o[w] = 0;
                z[w] = 0;
                for (int t = 0; t < strs[w].size(); t++)
                {
                    if (strs[w][t] == '0')
                    {
                        o[w]++;
                    }
                    else if (strs[w][t] == '1')
                    {
                        z[w]++;
                    }
                }
            }

            for (int w = 1; w <= num_items; w++)
            {
                for (int m = 0; m <= num_ones; m++)
                {
                    for (int n = 0; n <= num_zero; n++)
                    {
                        int a1 = answer[0][m][n];
                        if (m >= o[w - 1] && n >= z[w - 1])
                        {
                            int a2 = 1 + answer[0][m - o[w - 1]][n - z[w - 1]];
                            answer[1][m][n] = max(a1, a2);
                        }
                        else
                        {
                            answer[1][m][n] = a1;
                        }
                    }
                }
                for (int m = 0; m <= num_ones; m++)
                {
                    for (int n = 0; n <= num_zero; n++)
                    {
                        answer[0][m][n] = answer[1][m][n];
                    }
                }
            }

            return answer[1][num_ones][num_zero];
        }
    };
};

using namespace _LEET_ONES_AND_ZEROES;

int LEET_ONES_AND_ZEROES()
{
    Solution solution;
    // Input: Array = {"10", "0001", "111001", "1", "0"}, m = 5, n = 3

    vector<string> input;
    input.push_back("10");
    input.push_back("0001");
    input.push_back("111001");
    input.push_back("1");
    input.push_back("0");

    cout << solution.findMaxForm(input, 5, 3) << endl;
    
    return 0;
}