字典序排列

import java.util.*;

/**
 * NC362 字典序排列
 * @author d3y1
 */
public class Solution {
    ArrayList<Integer> list = new ArrayList<>();

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型
     * @return int整型ArrayList
     */
    public ArrayList<Integer> orderArray (int n) {
        // return solution1(n);
        // return solution2(n);
        // return solution3(n);
        // return solution33(n);
        return solution4(n);
    }

    /**
     * 迭代
     * @param n
     * @return
     */
    private ArrayList<Integer> solution1(int n){
        int num = 1;
        // i: 插入次数(也即正整数个数)
        for(int i=1; i<=n; i++){
            list.add(num);
            if(num*10 <= n){
                num = num*10;
            }else{
                // test case: 20
                while(num%10==9 || num+1>n){
                    num = num/10;
                }
                num = num+1;
            }
        }

        return list;
    }

    /**
     * 小根堆
     * @param n
     * @return
     */
    private ArrayList<Integer> solution2(int n){
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(Comparator.comparing(String::valueOf));

        // 小根堆: 按字典序排序
        for(int num=1; num<=n; num++){
            minHeap.offer(num);
        }

        while(!minHeap.isEmpty()){
            list.add(minHeap.poll());
        }

        return list;
    }

    /**
     * 递归
     * @param n
     * @return
     */
    private ArrayList<Integer> solution3(int n){
        for(int i=1; i<=9; i++){
            dfs(i, n);
        }
        return list;
    }

    private void dfs(int num, int n){
        if(num > n){
            return;
        }

        list.add(num);

        for(int i=0; i<=9; i++){
            dfs(num*10+i, n);
        }
    }

    /**
     * 递归: 优化
     * @param n
     * @return
     */
    private ArrayList<Integer> solution33(int n){
        for(int i=1; i<=9; i++){
            DFS(i, n);
        }
        return list;
    }

    private boolean DFS(int num, int n){
        if(num > n){
            return false;
        }

        list.add(num);

        for(int i=0; i<=9; i++){
            if(!DFS(num*10+i, n)){
                break;
            }
        }

        return true;
    }

    /**
     * Trie(字典树/前缀树)
     * @param n
     * @return
     */
    private ArrayList<Integer> solution4(int n){
        Trie trie = new Trie();
        for(int num=1; num<=n; num++){
            trie.insert(String.valueOf(num));
        }

        preOrder(trie, "");

        return list;
    }

    /**
     * 递归: 类似树的前序遍历
     * @param trie
     * @param num
     */
    private void preOrder(Trie trie, String num){
        if(trie == null){
            return;
        }

        if(trie.isEnd){
            list.add(Integer.parseInt(num));
        }

        for(int i=0; i<=9; i++){
            preOrder(trie.children[i], num+i);
        }
    }

    /**
     * Trie类
     */
    private class Trie {
        private Trie[] children;
        private boolean isEnd;

        public Trie(){
            this.children = new Trie[10];
            this.isEnd = false;
        }

        public void insert(String num){
            Trie curr = this;
            int idx;
            for(char digit: num.toCharArray()){
                idx = digit-'0';
                if(curr.children[idx] == null){
                    curr.children[idx] = new Trie();
                }
                curr = curr.children[idx];
            }
            curr.isEnd = true;
        }
    }
}

#include <algorithm>
#include <map>
#include <string>
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型vector
     */
    vector<int> orderArray(int n) {
        // write code here
        map<string, int>Hash;
        for(int i=0; i<n;i++)
        {
            string str;
            str = to_string(i+1);
            Hash[str] = i+1;
        }
        vector<int> output;
        for (auto item: Hash)
            output.push_back(item.second);
        return output;    
    }
};

package main

import "sort"
import "strconv"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param n int整型
 * @return int整型一维数组
 */
func orderArray(n int) []int {
	arr := make([]int, n)
	for i, _ := range arr {
		arr[i] = i + 1
	}
	sort.Slice(arr, func(i, j int) bool {
		return strconv.Itoa(arr[i]) < strconv.Itoa(arr[j])
	})
	return arr
}

