Tuesday, September 6, 2016

LeetCode OJ - Lexicographical Numbers

Problem:

Please find the problem here.

Analysis:

Suppose we are trying to do the lexicographical order for 213, here is how it should look like

1
10
100
101
...
109
11
110
111
...
199
2
20
200
201
...
213
22
23
...

The goal is to spot the pattern.

Solution:

By using an example, we can see some interesting rules:

Rule 1: Whenever possible, add 1 zero (e.g. 1 -> 10, 10->100)
Rule 2: If not possible to add zero (because it is too large) add 1. (e.g. 100->101)
Rule 3: If rule 2 result in any trailing zero, remove all of them. (e.g. 199 -> 200 -> 20 -> 2)
Rule 4: If reaching 'n', just fake it as if it reaches zero and apply rule 3. (213 -> 220 -> 22)

Applying this 4 rules, we can derive the order as needed. This approach requires only constant space!

Code:

#include "stdafx.h"

// https://leetcode.com/problems/lexicographical-numbers/

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

using namespace std;

namespace _LEET_LEXICOGRAPHICAL_NUMBERS
{
    class Solution
    {
    public:
        vector<int> lexicalOrder(int n)
        {
            vector<int> result;
            result.resize(n);
            int level = 0;
            int c = n;
            while (c > 0)
            {
                level++;
                c = c / 10;
            }

            int current = 1;
            int currentLevel = 1;

            for (int i = 0; i < n; i++)
            {
                result[i] = current;
                if ((currentLevel < level) && (current * 10 <= n))
                {
                    // We always try to increase the number of digit
                    current = current * 10;
                    currentLevel++;
                }
                else
                {
                    if (current == n)
                    {
                        // Take all the digits but the last one, increase by 1, and then add a zero
                        // e.g. 134 -> 13 -> 14 -> 140
                        current = ((current / 10) + 1) * 10;
                    }
                    else
                    {
                        current++;
                    }
                    while (current % 10 == 0)
                    {
                        // Whenever possible, remove trailing zero
                        currentLevel--;
                        current /= 10;
                    }
                }
            }
            return result;
        }
    };
};

using namespace _LEET_LEXICOGRAPHICAL_NUMBERS;

int LEET_LEXICOGRAPHICAL_NUMBERS()
{
    Solution solution;
    vector<int> r = solution.lexicalOrder(234);
    for (int i = 0; i < r.size(); i++)
    {
        cout << r[i] << endl;
    }
    return 0;
}

No comments :

Post a Comment