מספרים לקסיקוגרפיים פתרון Leetcode  


רמת קושי בינוני
נשאל לעתים קרובות Byte
אלגוריתמים קידוד עומק חיפוש ראשון ראיון אישי הוכחת ראיונות 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 ל- 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  

מורכבות זמן

מורכבות הזמן של הקוד הנ"ל היא O (nlogn) כי אנחנו ממיינים את המיתרים עם מחרוזת n. כאן n הוא המספר הנתון.

ראה גם
בעיית הכנאפה

מורכבות חלל

מורכבות החלל של הקוד הנ"ל היא O (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  

מורכבות זמן

מורכבות הזמן של הקוד הנ"ל היא O (n) כי אנחנו חוצים את האלמנטים רק פעם אחת. כאן n הוא הערך הנתון.

ראה גם
מעבר אלכסוני של עץ בינארי

מורכבות חלל

מורכבות החלל של הקוד הנ"ל היא O (יומן (h)) כי אנחנו משתמשים ב- DFS. הנה h הוא גובה עץ DFS.

הפניות