题解 | #火车进站II#
火车进站
http://www.nowcoder.com/practice/97ba57c35e9f4749826dc3befaeae109
// 多行输入
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
const inputArr = [];//存放输入的数据
rl.on('line', function (line) {
//line是输入的每一行，为字符串格式
inputArr.push(line.split(' ').map(item => Number(item)));//将输入流保存到inputArr中（用map将字符串数组转为数字）
}).on('close', function () {
let res = fun(inputArr)//调用函数
res.forEach(item => console.log(item.join(' '))) //打印结果
})
//解决函数
function fun(arr) {
let N = arr[0][0];
let train = arr[1].concat(); //未进站的火车
let res = []; //输出的结果
let station = [] //站台栈内的火车
let outStation = [] //发出的火车
let backtrace = (train, station, outStation) => {
if (outStation.length == N) {
res.push([...outStation])
return;
}
if (station.length == 0 && train.length != 0) {
// 如果车站为空且未进站的火车不为空，则进站
station.push(train.shift())
backtrace(train, station, outStation)
} else if (station.length != 0 && train.length == 0) {
// 如果车站不为空，且没有未进站的火车，则顺序出站
outStation.push(station.pop())
backtrace(train, station, outStation)
} else if (station.length != 0 && train.length != 0) {
// 如果车站不为空，且还有未进站的火车，则可以选择1.出站，2.进站,并回溯
let temp1 = [...outStation];
let temp2 = [...station];
let temp3 = [...train]
// 出站
outStation.push(station.pop())
backtrace(train, station, outStation)
// 回溯
outStation = temp1;
station = temp2;
train = temp3;
// 进站
station.push(train.shift())
backtrace(train, station, outStation)
}
}
backtrace(train, station, outStation)
return res.sort((a, b) => a.join('') - b.join(''))
}
