数据结构

回文链表 原题链接：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

两个链表的第一个重合节点 原题链接：https://leetcode.cn/problems/3u1WK4/ 给定两个单链表的头节点 headA 和 headB ，请找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。 图示两个链表在节点 c1 开始相交： 题目数据 保证 整个链式结构中不存在环。 函数返回结果后，链表必须 保持其原始结构 。 1.哈希表主要思路： 遍历listA将其中的结点全部标记存入unset中（哈希表） 遍历listB直到其中出现相同的next域的值 直接返回其值即为结果 若遍历listB都完都没有出现符合要求的结果则返回nullptr 1234567891011121314151617181920//注：将unordered_set放到成员方法内部可以提高时间效率class Solution {public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { unordered_set<ListNode*> unset; //1.initialize unset ListNode* tmp = headA; while (tmp) { unset.insert(tmp); tmp = tmp->next; } //2.find the first node tmp = headB; while (tmp) { if (unset.count(tmp)) return tmp; tmp = tmp->next; } return nullptr; }}; 时间：48ms 内存：16.24mb 时间复杂度：$O(N)$ 空间复杂度：$O(N)$ 2.双指针主要思路： 首先判断链表是否为空，如果其中有一个链表为空则两个链表一定不相交返回nullptr 当链表都不为空时 创建两个指 ...

链表中环的入口节点 原题链接：https://leetcode.cn/problems/c32eOV/ 给定一个链表，返回链表开始入环的第一个节点。 从链表的头节点开始沿着 next 指针进入环的第一个节点为环的入口节点。如果链表无环，则返回 null。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。 注意 pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。 说明：不允许修改给定的链表。 1.哈希表思路： 利用哈希表建立一个标记数组 用于标记已经出现的next指针域 while循环遍历链表 直到出现重复的next指针域 表示链表环开始出现 返回此时的链表结点指针 即为环入口结点 unordered_map1234567891011121314class Solution {public: unordered_map<ListNode*, int> mark; ListNode *detectCycle(ListNode *head) { if (head == nullptr) return nullptr; ListNode* p = head; while (p) { if (mark[p]) return p; mark[p] = 1; p = p->next; } return nullptr; }}; 时间：12ms 内存：9.8mb unordered_set12345678910111213public: unordered_set<ListNode*> mark; ListNode *detectCycle(ListNode *head) { if (head == nullptr) return nullptr; ListNode* p = head; while (p) { if (mark. ...

删除链表的倒数第 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.单链表数组实现的链表可以做指针实现的链表的所有事情，且数组实现的链表更快（静态链表），动态链表new操作太慢。 用数组模拟单链表，使用单链表构建一个邻接表（n个链表），用邻接表（最短路问题、最小生成树、最大流）进行存储图和树， 123int head;//头结点的next指针int data[MAX], next[MAX];//结点数据data、下一个结点的下标nextint currt;//当前可用点的下标 2.双链表用数组模拟双链表，双链表可用于优化某些问题， 12int dataa[MAX], left[MAX], right[MAX];//结点数据dataa、下一个结点的下标nexttint currt;//当前可用点的下标 3.AcWing826.单链表12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061#include<iostream>using namespace std;const int MAX = 100010;int head;//头结点的next指针int dataa[MAX], nextt[MAX];//结点数据dataa、下一个结点的下标nexttint currt;//当前可用点的下标void link_list_init() { head = -1; currt = 0;}void link_list_head_insert(int x) { dataa[currt] = x; nextt[currt] = head; head = currt; currt++;}void link_list_insert(int idx, int x) { dataa[currt] = x; nextt[currt] = nextt[idx]; nextt[idx] = currt; currt++;}void link_list_delete(int idx) { nextt[idx] = nextt[ne ...

栈 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") &# ...

队列 1.AcWing829.模拟队列12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758#include<iostream>using namespace std;const int MAX = 100010;typedef struct { int head; int tail; int data[MAX];} Queue;Queue queue1;void queue_push(Queue &queue, int x) { queue.data[queue.tail] = x; queue.tail++;}int queue_pop(Queue &queue) { int ret = queue.data[queue.head]; queue.head++; return ret;}int queue_head(Queue &queue) { return queue.data[queue.head];}bool queue_empty(Queue &queue) { if (queue.head < queue.tail) 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 data; while (m--) { cin >> opt; if (opt == "push") { cin >> x; queue_push(queue1, x); } else if (opt == "pop") { queue_pop(queue1); } e ...

移除指定元素 原题链接：https://leetcode.cn/problems/remove-element/ 1.巧妙的移动元素1234567891011121314class Solution {public: int removeElement(vector<int>& nums, int val) { int count = 0; for (int i = 0; i < nums.size(); ++i) { if (nums[i] == val) { count++; } else { nums[i - count] = nums[i]; } } return nums.size() - count; }}; 2.重复项删除类似12345678910111213class Solution {public: int removeElement(vector<int>& nums, int val) { int black = 0; for (int red = 0; red < nums.size(); ++red) { if (nums[red] != val) { nums[black] = nums[red]; black++; } } return black; }};

字符串括号匹配 原题链接：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 ...