Лексикографиялык сандар Leetcode чечими


Кыйынчылык деңгээли орто
Көп суралган ByteDance
Тереңдик Биринчи издөө

Көйгөйдү айтуу

"Лексикографиялык сандар" маселесинде бизге n саны берилген. Биздин милдет - 1ден n-ге чейинки сандарды басып чыгаруу лексикографиялык токтому.

мисал

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

Explanation: 1-13 аралыгындагы сандарды лексикографиялык тартипте басып чыгарууга туура келгендиктен, сандар [1 10 11 12 13 2 3 4 5 6 7 8 9].

Lexcographical Numbers Leutcode Solution үчүн Brute Force ыкмасы

Маселени чечүү үчүн катаал күчтөрдүн мамилеси төмөнкүчө:

  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]

Лексикографиялык сандар үчүн Java коду

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 Solution

Убакыттын татаалдыгы

Жогорудагы коддун убакыттын татаалдыгы O (nlogn) анткени биз кылдарды n сап менен иргеп жатабыз. Бул жерде n берилген сан.

Космостун татаалдыгы

Жогорудагы коддун мейкиндик татаалдыгы O (1) анткени биз жоопту сактоо үчүн өзгөрмө гана колдонобуз.

Lefcode Solution үчүн лексикографиялык сандар үчүн DFS ыкмасы

Идея абдан жөнөкөй. Ар бир жолу биз 1-9дан бир цифра менен башталып, андан кийин ал сандарга 0-9дан цифраларды, эгерде ал nден кичинекей болсо, кошо беребиз. Демек, бул таптакыр тереңдик-биринчи издөө алгоритмине окшош.

Ошентип, биз 1ден баштайбыз жана ал үчүн кичине же nге барабар болсо, DFSди аткарабыз.

Биз аларды 9га чейин бардык цифралар үчүн кайталайбыз, андан кийин DFS натыйжаларын сактап, басып чыгарабыз.

Лексикографиялык сандар Leetcode чечими

ишке ашыруу

Лексикографиялык сандар үчүн 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]

Лексикографиялык сандар үчүн Java коду

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 Solution

Убакыттын татаалдыгы

Жогорудагы коддун убакыттын татаалдыгы O (N) анткени биз элементтерди бир гана жолу кыдырып жатабыз. Бул жерде n берилген маани.

Космостун татаалдыгы

Жогорудагы коддун мейкиндик татаалдыгы O (журнал (ч)) анткени биз DFS колдонуп жатабыз. Бул жерде h - DFS дарагынын бийиктиги.

шилтемелер