Լեքսիկոգրաֆիկ համարներ 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 լուծում  

Խնդիրը լուծելու համար կոպիտ ուժի մոտեցումը հետևյալն է.

  1. 1-ի միջև եղած բոլոր դրական ամբողջ թվերը վերափոխեք տողերի:
  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 լուծում  

Timeամանակի բարդությունը

Վերոնշյալ ծածկագրի ժամանակի բարդությունն է O (nlogn) քանի որ մենք տողերը տեսակավորում ենք n լարով: Այստեղ n տրված թիվն է:

Տես նաեւ,
Պայուսակի խնդիրը

Տիեզերական բարդություն

Վերոնշյալ ծածկագրի տիեզերական բարդությունն է Ո (1) քանի որ մենք պատասխանը պահելու համար օգտագործում ենք միայն փոփոխական:

DFS մոտեցում բառարանագրական համարների համար Leetcode լուծում  

Գաղափարը բավականին պարզ է: Ամեն անգամ, երբ մենք սկսում ենք 1-9-ի մեկ նիշը և այնուհետև շարունակում ենք 0-9 թվանշաններ ավելացնել այդ թվերի վրա, քանի դեռ n- ից փոքր է: Այսպիսով, սա ճիշտ նույնն է, ինչ խորության առաջին որոնման ալգորիթմը:

Այսպիսով, մենք կսկսենք 1-ով և կկատարենք DFS դրա համար, քանի դեռ այն փոքր է կամ հավասար է n- ին:

Մենք դրանք կկրկնենք բոլոր թվանշանների համար մինչև 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 լուծում  

Timeամանակի բարդությունը

Վերոնշյալ ծածկագրի ժամանակի բարդությունն է O (n) քանի որ մենք միայն մեկ անգամ ենք անցնում տարրերը: Այստեղ n տրված արժեքն է:

Տես նաեւ,
Երկուական ծառի անկյունագծային անցում

Տիեզերական բարդություն

Վերոնշյալ ծածկագրի տիեզերական բարդությունն է O (տեղեկամատյան (h)) քանի որ մենք օգտագործում ենք DFS: Այստեղ h- ը DFS ծառի բարձրությունն է:

Սայլակ