ronald7个月前职场1810

    栈(stack)一种操作受限的线性结构,限定仅能在尾部进行插入和删除,能进行插入和删除操作的一端叫做栈顶,而另一端叫做栈底;我们将插入栈的操作叫做入栈,从栈中删除元素的操作叫做出栈,栈是一个先入后出(FILO)的数据结构,即先入栈的元素会后出栈。

    栈最常被我们接触的场景就是函数调用了,在进程地址空间中,有一块空间叫做栈空间,是在发生函数调用的时候我们通常将主调函数的上下文入栈,然后在栈上再开辟一块空间用于存放这个被调函数的上下文信息;因为调用链是自上而下的,而运行环境的恢复则是得按照一个自下而上的顺序逆序进行恢复,非常贴合栈自然的一个操作顺序。

栈的面试点

    上述主要介绍了栈的定义、操作上的一些特点,以及常用到的一些场景。另外因为栈的操作相对比较简单,所以也比较常见于技术开发面试的一些面试题目的,列举一些例子。

括号匹配(简单难度)

给定一个只包括 '(',')','{','}','[',']' 的字符串 s ,判断字符串是否有效。

有效字符串需满足:

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/valid-parentheses
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解法:

#include <stack>
class Solution {
public:
    bool isValid(string s) {
        stack<char> local_stack;
        for(int index = 0;index<s.length();++index){
            if((s[index] == '(') || (s[index]=='{') || (s[index]=='[')){
                local_stack.push(s[index]);
            }
            else if (s[index] == ')') {
                if((!local_stack.empty()) && local_stack.top() == '('){
                    local_stack.pop();
                }
                else {
                    return false;
                }
            }
            else if ((!local_stack.empty()) &&s[index] == ']') {
                if(local_stack.top() == '['){
                    local_stack.pop();
                }
                else {
                    return false;
                }
            }
            else if ((!local_stack.empty()) &&s[index] == '}') {
                if(local_stack.top() == '{'){
                    local_stack.pop();
                }
                else {
                    return false;
                }
            }
            else {
                return false;
            }
        }
        if(local_stack.empty()) {
            return true;
        }
        return false;
    }
};

    这道题的基本思路就是运用了栈的后进先出的规则,对于输入的括号串发现是左括号就入栈,发现是右括号就和栈顶进行匹配,能匹配上就出栈,这里需要关注两个边界点:

    1)最开始输入的时候就是右括号,此时栈为空,和栈顶进行比较的话会报异常;所以上面判断的步骤需要先判空

    2)需要防止输入非括号字符串的场景;

    此外由于上述判断分支比较多,我们可通过一些办法对代码进行一定程度的精简,如下:

#include <stack>
class Solution {
public:
    bool isValid(string s) {
        stack<char> local_stack;
        local_stack.push(' ');
        for(int index = 0;index<s.length();++index){
            if((s[index] == '(') || (s[index]=='{') || (s[index]=='[')){
                local_stack.push(s[index]);
            }
            else if ((s[index] == ')') || (s[index]=='}') || (s[index]==']')) {
                if((s[index] - local_stack.top()< 3) && (s[index] - local_stack.top() > 0)){
                    local_stack.pop();
                }
                else {
                    return false;
                }
            }
            else {
                return false;
            }
        }
        if(local_stack.top() == ' ') {
            return true;
        }
        return false;
    }
};

两个点:

    1)一个是新增一个哨兵,以后就不需要每一步都判断栈为空的情形

    2)根据ASC码来判断

    其他类似消消乐等编程题也是类似的解法,无非是出栈的条件从括号匹配变为其他指定的条件而已。

栈与线性结构(中等难度)

题目描述

    (源于leetcode上面的一道题),链表重排:假设我们的输入链表为L1->L2->L3->...->Ln-1->Ln,我们希望输出链表为L1->Ln->L2->Ln-1...

题目分解

    从题目我们可以看出,这个链表可以拆解为L1->L2->...->Ln/2和Ln->Ln-1->...->Ln/2+1的链表合并,即一个正序链表和逆序链表的归并。

实现代码:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
 #include <stack>
 #include <queue>
class Solution {
public:
    void reorderList(ListNode* head) {
        stack<ListNode*> reverse_stack;
        queue<ListNode*> traverse_queue;
        ListNode* reverse = head;
        int count = 0;
        while(reverse != nullptr) {
            reverse_stack.push(reverse);
            traverse_queue.push(reverse);
            ListNode* next = reverse->next;
            reverse->next = nullptr;
            reverse = next;
            count++;
        }
        ListNode* result = traverse_queue.front();
        traverse_queue.pop();
        count--;
        while((count>0)&&(!reverse_stack.empty())){
            ListNode* temp = reverse_stack.top();
            reverse_stack.pop();
            result->next = temp;
            result = temp;
            count--;
            
            if((count > 0) && (!traverse_queue.empty())) {
                ListNode* temp = traverse_queue.front();
                traverse_queue.pop();
                result->next = temp;
                result = temp;
                count--;
            }
        }

    }
};

    上述代码是栈的一个应用场景,但是从代码设计角度上说,空间复杂度偏高,用了O(2*N),我们可以用线性表的角度对这个代码进行优化,于是有:

 #include <vector>
