JJXxXLL

介绍栈和队列是STL（C++标准库）里面的两个数据结构。 HP STL 其他版本的C++ STL，一般是以HP STL为蓝本实现出来的，HP STL是C++ STL的第一个实现版本，而且开放源代码。 P.J.Plauger STL 由P.J.Plauger参照HP STL实现出来的，被Visual C++编译器所采用，不是开源的。 SGI STL 由Silicon Graphics Computer Systems公司参照HP STL实现，被Linux的C++编译器GCC所采用，SGI STL是开源软件，源码可读性甚高。 栈和队列也是SGI STL里面的数据结构 stack push(): 在栈顶添加一个元素。 pop(): 移除栈顶元素。 top(): 返回栈顶元素的引用，但不移除它。 empty():检查栈是否为空。 size(): 返回栈中元素的数量。 queue empty(): 检查队列是否为空。 size(): 返回队列中的元素数量。 front(): 返回队首元素的引用。 back(): 返回队尾元素的引用。 push(): 在队尾添加一个元素。 ...

151.翻转字符串里的单词题目链接状态：一遍过思路：使用栈，先进后出，除去空格 12345678910111213141516171819202122232425class Solution {public: string reverseWords(string s) { stack<string> stack; int n=s.size(); for(int i=0;i<n;i++){ string tmp; while(i<n&&s[i]!=' '){ tmp+=s[i++]; } if(tmp!=""){ stack.push(tmp); } } string ans = stac ...

344.反转字符串题目链接状态: 一遍过思路: 基础题 1234567891011class Solution {public: void reverseString(vector<char>& s) { int n=s.size(); for(int i=0;i<n/2;i++){ char tmp=s[i]; s[i]=s[n-i-1]; s[n-i-1]=tmp; } }}; 简洁版本 12345678class Solution {public: void reverseString(vector<char>& s) { for (int i = 0, j = s.size() - 1; i < s.size()/2; i++, j--) { swap(s[i],s[j]); ...

454.四数相加II题目链接状态：一次过但耗时长思路：和两数加和思路一样 12345678910111213141516class Solution {public: int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) { unordered_map<int, int> mp; int res = 0; for (int i : nums1) for (int j : nums2) mp[-(i + j)]++; for (int i : nums3) for (int j : nums4) res += mp[i + j];// 如果 m ...

哈希表理论基础目的：快速判断一个元素是否出现集合里常见的三种哈希结构数组、set （集合）、map(映射)（偷懒直接截图了） 242.有效的字母异位词题目链接状态：两遍过错误原因：为考虑两字符串长度不同可直接返回false思路：之前在《904. 水果成篮》中学到的unordered_map可直接用 12345678910111213class Solution {public: bool isAnagram(string s, string t) { int m = s.size(), n = t.size(); if (m != n) return false;//第一次未考虑到 unordered_map<char, int> ans; for (int i = 0; i < m; i++) ans[s[i]]++; for (int j = 0; j < n; j++) if (--ans[t[j]] < 0) ...

24. 两两交换链表中的节点题目链接状态： 一遍过思路： 使用虚拟节点放在开头，注意盯住三个节点的变化即可 原始代码 1234567891011121314151617181920212223class Solution {public: ListNode* swapPairs(ListNode* head) { if (head == nullptr || head->next == nullptr) return head; ListNode* dummynode = new ListNode(0); dummynode->next = head; ListNode *cur = head->next, *pre = head, *h = dummynode; while (cur != nullptr) { pre->next = cur->next; cur->next = ...

链表一、定义与方法使用结构体 123456// 单链表struct ListNode { int val; // 节点上存储的元素 ListNode *next; // 指向下一个节点的指针 ListNode(int x): val(x), next(NULL) {} // 节点的构造函数}; 使用类 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778class LNode {public: int val; LNode *next; LNode(int x) : val(x), next(nullptr) {}};class LinkedList {private: LNode *head;public: ...

27. 移除元素题目链接状态：一遍过思路：直接遍历一遍，若不等则改变 12345678910class Solution {public: int removeElement(vector<int>& nums, int val) { int k = 0, n = nums.size(); for (int i = 0; i < n; i++) if (nums[i] != val) nums[k++] = nums[i]; return k; }}; 小结：此方法为双指针法或快慢指针法 26. 删除有序数组中的重复项题目链接状态：有思路但错了很多次错误原因：下标范围错误，因为要考虑第一个元素的问题，判断错误 1234567891011121314151617class Solution {public: int removeDuplicates(vector<int>& nums ...

704. 二分查找题目链接 状态：一遍过思路：基本功 35. 搜索插入位置题目链接状态：有思路且三遍过思路：注意是升序，分两种情况： 数组中有该元素 = 二分查找 数组中没有该元素 = 查找失败后情况为： $left>right$ left向右超过right，说明nums[right]<target,right+1=left=n right向左超过left，说明位置在开头nums[left ]<target,right+1=left=n 答案思路：考虑所有情况： // 分别处理如下四种情况 // 目标值在数组所有元素之前 [0, -1] // 目标值等于数组中某一个元素 return middle; // 目标值插入数组中的位置 [left, right]，return right + 1 // 目标值在数组所有元素之后的情况 [left, right]， 因为是右闭区间， 所以 return right + 1 暴力解法： 12345678910111213141516class ...