月嫂公司网站建设构思,织梦网站栏目建设,wordpress hestia pro,郑州市网络设计目录
1. 用两个栈实现队列 2.包含min函数的栈
3.有效括号序列 4.滑动窗口的最大值
5.最小的K个数
6.倒置字符串 7.排序子序列
8.数字三角形#xff08;蓝桥杯#xff0c;学习一个大佬的博客....#xff09; 9.跳跃#xff08;蓝桥杯#xff09;
10.蓝肽子序列 1. 用…目录
1. 用两个栈实现队列 2.包含min函数的栈
3.有效括号序列 4.滑动窗口的最大值
5.最小的K个数
6.倒置字符串 7.排序子序列
8.数字三角形蓝桥杯学习一个大佬的博客.... 9.跳跃蓝桥杯
10.蓝肽子序列 1. 用两个栈实现队列
之前我们C实现过一次
但是当时手搓的栈和队列....
现在我们开始C实现一把
一个栈可以实现队列的push但是由于两种数据结构的性质一个栈不能满足先进先出
加入辅助栈
把队列栈的数据导入辅助栈这时候栈顶pop就可以成功删除
例如队列栈push 1 2 3
正确pop1 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:stackint stack1;stackint 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 tops.top(); s.pop();if(top_min.top())_min.pop();}int top() {return s.top();}int min() {return _min.top();}stack int s;stackint _min;
};
3.有效括号序列
首先碰到左括号入栈如果遇到右括号栈为空或者栈顶不是和他匹配的左括号那么直接false
遍历字符串结束之后如果栈是不是空证明左括号没有匹配完全那么false bool isValid(string s) {// write code herestackchar st;for(int i0;is.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.滑动窗口的最大值
这个题我是暴力写的直接挨个遍历每个窗口找里面的最大 vectorint maxInWindows(const vectorint num, unsigned int size) {vectorint v;if(size0 || sizenum.size()) return v;for(int i0;inum.size()-size1;i){int maxnum[i];for(int ji;jsizei;j)if(num[j]max) maxnum[j];v.push_back(max);}return v;} 学习一下大佬们的代码
其实就是把我们的思路写在队列... vectorint maxInWindows(const vectorint num, unsigned int size) {// vectorint v;// if(size0 || sizenum.size()) return v;// for(int i0;inum.size()-size1;i)// {// int maxnum[i];// for(int ji;jsizei;j)// if(num[j]max) maxnum[j];// v.push_back(max);// }// return v;vectorint ans;queueint q;if(size0 || sizenum.size()) return ans;for(int i0;inum.size()isizenum.size();i){q.push(num[i]);for(int ji;jisize;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入到优先级队列(默认大堆 vectorint GetLeastNumbers_Solution(vectorint input, int k) {vectorint ans;if(!k) return ans;priority_queueint pq;for(int i0;ik;i){pq.push(input[i]);}for(int jk;jinput.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最好不要cins其中s是一个字符串用getline函数 #includeiostream
#includestring
#includevector
#includealgorithm
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.排序子序列
一定要注意在一个非递增/非递减的区间里是可以有重复的元素但是在遍历整个数组的时候遇到重复元素直接跳过因为你放哪个区间都不合适还会影响子序列的判断
#includeiostream
#includevectorusing namespace std;int main(){int n;cin n;vectorint 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 vectorbool flag(101);void dfs(int i, int j, int time)//向左time-1;向右time1
{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;
} 这个是n11的代码 n10
发下规律然后从倒数第二行往上动态规划 #include iostream
#include vector
#include algorithm
using namespace std;int n, tmp;
vector vectorint num(101);
vector vectorbool 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 vectorint weight(101);//每个点的权值
vector vectorlong 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;
}
