单调栈 class Solution { public: vector<int> temperatures(vector<int>& dailyTemperatures) { //由于要找某个元素右边最近的比这个元素大的位置,所以可以逆向遍历创建一个单调栈 stack<int> stack1; int n =dailyTemperatures.size(); vector<int> ans; //逆向遍历创建一个单调栈 //...

class Solution { public: string decodeString(string s) { //定义两个栈 //栈1用于括号的匹配 //栈2用于辅助反转字符串 stack<char>stack1; stack<char>stack2; int n=s.length(); //ans和t都是用来辅助存过程中的字符串，answer用来存最后的答案字符串 string ans; string t,answ...

import java.util.*; public class Solution { public boolean isValidString (String s) { //创建两个linkedList(是基于双向链表实现的)，new LinkedList<>(); //ArrayList是基于数组实现的，动态分配内存 LinkedList<Integer> left=new LinkedList<>(); LinkedList<Integer> star=new Li...

class Solution { public: vector<vector<int> > foundMonotoneStack(vector<int>& nums) { int len=nums.size(); //调用vector的无参构造函数创建一个长度为len，宽为1的二维容器 vector<vector<int>> ans(len); //遍历二维容器的每一行，调用resize函数将容器的每一行的列宽都扩大为2 for(int i...

class Solution { public: vector<int> solve(vector<int>&a) { //ans用来存最后的答案，f数组用来存后面要入栈的剩余元素中的最大值 //倒序处理最大值 vector<int> ans,f(a.size()); stack<int> stack1; //先让f数组的最后一个元素的值为无穷小 //再从f数组倒数第二位开始填写 //倒序将f数组和a数组从最后一位开始...

class Solution { public: //创建三个容器用于存前序、中序、后序遍历的结果 vector<int>pre; vector<int>mid; vector<int>post; vector<vector<int> > threeOrders(TreeNode* root) { //只要根节点存在，就求这棵树的前序、中序、后序 if(root!=nullptr){ preorder(root); midorder(...

链接 public: string removeDuplicates(string s) { //创建一个栈 stack<char> stack1; //遍历字符串 for(int i=0;i<s.size();i++){ //只要栈不为空，并且栈顶元素与要入栈的字符是相同的，就让栈顶元素出栈 if(!stack1.empty()&&s[i]==stack1.top()){ stack1.pop(); ...

求m区间的最小值 代码1；（手写单调队列） #include<iostream> using namespace std; #define N 2000005 int n,m,a[N],b[N]; int head=0,rear=0; int main(){ scanf("%d %d",&n,&m); scanf("%d",&a[1]); printf("0\n"); b[rear]=1; for(int i=2;i<=n;i++){ scanf("%d",&a[i]); //注意队列为空的判断条件，如果初始化时head...

数据流中的中位数 方法一：vector中的sort函数 class Solution { public: vector<int> v; //将数据流输入到容器vector中存储 void Insert(int num) { v.push_back(num); } //由于vector自带排序函数sort，所以可以用vector自带的sort函数进行排序 //排好序后判断一下容器中的元素个数是奇数还是偶数 //如果是奇数，就返回下标为n/2的位置的值 //如果是偶数，就返回下标为n/2加上n/2-1...

寻找第k大 思路：快排+二分 1.对于快排，先设置第一个数为基准数 2.设置一个指针i指向区间的左端点，设置一个指针j指向区间的右端点 3.只要两个指针没有相遇，即i<j,就继续循环 4.i指针只要还没有与j指针相遇（i<j）,如果要进行升序，就让i去找比基准大的数，这样交换后就是大数在后 5.j指针只要还没有与j指针相遇（i<j）,如果要进行升序，就让j去找比基准小的数，这样交换后就是小数在前 5.降序操作相反 6.只要两个指针没有相遇，就将两个数交换 7.最后将基准数与指针相遇的位置的值进行交换 8.递归求[l,i-1]区间和[i+1,r]区间进行快排 用二分的思...

最小的k个数 方法一：用vector中的sort函数进行排序 思路： vector<int>input; sort(input.begin(),input.end()) return vector<int>({input.begin(),input.begin()+k}); 代码： class Solution{ public: vector<int> GetLeastNumbers_Solution(vector<int> input,int k){ vector<int> res; ...

循环队列（模板） 思路： 1.创建一个结构体用来表示循环队列：一个数组，一个队首head,一个队尾rear 2.初始化循环队列：head==rear=0; 3.如果head==rear,则队列为空 4.如果(rear+1)%(n+1)==head,则循环队列为满，注意是由于是循环队列，所以要取余才能得到正确的下标，注意由于对于循环队列会浪费一个空间，所以要申请n+1个空间，所以要取余（n+1） 5.将元素插入循环队列中，只要队列未满，则存到rear的位置，再让(rear+1)%(n+1) 6.输出队首元素，让队首元素出队列，head后移动一位，(head+1)%(n+1) 代码： #i...

队列（模板） 思路： 1.构造一个结构体表示队列：包含一个数组用来存队列中的元素，一个队头指针head，一个队列的尾指针rear 2.初始化为空队列：head=rear=0; 3.从队尾插入元素，即将元素插入下标为rear的位置，再将rear++ 4.获得队首，即head处的元素 5.让队首出队列，即让head++ 6.判断队列是否为空：如果head==rear,则队列为空 代码： #include<iostream> using namespace std; //最多进行的操作数 const int N=100005; int n,m; string op; //定义一个队...

链表（模板） 思路： 对于链表的插入和删除节点操作，由于头结点的插入和删除和其他节点的插入和删除操作不同，所以为了方便操作，可以增加一个虚的头节点，对于插入和删除操作设置两个指针pre和cur,pre指向需要删除或是插入的位置，pre指向需要删除或插入的位置的前一个节点 1.插入操作：创建一个新的节点，将pre的next指针指向新的节点，将新节点的next指向cur 2.删除操作：将pre的next指针指向cur的下一个节点 代码： #include<iostream> using namespace std; //对于创建静态链表：构造一个结构体表示链表的每个节点： /...