லெக்சோகிராஃபிக்கல் எண்கள் லீட்கோட் தீர்வு


சிரமம் நிலை நடுத்தர
அடிக்கடி கேட்கப்படுகிறது 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. இப்போது வரிசைப்படுத்தப்பட்ட சரங்களை மீண்டும் முழு எண்ணாக மாற்றவும், இது முடிவைக் கொடுக்கும்.

நடைமுறைப்படுத்தல்

லெக்சோகிராஃபிக்கல் எண்களுக்கான சி ++ குறியீடு

#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]

லெக்சோகிராஃபிக்கல் எண்களின் சிக்கலான பகுப்பாய்வு லீட்கோட் தீர்வு

நேர சிக்கலானது

மேலே உள்ள குறியீட்டின் நேர சிக்கலானது ஓ (nlogn) ஏனென்றால் நாம் சரங்களை n சரத்துடன் வரிசைப்படுத்துகிறோம். இங்கே n என்பது கொடுக்கப்பட்ட எண்.

விண்வெளி சிக்கலானது

மேலே உள்ள குறியீட்டின் இட சிக்கலானது ஓ (1) ஏனென்றால் பதிலைச் சேமிக்க ஒரு மாறி மட்டுமே பயன்படுத்துகிறோம்.

லெக்சோகிராஃபிக்கல் எண்களுக்கான டி.எஃப்.எஸ் அணுகுமுறை லீட்கோட் தீர்வு

யோசனை மிகவும் எளிது. ஒவ்வொரு முறையும் நாம் 1-9 இலிருந்து ஒரு இலக்கத்துடன் தொடங்கி, அந்த எண்ணிக்கையில் 0-9 இலிருந்து இலக்கங்களை n ஐ விட சிறியதாக இருக்கும் வரை சேர்க்கிறோம். எனவே இது ஆழம்-முதல்-தேடல் வழிமுறையைப் போன்றது.

எனவே நாம் 1 உடன் தொடங்குவோம், மேலும் அது சிறியதாகவோ அல்லது n க்கு சமமாகவோ இருக்கும் வரை DFS ஐ செய்வோம்.

9 வரை அனைத்து இலக்கங்களுக்கும் இவற்றை மீண்டும் செய்வோம், பின்னர் DFS முடிவை சேமித்து அச்சிடுவோம்.

லெக்சோகிராஃபிக்கல் எண்கள் லீட்கோட் தீர்வு

நடைமுறைப்படுத்தல்

லெக்சோகிராஃபிக்கல் எண்களுக்கான சி ++ குறியீடு

#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 மரத்தின் உயரம்.

குறிப்புகள்