2024.05.11 360春招WEB前端编程题

编程题第一题 探险

小X在一片大陆上探险，有一天他发现了一个洞穴，洞穴里面有n道门，打开每道门都需要对应的钥匙，编号为i的钥匙能用于打开第i道门，而且只有在打开了第i (i≥1)道门之后，才能打开第i+1道门，一开始只能打开第1道门。幸运的是，小X在外面探索的途中，每天都能发现一把能打开这n道门中其中一道门的钥匙，每天找完钥匙后他都会去打开所有能打开的门。现在给出他每天找到的钥匙编号，请问每道门分别在哪一天被打开。

输入：

第一行包含一个正整数n ，表示门的数量。

接下来一行包含n个正整数a1，a2，...，an，其中ai表示第i天他找到的钥匙的编号，能够打开第ai道门，数据保证a1-an为1-n的一个排列。

输出：

输出一行n个数s1，s2，...，sn，其中si表示第i道门在第si天被打开。

示例1：

输入：

5

[5, 3, 1, 2, 4]

输出：

[ 3, 4, 4, 5, 5 ]

var arr = []

var line

while ((line = gets(100000)) != "") {

arr.push(line.split(" "));

}

var keys = arr[1]

// var keys = [5, 3, 1, 2, 4]

var calculate = function (nums) {

let dp = Array.from({ length: nums.length + 1 }, () => 0)

dp[0] = -1

for (let i = 0; i < nums.length; i++) {

if (dp[nums[i] - 1] != 0) {

dp[nums[i]] = i + 1

let a = nums[i] + 1

while (dp[a] != 0 && a<=nums.length) {

dp[a] = i + 1

a++

}

}

else {

dp[nums[i]] = -1

}

}

return dp.slice(1,)

}

console.log(calculate(keys));

我的思路比较简单，就是用一个数组dp，表示对应索引index（第i个门）的钥匙是否已经出现，如果未出现就是0，出现了就是-1；

而判断第i道门能否打开，就是看它之前的门（第i-1道门）是否已经打开（题目：只有在打开了第i (i≥1)道门之后，才能打开第i+1道门），所以这里判断dp[i-1]是否==0（第i-1个钥匙是否出现）

因为一开始只能打开第1道门，所以dp[0]=-1;因为每天获取一把钥匙，所以钥匙在数组中的索引+1=第几天

在打开第i道门之后，还要判断第i+1个的钥匙是不是出现了？

这里使用while循环，一定要注意边界条件&& a<=nums.length，否则dp数组会一直往后无限循环。

（其实这是22年的360编程题了，我之前没有刷到过而已，并且承认自己真的不会在ACM模式写代码，菜就多练）