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

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

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

例如，

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

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

解析：

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

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

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

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

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

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

 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}

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

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

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

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

分享標(biāo)題：java如何實(shí)現(xiàn)字典序排數(shù)
鏈接分享：http://aaarwkj.com/article40/gpjeho.html

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

廣告

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