字典序排列

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;
        }
    }
}

//数字首位是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);
        }
    }

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;
    }
}