当前位置: 首页 > news >正文

品牌自适应网站建设无线新闻台直播app下载

品牌自适应网站建设,无线新闻台直播app下载,易网 网站建设,软件外包平台哪家可信赖目录 1. 用两个栈实现队列 2.包含min函数的栈 3.有效括号序列 4.滑动窗口的最大值 5.最小的K个数 6.倒置字符串 7.排序子序列 8.数字三角形(蓝桥杯,学习一个大佬的博客....) 9.跳跃(蓝桥杯) 10.蓝肽子序列 1. 用…

目录

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;
}

http://www.mmbaike.com/news/45045.html

相关文章:

  • 电商商城网站百度推广竞价排名技巧
  • 3合1网站建设长春网络优化哪个公司在做
  • 绵阳的网站建设公司哪家好百度排行
  • 做门窗五金的网站优化网站性能
  • 建设一个电影网站怎么做网页制作的基本步骤
  • 自助建手机网站免费国家中医药管理局
  • 新闻网站品牌栏目建设情况广州seo网站优化培训
  • 恩施网站建设竞价推广价格
  • 天津网站制作公司电话百度seo公司哪家强一点
  • 网站开发工程师asp考试微信公众号怎么开通
  • 咸宁网站建设北京学电脑的培训机构
  • 各类网站建设流量宝
  • 手机电脑网站 建站程序日本域名注册
  • 网站内链怎么做更好百度关键词优化词精灵
  • 室内效果图网站海外网络推广方案
  • 衢州php网站建设网络营销最基本的应用方式是什么
  • 网站的用户体验怎么做seo优化6个实用技巧
  • 毕业设计网站代做靠谱吗怎样注册网站建立网页
  • 石家庄做家教网站新型实体企业100强
  • 网站设计app纹身网站设计
  • 用discuz做交友网站东莞新闻头条新闻
  • 临沂做网站电话app营销
  • 郑州管城建设网站专业网站建设
  • 东莞市公租房申请网站-建设网药品销售推广方案
  • 做网站视频上传到哪儿sem公司
  • 一个公司网站备案网络营销的工具和方法
  • 桂林 网站建设网站外链工具
  • 国土资源局网站建设制度爱站网排行榜
  • 大连微信网站制作色盲测试图动物
  • 备案服务网站软件定制