数据结构不难9
2019/3/22更新:第一次更 没来得及写解题思路
————————————————————————
时间限制:1000ms
单点时限:1000ms
内存限制:256MB
描述
翻转一个链表
特殊要求：请使用以下链表结构
class Node
{
int value;
Node next;
}
输入
输入包含多组数据。对于每组数据：
第一行是n，表示链表长度；当n=-1时，表示输入结束。(1 <= n <= 100)
第二行是n个整数，表示链表每一位所存储的内容。
输出
针对每组输入，输出翻转后的链表的内容。
样例输入
4
1 3 5 7
-1
样例输出
7 5 3 1
ac代码
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
class ListNode
{
public:
int val;
ListNode *next;
ListNode (int val)
{
this->val = val;
this->next = NULL;
}
};
int main()
{
int n;
while (1) {
cin >> n;
if (n == -1) break;
ListNode dummy(0), *cur = &dummy;
int val;
// construct the linked list
for (int i = 0; i < n&&val!=-1; ++i) {
cin >> val;
cur->next = new ListNode(val);
cur = cur->next;
}
// reverse
ListNode *head = dummy.next;
ListNode *prev = NULL;
while (head) {
ListNode *next = head->next;
head->next = prev;
prev = head;
head = next;
}
head = prev;
// print
while (head->next) {
cout << head->val << " ";
head = head->next;
}
cout << head->val << endl;
}
}
第二题
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
<dl class="des">
描述
编写一个程序可以完成基本的带括号的四则运算。其中除法(/)是整除，并且在负数除法时向0取整。(C/C++/Java默认的除法就是向0取整，python默认的是向负无穷取整。)
例如计算 100 * ( 2 + 12 ) - (20 / 3) * 2, 结果是1388。
输入
一个长度不超过100的字符串，代表要计算的算式。包含数字0-9以及+-*/()。
输入保证计算过程不会超过32位有符号整数，并且其中的'-'都是减号没有负号。
输出
计算的结果。
样例输入
100*(2+12)-(20/3)*2
样例输出
1388
AC代码
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<string>
#include<stack>
using namespace std;
int getrink(char opt)
{
if(opt == '+' || opt == '-') return 10;
if(opt == '*' || opt == '/') return 20;
if(opt == '(') return 0;
else return -1;
}
int postfix(string &str_post,string &str_mid)
{
stack<char> opt;
while(!opt.empty()) opt.pop();
bool flag=false;
for(int i=0; str_mid[i]!='\0'; i++)
{
if(str_mid[i]>='0'&&str_mid[i]<='9')
{
if(flag)
{
str_post+='&';
}
else
{
flag=true;
}
while(str_mid[i]>='0'&&str_mid[i]<='9')
{
str_post+=str_mid[i];
i++;
}
i--;
}
else if(str_mid[i]=='(')
{
opt.push(str_mid[i]);
}
else if(str_mid[i]==')')
{
if(!opt.empty()&&opt.top()!='(')
{
str_post+=opt.top();
opt.pop();
flag=false;
}
if(opt.top()=='(')
{
opt.pop();
}
}
else if(str_mid[i]=='+'||str_mid[i]=='-'||str_mid[i]=='*'||str_mid[i]=='/')
{
int a1=getrink(str_mid[i]);
int a2;
while(!opt.empty())
{
a2=getrink(opt.top());
if(a1<=a2)
{
str_post+=opt.top();
opt.pop();
flag=false;
}
else
{
break;
}
}
opt.push(str_mid[i]);
}
}
while(!opt.empty())
{
str_post+=opt.top();
opt.pop();
}
}
int getresult(int a,int b,char opp)
{
if(opp=='+') return a+b;
if(opp=='-') return a-b;
if(opp=='*') return a*b;
if(opp=='/') return a/b;
}
int compute(string str)
{
int op1,op2,temp;
stack<int> data;
while(!data.empty()) data.pop();
for(int i=0;str[i]!='\0';i++)
{
if(str[i]=='&') continue;
else if(str[i]>='0'&&str[i]<='9')
{
temp=0;
while(str[i]>='0'&&str[i]<='9')
{
temp=temp*10+str[i]-'0';
i++;
}
i--;
data.push(temp);
}
else if(str[i]=='+'||str[i]=='-'||str[i]=='*'||str[i]=='/')
{
op1=data.top();
data.pop();
op2=data.top();
data.pop();
temp=getresult(op2,op1,str[i]);
data.push(temp);
}
}
return data.top();
}
int main()
{
string str_mid,str_post;
while(cin>>str_mid)
{
postfix(str_post,str_mid);
cout<<compute(str_post)<<endl;
break;
}
return 0;
}
第四题
时间限制:5000ms
单点时限:1000ms
内存限制:256MB
描述
柱状图是由一些宽度相等的长方形下端对齐后横向排列得到的图形。
现在有由n个宽度为1，高度分别为h1,h2...hn的长方形从左到右依次排列组成的柱状图。问里面包含的长方形的最大面积是多少。
如高度 1 2 3 包含的最大长方形面积是4
输入
数字n和随后的n个数字，空格隔开
输出
最大面积
样例输入
7 2 1 4 5 1 3 3
样例输出
8
AC代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <stack>
#include <vector>
#include <cmath>
using namespace std;
const int maxn = 100010;
int n;
int h[maxn],L[maxn],R[maxn];
int st[maxn];
void solve()
{
int t = 0;
for(int i=0;i<n;i++)
{
while(t>0 && h[st[t-1]] >= h[i])
t--;
L[i] = t==0?0:(st[t-1]+1);
st[t++] = i;
}
t = 0;
for(int i=n-1;i>=0;i--)
{
while(t > 0 && h[st[t-1]] >= h[i])
t--;
R[i] = t == 0 ? n : st[t-1];
st[t++] = i;
}
long long ans = 0;
for(int i=0;i<n;i++)
{
ans = max(ans , (long long)h[i]*(R[i]-L[i]));
}
printf("%lld\n",ans);
}
int main()
{
while(scanf("%d",&n)==1 && n){
for(int i=0;i<n;i++)
scanf("%d",&h[i]);
solve();
break;
}
return 0;
}
第五题
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
请你实现一个加强版的栈，支持以下操作：
push x: 向栈顶加入一个整数x
pop: 从栈顶弹出一个整数，并且输出该整数
inc k x: 将处于栈底的前k个整数加x。
输入
第一行包含一个整数N，代表操作的数量。
以下N行每行一条操作。
1 ≤ N ≤ 200000, 0 ≤ x ≤ 100000, 1 ≤ k ≤ 当前栈的大小
输出
对于每一个pop操作，输出弹出的整数数值。
样例输入
6
push 1
inc 1 2
push 2
inc 2 2
pop
pop
样例输出
4
5
AC代码
#include <bits/stdc++.h>
using namespace std;
int sk[210000], top, fg[210000];
int main()
{
int n, a, b;
cin>>n;
string op;
top = -1;
memset(fg, 0, sizeof(fg));
while(n--){
cin>>op;
if(op=="push"){
cin>>a;
sk[++top] = a;
}else if(op=="inc"){
cin>>a>>b;
fg[a-1] += b;
}else if(op=="pop"){
cout<<sk[top]+fg[top]<<endl;
fg[top-1] += fg[top];
fg[top] = 0;
top--;
}
}
return 0;
}
第六题
时间限制:5000ms
单点时限:1000ms
内存限制:256MB
描述
有一个整型数组arr和一个大小为w的窗口从数组的最左边滑到最右边，窗口每次向右滑动一个位置。
例如，数组为[4,3,5,4,3,3,6,7]，窗口大小为3时：依次出现的窗口为[4,3,5], [3,5,4], [5,4,3], [4,3,3], [3,3,6], [3,6,7]。
如果数组长度是n，窗口大小是w，则一共产生n-w+1个窗口。
输入
第一行 n 和 w，空格隔开，n为数组长度，w为窗口宽度
第二行为n个整数，作为数组元素，空格隔开
输出
n-w+1个数，每个数是对应窗口中的最大值。
例如上面的例子，应该返回[5,5,5,4,6,7]。
样例输入
8 3
4 3 5 4 3 3 6 7
样例输出
5 5 5 4 6 7
AC代码
#include <bits/stdc++.h>
#include<vector>
#include <iostream>
using namespace std;
vector<int> fun(const vector<int> &vec, const int &n, const int &w)
{
vector<int> res;
deque<int> dq;
for (int i = 0; i<n; ++i)
{
if (dq.empty()) dq.push_back(vec[i]);
//从队尾插入元素
else
{
while (!dq.empty())
{
if (dq.back() >= vec[i]) break;
else
//如果队尾元素<下一个元素，则不断删除队尾元素（保证次最大值总是紧邻队头元素）
dq.pop_back();
}
dq.push_back(vec[i]);
//如果队尾（有时候也是队头）元素>=下一个元素加入队尾
}
if (dq.size() >= w+1)
//当前队列元素>=窗口大小，删除队头元素
dq.pop_front();
if (i >= w -1) res.push_back(dq.front());
//队头元素是滑动窗口的最大值
}
return res;
}
int main()
{
int a,b;
cin>>a>>b;
int x[a];
for (int i =0;i<a;i++){
cin>>x[i];
}
vector<int> v1(x,x+a);
vector<int> v2 = fun(v1, a, b);
int y = v2.size();
for (int i = 0;i<y;i++){
cout << v2[i] ;
if (i!=y-1)
cout<<" ";
}
return 0;
}
