online advertising

Saturday, October 8, 2016

LeetCode OJ - Remove K Digits

Problem:

Please find the problem here.

Analysis:

The key is to minimize the significant digits. If the first digits are 12, there is no reason to eliminate 1 because 1xx is always better than 2xx.

On the other hand, if the sequence is 123214, there is no reason not to eliminate the 3 either, since 122xx is always better than 123xx, and there is no way to obtain 12xxx < 123xx without eliminating the 3.

Solution:

The analysis above indicate we are unwilling to eliminate the first digits of an increasing sequence but wanted to eliminate the digit that start a decreasing sequence.

Therefore the algorithm maintains a stack of increasing indices. Whenever we hit the top of the stack (i.e. there is no way I can add more digits without going down (or ends the array)), we remove it.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/remove-k-digits/

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

using namespace std;

namespace _LEET_REMOVE_K_DIGITS
{
    class Solution
    {
    public:
        string removeKdigits(string num, int k)
        {
            if (k >= num.size())
            {
                return "0";
            }
            stack<int> increasing_indice;
            int i = 0;
            while (k > 0)
            {
                while (true)
                {
                    if (increasing_indice.size() == 0)
                    {
                        increasing_indice.push(i++);
                    }
                    else if (num[i] >= num[increasing_indice.top()])
                    {
                        increasing_indice.push(i++);
                    }
                    else
                    {
                        break;
                    }
                }
                int index_to_remove = increasing_indice.top();
                num[index_to_remove] = ' ';
                increasing_indice.pop();
                k--;
            }

            bool leading = true;
            char* resultBuffer = new char[num.size() - k + 1];
            size_t j = 0;
            for (size_t i = 0; i < num.size(); i++)
            {
                if (num[i] != ' ')
                {
                    if (!leading || num[i] != '0')
                    {
                        resultBuffer[j++] = num[i];
                        leading = false;
                    }
                }
            }

            if (leading)
            {
                resultBuffer[j++] = '0';
                leading = false;
            }

            resultBuffer[j++] = '\0';
            string resultString(resultBuffer);
            delete[] resultBuffer;
            return resultString;
        }
    };
};

using namespace _LEET_REMOVE_K_DIGITS;

int LEET_REMOVE_K_DIGITS()
{
    Solution solution;
    cout << solution.removeKdigits("1432219", 3) << endl;
    cout << solution.removeKdigits("10200", 1) << endl;
    cout << solution.removeKdigits("10", 2) << endl;
    return 0;
}

No comments :

Post a Comment