class Solution {
public:
    void reorderList(ListNode* head) {
        vector<ListNode*> list_vec;
        ListNode* iter = head;
        while(iter!=nullptr){
            list_vec.push_back(iter);
            ListNode* temp = iter->next;
            iter->next = nullptr;
            iter = temp;
        }
        vector<ListNode*>::iterator vec_iter = list_vec.begin()+1;
        vector<ListNode*>::iterator vec_riter = list_vec.end()-1;
        iter = head;
        while(vec_iter <= vec_riter){
            iter->next = *vec_riter;
            iter = iter->next;
            vec_riter--;
            if(vec_iter <= vec_riter) {
                iter->next = *vec_iter;
                iter = iter->next;
                vec_iter++;
            }
        }
    }
};

    主体思路是,用vector管理链表,然后头尾指针交替插入;但是这个还是会有新增O(n)的额外空间开销,我们希望达到O(1)的空间复杂度,于是有:

class Solution {
public:
    void reorderList(ListNode* head) {
        ListNode* iter_first = head;
        ListNode* tail = nullptr;
        if(iter_first == nullptr){
            return;
        }
        //找到中间位置
        ListNode* iter_second = head->next;
        while(iter_second != nullptr) {
            iter_second = iter_second->next;
            if(iter_second != nullptr){
                iter_second = iter_second->next;
                iter_first = iter_first->next;
            }
        }
        //后半部分reverse
        ListNode* iter_pre = iter_first->next;
        if(iter_pre == nullptr){
            return;
        }
        ListNode* iter_curr = iter_pre->next;
        iter_pre->next = nullptr;
        if(iter_curr != nullptr){
            iter_next = iter_curr->next;
            
            while(iter_next != nullptr){
                iter_curr->next = iter_pre;
                iter_pre = iter_curr;
                iter_curr = iter_next;
                iter_next = iter_next->next;
            }
            iter_curr->next = iter_pre;
            tail = iter_curr;
        }
        else{
            tail = iter_pre;
        }
        //链表归并
        ListNode* first = head;
        while(first != nullptr && tail != nullptr){
            ListNode* temp1 = first->next;
            ListNode* temp2 = tail->next;
            first->next = tail;
            tail->next = temp1;
            first = temp1;
            tail=temp2;
        }
    }
};

    总体思路是,先通过二倍步长找到链表的中间位置,然后对后半部分的链表进行reverse,剩下的就是对两个链表的归并排序了。

栈与一些算法(高难度)

    栈也可以和一些算法如动态规划等结合,这类问题在面试过程中属于比较难的题目了,这里举一个比较简单的例子,最长有效括号问题,给一个只包含'('和‘)’的字符串,找出最长有效括号字串的长度:

class Solution {
public:
    int longestValidParentheses(string s) {
        int maxans = 0;
        stack<int> stk;
        stk.push(-1);
        for (int i = 0; i < s.length(); i++) {
            if (s[i] == '(') {
                stk.push(i);
            } else {
                stk.pop();
                //空了表示是非法串了
                if (stk.empty()) {
                    stk.push(i);
                } else {
                    //非空,top记录的是上一个合法串的起始位置,i-top就是合法串的长度,每次合法都更新一下
                    maxans = max(maxans, i - stk.top());
                }
            }
        }
        return maxans;
    }
};


相关文章

第四次引擎编程尝试

第四次引擎编程尝试

本节我们将尝试在游戏中创建AI,并针根据游戏内的事件做出对应的反应。创建自己的AI类· 按照介绍的,先创建一个我们的AI类,因为AI可以移动、碰撞等,所以我们选择其继承自Character· 创建好AI类之后,我们创建其蓝图类· 创建好蓝图我们进入AI的编辑界面从界面中,我们可以看到:    我们的FPSTpl2AIGuard继承自Character,拥有A...

协程-有栈协程(libco)

协程-有栈协程(libco)

libco      还有一个广泛使用的协程库就是libco,libco是被由微信开发并大规模应用的协程库,自2013年起稳定运行于数万台微信后台机器上;具备以下特性:高性能,号称可以调度千万级协程在IO阻塞时,可以自动切换,利用hook技术+epoll事件循环实现阻塞逻辑IO化改造支持嵌套创建既支持共享栈模式也支持独立栈模式提供超时管...

Lua和C

Lua和C

一.背景    在实际游戏业务运营过程中,经常会出现一些紧急的配置修改、bug修复等;这种规划外的变更行为希望能做到用户无感知,否则对于游戏体验和产品口碑有很大影响,在此背景下,热更新能力成为成熟上线游戏的标准配置。    一般情况下,后台逻辑热更新能力的技术方案有两种:    ...

协程-无栈协程(下)

无栈协程库——protothread    ProtoThread源码如下所示:#define LC_INIT(s) s = 0; #define LC_RESUME(s) switch(s) { case 0: #define LC_SET(s)...

K8S入门-概念篇(下)

K8S入门-概念篇(下)

一. volume    volume解决的是pod上不同容器之间共享文件的问题和容器文件持久化的问题;K8S提供了以下几类volume:1. hostPath    hostPath是一种通过pod所在node上的文件系统指定的文件或者目录实现文件共享,如下所示,先在Pod内定义一个volume,类型定义为hostP...

关于LUA(下)

关于LUA(下)

Lua与OOP    Lua是面向过程的语言,不提供面向对象的特性,但是我们可以利用Lua的元表和元方法模拟面向对象的效果。OOP的特性封装    所谓封装,是隐藏对象的属性和细节,仅对外暴露公共的访问方式。本质上分为两层:    1)成员变量和成员方法,提升代码的内聚性,降低模...

发表评论    

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。