2019/3/22更新:第一次更 沒來得及寫解題思路
————————————————————————
時間限制:1000ms
單點時限:1000ms
內(nèi)存限制:256MB
描述
翻轉(zhuǎn)一個鏈表
特殊要求：請使用以下鏈表結(jié)構(gòu)
class Node
{
int value;
Node next;
}
輸入
輸入包含多組數(shù)據(jù)府适。對于每組數(shù)據(jù)：
第一行是n载碌，表示鏈表長度勿她；當(dāng)n=-1時善镰，表示輸入結(jié)束墨叛。(1 <= n <= 100)
第二行是n個整數(shù)博其，表示鏈表每一位所存儲的內(nèi)容殃恒。
輸出
針對每組輸入植旧，輸出翻轉(zhuǎn)后的鏈表的內(nèi)容。
樣例輸入
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
內(nèi)存限制:256MB
<dl class="des">
描述
編寫一個程序可以完成基本的帶括號的四則運(yùn)算离唐。其中除法(/)是整除病附，并且在負(fù)數(shù)除法時向0取整。(C/C++/Java默認(rèn)的除法就是向0取整亥鬓，python默認(rèn)的是向負(fù)無窮取整完沪。)
例如計算 100 * ( 2 + 12 ) - (20 / 3) * 2, 結(jié)果是1388。
輸入
一個長度不超過100的字符串嵌戈，代表要計算的算式覆积。包含數(shù)字0-9以及+-*/()。
輸入保證計算過程不會超過32位有符號整數(shù)熟呛，并且其中的'-'都是減號沒有負(fù)號宽档。
輸出
計算的結(jié)果。
樣例輸入
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
內(nèi)存限制:256MB
描述
柱狀圖是由一些寬度相等的長方形下端對齊后橫向排列得到的圖形惰拱。
現(xiàn)在有由n個寬度為1雌贱，高度分別為h1,h2...hn的長方形從左到右依次排列組成的柱狀圖。問里面包含的長方形的最大面積是多少偿短。
如高度 1 2 3 包含的最大長方形面積是4
輸入
數(shù)字n和隨后的n個數(shù)字欣孤，空格隔開
輸出
最大面積
樣例輸入
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
內(nèi)存限制:256MB
描述
請你實現(xiàn)一個加強(qiáng)版的棧，支持以下操作：
push x: 向棧頂加入一個整數(shù)x
pop: 從棧頂彈出一個整數(shù)昔逗，并且輸出該整數(shù)
inc k x: 將處于棧底的前k個整數(shù)加x降传。
輸入
第一行包含一個整數(shù)N，代表操作的數(shù)量勾怒。
以下N行每行一條操作婆排。
1 ≤ N ≤ 200000, 0 ≤ x ≤ 100000, 1 ≤ k ≤ 當(dāng)前棧的大小
輸出
對于每一個pop操作，輸出彈出的整數(shù)數(shù)值笔链。
樣例輸入
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
內(nèi)存限制:256MB
描述
有一個整型數(shù)組arr和一個大小為w的窗口從數(shù)組的最左邊滑到最右邊段只，窗口每次向右滑動一個位置。
例如鉴扫，數(shù)組為[4,3,5,4,3,3,6,7]赞枕，窗口大小為3時：依次出現(xiàn)的窗口為[4,3,5], [3,5,4], [5,4,3], [4,3,3], [3,3,6], [3,6,7]。
如果數(shù)組長度是n，窗口大小是w炕婶，則一共產(chǎn)生n-w+1個窗口姐赡。
輸入
第一行 n 和 w，空格隔開柠掂，n為數(shù)組長度项滑，w為窗口寬度
第二行為n個整數(shù)，作為數(shù)組元素涯贞，空格隔開
輸出
n-w+1個數(shù)枪狂，每個數(shù)是對應(yīng)窗口中的最大值。
例如上面的例子宋渔，應(yīng)該返回[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)
//當(dāng)前隊列元素>=窗口大小傻谁，刪除隊頭元素
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;
}
