题解 | #火车进站#

火车进站

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

解题思路

这是一个典型的栈应用问题,可以使用DFS(深度优先搜索)来解决:

  1. 对于每一列火车,在任意时刻都有两种选择:

    • 如果还有火车未进站,可以让一列火车进站
    • 如果站内有火车,可以让一列火车出站
  2. 使用递归来模拟这个过程:

    • 维护一个栈来表示站内的火车
    • 记录已经进站的火车数量和已经出站的火车序列
    • 当所有火车都出站后,得到一个有效的出站序列
  3. 为了保证字典序输出:

    • 使用 setvector 存储所有可能的出站序列
    • 最后按字典序排序输出

代码

#include <iostream>
#include <vector>
#include <stack>
#include <set>
using namespace std;

void dfs(vector<int>& in_seq, stack<int>& station, vector<int>& out_seq, set<string>& result, int pos) {
    if (pos == in_seq.size() && station.empty()) {
        string s;
        for (int i = 0; i < out_seq.size(); i++) {
            if (i > 0) s += " ";
            s += to_string(out_seq[i]);
        }
        result.insert(s);
        return;
    }
    
    // 选择让火车进站
    if (pos < in_seq.size()) {
        station.push(in_seq[pos]);
        dfs(in_seq, station, out_seq, result, pos + 1);
        station.pop();
    }
    
    // 选择让火车出站
    if (!station.empty()) {
        int temp = station.top();
        station.pop();
        out_seq.push_back(temp);
        dfs(in_seq, station, out_seq, result, pos);
        out_seq.pop_back();
        station.push(temp);
    }
}

int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    
    stack<int> station;
    vector<int> out_seq;
    set<string> result;
    
    dfs(nums, station, out_seq, result, 0);
    
    for (const string& s : result) {
        cout << s << endl;
    }
    
    return 0;
}
import java.util.*;

public class Main {
    private static void dfs(int[] in_seq, Stack<Integer> station, List<Integer> out_seq, 
                          Set<String> result, int pos) {
        if (pos == in_seq.length && station.isEmpty()) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < out_seq.size(); i++) {
                if (i > 0) sb.append(" ");
                sb.append(out_seq.get(i));
            }
            result.add(sb.toString());
            return;
        }
        
        // 选择让火车进站
        if (pos < in_seq.length) {
            station.push(in_seq[pos]);
            dfs(in_seq, station, out_seq, result, pos + 1);
            station.pop();
        }
        
        // 选择让火车出站
        if (!station.isEmpty()) {
            int temp = station.pop();
            out_seq.add(temp);
            dfs(in_seq, station, out_seq, result, pos);
            out_seq.remove(out_seq.size() - 1);
            station.push(temp);
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }
        
        Stack<Integer> station = new Stack<>();
        List<Integer> out_seq = new ArrayList<>();
        Set<String> result = new TreeSet<>();
        
        dfs(nums, station, out_seq, result, 0);
        
        for (String s : result) {
            System.out.println(s);
        }
    }
}
def dfs(in_seq, station, out_seq, result):
    if not in_seq and not station:  # 所有火车都已经出站
        result.add(' '.join(map(str, out_seq)))
        return
    
    # 选择让火车进站
    if in_seq:
        station.append(in_seq[0])
        dfs(in_seq[1:], station, out_seq, result)
        station.pop()
    
    # 选择让火车出站
    if station:
        out_seq.append(station[-1])
        temp = station.pop()
        dfs(in_seq, station, out_seq, result)
        station.append(temp)
        out_seq.pop()

def solve(n, nums):
    result = set()
    dfs(nums, [], [], result)
    return sorted(result)

# 处理输入
n = int(input())
nums = list(map(int, input().split()))

# 获取所有可能的出站序列并输出
for seq in solve(n, nums):
    print(seq)

算法及复杂度

  • 算法:DFS (深度优先搜索) + 栈
  • 时间复杂度: - 对于 列火车,每列火车都有进/出两种选择
  • 空间复杂度: - 需要一个栈来存储站内火车,以及递归调用栈的深度
全部评论

相关推荐

来个厂收我吧:首先,市场侧求职我不是很懂。 但是,如果hr把这份简历给我,我会觉得求职人不适合做产品经理。 问题点: 1,简历的字体格式不统一,排版不尽如人意 2,重点不突出,建议参考star法则写个人经历 3,印尼官方货币名称为印度尼西亚卢比(IDR),且GMV690000印尼盾换算为305人民币,总成交额不高。 4,右上角的意向职位在发给其他公司时记得删除。 5,你所有的经历都是新媒体运营,但是你要投市场营销岗位,jd和简历不匹配,建议用AI+提示词,参照多个jd改一下经历内容。 修改建议: 1,统一字体(中文:思源黑体或微软雅黑,英文数字:time new romans),在word中通过表格进行排版(b站学) 2,校招个人经历权重:实习经历=创业经历(大创另算)>项目经历>实训经历>校园经历 3,请将项目经历时间顺序改为倒序,最新的放最上方。 4,求职方向不同,简历文字描述侧重点也需要不同。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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