【基础算法训练】—— 栈

目录

• • 💓前言
  • 💓第一题 P4702 取石子
  • • 💒题目描述
    • 🌟解题报告
    • 🌻参考代码(C++版本)
  • 💓第二题 P5638 【CSGRound2】光骓者的荣耀
  • • 💒题目描述
    • 🌟解题报告
    • 🌻参考代码(C++版本)
  • 💓第三题 1441. 用栈 *** 作构建数组
  • • 💒题目描述
    • 🌟解题报告
    • 🌻参考代码(C++版本)
  • 💓第四题 1021. 删除最外层的括号
  • • 💒题目描述
    • 🌟解题报告
    • 🌻参考代码(C++版本)
  • 💓第五题 1700. 无法吃午餐的学生数量
  • • 💒题目描述
    • 🌟解题报告
    • 🌻参考代码(C++版本)
  • 💓第六题 1381. 设计一个支持增量 *** 作的栈
  • • 💒题目描述
    • 🌟解题报告
    • 🌻参考代码(C++版本)
  • 💓 总结

💓前言

每日算法练习，千锤百炼，静待花开。

Leetcode的专栏会持续更，因为在跟着英雄哥做知识星球的事儿：在lc被欺负的这些年；
对英雄哥的知识星球有兴趣的可以看看他这篇文章喔： 英雄算法联盟 | 31天让你的算法与众不同
但是英雄哥这儿了，五月不再招人啦，有想法的小伙伴浅等六月嗷~
单片机是会持续更的，但是硬件看到人比较少吧，或者我理解它不投策，这个更得慢：十四天学会51单片机；

至于现在这个专栏只会记录全部是每日的算法题：知识星球每天的习题，以及在咱高校算法学习社区中，泡泡和p佬普及组和提高组的题目，一般是当天写当天更吧。现在优先写泡泡的题，p佬的有点小把握不住


好朋友执梗正在带新星计划，有想法的小伙伴不要犹豫嗷
点击查看详情

💓第一题 P4702 取石子 💒题目描述

原题传送门

🌟解题报告

原本以为会使很复杂的题目，比如去思考各自怎么取才能保证最优了，其实这些想法都是不必要的，因为题目已经说，两个人都很聪明，都是采用的最优取法，那么此时，题目的前提是Alice先手，而且最后一定会把石子拿完。

倘若Alice想赢，最后一次必须她来取，也就是石子的总数要是奇数；
因为Bob是第二个拿，倘若想要Bob赢，那么就石子的总数就必须是偶数，在偶数的情况下，Bob拿了石子之后，可以直接再让Alice拿不到石头。
这两个人太坏了

🌻参考代码(C++版本)

#include  

using namespace std;
typedef long long LL;

int main()
{
	int n;
	cin >> n;

	int sum = 0;
	//统计每一堆石子的个数
	for(int i = 0; i < n;i++) 
	{
		int m;
		cin >> m;
		sum += m;
	}
	
	if(sum%2) puts("Alice");
	else puts("Bob");
	
	return 0;
}

💓第二题 P5638 【CSGRound2】光骓者的荣耀 💒题目描述

原题传送门

🌟解题报告

第一次读题可能会感觉像是图的题，但是看到下面的样例演示，应该可以感觉到，其实是让统计某个区间中花费的时间，数据范围是 1 0 6 10^6 106，直接暴力是会超时的。求区间和？前缀和算法就可以拿出来了。

🌻参考代码(C++版本)

#include  

using namespace std;
typedef long long LL;
const int N = 1e6+10;
LL sum[N];

int main()
{
	//前缀和
	int n , k;
	cin >> n >>k;

	//可以从1号点直达n号点，其间的半径为n-1
	if(k >= n-1) cout << 0;
	//预处理前缀和
	for(int i = 1; i < n;i++)
	{
		LL x = 0;
		cin >>x;
		sum[i] = sum[i-1] + x;
	}
		
	
	LL ans = sum[n-1];//这个ans记录的是当前最大的前缀和
	//再使用传送机k来跳跃，找到最小的
	for(int i = k; i < n;i++)
		ans = min(ans,sum[n-1]-(sum[i]-sum[i-k]));

	cout << ans;

	return 0;
}

💓第三题 1441. 用栈 *** 作构建数组 💒题目描述

原题传送门

🌟解题报告

题目的背景蛮简单的，是相当于给咱一个序列，然后让咱们用栈的出栈和入栈的思想，去实现目标数组的状态。
因为序列和目标数组都是严格升序排列的，那么我们只需要从1开始，逐渐将1到n的数字转移Push进去，倘若在遍历的过程中，遇到目标数组不想要的，就使用Popd出。

🌻参考代码(C++版本)

class Solution {
public:
    vector<string> buildArray(vector<int>& target, int n) {
        //题目意思是给我们一个1~n的数组，然后嘞，咱们用栈的思想去构建模板数组
        vector<string> ans;
        int len = target.size();

        //扫一遍,根据情况push 和 pop
        for(int i = 1,j = 0;i <= n;i++)
        {
            //凑成目标数组了
            if(j == len) return ans;
            //遇到数字直接先压进去
            ans.push_back("Push");
            //倘若不是模板数组中想要的了，再d出来。
            if(i != target[j]) ans.push_back("Pop");
            else j++;
        }
        return ans;

    }
};

