Leetcode 栈与DFS探索卡片 94/494/133/200/150/739/155 （C++）

Dear 丶 2023-05-21 13:50 1阅读 0赞

最近刷题数目上来了，一天能多刷几道，每道题发一个博客感觉有点耗时，就把当天刷的题目一起发上来做个总结；

昨天刷了栈与队列的卡片，中等难度的题目陡然增多，脑子开始有点不够用了，部分题目还是得看题解才会做，不过没关系，已经形成了一个解题思路，如果一天就能掌握DFS的各种应用那应该算是表现不错，下面看题

155 最小栈

> *设计一个支持 `push` ，`pop` ，`top` 操作，并能在常数时间内检索到最小元素的栈。*

前三个push,pop,top操作在STL stack里面都有自带，可以直接用，关键在于一个在常数时间内检索到最小元素的栈；如果单用一个栈的话，检索到最小元素的时间复杂度应该是O（n）,要在常数时间内找到最小元素肯定要再借助一个额外的栈或者别的容器来实现，这里使用了一个额外的栈minstack，储存当前栈中最小的元素；当push到栈内的元素小于最小值（minstack.top()），就把该元素同时Push到最小栈里，这样就避免了如果用单个变量储存最小值min, min被pop出去后找不到次小值的尴尬场景，代码如下：

class MinStack {
    private:
        stack<int>mystack;        //当前栈
        stack<int>minstack;        //最小栈
    
    public:
        /** initialize your data structure here. */
        MinStack() {
    
        }
        
        void push(int x) {
            mystack.push(x);                                //push当前栈
            if(minstack.empty()) minstack.push(x);            //最小栈为空时直接Push,
            else{    
                if(x<=minstack.top()) minstack.push(x);        //当前值小于最小栈top()时push，否则不作任何操作
            }
    
        }
        
        void pop() {
            int temp = mystack.top();
            if(temp==minstack.top()) minstack.pop();        //如果pop了当前最小值，最小栈里储存了次小值因此top()仍旧是当前最小值
            mystack.pop();
            
    
        }
        
        int top() {
            return mystack.top();
    
        }
        
        int getMin() {
            return minstack.top();
        }
    };

时间复杂度：O（1），空间复杂度O（n）,测试结果显示内存超过100%，时间超过15%

739. 每日温度

> *根据每日 气温 列表，请重新生成一个列表，对应位置的输出是需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置用 0 来代替。*
> 
> *例如，给定一个列表 temperatures = \[73, 74, 75, 71, 69, 72, 76, 73\]，你的输出应该是 \[1, 1, 4, 2, 1, 1, 0, 0\]。*
> 
> *提示：气温 列表长度的范围是 \[1, 30000\]。每个气温的值的均为华氏度，都是在 \[30, 100\] 范围内的整数。*

此题方法同上题，使用一个辅助栈来储存当前最小的气温，不过这里辅助栈储存的不是气温值而是日期的索引，因为要返回的是距离多久才能超过该日温度的天数，因此结果数组里应该存放的是日期差值，代码如下：

class Solution {
    public:
        vector<int> dailyTemperatures(vector<int>& T) {
            
            stack<int>mystack;
            mystack.push(0);                    //第一天的索引Push入栈
            vector<int>ans(T.size(),0);        //创建结果数组，初始化为0
            for(int i=1;i<T.size();i++)
            {
                while(!mystack.empty())        //每当遇到大于栈顶的温度时表明栈顶元素已经找到比其温度高的日期
                {
                    int top = mystack.top();
                    if(T[top]<T[i])
                    {
                        ans[top]=i-top;        //找到目标日期，结果数组里放入
                        mystack.pop();        //栈定元素pop
                    }
                    else{break;}
                }
                mystack.push(i);            //如果当前值小于最小值，说明还未超过前面的温度，继续入栈
            }
    
            return ans;                    //最后其实有一个判断是否栈空的情况，如果不空，说明剩下的元素在后面均没有超过它温度的日期，因此应该为0，这里在一开始就设置了0所以不需要判断
    
        }
    };

时间复杂度：O（n）, 空间复杂度O（n）,只需完整遍历一次数组就可得出结果

150. 逆波兰表达式求值

> *根据逆波兰表示法，求表达式的值。*
> 
> *有效的运算符包括 +, -, \*, / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。*
> 
> *说明：*
> 
> *整数除法只保留整数部分。  
> 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。  
> 示例 1：*
> 
> *输入: \["2", "1", "+", "3", "\*"\]  
> 输出: 9  
> 解释: ((2 + 1) \* 3) = 9  
> 示例 2：*
> 
> *输入: \["4", "13", "5", "/", "+"\]  
> 输出: 6  
> 解释: (4 + (13 / 5)) = 6  
> 示例 3：*
> 
> *输入: \["10", "6", "9", "3", "+", "-11", "\*", "/", "\*", "17", "+", "5", "+"\]  
> 输出: 22  
> 解释:   
>   ((10 \* (6 / ((9 + 3) \* -11))) + 17) + 5  
> = ((10 \* (6 / (12 \* -11))) + 17) + 5  
> = ((10 \* (6 / -132)) + 17) + 5  
> = ((10 \* 0) + 17) + 5  
> = (0 + 17) + 5  
> = 17 + 5  
> = 22*

