词典编号Leetcode解决方案  


难度级别 中等
经常问 ByteDance
算法 编码 深度优先搜索 访谈 面试准备 力码 力码解决方案

问题陈述  

在“辞书编号”问题中,我们得到了一个数字n。 我们的任务是打印1到n之间的数字 秩序。

使用案列

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

说明: 由于我们必须按字典顺序打印1-13之间的数字,因此数字为[1 10 11 12 13 2 3 4 5 6 7 8 9]。

词典编号Leetcode解决方案的蛮力方法  

解决该问题的蛮力方法如下:

  1. 将1到n之间的所有正整数转换为字符串。
  2. 现在,对字符串进行排序。 这将按字典顺序排列数字。
  3. 现在,将已排序的字符串再次转换为整数,这将给出结果。

实施

词典编号的C ++代码

#include <bits/stdc++.h> 
using namespace std; 
    vector<int> lexicalOrder(int n) {
        string a[n];
        for(int i=1;i<=n;i++)
            a[i-1]=to_string(i);
        sort(a,a+n);
        vector<int>ans;
        for(int i=1;i<=n;i++)
           ans.push_back(stoi(a[i-1]));
        return ans;
    }
int main() 
{ 
 int n=13;
 vector<int> ans=lexicalOrder(n);
 for(int i=0;i<n;i++)
 cout<<ans[i]<<" ";
 return 0;
}
[1 10 11 12 13 2 3 4 5 6 7 8 9]

词典编号的Java代码

import java.util.Arrays;
import java.util.Set ;
import java.util.HashSet;
import java.util.*; 
public class Tutorialcup {
    public static List<Integer> lexicalOrder(int n) {
                String[] a = new String[n];
        for(int i=1;i<=n;i++)
            a[i-1]=Integer.toString(i);
        Arrays.sort(a);
        List<Integer> ans=new ArrayList<Integer>();  
        for(int i=1;i<=n;i++)
           ans.add( Integer.parseInt(a[i-1]));
       
        return ans;
    }
  public static void main(String[] args) {
         int n=13;
          List<Integer> ans = new ArrayList<>(n);
         ans=lexicalOrder(n);
        System.out.println(Arrays.toString(ans.toArray()));
  }
}
[1 10 11 12 13 2 3 4 5 6 7 8 9]

辞书数字Leetcode解决方案的复杂性分析  

时间复杂度

上面代码的时间复杂度是 O(登录) 因为我们正在使用n字符串对字符串进行排序。 这里n是给定的数字。

参见
背包问题

空间复杂度

上面代码的空间复杂度是 O(1) 因为我们只使用一个变量来存储答案。

DFS方法用于词典数字Leetcode解决方案  

这个想法很简单。 每次我们从1-9的一个数字开始,然后继续在这些数字上添加0-9的数字,只要它小于n。 因此,这与“深度优先搜索”算法完全相同。

因此,我们将从1开始,并在它小于或等于n时对其执行DFS。

我们将对所有数字重复这些操作,直到9,然后存储并打印DFS结果。

词典编号Leetcode解决方案Pin

实施

词典编号的C ++代码

#include <bits/stdc++.h> 
using namespace std; 
        void dfs(int cur, int n, std::vector<int>& ret)
    {
        if (cur <= n)
        {
            ret.push_back(cur);
            for (int i = 0; i <= 9; ++i)
            {
                dfs(cur*10+i, n, ret);
            }
        }
    }
    vector<int> lexicalOrder(int n) {
        vector<int> ret;
        for (int i = 1; i <= 9; ++i)
        {
            dfs(i, n, ret);
        }
        return ret;
        
    }

int main() 
{ 
 int n=13;
 vector<int> ans=lexicalOrder(n);
 for(int i=0;i<n;i++)
 cout<<ans[i]<<" ";
 return 0;
}
[1 10 11 12 13 2 3 4 5 6 7 8 9]

词典编号的Java代码

import java.util.Arrays;
import java.util.Set ;
import java.util.HashSet;
import java.util.*; 
public class Tutorialcup {
    public static List<Integer> lexicalOrder(int n) {
        List<Integer> res = new ArrayList<>();
        for(int i=1;i<10;++i){
          dfs(i, n, res); 
        }
        return res;
    }
    
    public static void dfs(int cur, int n, List<Integer> res){
        if(cur>n)
            return;
        else{
            res.add(cur);
            for(int i=0;i<10;++i){
                if(10*cur+i>n)
                    return;
                dfs(10*cur+i, n, res);
            }
        }
    }
  public static void main(String[] args) {
         int n=13;
          List<Integer> ans = new ArrayList<>(n);
         ans=lexicalOrder(n);
        System.out.println(Arrays.toString(ans.toArray()));
  }
}
[1 10 11 12 13 2 3 4 5 6 7 8 9]

辞书数字Leetcode解决方案的复杂性分析  

时间复杂度

上面代码的时间复杂度是 O(N) 因为我们只遍历元素一次。 这里n是给定值。

参见
二叉树的对角遍历

空间复杂度

上面代码的空间复杂度是 O(log(h)) 因为我们正在使用DFS。 这里h是DFS树的高度。

參考資料