Violet

代码随想录算法训练营第十三天 | 239. 滑动窗口最大值 347. 前 K 个高频元素滑动窗口最大值思路：定义一个数据结构，包含pop，push，getmax。其中pop()将deque结构的前端弹出（满足相应条件）push（）将数据push入deque中（满足其前面没有比其大的数据，若有将前面元素弹出（因为比其小的元素不可能成为最大值了））getmax获取que.front即可。 123456789101112131415161718192021222324252627282930313233343536373839404142class Solution {private: class MyQueue { //单调队列（从大到小） public: deque<int> que; // 使用deque来实现单调队列 // 每次弹出的时候，比较当前要弹出的数值是否等于队列出口元素的数值，如果相等则弹出。 // 同时pop之前判断队列当前是否为空。 void pop(int value) ...

代码随想录算法训练营第十一天 | 20.有效的括号 1047. 删除字符串中的所有相邻重复项 150.逆波兰表达式求值有效的括号思路：括号匹配是使用栈解决的经典问题。首先判断字符串是否为奇数,奇数返回false。声明栈st，遍历字符串，若遇到左括号则将右括号push入栈。若遇到右括号，则看他是否与st.top相同，若不相同则返回false，否则将st.top pop，遍历结束返回st.empty(); 123456789101112131415161718class Solution {public: bool isValid(string s) { if (s.size() % 2 != 0) return false; // 如果s的长度为奇数，一定不符合要求 stack<char> st; for (int i = 0; i < s.size(); i++) { if (s[i] == '(') st.push(')'); ...

代码随想录算法训练营第十天 | 232.用栈实现队列 225.用队列实现栈用栈实现队列思路：在push数据的时候，只要数据放进输入栈就好，但在pop的时候，操作就复杂一些，输出栈如果为空，就把进栈数据全部导入进来（注意是全部导入），再从出栈弹出数据，如果输出栈不为空，则直接从出栈弹出数据就可以了。最后如何判断队列为空呢？如果进栈和出栈都为空的话，说明模拟的队列为空了。 12345678910111213141516171819202122232425262728293031323334class MyQueue {public: stack<int> stIn; stack<int> stOut; MyQueue() { } void push(int x) { stIn.push(x); } int pop() { if (stOut.empty()) { while (!stIn.empty()) ...

代码随想录算法训练营第九天 |28.找出字符串中第一个匹配项的下标 双指针回顾找出字符串中第一个匹配项的下标思路：应用kmp算法 123456789101112131415161718192021222324252627282930313233343536class Solution {public: void getNext(int* next, const string& s) { int j = 0; next[0] = 0; for(int i = 1; i < s.size(); i++) { while (j > 0 && s[i] != s[j]) { j = next[j - 1]; } if (s[i] == s[j]) { j++; } next[ ...

代码随想录算法训练营第八天 |344.反转字符串 541.反转字符串II 替换数字 151.反转字符串中的单词 右旋字符串反转字符串思路：双指针法 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]); } }}; 反转字符串II思路：在遍历字符串的过程中，只要让 i += (2 * k)，i 每次移动 2 * k 就可以了，然后判断是否需要有反转的区间。 123456789101112131415161718192021class Solution {public: void reverse(string& s, int start, int end)  ...

代码随想录算法训练营第七天 |454.四数相加II 383.赎金信 15.三数之和 18.四数之和思路：首先定义 一个unordered_map，key放a和b两数之和，value 放a和b两数之和出现的次数。遍历大A和大B数组，统计两个数组元素之和，和出现的次数，放到map中。定义int变量count，用来统计 a+b+c+d = 0 出现的次数。在遍历大C和大D数组，找到如果 0-(c+d) 在map中出现过的话，就用count把map中key对应的value也就是出现次数统计出来。最后返回统计值 count 就可以了 12345678910111213141516171819202122class Solution {public: int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) { unordered_map<int, int> ...

代码随想录算法训练营第六天 | 242. 有效的字母异位词 349.两个数组的交集 202. 快乐数 1.两数之和有效的字母异位词思路：定义一个数组叫做record用来上记录字符串s里字符出现的次数。 需要把字符映射到数组也就是哈希表的索引下标上，因为字符a到字符z的ASCII是26个连续的数值，所以字符a映射为下标0，相应的字符z映射为下标25。 再遍历 字符串s的时候，只需要将 s[i] - ‘a’ 所在的元素做+1 操作即可，并不需要记住字符a的ASCII，只要求出一个相对数值就可以了。 这样就将字符串s中字符出现的次数，统计出来了。 那看一下如何检查字符串t中是否出现了这些字符，同样在遍历字符串t的时候，对t中出现的字符映射哈希表索引上的数值再做-1的操作。 那么最后检查一下，record数组如果有的元素不为零0，说明字符串s和t一定是谁多了字符或者谁少了字符，return false。 最后如果record数组所有元素都为零0，说明字符串s和t是字母异位词，return true。 时间复杂度为O(n)，空间上因为定义是的一个常量大小的辅助数组，所以空间复杂度为O(1)。 1 ...

代码随想录算法训练营第四天 | 24. 两两交换链表中的节点 19.删除链表的倒数第N个节点 02.07. 链表相交 142.环形链表II两两交换链表中的节点思路：设置虚拟头结点，然后两两交换。 1234567891011121314151617class Solution {public: ListNode* swapPairs(ListNode* head) { ListNode* ahead = new ListNode(); ahead->next= head; ListNode* temp; ListNode* cur = ahead; while (head!=NULL) { cur->next = head->next; temp = head->next->next; head->next->next = head; head = tem ...

代码随想录算法训练营第三天 | 203.移除链表元素、 707.设计链表、 206.反转链表移除链表元素思路：遍历链表，若遇到目标值，则删除，记得释放内存 12345678910111213141516171819202122232425262728/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */class Solution {public: ListNode* removeElements(ListNode* head, in ...

代码随想录算法训练营第二天 | 977.有序数组的平方、209.长度最小的子数组、59.螺旋矩阵有序数组的平方1.思路：遍历整个数组将其平方，用冒泡排序将其排列。超时！！！应用双指针法，数组是有序的，只不过负数平方之后可能成为最大数了。那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。i指向开头，j指向结尾。将较大值插入到新数组。 1234567891011121314151617181920class Solution {public: vector<int> sortedSquares(vector<int>& nums) { int i = 0; int j = nums.size() - 1; vector<int> result(nums.size(), 0); int n = j; while (i<=j) { if (nums[i] * nums[i] < nums[j ...