أرقام معجمية Leetcode الحل


مستوى الصعوبة متوسط
كثيرا ما يطلب في ByteDance
عمق البحث الأول

بيان المشكلة

في مشكلة "الأرقام المعجمية" لدينا رقم ن. مهمتنا هي طباعة الأرقام بين 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 إلى 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]

كود جافا للأرقام المعجمية

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 للأرقام المعجمية

تعقيد الوقت

التعقيد الزمني للشفرة أعلاه O (nlogn) لأننا نفرز السلاسل باستخدام سلسلة n. هنا n هو الرقم المعطى.

تعقيد الفضاء

تعقيد الفضاء من الكود أعلاه يا (1) لأننا نستخدم متغيرًا فقط لتخزين الإجابة.

نهج DFS لحل كود Leetcode للأرقام المعجمية

الفكرة بسيطة جدا. في كل مرة نبدأ برقم واحد من 1-9 ثم نواصل جمع الأرقام من 0 إلى 9 على هذه الأرقام طالما أنها أصغر من n. لذلك هذا هو بالضبط نفس خوارزمية Depth-First-Search.

لذلك سنبدأ بالرقم 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]

كود جافا للأرقام المعجمية

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 للأرقام المعجمية

تعقيد الوقت

التعقيد الزمني للشفرة أعلاه O (ن) لأننا نجتاز العناصر مرة واحدة فقط. هنا n هي القيمة المعطاة.

تعقيد الفضاء

تعقيد الفضاء من الكود أعلاه O (تسجيل (ح)) لأننا نستخدم DFS. هنا h هو ارتفاع شجرة DFS.

المراجع