diff options
-rw-r--r-- | lexicographical_numbers.c | 44 | ||||
-rw-r--r-- | lexicographical_numbers.cpp | 19 | ||||
-rw-r--r-- | lexicographical_numbers.py | 31 |
3 files changed, 93 insertions, 1 deletions
diff --git a/lexicographical_numbers.c b/lexicographical_numbers.c new file mode 100644 index 0000000..5823da1 --- /dev/null +++ b/lexicographical_numbers.c @@ -0,0 +1,44 @@ +// 386. Lexicographical Numbers +#include "leetcode.h" + +/* + * given an integer 'n', return all the numbers in the range '[1, n]' sorted in + * lexicographical order. you must write an algorithm that runs in O(n) time + * complexity and uses O(1) extra space. + */ + +void lex(int *res, int n, int i, int digit, int *k) { + if (!digit) + return; + for (int j = i * 10; j < (i + 1) * 10 && j <= n; j++) { + res[(*k)++] = j; + lex(res, n, j, digit - 1, k); + } +} + +int *lexicalOrder(int n, int *returnSize) { + int *ans = (int *)malloc((n + 1) * sizeof(int)); + int tmp = n, max_digit = 0, k = 0; + while (tmp) { + tmp /= 10; + max_digit++; + } + for (int i = 1; i < 10 && i <= n; i++) { + ans[k++] = i; + lex(ans, n, i, max_digit, &k); + } + *returnSize = k; + return ans; +} + +int main() { + int rs1, rs2; + int *lo1 = lexicalOrder(13, &rs1), *lo2 = lexicalOrder(2, &rs2); + for (int i = 0; i < rs1; i++) + printf("%d ", lo1[i]); // expect: [1,10,11,12,13,2,3,4,5,6,7,8,9] + printf("\n"); + for (int i = 0; i < rs2; i++) + printf("%d ", lo2[i]); // expect: [1,2] + printf("\n"); + free(lo1), free(lo2); +} diff --git a/lexicographical_numbers.cpp b/lexicographical_numbers.cpp index 55e9fe3..ab48ce5 100644 --- a/lexicographical_numbers.cpp +++ b/lexicographical_numbers.cpp @@ -1,6 +1,12 @@ -// dnw +// 386. Lexicographical Numbers #include "leetcode.h" +/* + * given an integer 'n', return all the numbers in the range '[1, n]' sorted in + * lexicographical order. you must write an algorithm that runs in O(n) time + * complexity and uses O(1) extra space. + */ + class Solution { public: vector<int> ans; @@ -24,3 +30,14 @@ private: } } }; + +int main() { + Solution obj; + vector<int> lo1 = obj.lexicalOrder(13), lo2 = obj.lexicalOrder(2); + for (int i = 0; i < lo1.size(); i++) + printf("%d ", lo1[i]); // expect: [1,10,11,12,13,2,3,4,5,6,7,8,9] + printf("\n"); + for (int i = 0; i < lo2.size(); i++) + printf("%d ", lo2[i]); // expect: [1,2] + printf("\n"); +} diff --git a/lexicographical_numbers.py b/lexicographical_numbers.py new file mode 100644 index 0000000..0ab6d4e --- /dev/null +++ b/lexicographical_numbers.py @@ -0,0 +1,31 @@ +# 386. Lexicographical Numbers + +""" +given an integer 'n', return all the numbers in the range '[1, n]' sorted in +lexicographical order. you must write an algorithm that runs in O(n) time +complexity and uses O(1) extra space. +""" + + +class Solution(object): + def lexicalOrder(self, n): + """ + :type n: int + :rtype: List[int] + """ + ans = [1] + while len(ans) < n: + tmp = ans[-1] * 10 + while tmp > n: + tmp /= 10 + tmp += 1 + while tmp % 10 == 0: + tmp /= 10 + ans.append(tmp) + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.lexicalOrder(13)) + print(obj.lexicalOrder(2)) |