牛客NC362 字典序排列【中等 DFS Java/Go/PHP】

题目

题目链接：
https://www.nowcoder.com/practice/de49cf70277048518314fbdcaba9b42c

解题方法

DFS，剪枝

Java代码

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型
     * @return int整型ArrayList
     */
    public ArrayList<Integer> orderArray (int n) {
        //DFS  注意剪枝
        ArrayList<Integer> ans = new ArrayList<>();

        int end = 9;
        if (n < 9) {
            end = n;
        }

        for (int i = 1; i <= end ; i++) {
            dfs(i, n, ans);
        }
        return ans;
    }

    public void dfs(int cur, int n, ArrayList<Integer> ans) {
        if (cur > n) return;

        ans.add(cur);

        for (int i = 0; i <= 9 ; i++) {
            int num = cur * 10 + i;
            if (num > n) //剪枝
                break;
            dfs(num, n, ans);
        }
    }
}

Go代码

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param n int整型
 * @return int整型一维数组
 */
func orderArray(n int) []int {
		//dfs,注意剪枝
	ans := []int{}
	end := 9
	if n < end {
		end = n
	}

	for i := 1; i <= end; i++ {
		dfs(i, n, &ans)
	}
	return ans
}

func dfs(cur, n int, ans *[]int) {
	if cur > n {
		return
	}

	*ans = append(*ans, cur)
	for i := 0; i <= 9; i++ {
		num := cur*10 + i
		if cur > n { //剪枝 很重要
			break
		}

		dfs(num, n, ans)
	}
}

PHP代码

<?php


/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param n int整型 
 * @return int整型一维数组
 */
function orderArray( $n )
{
   // dfs+剪枝
    $ans = [];

    $end = 9;
    if($n<9){
        $end= $n;
    }

    for($i=1;$i<=$end;$i++){
        dfs($i,$n,$ans);
    }
    return $ans;
}

function dfs($cur,$n,&$ans){
    if($cur>$n){
        return;
    }

    $ans[count($ans)] = $cur;

    for($i=0;$i<=9;$i++){
        $num = $cur*10+$i;

        if($num > $n) break; //剪枝，非常关键

        dfs($num,$n,$ans);
    }
}