其实这题过程很简单，遇到数字压入栈，遇到运算符就取出栈的两个数做相应的运算，只是这里有几个麻烦的地方在于首先要判断是运算数还是运算符，这里一开始我的逻辑没找好，自己去造了轮子，而且这个轮子还不是很好使，导致最后运算时间有点落后，代码如下：

bool isNumber(string& str)            //判断str是数字
    {
        if (str[0] == '-')                    //判断负数的情况
        {
            if (str.length() == 1) return false;
            else
            {
                for (int i = 1; i < str.length(); i++)
                {
                    if (str[i] < '0' || str[i]>'9') return false;
                }
                return true;
            }
        }
        else
        {
            for (int i = 0; i < str.length(); i++)
            {
                if (str[i] < '0' || str[i]>'9') return false;
            }
            return true;
        }
    }
    int stoi(string& str)                //将字符串转化成数字
    {
        int flag = 1, sum = 0;
        for (int i = 0; i < str.length(); i++)
        {
            if (str[i] == '-')            //负数的第一位为'-'
            {
                flag = -1; continue;
            }
            sum = sum * 10 + str[i]-'0';
        }
        return sum * flag;
    }
    class Solution {
    public:
        int evalRPN(vector<string>& tokens) {
            stack<int>numbers;                //数字栈
            for (auto str : tokens)            //练习下C++11的语法
            {
                if (isNumber(str))
                {
                    numbers.push(stoi(str));        //是数字就判断入栈，这里其实可以写一个isnotnumber函数，代码逻辑比较简单
                }
                else
                {
                    int number2 = numbers.top(); numbers.pop();        //下面的就很好想了
                    int number1 = numbers.top(); numbers.pop();
                    if (str[0] == '*') { numbers.push(number1 * number2); }
                    if (str[0] == '/') { numbers.push(number1 / number2); }
                    if (str[0] == '+') { numbers.push(number1 + number2); }
                    if (str[0] == '-') { numbers.push(number1 - number2); }
                }
            }
            return numbers.top();
    
        }
    };

时间空间复杂度都是O（n）,如果详细点的话空间复杂度应该是O（n-n符号）

200 岛屿数量

> 给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。
> 
> 示例 1:
> 
> 输入:  
> 11110  
> 11010  
> 11000  
> 00000
> 
> 输出: 1  
> 示例 2:
> 
> 输入:  
> 11000  
> 11000  
> 00100  
> 00011
> 
> 输出: 3
> 
> 来源：力扣（LeetCode）  
> 链接：https://leetcode-cn.com/problems/number-of-islands  
> 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这题之前写过BFS的方法，这次来写DFS，DFS跟BFS很大不同的地方是DFS很多情况都需要用到递归，我在这一块写得少所以做的磕磕绊绊，重要是判断循环结束的条件，一般来说是!.empty()；和记录已经访问过的节点，这两点在不同的题型里方法是不一样的，下面的几道题都有实例，这里先贴上岛屿数量的DFS方法代码：

class Solution {
    public:
        bool inIsland(vector<vector<char>>& grid, pair<int,int>index)        //判断在岛内
        {
            if (index.first >= 0 && index.first < grid.size() && index.second >= 0 && index.second < grid[0].size()) return true;
            return false;
        }
    
        void DFS(vector<vector<char>>& grid, stack<pair<int, int>>&mystack)    //这里有个要注意的地方是参数应该为grid和mystack的引用，前面几次因为没有在mystack前加&导致用时和内存都爆炸多
        {
            if (mystack.empty()) return;            //栈空，DFS结束
            pair<int, int>temp = mystack.top();
            mystack.pop();
            grid[temp.first][temp.second] = '0';        //已访问的节点改为0
            pair <int,int> up = {temp.first + 1, temp.second}; 
            pair <int,int> down = {temp.first - 1, temp.second};
            pair <int,int> left = {temp.first, temp.second - 1};
            pair <int,int> right = {temp.first, temp.second + 1};
            if(inIsland(grid,up) && grid[temp.first + 1][temp.second] == '1') //若拓展出去的点仍在边界之内，且是岛屿的一部分，将其push入栈内，作为之后迭代的起始点
                mystack.push(up);
            if(inIsland(grid,down) && grid[temp.first - 1][temp.second] == '1')
                mystack.push(down);
            if(inIsland(grid,left) && grid[temp.first][temp.second - 1] == '1')
                mystack.push(left);
            if(inIsland(grid,right) && grid[temp.first][temp.second + 1] == '1')
                mystack.push(right);
            return DFS(grid, mystack);
        }
    
