首页 > 试题广场 >

用栈操作构建数组

[编程题]用栈操作构建数组

热度指数：209 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给你一个目标数组 target 和一个整数 n。每次迭代，需要从 list = {1,2,3..., n} 中依序读取一个数字。

请使用下述操作来构建目标数组 target ：

Push：从 list 中读取一个新元素，并将其推入数组中。
Pop：删除数组中的最后一个元素。
如果目标数组构建完成，就停止读取更多元素。

题目数据保证目标数组严格递增，并且只包含 1 到 n 之间的数字。

请返回构建目标数组所用的操作序列。

题目数据保证答案是唯一的。

示例1

输入

[1,3],3

输出

["Push","Push","Pop","Push"]

说明

读取 1 并自动推入数组 -> [1]
读取 2 并自动推入数组，然后删除它 -> [1]
读取 3 并自动推入数组 -> [1,3]

示例2

输入

[1,2,3], 3

输出

["Push","Push","Push"]

示例3

输入

[1,2],4

输出

["Push","Push"]

说明

只需要读取前 2 个数字就可以停止。

示例4

输入

[2,3,4],4

输出

["Push","Pop","Push","Push","Push"]

算法知识视频讲解

Zero′

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * @param target int整型一维数组
 * @param n int整型
 * @return string字符串一维数组
 */
// 模拟栈
function buildArray( t ,  n ) {
    let stk = []
    let ans = []
    for(let i=1, j=0;i<=n;i++) {
        stk.push(i)
        ans.push('Push')
        if(stk[stk.length-1] != t[j]) {
            stk.pop()
            ans.push('Pop')
        }
        else j++
    }
    return ans
}
module.exports = {
    buildArray : buildArray
};

发表于 2021-01-24 16:41:01 回复(1)

Mirko_996

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# @param target int整型一维数组
# @param n int整型
# @return string字符串一维数组
#
class Solution:
    def buildArray(self , target , n ):
        # write code here
        NOT_IN = ['Push', 'Pop']
        IN = ['Push']
        pre = 0
        res = []
        for v in target:
            if v <= n:
                res += NOT_IN * (v - pre - 1) + IN
                pre = v
            else:
                break
        return res

发表于 2020-12-17 23:28:31 回复(0)