leetcode386. Lexicographical Numbers

cppprimer 發(fā)布于2019-08-19 11:33 / 1114人閱讀

題目要求

Given an integer n, return 1 - n in lexicographical order.

For example, given 13, return: [1,10,11,12,13,2,3,4,5,6,7,8,9].

Please optimize your algorithm to use less time and space. The input size may be as large as 5,000,000.

將1~n這n個數(shù)字按照字母序排序，并返回排序后的結(jié)果。
即如果n=13，則1~13的字母序為1,10,11,12,13,2,3,4,5,6,7,8,9

思路和代碼

這題其實要求我們將數(shù)字是做字母來進行排序，因此當我們排序的時候可以看到，假如已知當前的數(shù)字為i，則它首先后一位數(shù)字應當是(i x 10)，如果(i x 10)大于n，再考慮i+1, 如果i+1也大于n，此時再考慮(i/10)+1。

    public List lexicalOrder(int n) {
        List result = new ArrayList();
        for(int i = 1 ; i<=9 ; i++) {
            lexicalOrder(n, i, result);
        }
        return result;
    }
    
    public void lexicalOrder(int n, int cur, List result) {
        if(cur > n) return;
        result.add(cur);
        for(int i = 0 ; i <=9 ; i++) {
            lexicalOrder(n, cur*10+i, result);
        }
    }

想要了解更多開發(fā)技術，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關注我的微信公眾號！將會不定期的發(fā)放福利哦~

云服務器 GPU云服務器 Lexicographical Numbers i386 linux linux i386

文章版權歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/yun/77444.html

[LintCode] Permutation Index I & Permutation I

摘要：我覺得雖然在里分類是，但其實是一道難題。思路如下搞一個哈希表，存儲數(shù)組中每一位的后面小于它的數(shù)的個數(shù)。與上一題的不同之處時會有重復的數(shù)。當然，每個重復數(shù)的都要階乘，例如有個，個，就是。是所有排列的次數(shù)和，返回下一次。 Permutation Index Problem Given a permutation which contains no repeated number, find...

lucas 2019-08-14 16:23 評論0 收藏0
LeetCode[316] Remove Duplicate Letters

摘要：復雜度思路用一個每次考慮當前的字符大小和的頂端字符的大小，如果當前字符比較小的話，則可以出頂端的字符，將當前的字符放進中。需要維持了一個判斷當前字符在剩余字符串中的出現(xiàn)次數(shù)，考慮能否將這個字符從棧中彈出。 LeetCode[316] Remove Duplicate Letters Given a string which contains only lowercase letter...

tomorrowwu 2019-08-14 15:04 評論0 收藏0
[LeetCode] 953. Verifying an Alien Dictionary

Problem In an alien language, surprisingly they also use english lowercase letters, but possibly in a different order. The order of the alphabet is some permutation of lowercase letters. Given a seque...

ghnor 2019-08-16 13:57 評論0 收藏0
leetcode17 Letter Combinations of a Phone Number

摘要：題目要求也就是說，將數(shù)字對應的字母的排列組合的的所有可能結(jié)果都枚舉出來，順序不唯一。這種類型的題目一般需要求出上一種情況的前提下才可以得知下一種情況。這一種數(shù)據(jù)結(jié)構(gòu)通過來實現(xiàn)。相比于上一種思路中，內(nèi)存占用更小，而且更加靈活。題目要求 Given a digit string, return all possible letter combinations that the numbe...

snowell 2019-08-14 18:09 評論0 收藏0
[LintCode/LeetCode] Remove Duplicate Letters

Problem Given a string which contains only lowercase letters, remove duplicate letters so that every letter appear once and only once. You must make sure your result is the smallest in lexicographical...

wanghui 2019-08-15 18:01 評論0 收藏0