Given an array target and an integer n. In each iteration, you will read a number from  list = {1,2,3..., n}.

Build the target array using the following operations:

Push: Read a new element from the beginning list, and push it in the array.
Pop: delete the last element of the array.
If the target array is already built, stop reading more elements.
Return the operations to build the target array. You are guaranteed that the answer is unique.

 

Example 1:

Input: target = [1,3], n = 3
Output: ["Push","Push","Pop","Push"]
Explanation: 
Read number 1 and automatically push in the array -> [1]
Read number 2 and automatically push in the array then Pop it -> [1]
Read number 3 and automatically push in the array -> [1,3]
Example 2:

Input: target = [1,2,3], n = 3
Output: ["Push","Push","Push"]
Example 3:

Input: target = [1,2], n = 4
Output: ["Push","Push"]
Explanation: You only need to read the first 2 numbers and stop.
Example 4:

Input: target = [2,3,4], n = 4
Output: ["Push","Pop","Push","Push","Push"]
 

Constraints:

1 <= target.length <= 100
1 <= target[i] <= n
1 <= n <= 100
target is strictly increasing.

这题直接遍历一下1-N,看看是否在列表中,不在就pop。需要注意越界的情况。


class BuildAnArrayWithStackOperations : public Solution {
public:
    void Exec() {
        auto res = buildArray(vector<int>{1, 2}, 4);
    }
    vector<string> buildArray(const vector<int>& target, int n) {
        vector<string> opts;
        int index = 0;
        for (int i = 1; i <= n; i++) {
            if (index >= target.size()) {
                break;
            }
            opts.push_back("Push");
            if (target[index] != i) {
                opts.push_back("Pop");
            } else {
                index++;
            }
        }
        return opts;
    }
};
共 0 条回复
暂时没有人回复哦,赶紧抢沙发
发表新回复

作者

sryan
today is a good day