leetcode386. Lexicographical Numbers

cppprimer 发布于2019-08-19 11:33 / 954人阅读

题目要求

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个数字按照字母序排序，并返回排序后的结果。
即如果n=13，则1~13的字母序为1,10,11,12,13,2,3,4,5,6,7,8,9

思路和代码

这题其实要求我们将数字是做字母来进行排序，因此当我们排序的时候可以看到，假如已知当前的数字为i，则它首先后一位数字应当是(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);
        }
    }

想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~

服务器托管专线服务 Lexicographical Numbers i386 linux linux i386

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/77444.html

[LintCode] Permutation Index I & Permutation I

摘要：我觉得虽然在里分类是，但其实是一道难题。思路如下搞一个哈希表，存储数组中每一位的后面小于它的数的个数。与上一题的不同之处时会有重复的数。当然，每个重复数的都要阶乘，例如有个，个，就是。是所有排列的次数和，返回下一次。 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

摘要：复杂度思路用一个每次考虑当前的字符大小和的顶端字符的大小，如果当前字符比较小的话，则可以出顶端的字符，将当前的字符放进中。需要维持了一个判断当前字符在剩余字符串中的出现次数，考虑能否将这个字符从栈中弹出。 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

摘要：题目要求也就是说，将数字对应的字母的排列组合的的所有可能结果都枚举出来，顺序不唯一。这种类型的题目一般需要求出上一种情况的前提下才可以得知下一种情况。这一种数据结构通过来实现。相比于上一种思路中，内存占用更小，而且更加灵活。题目要求 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