java如何實現字典序排數

這篇文章主要為大家展示了java如何實現字典序排數，內容簡而易懂，條理清晰，希望能夠幫助大家解決疑惑，下面讓小編帶大家一起來研究并學習一下“java如何實現字典序排數”這篇文章吧。

給定一個整數 n, 返回從 1 到 n 的字典順序。

例如，

給定 n =13，返回 [1,10,11,12,13,2,3,4,5,6,7,8,9] 。

請盡可能的優(yōu)化算法的時間復雜度和空間復雜度。輸入的數據 n 小于等于 5,000,000。

答案：

 1public List<Integer> lexicalOrder(int n) {
 2    List<Integer> res = new ArrayList<>();
 3    for (int i = 1; i < 10; ++i) {
 4        dfs(i, n, res);
 5    }
 6    return res;
 7}
 8
 9public void dfs(int cur, int n, List<Integer> res) {
10    if (cur > n)
11        return;
12    res.add(cur);
13    for (int i = 0; i < 10; ++i) {
14        dfs(10 * cur + i, n, res);
15    }
16}

解析：

解這題之前實現要明白什么是字典序，其實就是類似于字典一樣，根據字母的順序進行排列，我們先來看下面的圖

我們可以把它看成有9棵樹，每棵樹的根節(jié)點的值分別是從1到9，并且每棵樹都有10個子節(jié)點，并且每個子節(jié)點又會有10個子節(jié)點……

1，代碼3到5行分別遍歷這9棵樹。

2，方法dfs對每棵樹執(zhí)行dfs（深度優(yōu)先搜索），關于樹的深度優(yōu)先搜索可以參考前面介紹過的304，完全二叉樹的節(jié)點個數這道題第二種解法使用的就是深度優(yōu)先搜索（dfs）

我們仔細觀察上面的圖，字典序排數有一個規(guī)律，比如當n等于300的時候，結果是下面這樣的

我們可以觀察上面的數字，也可以查看最上面的圖，就會發(fā)現這樣一個規(guī)律。當數字curr小于n的時候，只要curr的個位數是9，那么他的下一個數就是(curr/10)+1（但要保證curr/10的個位數不能是9，如果是9就繼續(xù)執(zhí)行curr/10，直到curr/10的個位數不是9為止，比如199的下一個數是2），比如109的下一個是11，129的下一個是13一樣。如果curr等于n，那么他的下一個數也是和上面同樣的操作。理解了這點，代碼就很容易寫出來了

 1public List<Integer> lexicalOrder(int n) {
 2    List<Integer> ans = new ArrayList<>(n);
 3    int curr = 1;
 4    for (int i = 1; i <= n; ++i) {
 5        ans.add(curr);
 6        if (curr * 10 <= n) {
 7            curr *= 10;
 8        } else {
 9            while (curr % 10 == 9 || curr == n)
10                curr /= 10;
11            curr++;
12        }
13    }
14    return ans;
15}

重點是在第9到10行，如果curr的個位數是9或者curr等于n就要執(zhí)行curr/10這步操作，直到curr的個位數不是9為止。

Java的優(yōu)點是什么

1. 簡單，只需理解基本的概念，就可以編寫適合于各種情況的應用程序；2. 面向對象；3. 分布性，Java是面向網絡的語言；4. 魯棒性，java提供自動垃圾收集來進行內存管理，防止程序員在管理內存時容易產生的錯誤。；5. 安全性，用于網絡、分布環(huán)境下的Java必須防止病毒的入侵。6. 體系結構中立，只要安裝了Java運行時系統(tǒng)，就可在任意處理器上運行。7. 可移植性，Java可以方便地移植到網絡上的不同機器。8.解釋執(zhí)行，Java解釋器直接對Java字節(jié)碼進行解釋執(zhí)行。

以上就是關于“java如何實現字典序排數”的內容，如果該文章對您有所幫助并覺得寫得不錯，勞請分享給您的好友一起學習新知識，若想了解更多相關知識內容，請多多關注億速云行業(yè)資訊頻道。