Mündəricat
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-dən n-dək olan bütün müsbət tam ədədləri sətirlərə çevirin.
- İndi ipləri sıralayın. Bu rəqəmləri leksikoqrafik qaydada düzəldəcəkdir.
- İ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.
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.
