diff options
author | Jack Sangdahl <[email protected]> | 2025-03-10 00:36:13 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-03-10 00:36:13 -0600 |
commit | 7c60dee83b436e8e8a667bf9f191beced8de4fc3 (patch) | |
tree | eb7a24ee2067f92245c57bb118e85a1baf15df50 /other/lexicographical_numbers.cpp | |
parent | 5d7cdc215e4ba1ec4cbb24c084cccb5e5e641468 (diff) | |
download | leetcode-7c60dee83b436e8e8a667bf9f191beced8de4fc3.tar.gz leetcode-7c60dee83b436e8e8a667bf9f191beced8de4fc3.zip |
chore: move cpp and rust code to directory
Diffstat (limited to 'other/lexicographical_numbers.cpp')
-rw-r--r-- | other/lexicographical_numbers.cpp | 43 |
1 files changed, 43 insertions, 0 deletions
diff --git a/other/lexicographical_numbers.cpp b/other/lexicographical_numbers.cpp new file mode 100644 index 0000000..ab48ce5 --- /dev/null +++ b/other/lexicographical_numbers.cpp @@ -0,0 +1,43 @@ +// 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; + vector<int> lexicalOrder(int n) { + ans.resize(n); + int pos = 0; + for (int i = 1; i <= 9 && i <= n; i++) + helper(i, n, pos); + return ans; + } + +private: + void helper(int i, int n, int pos) { + ans[pos++] = i; + int tmp; + for (int j = 0; j <= 9; j++) { + tmp = i * 10 + j; + if (tmp > n) + break; + helper(tmp, n, pos); + } + } +}; + +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"); +} |