JLU数据结构荣誉课——第一次上机实验
一、7—1重复计数
在一个有限的正整数序列中，有些数会多次重复出现。请你统计每个数的出现次数， 然后按数字在序列中第一次出现的位置顺序输出数及其次数。
输入格式: 第1行，1个整数N，表示整数的个数，(1≤N≤50000)。
第2行，N个正整数，每个整数x 都满足 1 ≤ x ≤2000000000。
输出格式: 若干行，每行两个用一个空格隔开的数，第一个是数列中出现的数，第二个是该数在序列中出现的次数。 输入样例:
在这里给出一组输入。例如：
12
8 2 8 2 2 11 1 1 8 1 13 13
输出样例:
在这里给出相应的输出。例如：
8 3
2 3
11 1
1 3
13 2
方法：
这里直接推荐使用C++STL库中的map容器，数据在map容器中存储结构是红黑树，其操作函数中find``count在查找过程中均为O(nlogn) 不超出这道题的时间限制，且退化性不强，下面是代码：
#include<iostream>
#include<map>
using namespace std;
int a[50010];
int main()
{
int n;
cin>>n;
map<int,int>m;//定义map容器，key值为所给数字值，value值为所给计数值
int count1=0;
int n1;
for(int i=0;i<n;i++)
{
cin>>n1;
map<int,int>::iterator pos=m.find(n1);
if(pos!=m.end())//没有该数字
{
pos->second++;
}
else
{
m.insert(pair<int,int>(n1,1));
a[count1++]=n1;
}
}
for(int i=0;i<count1;i++)
{
map<int,int>::iterator p0=m.find(a[i]);//查找为O(nlogn)
cout<<a[i]<<" "<< (*p0).second ;
if(i!=count1-1)
cout<<endl;
}
return 0;
}
//本题目没有使用时间复杂度较低的扫描和打印就通过了.
评价：没有像许多同学一样，开了数组存value,直接存到second中不香么。
二、7-2报数游戏
n个人围成一圈，从1开始依次编号，做报数游戏。 现指定从第1个人开始报数，报数到第m个人时，该人出圈，然后从其下一个人重新开始报数，仍是报数到第m个人出圈，如此重复下去，直到所有人都出圈。 总人数不足m时将循环报数。请输出所有人出圈的顺序。
输入格式: 一行，两个整数n和m。n表示游戏的人数，m表示报数出圈的数字，1≤n≤50000，1≤m≤100.
输出格式: 一行，n个用空格分隔的整数，表示所有人出圈的顺序
输入样例: 在这里给出一组输入。例如：
5 2
输出样例: 在这里给出相应的输出。例如：
2 4 1 5 3
分析：约瑟夫问题，我认为这类题用循环链表实现最为直观，每次报数报到m-1个时，跳出循环，删去节点。具体代码如下：
#include<iostream>
using namespace std;
struct Node
{
int n;
Node*next;
};
int main()
{
int m,n;
cin>>m>>n;
int num=m;
Node*p=NULL;
Node*p1=NULL;
Node*head=NULL,*rear=NULL;//用尾插法
while(num!=0)
{
p=new Node;
p->n=m-num+1;
p->next=NULL;
if(head==NULL)
head=rear=p;
else
{
rear->next=p;
rear=p;
}
num--;
}//建立链表
rear->next=head;
p=head;
p1=rear;
while(p->next!=p)
{
int num1=n-1;
while(num1!=0)
{
p1=p;
//cout<<p->n;
p=p->next;
num1--;
}
cout<<p->n<<" ";
p1->next=p->next;
delete p;
p=p1->next;//删除操作
}
cout <<p->n;
return 0;
}
建议：这里建议使用静态链表，空间缩小的同时，操作和书写较为方便。
三、7-3 算术表达式计算
任务: 计算算术表达式的值。 算术表达式按中缀给出，以=号结束，包括+,-,/四种运算和(、)分隔符。运算数的范围是非负整数，没有正负符号，小于等于109 。
计算过程中,如果出现除数为0的情况,表达式的结果为”NaN” ; 如果中间结果超出32位有符号整型范围,仍按整型计算，不必特殊处理。 输入保证表达式正确。
思路：使用了双栈结构，典型的大模拟，麻烦不好调，但是冗长的代码，依旧可以写的很优美。用一个栈存储符号，用另一个栈存储数据，根据优先级进行评判出栈入栈顺序。
注意：这道题的测试点给的非常刁钻，注意空廓号，和单括号的处理，以及多种符号的评判。
代码如下：
#include<iostream>
#include<stack>
#include<cstdlib>
using namespace std;
bool level(char &ch1,char &ch2);//比较优先级函数
int givelevel(const char ch);//评级函数
int calculate(const int num1,const int num2,const char operator_ch);//计算函数
bool checklevel(int n1,int n2);//显示等级函数
void do_calculate();//单步计算函数
stack<char>Cstack;//符号栈
stack<int>Istack;//数字栈
int main()
{
char ch;
int num1=0;
cin>>ch;
while(1)
{
if(ch>='0'&&ch<='9')
{
while(ch>='0'&&ch<='9')
{
num1=num1*10+(ch-'0');
cin>>ch;
}
Istack.push(num1);
num1=0;
}
if(ch!='=')
{
if(Cstack.empty())
{
Cstack.push(ch);
}
else if(ch==')')
{
while(Cstack.top()!='(')
{
do_calculate();
}
Cstack.pop();
}
else if(ch=='('||
checklevel(givelevel(ch),givelevel(Cstack.top())))
{
Cstack.push(ch);
}
else
{
while(!Cstack.empty()&&
(!checklevel(givelevel(ch),givelevel(Cstack.top()))))
{
do_calculate();
}
Cstack.push(ch);
}
}
else
{
while(!Cstack.empty())
{
do_calculate();
}
if(!Istack.empty())
cout << Istack.top();
else
cout<<'0';
break;
}
cin>>ch;
}
return 0;
}
bool checklevel(int n1,int n2)
{
if(n1>n2)
return true;
else return false;
}
int givelevel(const char ch)
{
if(ch=='*'||ch=='/')
return 2;
else if(ch=='+'||ch=='-')
return 1;
else return 0;
}
int calculate(const int num1,const int num2,const char operator_ch)
{
if(operator_ch=='*')
return num1*num2;
else if(operator_ch=='/')
return num1/num2;
else if(operator_ch=='+')
return num1+num2;
else if(operator_ch=='-')
return num1-num2;
else
return -1;
}
void do_calculate()
{
char ch1=Cstack.top();
Cstack.pop();
int num1=Istack.top();
Istack.pop();
int num2=Istack.top();
Istack.pop();
if(num1==0&&ch1=='/')
{
cout << "NaN"<<endl;
exit(0);
}
else
Istack.push(calculate(num2,num1,ch1));
}
四、7-4 最喜爱的序列
小唐这段时间在研究序列。拿来N个整数的序列，他给序列中的每个整数都赋予一个喜爱值。喜爱值也是整数，有正有负，越大表明越喜欢。他想知道，如何从序列中连续取最多m个数，他获得喜爱值最大。1≤N≤500000，1≤m≤N。 输入格式: 第一行是两个整数N,m。分别代表序列中数的个数以及能取的最多个数。
第二行用空格隔开的N个整数，第i个整数Li代表他对第i个数的喜爱值。│Li│≤1000
输出格式: 一行，三个数，表示获得最大喜爱值，及第一个取最大喜爱值的区间。
输入样例: 在这里给出一组输入。例如：
5 2
1 4 5 2 3
输出样例: 在这里给出相应的输出。例如：
9 2 3
思路：一开始一看没时间了，直接暴力了，不出所料，给了60，哎，要是我看错了题多好😂🤣,仔细一想，并看到大佬们的做法，豁然开朗，不就是单调队列+前缀和么，维护一个前缀和序列，维护一个给定区间，让队列保持递增，即最前者所代表前缀和在给定区间最小。
单调队列部分：
while(head<rear&&sum[i]<sum[que[rear-1]])rear--;
que[++rear]=i;
while(que[head]<i-m+1&&head<rear)head++;
代码如下：
#include<iostream>
#include<cstdlib>
using namespace std;
int ans[500010];
int sum[500010];
int que[500010];
int main()
{
int N,m;
cin>>N>>m;
for(register int i=0;i<N;i++)
{
cin>>ans[i];
sum[i]=sum[i-1]+ans[i];
}
int score[3]={0};
score[0]=sum[0];
int head=0,rear=0;
for(int i=1;i<N;i++)
{
if(score[0]<sum[i]-sum[que[head]])
{
score[0]=sum[i]-sum[que[head]];
score[1]=que[head]+1;
score[2]=i;
}//每次判断存储最大差值。
while(head<rear&&sum[i]<sum[que[rear-1]])rear--;
que[++rear]=i;
while(que[head]<i-m+1&&head<rear)head++;
}
cout<<score[0]<<" "<<score[1]+1<<" "<<score[2]+1;
return 0;
}