💓第四题 1021. 删除最外层的括号 💒题目描述

原题传送门

🌟解题报告

这个题目，难度可能不大，但是读题挺费解的，题目的意思其实是让我们拆出一对()中包含的括号。
倘若使用栈来维护，那么我们需要在统计的一对()之间的内容。
因此，我们在栈为空，并且当前的字符是(的时候，标记该字符的下一个位置，即l = i + 1。
当遇到的字符是)的时候，就以为着出现一对()括号了，此时就得开始清楚这个括号()里的内容了，假如经过pop之后，栈变成空的了，那么就是当前这个()区间的信息统计完成了，标记当前位置，即r = i。
最后使用substr截取出这个区间中字符串信息。

🌻参考代码(C++版本)

class Solution {
public:
    string removeOuterParentheses(string s) {
        //栈结合双指针来玩
        int l = 0,r= 0;//代表截取区间的左指针和右指针
        int n = s.size();
        stack<char> stk;
        string ans = "";

        for(int i = 0; i < n;i++)
        {
            //如果当前遇到的是左括号
            if(s[i] == '(')
            {
                //而且当前这个栈是空的，标记截取区间的左端点
                if(stk.empty()) l = i+1;
                //否则不标记，常规的入栈
                stk.push(s[i]);
            }
            //如果当前的栈不是空的，而且当前遇到右括号了，d出栈顶的东西
            if(!stk.empty() && s[i] == ')') stk.pop();
            //经过出栈 *** 作之后，栈空
            if(stk.empty())
            {
                r = i;
                //s.substr(pos, n) 截取s中从pos开始（包括0）的n个字符的子串，并返回
                ans += s.substr(l,r-l);
            }
        }
        return ans;
    }
};

💓第五题 1700. 无法吃午餐的学生数量 💒题目描述

原题传送门

🌟解题报告

本题的逻辑了，仍是常规的模拟吧。
因为三明治只有被取，那么相当于栈的出栈，所以就用栈来维护了。
学生排队取三明治了，有拿到满意的了，顺利出队不再回来，也有暂时拿不到满意的，出队之后又入队，所以可以使用一个队列来维护了。

题目给咱的是两个数组，这就需要咱们把数据取出来分别放到栈和队列中的。至于模拟取三明治的过程了，可以使用学生队列的长度用于循环，当有学生拿到自己满意的了，就将循环变量重置置为0，重新循环。
那么，倘若整个队列循环结束了，仍是匹配不到适合的三明治的时候，就结束循环，返回结果，确实是吃不到了。

🌻参考代码(C++版本)

class Solution {
public:
    int countStudents(vector<int>& students, vector<int>& sandwiches) {
        //用栈记录三明治，三明治只有出栈
        //用队列记录学生，学生有出队和入队
        stack<int> stk;
        queue<int> q;

        int sand_len = sandwiches.size();
        int stu_len = students.size();
        //把三明治的信息倒着存入栈中
        for(int i = sand_len-1; i >= 0;i--)
            stk.push(sandwiches[i]);
        

        //把学生的信息顺着存到队列中
        for(int i = 0; i < stu_len;i++)
            q.push(students[i]);
        
        //把学生作为循环
        for(int i = 0; i < q.size();i++)
        {
            //如果栈顶和队列首相同，就是代表爱吃，那么就出栈，出队
            if(stk.top() == q.front())
            {
                stk.pop();
                q.pop();
                i = -1;//重置循环为i = 0,进行新的一轮（因为待会会有i++）
            }else
            {
                //如果不相同，就是出队，入队
                int tmp = q.front();
                q.pop();
                q.push(tmp);
            }
        }

        //最后队列的长度，就是是在满足不了的。
        return q.size();
    }
};

💓第六题 1381. 设计一个支持增量 *** 作的栈 💒题目描述

原题传送门

🌟解题报告

本质上是用咱们熟悉的数组，手动去模拟栈的实现，算是基础知识了吧，注意细节吧~

🌻参考代码(C++版本)

class CustomStack {
public:
    //这个题，其实就是让咱们数组模拟栈的功能了，基础的数据结构的知识了
    vector<int> stk;
    int top;
    CustomStack(int maxSize) {
        //使用vecotr的resize方法改变Vector元素数量的大小
        stk.resize(maxSize);
        top = -1;
    }
    
    void push(int x) {
        //先要判断当前的栈有没有满，不满才可以 *** 作
        if(top != stk.size()-1)
        {
            stk[++top] = x;
        }
    }
    
    int pop() {
        //还是判断可不可以出栈
        if(top == -1) return -1;
        else return stk[top--];
    }
    
    void increment(int k, int val) {
        //栈底的 k 个元素的值都增加
        int n = min(k,top+1);
        for(int i = 0; i < n;i++)
            stk[i] += val;
        
    }
};

/**
 * Your CustomStack object will be instantiated and called as such:
 * CustomStack* obj = new CustomStack(maxSize);
 * obj->push(x);
 * int param_2 = obj->pop();
 * obj->increment(k,val);
 */

💓 总结

① 无论是链表还是栈，其实都是可以使用数组模拟出来的，虽然有了STL大法，但是还是不能忘记可爱的数组
② 今天的简单博弈论了，先浅记录一下，不要去管它们怎么拿，只关心谁先手，谁想赢应该怎么办。