美团 AIoT-视觉算法开发工程师一面算法题
美团 AIoT-视觉算法开发工程师一面算法题
程序员小熊
发布于 2022-01-25 09:09:20
发布于 2022-01-25 09:09:20
前言
大家好，我是熊哥。最近一位做后台开发的朋友去面试了美团的AIoT-视觉算法开发工程师的岗位，熊哥分享一下一面的算法题，供大家参考，希望能对大家找工作有所帮助。
栈的压入、弹出序列
原题
示例
解题思路
这道题其实是力扣的原题，如果有刷过该题，相信能很快写出来。
本题主要考察栈的性质(先进后出)，具体分析如下示例。
示例
以 pushV = [1,2,3,4,5], popv = [4,5,3,2,1]为例，如下图示：
例子
- 当前栈顶元素为空或不是 4(popV[0])，将 1、2 和 3 分别压入栈中。
入栈
- 当栈顶元素为 4 时，由于其等于 popV[0]，将 4 出栈。
将 4 先入栈
由于其等于 popV[0]，将其弹出
- 当栈顶元素不等于 popV[i] 时，依次将 pushV[i] 入栈，否则将栈顶元素出栈，最后看栈是否为空。
最终结果
完整的判断过程如下动图示：
完整过程
Show me the Code
C
bool IsPopOrder(int* pushV, int pushVLen, int* popV, int popVLen){
int* stack = (int *)malloc(pushVLen * sizeof(int));
if (stack == NULL) {
return false;
}
int top = -1; // 栈顶
int popIndex = 0; // popV 索引
for (int i = 0; i < pushVLen; ++i) {
stack[++top] = pushV[i]; // 压栈
/* 栈不为空并且栈顶的元素等于 popV[index] 时，出栈*/
while (top != -1 && stack[top] == popV[popIndex]) {
top--;
popIndex++;
}
}
return top == -1; // 最后判断栈是否为空
}
C++
bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
int t = 0;
stack<int> s;
for(int x : pushV){
s.push(x);
while(!s.empty() && popV[t] == s.top()){
s.pop();
t++;
}
}
return s.empty();
}
Java
boolean validateStackSequences(int[] pushV, int[] popV) {
int t = 0;
Stack<Integer> s = new Stack<>();
for(int x : pushV){
s.push(x);
while(!s.isEmpty() && s.peek() == popV[t]){
s.pop();
t++;
}
}
return s.isEmpty();
}
Python3
def validateStackSequences(self, pushV: List[int], popV: List[int]) -> bool:
stack, t = [], 0
for x in pushV:
s.append(x)
while stack and s[-1] == popV[t]:
stack.pop()
t += 1
return not stack
Golang
func validateStackSequences(pushV []int, popV []int) bool {
i := 0
stack := make([]int,0)
for _,value := range pushV{
stack = append(stack,value)
for len(stack) != 0 && stack[len(stack) - 1] == popV[i] {
stack = stack[:len(stack) - 1]
i++
}
}
return len(stack) == 0
}
复杂度分析
时间复杂度：O(N)，其中 N 为 pushV 序列的长度；
空间复杂度：O(N)。
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2022-01-18，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录