        int numIslands(vector<vector<char>>& grid)
        {
            if(grid.empty()) return 0;
            stack<pair<int,int>>mystack;
            int ans = 0;
            int M = grid.size();
            int N = grid[0].size();
            for (int i = 0; i < M; ++i)
            {
                for (int j = 0; j < N; ++j)
                {
                    if (grid[i][j] == '1')
                    {
                        ++ans;
                        mystack.push(make_pair(i, j));
                        DFS(grid, mystack);
                    }
                }
            }
            return ans;
        }
    };

详细解释不需要多说，可以看以前的那篇博客，这里再提醒自己一下就是传入大型数据结构作为函数参数的时候最好传引用，没有&符号的话肯定会加大时间和空间损耗。

133 克隆图

题目太长就不复制了，题目的要求就是要求深复制一个无向连通图,这题其实用BFS来写可能逻辑更清晰一点，但是这题是在DFS的卡片里所以还是练习一下DFS的写法，DFS的关键就是递归和储存已访问过的节点，利用栈来满足要求，这题里有几个容易出错的地方在下面代码中展示出来

/*
    // Definition for a Node.
    class Node {
    public:
        int val;
        vector<Node*> neighbors;
        
        Node() {
            val = 0;
            neighbors = vector<Node*>();
        }
        
        Node(int _val) {
            val = _val;
            neighbors = vector<Node*>();
        }
        
        Node(int _val, vector<Node*> _neighbors) {
            val = _val;
            neighbors = _neighbors;
        }
    };
    */
    
    class Solution {
    public:
        Node* cloneGraph(Node* node) {
            unordered_map<Node*, Node*> mymap;   //用undered_map来储存原节点和复制节点的映射
            stack<Node*>mystack;                //用stack来储存DFS节点
            if(!node) return nullptr;
            const auto newnode = new Node(node->val);    //创建新节点并加入映射图和栈
            mymap[node] = newnode;
            mystack.push(node);
            while(!mystack.empty())                    //栈空则遍历结束
            {
                Node* temp = mystack.top();
                mystack.pop();                            //遍历栈顶元素
                for(const auto& neigh:temp->neighbors )
                {
                    if(mymap.count(neigh)!=1)            //若未遍历过则入栈并加入已遍历映射map
                    {
                        mystack.push(neigh);
                        mymap[neigh]= new Node(neigh->val);
    
                    }
                    mymap[temp]->neighbors.push_back(mymap[neigh]);    //这句话很关键，特别是后面那句push_back里面的参数，必须是复制的节点；无论是否遍历都要讲当前节点的邻居加到复制节点的邻居中
                }
            }
            return mymap[node];
    
            
            
        }
    };

这里在把当前节点的邻居添加到复制节点的邻居列表中的时候注意要同时把当前节点的邻居同时复制了。

494 目标和

> *给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。*
> 
> *返回可以使最终数组和为目标数 S 的所有添加符号的方法数。*
> 
> *示例 1:*
> 
> *输入: nums: \[1, 1, 1, 1, 1\], S: 3  
> 输出: 5  
> 解释: *
> 
> *-1+1+1+1+1 = 3  
> \+1-1+1+1+1 = 3  
> \+1+1-1+1+1 = 3  
> \+1+1+1-1+1 = 3  
> \+1+1+1+1-1 = 3*
> 
> *一共有5种方法让最终目标和为3。  
> 注意:*
> 
> *数组非空，且长度不会超过20。  
> 初始的数组的和不会超过1000。  
> 保证返回的最终结果能被32位整数存下。*
> 
> *来源：力扣（LeetCode）  
> 链接：https://leetcode-cn.com/problems/target-sum  
> 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*

这道题有很多种做法，包括动态规划、01背包、暴力法（DFS遍历），这里根据卡片要求用DFS暴力解法来做,如果用非递归的算法的话得需要额外一个栈来记录当前栈的深度，想了很久不太会操作，就直接用递归写了，思路很简单清晰，代码如下：

class Solution {
    public:
        int ans=0;
        void DFS(vector<int>&nums, int level, int sum, int target)  //level为当前累加数字个数，sum为当前累加和
        {
            if(level==nums.size()-1)                //累加数字达到上限，开始比对结果
            {
                if(sum+nums[level]==target) ans++;    //为什么不用||是当nums[level]==0时加和减是各算一次的，否则就会少一个答案
                if(sum-nums[level]==target) ans++;
            }
            else
            {
                DFS(nums, level+1, sum+nums[level], target);     //未达到上限继续累加
                DFS(nums, level+1, sum-nums[level], target);
            }
            
    
        }
        int findTargetSumWays(vector<int>& nums, int S) {
            DFS(nums, 0, 0, S);
            return ans;
    
        }
    };

有个01背包的解法也挺好用的，下次刷的时候尝试一下；

94 二叉树的中序遍历

递归方法秒解，用栈迭代算法看了下难度应该也还好，下次再写把，这次写这个博客仿佛把过去两天的题目重新做了一遍，头晕晕的。