1. 题目

2. 解答

2.1 方法一

假设返回 118 以内数的字典顺序，则为 1,10,100,101,102,...,109,11,110,111,112,...,118,12,13,...。根据这个序列，我们发现有以下几种情况。

• 1,10,100，每次都乘以 10
• 100,101,102,...,109，每次加 1
• 109,11，末尾为 9 则先除以 10 直到末尾不为 9 再加 1
• 118,12，排到 n 了则先除以 10 再加 1

class Solution {public:    vector
    
      lexicalOrder(int n) {                vector
     
       result;        int num = 1;        result.push_back(1);                for (int i = 1; i < n; i++)        {            if (num * 10 <= n)  num *= 10;            else            {                while (num % 10 == 9 || num == n)   num /= 10;                num++;            }            result.push_back(num);        }                return result;    }};
     
    

2.2 方法二

字典序排数可以看做是第一层节点分别为 1-9 的十叉树，然后我们在树上进行深度优先搜索即可。

class Solution {public:    void DFS(int num, vector
    
      &result, int n)    {        for (int i = 0; i < 10; i++) // 横向扩展        {            int data = num * 10 + i;            if (data > n)  break;            result.push_back(data);            DFS(data, result, n);  // 先向深度扩展        }    }        vector
     
       lexicalOrder(int n) {                vector
      
        result;                for (int i = 1; i < 10; i++) // 以 1-9 为根节点的十叉树        {            if (i <= n)  result.push_back(i);            if (i * 10 <= n)  DFS(i, result, n); // 进入子树        }           return result;    }    };
      
     
    

获取更多精彩，请关注「seniusen」!