java如何實現(xiàn)字典序排數(shù)

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

創(chuàng)新互聯(lián)主要從事做網(wǎng)站、網(wǎng)站設計、網(wǎng)頁設計、企業(yè)做網(wǎng)站、公司建網(wǎng)站等業(yè)務。立足成都服務包河,十多年網(wǎng)站建設經(jīng)驗,價格優(yōu)惠、服務專業(yè),歡迎來電咨詢建站服務:028-86922220

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

例如，

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

請盡可能的優(yōu)化算法的時間復雜度和空間復雜度。輸入的數(shù)據(jù) 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}

解析：

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

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

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

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

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

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

 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的個位數(shù)是9或者curr等于n就要執(zhí)行curr/10這步操作，直到curr的個位數(shù)不是9為止。

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

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

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

分享標題：java如何實現(xiàn)字典序排數(shù)
鏈接分享：http://muchs.cn/article40/gpjeho.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供軟件開發(fā)、網(wǎng)站導航、網(wǎng)站設計公司、品牌網(wǎng)站設計、靜態(tài)網(wǎng)站、建站公司

廣告

聲明：本網(wǎng)站發(fā)布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經(jīng)允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯(lián)