《五月集训》（第14天）——栈

前言：

五月集训，前面为学习内容，想要一起学习的可以看一看，最后的才是五月集训每天的作业。

一、知识点

栈不严格地说就相当于一个只能在尾部进行插入和删除的线性表。

二、课堂习题

这里的题均出自《算法零基础100讲》
暑假前先不写了QAQ

三、作业

1441. 用栈操作构建数组
1021. 删除最外层的括号
1700. 无法吃午餐的学生数量
1381. 设计一个支持增量操作的栈
解题思路：
1.循环依次判断链表中对应的元素是否正确，正确则push，错误则push后pop；
2.用一个l作为计数器，来对完整的括号数进行计数，当l=0时，说明对应的括号是最外层的括号，不放入答案中，其余的全都依次放入答案中；
3.记录爱吃不同三明治的学生的人数，按题意让学生按照三明治摆放顺序以此减少，当某一类人数归零时，剩下的学生就是吃不到的人数；
4.用数组模拟栈即可。
代码：

class Solution {    public List<String> buildArray(int[] target, int n) { List<String> res = new ArrayList<>(); int i = 0; for (int j = 1; j <= n; j++) {     if (i == target.length) {  break;     }     if (target[i] == j) {  res.add("Push");  i++;     } else {  res.add("Push");  res.add("Pop");     } } return res;    }}

class Solution {    public String removeOuterParentheses(String s) { StringBuilder sb = new StringBuilder(); int l = 0; for(int i = 0;i < s.length();i++){     if(s.charAt(i) == '(' && l++ > 0){  sb.append('(');     }     if(s.charAt(i) == ')' && --l > 0){  sb.append(')');     } } return sb.toString();    }}

class Solution {    public int countStudents(int[] students, int[] sandwiches) { int[] hash = new int[2]; for(int x : students){     hash[x]++; } for(int x : sandwiches){     if(hash[x] > 0)  hash[x]--;  else{      break;  } } return hash[0]+hash[1];    }}

class CustomStack {    int[] num;    int head;    public CustomStack(int maxSize) { num = new int[maxSize]; head = -1;    } public void push(int x) { if(head == num.length - 1){     return; } num[++head] = x;    } public int pop() { if(head == -1){     return -1; } return num[head--];    } public void increment(int k, int val) { for(int i = 0;i < Math.min(k, head+1);i++){     num[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); */

四、总结

对于算法的掌握还是不够熟练，需要进行反复训练！
另外，剩下的课堂训练题目留到下个月的集训啦(●ˇ∀ˇ●)