لغو گرافیکل نمبر لیٹکوڈ حل


مشکل سطح درمیانہ
اکثر پوچھا جاتا ہے ByteDance
گہرائی پہلی تلاش

مسئلہ یہ بیان

مسئلے میں "لِکس گرافیکل نمبر" ہمیں ایک نمبر دیا جاتا ہے۔ ہمارا کام 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] ہیں۔

لغو گرافیکل نمبر لیٹ کوڈ حل کے لئے بروٹ فورس اپروچ

اس مسئلے کو حل کرنے کے لئے بروٹ فورس نقطہ نظر اس طرح ہے:

  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) کیونکہ ہم ن تار کے ساتھ چھانٹ رہے ہیں۔ یہاں ن دیا ہوا نمبر ہے۔

خلائی پیچیدگی

مذکورہ کوڈ کی جگہ کی پیچیدگی ہے O (1) کیونکہ ہم جواب کو ذخیرہ کرنے کے لئے صرف متغیر کا استعمال کررہے ہیں۔

لغوگرافیکل نمبر لیٹ کوڈ حل کے لئے ڈی ایف ایس اپروچ

خیال بہت آسان ہے۔ ہر بار جب ہم ایک ہی ہندسے کو 1-9 سے شروع کرتے ہیں اور پھر اس نمبر پر 0-9 سے ہندسوں کا اضافہ کرتے رہتے ہیں جب تک کہ یہ n سے چھوٹا ہو۔ تو یہ بالکل ویسا ہی ہے جیسے پہلے گہرائی کا پہلا سرچ الگورتھم ہے۔

لہذا ہم 1 سے شروع کریں گے اور اس کے ل smaller DF انجام دیں گے جب تک کہ یہ n کے برابر یا چھوٹا ہو۔

ہم ان کو 9 تک تمام ہندسوں کے لئے دہرائیں گے پھر ڈی ایف ایس کے نتائج کو اسٹور اور پرنٹ کریں گے۔

لغو گرافیکل نمبر لیٹکوڈ حل

عمل

لغو گرافیکل نمبروں کے لئے 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 دی گئی قیمت ہے۔

خلائی پیچیدگی

مذکورہ کوڈ کی جگہ کی پیچیدگی ہے O (لاگ (h)) کیونکہ ہم ڈی ایف ایس استعمال کر رہے ہیں۔ یہاں H DF درخت کی اونچائی ہے۔

حوالہ جات