栈

回文链表 原题链接：https://leetcode.cn/problems/aMhZSa/ 给定一个链表的 头节点 head ，请判断其是否为回文链表。 如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。 1.试解栈123456789101112131415161718192021class Solution {public: bool isPalindrome(ListNode* head) { if (head->next == nullptr) return true; //1.stk push stack<ListNode*> stk; ListNode* p = head; while (p) { stk.push(p); p = p->next; } //2.traverse linklist p = head; while (p) { if (stk.top()->val != p->val) return false; stk.pop(); p = p->next; } return true; }}; 2.数组+双指针1 3.递归1 4.快慢指针1

删除链表的倒数第 n 个结点 原题链接：https://leetcode.cn/problems/SLwz0R/ 给定一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。 1.计算链表长度一种最容易想到的方法：（无虚拟头结点） 首先从头节点开始对链表进行一次遍历，得到链表的长度length 然后从头节点开始对链表进行一次遍历，当遍历到第L−n+1个节点时，其下一个就是需要删除的节点 1234567891011121314151617181920212223242526272829303132333435363738class Solution {public: int getLength(ListNode *head) { int length = 0; while (head) { head = head->next; length++; } return length; } ListNode* removeNthFromEnd(ListNode *head, int n) { if (head == nullptr) return nullptr; int listSize = getLength(head); if (n < 1 || n > listSize) return nullptr;// 1 <= n <= len ListNode* deleteNode; if (n == listSize) { //delete the firstNode deleteNode = head; head = head->next; } else { ListNode* p = head; int ind = listSize - n - 1; while (ind--) p = p->n ...

栈 1.AcWing828.模拟栈123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657#include <iostream>using namespace std;const int MAX = 100010;typedef struct { int data[MAX]; int top;} Stack;Stack stack1;void stack_push(Stack &stack, int x) { stack.data[stack.top] = x; stack.top++;}int stack_pop(Stack &stack) { int ret = stack.data[stack.top]; stack.top--; return ret;}int stack_top(Stack &stack) { return stack.data[stack.top - 1];}bool stack_empty(Stack &stack) { if (stack.top > 0) return false; return true;}int main() { std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0); int m; cin >> m; string opt; int x; int top; while (m--) { cin >> opt; if (opt == "push") { cin >> x; stack_push(stack1, x); } else if (opt == "pop") { stack_pop(stack1); } else if (opt == "empty") &# ...

有效的括号 原题链接：https://leetcode.cn/problems/valid-parentheses/ 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。 有效字符串需满足： 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 每个右括号都有一个对应的相同类型的左括号。 1.化简思维可以将问题先简化为1种括号的匹配问题（判断左括号、右括号的数量是否相等），再扩展括号匹配的种类： +1可以等价为进入，-1可以等价为出去 一对()可以等价为一个完整的事件 (())可以看做事件与事件之间的完全包含关系 1种括号匹配123456789101112131415//写法1bool isValid(char *s) { int lum = 0, rnum = 0; int len = strlen(s); for (int i = 0; i < len; ++i) { switch (s[i]) { case '(' : ++lnum; break; case ')' : ++rnum; break; default : return flase; } if (lnum >= rnum) continue; return false; } return lnum = rnum;} 123456789101112131415//写法2bool isValid(char *s) { int lum = 0; int len = strlen(s); for (int i = 0; i < len; ++i) { switch (s[i]) { case '(' : ++lnum; break; ...

