online advertising

Wednesday, January 11, 2017

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;
}

No comments :

Post a Comment