当前位置：网站首页>【dfs】386. 字典序排数

【dfs】386. 字典序排数

2022-04-22 20:19:00 【wjh776a68】

题目

  给你一个整数 n ，按字典序返回范围 [1, n] 内所有整数。
  你必须设计一个时间复杂度为 O(n) 且使用 O(1) 额外空间的算法。

示例 1：
输入：n = 13
输出：[1,10,11,12,13,2,3,4,5,6,7,8,9]
示例 2：
输入：n = 2
输出：[1,2]

提示：

  • 1 <= n <= 5 * 104

答案

使用常量空间的dfs
链接

解

class Solution {
    
public:
    vector<int> lexicalOrder(int n) {
     //使用栈的dfs，能通过，但不确定是否满足题目要求的时空复杂度
        vector<int> ans;
        stack<int> buf;
        int curnum = 1;
        buf.push(curnum);
        while (!buf.empty()) {
    
            curnum = buf.top();
            buf.pop();
            while (curnum <= n) {
    
                ans.push_back(curnum);
                if (curnum % 10 < 9) {
    
                    buf.push(curnum+1);
                }
                
                curnum *= 10;
            }
        }
        return ans;
    }
};

版权声明
本文为[wjh776a68]所创，转载请带上原文链接，感谢
https://blog.csdn.net/qq_45434284/article/details/124287298

边栏推荐

猜你喜欢

随机推荐