字符串括号匹配 原题链接：https://oj.haizeix.com/problem/377 给出一个字符串，判断其中的左右圆括号是否匹配， 注：需同时判断左右圆括号 ( 和 ) ，左右中括号 [ 和 ]，左右大括号 { 和 } 不需要考虑括号之间的优先级的问题，也就是说，小括号包含大括号，也是被允许的 输入： 一行一个字符串，以字符@为结尾 输出： 若匹配，输出 YES，若不匹配，则输出 NO 样例： 1a(cc[])bbb()@ YES 1a(cc[)]bbb()@ NO 代码1234567891011121314151617181920212223242526272829303132333435363738394041#include<iostream>#include<string>#include<stack>using namespace std;bool isValid(string str) { stack<char> stack; for (int i = 0; i < str.length(); ++i) { switch (str[i]) { case '(': case '[': case '{': stack.push(str[i]); break; case ')': if (stack.empty() || stack.top() != '(') return false; stack.pop(); break; case '}': if (stack.empty() || stack.top() != '{') return false; stack.pop(); break; case ']': if (stack.empty() || stack.top() != &# ...

括号画家 原题链接：https://oj.haizeix.com/problem/265 Candela 是一名漫画家，她有一个奇特的爱好，就是在纸上画括号。 这一天，刚刚起床的 Candela 画了一排括号序列，其中包含小括号 ()、中括号 [] 和大括号 {}，总长度为 N。 这排随意绘制的括号序列显得杂乱无章，于是 Candela 定义了什么样的括号序列是美观的。 1231.空的括号序列是美观的；2.若括号序列 A 是美观的，则括号序列 (A)、[A]、{A} 也是美观的；3.若括号序列 A、B 都是美观的，则括号序列 AB 也是美观的； 例如 [(){}]() 是美观的括号序列，而 )({)[}]( 则不是。 现在 Candela 想在她绘制的括号序列中找出其中连续的一段，满足这段子序列是美观的并且长度尽量大。你能帮帮她吗？ 输入： 1 个长度为 N 的括号序列。(5 ≤ N ≤ 10000) 输出： 一个整数，表示最长的美观的连续子序列的长度。 样例： 1[[[[]]{}]] 110 代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#include<iostream>#include<stack>#include<string>using namespace std;stack<char> stack1;stack<int> stack2;string str;int ans;void ansUpdate(int i) { stack1.pop(); stack2.pop(); ans = max(ans, i - stack2.top());}void stack12Clear(int i) { while (!stack1.empty()) { stack1.pop(); stack2.pop(); } stack1.push('#'); stack2.pus ...

仓库日志 原题链接：https://oj.haizeix.com/problem/379 某仓库购入新的货物并将一部分老货物发出，这个过程会有软件对数据以日志形式保存，规则如下： 该日志记录了两类操作： 第一类操作为入库操作，以及该次入库的货物数量； 第二类操作为出库操作。 这些记录都严格按时间顺序排列。入库和出库的规则为先进后出，即每次出库操作货物为当前在仓库里所有货物中最晚入库的货物。 为了便于分析，现在加入了第三类查询操作，每次查询时输出当前仓库数量最多的货物的数量。 输入： 包含 N+1行： 第一行为 1 个正整数 N，对应于日志内所含操作的总数。 接下来的 N 行，分别属于以下三种格式之一： 0 X ：一次入库操作，正整数 X 表示该次入库的货物的数量 1 ：一次出库操作，（就当时而言）最后入库的货物出库 2 ：一次查询操作，要求分析程序输出当前仓库内数量最多的货物的数量 当仓库为空时你应该忽略出库操作，当仓库为空查询时你应该输出 0。 初始时仓库状态为空。 输出： 输出行数等于日志中查询操作的次数。每行为一个正整数，表示查询结果。 样例： 1234567891011121314130 10 220 40 221211212 1234524410 代码12345678910111213141516171819202122232425262728293031323334#include<iostream>#include<stack>using namespace std;stack<int> stack1;//存储仓库货物的数量stack<int> stack2;//存储当前仓库内数量最多的货物数量int main() { int n; cin >> n; for (int i = 0; i < n; ++i) { int x; cin >> x; switch (x) { case 0://入库操作（入栈操作） int num; cin >> num; stack1.push(num); if (stack1.size() == 1) stack2.push(num); else ...