重庆网站制作开发_建设摩托车报价大全_seo关键词快速提升软件官网_上海百度竞价点击软件

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 and uses O(1) extra space.
 

Example 1:

Input: n = 13
Output: [1,10,11,12,13,2,3,4,5,6,7,8,9]

Example 2:

Input: n = 2
Output: [1,2]

Constraints:

• $1<=n<=5\ast 10^4$

From: LeetCode
Link: 386. Lexicographical Numbers

---

Solution:

Ideas:

• Handling integers: If s doesn’t start with a [, it’s a single integer, so we parse it using atoi and return a NestedInteger containing that integer.
• Handling lists: We traverse through the string character by character.
  • When encountering [, we initialize a new NestedInteger and push the current one onto a stack if necessary.
  • When encountering ], we pop from the stack and add the current NestedInteger to the parent.
  • When encountering digits (or - for negative numbers), we parse the number and add it to the current list.
• Memory management: We use a stack to keep track of nested structures, and

Code:

/*** Note: The returned array must be malloced, assume caller calls free().*/
void dfs(int current, int n, int* result, int* index) {// Add the current number to the result arrayresult[(*index)++] = current;// Try to append digits (0-9) to the current numberfor (int i = 0; i <= 9; i++) {int next = current * 10 + i;if (next > n) {break; // Stop if the number exceeds n}dfs(next, n, result, index);}
}int* lexicalOrder(int n, int* returnSize) {// Allocate memory for the result arrayint* result = (int*)malloc(n * sizeof(int));int index = 0;// Perform DFS starting from 1 to 9for (int i = 1; i <= 9; i++) {if (i > n) {break;}dfs(i, n, result, &index);}// Set the return size*returnSize = n;return result;
}