Lexicographical နံပါတ်များ Leetcode ဖြေရှင်းချက်


ခက်ခဲအဆင့် အလယ်အလတ်
မကြာခဏမေးတယ် ByteDance
အနက်ရောင်ပထမရှာဖွေမှု

ပြstatementနာကြေညာချက်

ပြLexနာမှာ“ Lexicographical နံပါတ်များ” ဆိုတဲ့နံပါတ်ကို n ပေးထားတယ်။ ကျွန်ုပ်တို့၏တာ ၀ န်သည်နံပါတ်များ ၁ နှင့် 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] ဖြစ်သည်။

Lexicographic နံပါတ်များအတွက် Brute Force ချဉ်းကပ်မှု Leetcode Solution

ပြtheနာကိုဖြေရှင်းရန် Brute Force ချဉ်းကပ်မှုမှာအောက်ပါအတိုင်းဖြစ်သည်။

  1. 1 မှ n သို့အပေါင်းအပြုသဘောကိန်းဂဏန်းအားလုံးကို string သို့ပြောင်းပါ။
  2. ကြိုးတွေကိုစီပါ။ ဒီနံပါတ်များကို lexicographical နိုင်ရန်အတွက်စီစဉ်ပါလိမ့်မယ်။
  3. နောက်တစ်ခုက sorted strings တွေကို integer အဖြစ်ပြန်ပြောင်းပြီးတော့ရလဒ်ကိုပေးပါလိမ့်မယ်။

အကောင်အထည်ဖော်ရေး

Lexicographical နံပါတ်များအတွက် 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]

Lexicographical နံပါတ်များအတွက်ဂျာဗားကုဒ်

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]

Lexicographical နံပါတ်များ Leetcode ဖြေရှင်းချက်၏ရှုပ်ထွေးအားသုံးသပ်ခြင်း

အချိန်ရှုပ်ထွေး

အထက်ပါကုဒ်၏အချိန်ရှုပ်ထွေးသည် အို (လူသစ်) ဘာလို့လဲဆိုတော့ကျွန်တော်တို့ဟာ string တွေကို n string နဲ့ sorting လုပ်နေကြလို့ပါ။ ဒီမှာ n ကပေးထားတဲ့နံပါတ်ပါ။

အာကာသရှုပ်ထွေးမှု

အပေါ်ကကုဒ်ရဲ့ရှုပ်ထွေးမှုက အို (၁) ဘာလို့လဲဆိုတော့ငါတို့ကအဖြေကိုသိမ်းဖို့ variable တစ်ခုပဲသုံးတယ်။

Lexicographical နံပါတ်များ Leetcode Solution အတွက် DFS ချဉ်းကပ်မှု

စိတ်ကူးကတော်တော်လေးရိုးရှင်းပါတယ် 1-9 မှဂဏန်းတစ်ခုဖြင့်စတင်တိုင်း n သည်သေးငယ် သ၍ 0 to 9 မှဂဏန်းများကိုဆက်ထည့်သည်။ ဒီတော့ဒါက Depth-First-Search algorithm နဲ့အတူတူပဲ။

ထို့ကြောင့်ကျွန်ုပ်တို့သည် 1 ဖြင့်စတင်မည်ဖြစ်ပြီး၎င်းသည်သေးငယ်သည်သို့မဟုတ် n နှင့်ညီမျှနေသမျှကာလပတ်လုံး DFS ကိုလုပ်ဆောင်လိမ့်မည်။

ဂဏန်း ၉ လုံးအထိ ၉ လုံးအထိဒီဟာကိုပြန်လုပ်ပြီးရင် DFS ရလဒ်ကိုသိမ်းပြီးပုံနှိပ်ပါ။

Lexicographical နံပါတ်များ Leetcode ဖြေရှင်းချက်

အကောင်အထည်ဖော်ရေး

Lexicographical နံပါတ်များအတွက် 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]

Lexicographical နံပါတ်များအတွက်ဂျာဗားကုဒ်

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]

Lexicographical နံပါတ်များ Leetcode ဖြေရှင်းချက်၏ရှုပ်ထွေးအားသုံးသပ်ခြင်း

အချိန်ရှုပ်ထွေး

အထက်ပါကုဒ်၏အချိန်ရှုပ်ထွေးသည် အို (ဎ) ဘာလို့လဲဆိုတော့ကျွန်တော်တို့ကဒြပ်စင်တွေကိုတစ်ကြိမ်သာဖြတ်သန်းနေလို့ပါ။ ဒီမှာ n ကပေးထားတဲ့တန်ဖိုးပါ။

အာကာသရှုပ်ထွေးမှု

အပေါ်ကကုဒ်ရဲ့ရှုပ်ထွေးမှုက အို (မှတ်တမ်း (ဇ)) ဘာလို့လဲဆိုတော့ငါတို့ DFS ကိုသုံးနေလို့ပါ။ ဤတွင် h DFS သစ်ပင်၏အမြင့်သည်။

ကိုးကား