【C++】面试101，用两个栈实现队列,包含min函数的栈，有效括号序列,滑动窗口的最大值,最小的K个数，倒置字符串，排序子序列，跳跃，数字三角形，蓝肽子序列

目录

1. 用两个栈实现队列

 2.包含min函数的栈

3.有效括号序列

 4.滑动窗口的最大值

5.最小的K个数

6.倒置字符串

 7.排序子序列

8.数字三角形（蓝桥杯，学习一个大佬的博客....）

 9.跳跃（蓝桥杯）

10.蓝肽子序列

---

 

1. 用两个栈实现队列

之前我们C实现过一次

但是当时手搓的栈和队列....

现在我们开始C++实现一把

一个栈可以实现队列的push，但是由于两种数据结构的性质，一个栈不能满足先进先出

加入辅助栈

把队列栈的数据导入辅助栈，这时候栈顶pop就可以成功删除

例如：队列栈push：  1  2  3

正确pop：1 2 3

现在辅助栈是空，把队列栈数据导入：3 2 1

删除辅助栈栈顶：1 2 3

只要辅助栈为空，就一次性导入所有队列栈元素

辅助栈不为空，优先pop辅助栈数据，因为这可能是上一个残留元素，顺序不能乱 

class Solution
{
public:void push(int node) {stack1.push(node); //随便选一个栈作为构建队列的栈（队列栈），这里选stack2也可以，但是下面所有都要换}int pop() {if (stack2.empty()) //如果辅助栈是空 {while (!stack1.empty()) //当队列栈不是空{stack2.push(stack1.top()); //把队列栈导入辅助栈stack1.pop();}}int ans = stack2.top();//辅助栈pop顺序是要删除的顺序stack2.pop();return ans;}private:stack<int> stack1;stack<int> stack2;
};

 2.包含min函数的栈

现在还记得C写的阴影

用C++实现一下

真的很简单啊，push函数，只要min栈为空或者现在要入的值<=min栈栈顶元素，那么入栈

class Solution {
public:void push(int value) {s.push(value);if(_min.empty()||value<=_min.top())_min.push(value);}void pop() {int top=s.top();       s.pop();if(top==_min.top())_min.pop();}int top() {return s.top();}int min() {return _min.top();}stack <int> s;stack<int> _min;
};

3.有效括号序列

首先碰到左括号入栈，如果遇到右括号，栈为空或者栈顶不是和他匹配的左括号，那么直接false

遍历字符串结束之后，如果栈是不是空，证明左括号没有匹配完全，那么false 