//数字首位是1或者2、3、4...，分成9个大的层次，字典序排列就是分别从每一层次向后排列到底（此处范围判定只有是否超过n这个条件），然后再排列下一层次的数据，属于深度优先搜索
ArrayList<Integer> list = new ArrayList<>();
    public ArrayList<Integer> orderArray (int n) {
                //判断n小于10时，就是简单的顺序排列，这步其实可以不要
        if(n<10){
            for(int i=1;i<=n;i++){
                list.add(i);
            }
        }else{
            for(int i=1;i<10;i++){
                dfs(i,n);
            }
        }
        return list;
    }
    public void dfs(int num,int n){
                //边界判定，每个层次的数据是否超过n，超过就返回不排列
        if(num > n){
            return;
        }
        list.add(num);
        for(int i=0;i<10;i++){
            dfs(num*10+i,n);
        }
    }

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型vector
     */
    static bool cmp(int a, int b){
        string A = to_string(a);
        string B = to_string(b);
        return A < B;
    }
    vector<int> orderArray(int n) {
        // write code here
        vector<int> v;
        for(int i=1; i<=n; i++){
            v.push_back(i);
        }
        sort(v.begin(), v.end(), cmp);
        return v;
    }
};

# -*- coding: utf-8 -*-


#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param n int整型
# @return int整型一维数组
#
class Solution1:
    """
    题目：
        https://www.nowcoder.com/practice/de49cf70277048518314fbdcaba9b42c?tpId=196&tqId=40452&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3FjudgeStatus%3D3%26page%3D1%26pageSize%3D50%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=3&tags=&title=
    算法：
        字符串排序
    复杂度：
        时间复杂度：O(nlogn)
        空间复杂度：O(n)
    """

    def orderArray(self, n):
        # write code here
        strNums = [str(i) for i in range(1, n + 1)]

        strNums.sort()

        return map(int, strNums)


class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/de49cf70277048518314fbdcaba9b42c?tpId=196&tqId=40452&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3FjudgeStatus%3D3%26page%3D1%26pageSize%3D50%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=3&tags=&title=
    参考：
        大神：唐喻铭
    算法：
        字典树
        初始：num = 1
        按照字典序规律：1 -> 10 -> 100 ...直到大于n时，从*10变为+1操作，这里需要注意的是：如果个位数是9，那么再+1，就需要进位，比如9 + 1 -> 2；或者num + 1 > n，也需要进位处理
        比如n = 28：
        1,10,11,12,13,...,19 下一个数组为2，而不是20
        1,10,11,...,19,2,20,21,...,28 下一个数字为3，而不是29
    复杂度：
        时间复杂度：O(n)
        空间复杂度：O(1)
    """

    def orderArray(self, n):
        # write code here
        res, num = [], 1

        for i in range(n):
            res.append(num)
            if num * 10 <= n:
                num *= 10
            else:
                while num % 10 == 9&nbs***bsp;num + 1 > n:
                    num /= 10
                num += 1

        return res


if __name__ == "__main__":
    sol = Solution()

    # n = 5

    # n = 10

    n = 28

    res = sol.orderArray(n)

    print res

import java.util.*;
public class Solution {
    //如果num*10后比n小，那么num*10就是下一个要放入list中的数
    //如果num*10后比n大，那么就num++，其结果就是下一个要放入list中的数
    //如果num的个位数为9或者num+1>n，说明需要进行进位操作，num=num/10,num++
    //比如n为28
    //num=19的话，就需要进位，即num/10后的结果加一，下一位数2
    //num=28的话，也需要进位，即num/10后的结果加一，下一位数3
    //一共需要向list中添加n次数字
    public ArrayList<Integer> orderArray (int n) {
        ArrayList<Integer> list = new ArrayList<>();
        int num = 1;
        for(int i = 0;i < n;i ++) {
            list.add(num);
            if(num * 10 <= n) {
                num *= 10;
            }else {
                while((num % 10 == 9) || (num + 1 > n)) {
                    num /= 10;
                }
                num ++;
            }
        }
        return list;
    }
}