题解 | #字典序排列#

import java.util.*;

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

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

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

        dfs(trie, "");

        return result;
    }

    /**
     * 递归: 前序遍历
     * @param trie
     * @param word
     */
    private void dfs(Trie trie, String word){
        if(trie == null){
            return;
        }

        if(trie.isEnd){
            result.add(Integer.valueOf(word));
        }

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

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

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

        public void insert(String word) {
            Trie node = this;
            for (int i = 0; i < word.length(); i++) {
                char ch = word.charAt(i);
                int index = ch - '0';
                if (node.children[index] == null) {
                    node.children[index] = new Trie();
                }
                node = node.children[index];
            }
            node.isEnd = true;
        }
    }

    /**
     * 迭代
     * @param n
     * @return
     */
    public ArrayList<Integer> solution2(int n) {
        int number = 1;
        for (int i = 1; i <= n; i++) {
            result.add(number);
            if (number * 10 <= n) {
                number *= 10;
            } else {
                while (number % 10 == 9 || number + 1 > n) {
                    number /= 10;
                }
                number++;
            }
        }
        return result;
    }

    /**
     * dfs
     * @param n
     * @return
     */
    public ArrayList<Integer> solution3(int n) {
        // first digit: 1-9
        for(int i=1; i<10; i++){
            dfs(i, n);
        }

        return result;
    }

    /**
     * 递归: 前序遍历
     * @param num
     * @param n
     */
    public void dfs(int num, int n){
        if(num > n){
            return;
        }

        result.add(num);

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