  bool isValid(string s) {// write code herestack<char> st;for(int i=0;i<s.size();i++){if(s[i]=='{' || s[i]=='[' || s[i]=='(')st.push(s[i]);if(s[i]==']'){if(st.empty()||st.top()!='[')return false;st.pop();}else if(s[i]=='}'){if(st.empty()||st.top()!='{')return false;st.pop();}if(s[i]==')'){if(st.empty()||st.top()!='(')return false;st.pop();}}if(st.empty()) return true;return false;}

 4.滑动窗口的最大值

这个题我是暴力写的，直接挨个遍历每个窗口，找里面的最大

 vector<int> maxInWindows(const vector<int>& num, unsigned int size) {vector<int > v;if(size==0 || size>num.size()) return v;for(int i=0;i<num.size()-size+1;i++){int max=num[i];for(int j=i;j<size+i;j++)if(num[j]>max) max=num[j];v.push_back(max);}return v;}

 学习一下大佬们的代码

其实就是把我们的思路写在队列...

    vector<int> maxInWindows(const vector<int>& num, unsigned int size) {//     vector<int > v;//     if(size==0 || size>num.size()) return v;//   for(int i=0;i<num.size()-size+1;i++)//   {//       int max=num[i];//       for(int j=i;j<size+i;j++)//       if(num[j]>max) max=num[j];//       v.push_back(max);//   }//     return v;vector<int> ans;queue<int> q;if(size==0 || size>num.size()) return ans;for(int i=0;i<num.size()&&i+size<=num.size();i++){q.push(num[i]);for(int j=i;j<i+size;j++){if(num[j]>q.front()){q.pop();q.push(num[j]);}}ans.push_back(q.front());while(!q.empty())q.pop();}return ans;}

5.最小的K个数

其实就是建大堆，把最小的前k入到优先级队列(默认大堆）

  vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {vector<int > ans;if(!k) return ans;priority_queue<int> pq;for(int i=0;i<k;i++){pq.push(input[i]);}for(int j=k;j<input.size();j++){if(input[j]<pq.top()){pq.pop();pq.push(input[j]);}}while(!pq.empty()){ans.push_back(pq.top());pq.pop();}return ans;}

6.倒置字符串

之前用C实现过，真的不好理解，很绕

但是这次用C++

oj最好不要cin>>s，其中s是一个字符串，用getline函数

 

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;int main1()
{string s1;while (getline(cin, s1)){reverse(s1.begin(), s1.end());//将整个句子逆置auto start = s1.begin();for (int i = 0;s1.begin()+i!=s.end()+1; i++)//可能不会直接到end(){if (s1[i] == ' '){auto end = s1.begin() + i;reverse(start, end);//将每个单词逆置回来,逆置空格前的字符串start = end + 1;//跳过空格进入下一个单词}if(s1.begin() + i == s1.end())//最后一个单词找没有空格，所以找到s1.end()进行逆置{reverse(start, s1.end());}}cout << s1 << endl;}return 0;
}

 7.排序子序列

一定要注意，在一个非递增/非递减的区间里，是可以有重复的元素，但是在遍历整个数组的时候，遇到重复元素直接跳过！因为你放哪个区间都不合适，还会影响子序列的判断 

#include<iostream>
#include<vector>using namespace std;int main(){int n;cin >> n;vector<int> a;a.resize(n + 1);a[n] = 0;int i = 0;for (i = 0; i < n; ++i){cin >> a[i];}i = 0;int count = 0;while (i < n){// 非递减子序列if (a[i] < a[i + 1]){while (i < n && a[i] <= a[i + 1]){i++;}count++;i++;}else if (a[i] == a[i + 1]){i++;}else // 非递增子序列{while (i < n && a[i] >= a[i + 1]){i++;}count++;i++;}}cout << count << endl;return 0;}

8.数字三角形（蓝桥杯，学习一个大佬的博客....）

首先观察到这个题目要求

 

所以写一个dfs的代码，看一下最后的结果应该是什么样的 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;int n;
vector< vector<bool> >flag(101);void dfs(int i, int j, int time)//向左，time-1;向右，time+1
{if (flag[i][j])//若当前点已递归过，则直接返回（降低时间复杂度）return;flag[i][j] = true;//当前点满足if (time == -1 && i + 1 < n)//必须向右dfs(i + 1, j + 1, 0);//向右下方点递归else if (time == 1 && i + 1 < n)//必须向左dfs(i + 1, j, 0);//向左下方点递归else if (!time && i + 1 < n)//可向左也可向右{dfs(i + 1, j + 1, 1);dfs(i + 1, j, -1);}else//其他情况则返回return;
}int main()
{cin >> n;for (int i = 0; i < n; i++)for (int j = 0; j < i + 1; j++)flag[i].push_back(false);//初始化为falsedfs(0, 0, 0);//从第一个点往下递归//输出结果for (int i = 0; i < n; i++){for (int j = 0; j < i + 1; j++)if (flag[i][j])cout << "1 ";elsecout << "0 ";cout << endl;}cout << endl << endl;return 0;
}

这个是n=11的代码

 

 

 n=10

发下规律，然后从倒数第二行往上动态规划

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;int n, tmp;
vector< vector<int> >num(101);
vector< vector<bool> >flag(101);int main()
{// 请在此输入您的代码cin >> n;for (int i = 0; i < n; i++)for (int j = 0; j < i + 1; j++){cin >> tmp;num[i].push_back(tmp);flag[i].push_back(false);}if (n % 2)	//n为奇数，则最后一行有奇数个数，最中间的数可作为终点flag[n - 1][(n - 1) / 2] = true;else		//i为偶数，则最后一行有偶数个数，最中间两个数可作为终点{flag[n - 1][n / 2] = true;flag[n - 1][n / 2 - 1] = true;}for (int j = 0; j < n; j++)//最后一行其余的数设为0if (!flag[n - 1][j])num[n - 1][j] = 0;for (int i = n - 2; i >= 0; i--)//从倒数第二行往上遍历{for (int j = 0; j <= i; j++)//从左往右遍历{if (!flag[i + 1][j] && !flag[i + 1][j + 1])//该点不能到达num[i][j] = 0;//设为0，方便计算else										//该点能到达{num[i][j] += max(num[i + 1][j], num[i + 1][j + 1]);//取两者最大即可flag[i][j] = true;//标记该点能到达}}}cout << num[0][0] << endl;//输出结果return 0;
}

 9.跳跃（蓝桥杯）

#include <iostream>
#include <algorithm>
#include "string.h"
#include <climits>
#include <vector>
using namespace std;int n, m;
vector< vector<int> >weight(101);//每个点的权值
vector< vector<long long> >totoal_weight(101);//存储走到每个点的最大权值和long long find_max(int x, int y)//找到走到该点的所需的最大权值和（不包括该点的权值）
{long long max = LLONG_MIN;for (int i = x; i >= 1; i--)//从该点往上{for (int j = y; j >= 1; j--)//从该点往左{//1.不能原地踏步，所以不能与该点坐标一样//2.步数要小于等于3//3.要比当前的max大才更新maxif (!(x == i && y == j) && (x - i + y - j) <= 3 && max < totoal_weight[i][j])max = totoal_weight[i][j];}}if (max == LLONG_MIN)//说明是起点，返回0即可return 0;else                 //返回走到该点所需的最大权值和（不包括该点的权值）return max;
}int main()
{cin >> n >> m;int w;//临时变量，某点的权值for (int i = 1; i <= n; i++)    //行输入{weight[i].push_back(0);    //占位，因为j要从1开始，而数组下标从0开始totoal_weight[i].push_back(0);  //占位for (int j = 1; j <= m; j++)    //列输入{cin >> w;weight[i].push_back(w);         totoal_weight[i].push_back(w);}}for (int i = 1; i <= n; i++)        //从上往下{    for (int j = 1; j <= m; j++)    //从左往右{totoal_weight[i][j] += find_max(i, j);//得到每个点的最大权值和}}cout << totoal_weight[n][m] << endl;    //输出最后一个点的最大权值和return 0;
}

10.蓝肽子序列

#include <iostream>
#include <algorithm>
using namespace std;
int dp[1005][1005];
string s1, s2;
string str1[1005], str2[1005];
int cnt1, cnt2;
int main()
{cin >> s1 >> s2;int d1 = s1.length(), d2 = s2.length();for (int i = 0; i < d1;){cnt1++;if (s1[i] >= 'A' && s1[i] <= 'Z'){str1[cnt1] += s1[i++];while (s1[i] >= 'a' && s1[i] <= 'z'){str1[cnt1] += s1[i++];}}}for (int i = 0; i < d2;){cnt2++;if (s2[i] >= 'A' && s2[i] <= 'Z'){str2[cnt2] += s2[i++];while (s2[i] >= 'a' && s2[i] <= 'z'){str2[cnt2] += s2[i++];}}}for (int i = 1; i <= cnt1; i++)for (int j = 1; j <= cnt2; j++){if (str1[i] == str2[j]) dp[i][j] = dp[i - 1][j - 1] + 1;else dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);}cout << dp[cnt1 ][cnt2 ] << endl;return 0;
}