当前位置：首页 > news >正文

Leetcode 1441. 用栈操作构建数组

news 来源：原创 2024/5/7 6:28:06

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

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

“Push”：从 list 中读取一个新元素，并将其推入数组中。
“Pop”：删除数组中的最后一个元素。
如果目标数组构建完成，就停止读取更多元素。
题目数据保证目标数组严格递增，并且只包含 1 到 n 之间的数字。

请返回构建目标数组所用的操作序列。如果存在多个可行方案，返回任一即可。

示例 1：

输入：target = [1,3], n = 3
输出：[“Push”,“Push”,“Pop”,“Push”]
解释：
读取 1 并自动推入数组 -> [1]
读取 2 并自动推入数组，然后删除它 -> [1]
读取 3 并自动推入数组 -> [1,3]

示例 2：

输入：target = [1,2,3], n = 3
输出：[“Push”,“Push”,“Push”]

示例 3：

输入：target = [1,2], n = 4
输出：[“Push”,“Push”]
解释：只需要读取前 2 个数字就可以停止。

我的想法：
看了示例之后第一想法是：
1.取 target 列表长度和 n 比较，如果长度等于 n 或者当 target 最后一个元素小于 n 的时候，返回 [“Push”] * target 的长度；
2.新搞个数组 returnlist 。当不满足 1 的条件下，for 循环1 - n 的数字，如果这个数字在 target 里，returnlist 里续上 “Push”，否则续上 “Push”、“Pop”。

class Solution:
    def buildArray(self, target: List[int], n: int) -> List[str]:
        targetlen = len(target)
        if targetlen == n or target[-1] < n:
            return ["Push"] * targetlen
        else:
            returnlist = []
            for i in range(1,n+1):
                if i not in target:
                    returnlist.extend(["Push", "Pop"])
                else:
                    returnlist.append("Push")
            return returnlist

然后没过

36 / 49 个通过的测试用例
输入
target = [1,3,4,6,7,8] n = 9
输出
[“Push”,“Push”,“Push”,“Push”,“Push”,“Push”]
预期结果
[“Push”,“Push”,“Pop”,“Push”,“Push”,“Push”,“Pop”,“Push”,“Push”,“Push”]

然后觉着是不是 n 没用啊，迷惑人来着。for 循环1 - target[-1] 的数字，如果这个数字在 target 里，targetlist 里续上 “Push”，否则续上 “Push”、“Pop”。试了一下，过了。

class Solution:
    def buildArray(self, target: List[int], n: int) -> List[str]:
        targetlist = list()
        for i in range(1, target[-1] + 1):
            if i in target:
                targetlist.append("Push")
            else:
                targetlist.extend(["Push", "Pop"])
        return targetlist

官方思路也差不多：
在这里插入图片描述
Python3:

class Solution:
    def buildArray(self, target: List[int], n: int) -> List[str]:
        res = []
        prev = 0
        for number in target:
            for _ in range(number - prev - 1):
                res.append('Push')
                res.append('Pop')
            res.append('Push')
            prev = number
        return res

C++：

class Solution {
public:
    vector<string> buildArray(vector<int>& target, int n) {
        vector<string> res;
        int prev = 0;
        for (int number : target) {
            for (int i = 0; i < number - prev - 1; i++) {
                res.emplace_back("Push");
                res.emplace_back("Pop");
            }
            res.emplace_back("Push");
            prev = number;
        }
        return res;
    }
};

char ** buildArray(int* target, int targetSize, int n, int* returnSize) {
    char **res = (char **)malloc(sizeof(char *) * n * 2);
    int prev = 0, pos = 0;
    for (int j = 0; j < targetSize; j++) {
        for (int i = 0; i < target[j] - prev - 1; i++) {
            res[pos] = (char *)malloc(sizeof(char) * 8);
            strcpy(res[pos++], "Push");
            res[pos] = (char *)malloc(sizeof(char) * 8);
            strcpy(res[pos++], "Pop");
        }
        res[pos] = (char *)malloc(sizeof(char) * 8);
        strcpy(res[pos++], "Push");
        prev = target[j];
    }
    *returnSize = pos;
    return res;
}