**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