ლექსიკოგრაფიული რიცხვები Leetcode ამოხსნა  


Რთული ტური საშუალო
ხშირად ეკითხებიან ByteDance
ალგორითმები კოდირება სიღრმისეული პირველი ძებნა ინტერვიუ ინტერვიუს მოსამზადებელი LeetCode LeetCodeSolutions

პრობლემის განცხადება  

პრობლემში ”ლექსიკოგრაფიული რიცხვები” მოცემულია რიცხვი 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 Solution  

უხეში ძალის მიდგომა პრობლემის გადასაჭრელად ასეთია:

  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]

ლექსიკოგრაფიული რიცხვების სირთულის ანალიზი Leetcode ამოხსნა  

დროის სირთულე

ზემოთ მოცემული კოდის სირთულეა ო (ნლოგნი) რადგან ჩვენ ვალაგებთ სტრიქონებს n სტრიქონით. აქ n არის მოცემული რიცხვი.

იხილეთ ასევე
ზურგჩანთის პრობლემა

კოსმოსური სირთულის

ზემოთ მოცემული კოდის სივრცის სირთულეა O (1) რადგან პასუხის შესანახად ვიყენებთ მხოლოდ ცვლადს.

DFS მიდგომა ლექსიკოგრაფიული რიცხვებისთვის Leetcode Solution  

იდეა საკმაოდ მარტივია. ყოველ ჯერზე, როდესაც ჩვენ ვიწყებთ ერთნიშნა რიცხვს 1-9-დან და შემდეგ ვაგრძელებთ 0-9 რიცხვების ციფრებს ამ რიცხვებზე, რადგან ის n- ზე ნაკლებია. ეს ზუსტად იგივეა, რაც სიღრმისეული პირველი ძიების ალგორითმი.

ასე რომ, ჩვენ დავიწყებთ 1 – ით და შევასრულებთ DFS– ს მისთვის, სანამ ის უფრო მცირეა ან ტოლია n– ს.

ამას ვიმეორებთ ყველა ციფრისთვის 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]

ლექსიკოგრაფიული ნომრების ჯავის კოდი

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 (ჟურნალი (თ)) რადგან ჩვენ ვიყენებთ DFS- ს. აქ h არის DFS ხის სიმაღლე.

ლიტერატურა