牛客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 := 9if 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 + iif 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);}
}