د قاموسونو شمیره د لیټکوډ حل  


مشکل کچه منځني
په مکرر ډول دننه پوښتل کیږي 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 XNUMX] دي.

د لیکسوګرافیک نمبرونو لیټکوډ حل لپاره د بروټ فورس چلند  

د ستونزې د حل لپاره د ځواک ځواک چلن په لاندې ډول دی:

  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]

د لیکسوګرافیک نمبرونو لپاره د جاوا کوډ

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]

د لیکسګرافیک شمیرو پیچلتیا تحلیل لیټکوډ حل  

د وخت پیچلتیا

د پورتنۍ کوډ وخت پیچلتیا ده O (nlogn) ځکه چې موږ د تار سره د N تار سره تنظیم کوو. دلته n ورکړل شوی لمبر دی.

هم وګوره
د نیپکس ستونزه

د ځای پیچلتیا

د پورتنۍ کوډ د ځای پیچلتیا ده O (1) ځکه چې موږ یوازې د ځواب ذخیره کولو لپاره تغیر ورکوو.

د لسیزوګرافیک شمیرو لیټکوډ حل لپاره د DFS لاره  

نظر خورا ساده دی. هرځله چې موږ له 1-9 څخه د یوې ګ digitې سره پیل کوو او بیا له 0-9 څخه په ډیرو شمېرو اضافه کولو ته دوام ورکوو تر هغه چې دا د n څخه کوچنی وي. نو دا بالکل د ډیپټ - لومړي - لټون الګوریتم سره ورته دی.

نو موږ به د 1 سره پیل وکړو او د دې لپاره به DFS ترسره کړو تر هغه چې دا د n سره کوچنی وي یا مساوي وي.

موږ به دا تر 9 پورې د ټولو ګ forو لپاره تکرار کړو بیا به د DFS پایله زیرمه او چاپ کړو.

د قاموسونو شمیره د لیټکوډ حلقید

تطبیق

د قاموسونو شمیرو لپاره 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]

د لیکسوګرافیک نمبرونو لپاره د جاوا کوډ

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]

د لیکسګرافیک شمیرو پیچلتیا تحلیل لیټکوډ حل  

د وخت پیچلتیا

د پورتنۍ کوډ وخت پیچلتیا ده اې (N) ځکه چې موږ یوازې یو ځل عناصر تعقیبوو. دلته n ورکړل شوی ارزښت دی.

هم وګوره
د بائنری ونې ډیجیونل ټریورسل

د ځای پیچلتیا

د پورتنۍ کوډ د ځای پیچلتیا ده او (لاګ (ه)) ځکه چې موږ د DFS کاروو. دلته h د DFS ونې لوړوالی دی.

ماخذونه