Lexcographical Numbers Leetcode Həlli

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur ByteDance
alqoritmlər kodlaşdırma Dərinlik İlk Axtarış müsahibə müsahibə hazırlığı LeetCode LeetCodeSolutionsBaxılıb 28

Problem bəyanat

”Leksikoqrafiya nömrələri” problemində bizə n rəqəmi verilir. Bizim vəzifəmiz 1 ilə n arasında rəqəmlər yazdırmaqdır leksikoqrafik üçün.

misal

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

Explanation: 1-13 arasındakı rəqəmləri leksikoqrafiya sırası ilə çap etməli olduğumuz üçün rəqəmlər [1 10 11 12 13 2 3 4 5 6 7 8 9].

Lexcographical Numbers Leetcode Həlli üçün Kobud Güc Yanaşması

Problemi həll etmək üçün kobud güc yanaşması belədir:

  1. 1-dən n-dək olan bütün müsbət tam ədədləri sətirlərə çevirin.
  2. İndi ipləri sıralayın. Bu rəqəmləri leksikoqrafik qaydada düzəldəcəkdir.
  3. İndi sıralanmış simləri yenidən tam ədədə çevirin və bu nəticə verəcəkdir.

Həyata keçirilməsi

Lexicographical Numbers üçün C ++ kodu

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

Sözlük lüğətləri üçün Java kodu

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]

Lexcographical Numbers Leetcode Solutions-un Mürəkkəblik Analizi

Zaman mürəkkəbliyi

Yuxarıdakı kodun zaman mürəkkəbliyi O (nlogn) çünki simləri n simli ilə çeşidləyirik. Burada n verilən rəqəmdir.

Kosmik mürəkkəblik

Yuxarıdakı kodun kosmik mürəkkəbliyi O (1) çünki cavabı saxlamaq üçün yalnız dəyişəndən istifadə edirik.

Lexcographical Numbers Leetcode Həlli üçün DFS Yanaşması

Fikir olduqca sadədir. Hər dəfə 1-9-dan bir rəqəmlə başlayırıq və sonra n-dən kiçik olduğu müddətdə bu rəqəmlərə 0-9-dan rəqəmlər əlavə etməyə davam edirik. Yəni bu, Dərinlik-İlk Axtarış alqoritmi ilə tamamilə eynidir.

Beləliklə, 1 ilə başlayacağıq və daha kiçik və ya n-ə bərabər olduğu müddətdə bunun üçün DFS həyata keçirəcəyik.

Bunları 9-a qədər bütün rəqəmlər üçün təkrarlayacağıq, sonra DFS nəticəsini saxlayırıq və çap edirik.

Lexcographical Numbers Leetcode HəlliPin

Həyata keçirilməsi

Lexicographical Numbers üçün C ++ kodu

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

Sözlük lüğətləri üçün Java kodu

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]

Lexcographical Numbers Leetcode Solutions-un Mürəkkəblik Analizi

Zaman mürəkkəbliyi

Yuxarıdakı kodun zaman mürəkkəbliyi O (n) çünki elementləri yalnız bir dəfə dolaşırıq. Burada n verilən dəyərdir.

Kosmik mürəkkəblik

Yuxarıdakı kodun kosmik mürəkkəbliyi O (log (h)) çünki DFS istifadə edirik. Burada h DFS ağacının hündürlüyüdür.

References

Şərh yaz

Translate »