题解 | #火车进站#

火车进站

https://www.nowcoder.com/practice/97ba57c35e9f4749826dc3befaeae109

这道题还是比较难的, 我最先开始想的也是递归, 广度就是入栈和出栈, 但是做的事情不一样, 所以无从下笔. 鼓捣一阵无果后查看答案发现了两点, 广度是进栈和出栈, 但是返回到原函数需要还原, 入栈元素的下标用i表示, 深度和结束条件相关, 就是所有元素出栈完了, 出栈了arr.length()次的时候返回原函数, 结束递归

import java.util.*;

public class Main
{
    public static ArrayList<String> list = new ArrayList<>();
    public static StringBuilder sb = new StringBuilder();
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        Stack<Integer> stack = new Stack<>();
        int n = sc.nextInt();
        int []arr = new int[n];
        for (int i = 0; i < n; i++)
        {
            arr[i] = sc.nextInt();
        }
        recursion(0,0,arr,stack);
        Collections.sort(list);
        for (String i: list)
        {
            System.out.println(i);
        }
    }
//1   2   3
    public static void recursion( int len, int i, int []arr ,Stack<Integer> stack  )
    {
        if(len == arr.length)
        {
            list.add(sb.toString());
            return;
        }
        //出栈
        if( !stack.isEmpty())
        {
            int k = stack.pop();
            sb.append(k+" ");
            recursion(len+1,i,arr,stack);
            stack.push(k);
            sb.delete(sb.length()-2, sb.length());

            //sb.deleteCharAt(sb.length()-1);
        }
        //入栈
        if(i< arr.length)
        {
            stack.push(arr[i]);
            recursion(len,i+1,arr,stack);
            stack.pop();
        }
    }
}




华为机试题解 文章被收录于专栏

华为机试题解

全部评论

相关推荐

点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-07 12:04
毕业生招你惹你了,问一个发薪日来一句别看网上乱七八糟的你看哪个工作没有固定发薪日扭头就取消了面试就问了一句公司都是这个态度吗还搞上人身攻击了...
程序员小白条:呃呃呃,都还没面试,我都不会问这么细,何况通不通过,去不去都另说,你没实力和学历的话,在外面就这样,说实话没直接已读不回就不错了,浪费时间基本上
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务