数据结构荣誉课-第一次实验-解题报告

JLU-数据结构荣誉课-第一次实验-解题报告

  • 一、重复计数
    • 题目
    • 解题思路
    • 参考代码
  • 二、报数游戏
    • 题目
    • 解题思路
    • 参考代码
  • 三、算数表达式计算
    • 题目
    • 解题思路
    • 参考代码
  • 四、最喜爱的序列
    • 题目
    • 解题思路
    • 参考代码

一、重复计数

题目

在一个有限的正整数序列中,有些数会多次重复出现。请你统计每个数的出现次数,然后按数字在序列中第一次出现的位置顺序输出数及其次数。
输入格式:
第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

解题思路

题目比较简单,我是先建立了一个结构体来表示这个数与它出现的次数,想到的第一种方法就是每次读入一个数就对结构体数组进行遍历,如果存在该数count就+1否则就将这个数加入到结构体数组中,虽然我知道这样很大概率会超时,但我还是吧这种方法打了下来碰碰运气(当时并不会map,呜呜呜)第一次并没有通过果然被卡了时间,但是改了改代码就过了,哈哈哈。

参考代码

#include<stdio.h>
#define MAX 50001
 struct list{
	int num;
	int count;
};
int t=1;
int main(){
	struct list a[MAX];
	int N;
	scanf("%d",&N);
	int i,j;
	int x;
	scanf("%d",&x);
	a[0].num=x;
	a[0].count=1;
	for(i=1;i<N;i++)
	{
		scanf("%d",&x);
		for(j=0;j<t;j++)
		{
			if(a[j].num==x) { a[j].count++; break; } 
		}
		if(j==t)
		{
			t++;
			a[j].num=x;
			a[j].count=1;
		}
	}
	for(i=0;i<t;i++){
		printf("%d %d",a[i].num,a[i].count);
		if(i!=t-1) printf("\n");
	}
	return 0;
}

二、报数游戏

题目

n个人围成一圈,从1开始依次编号,做报数游戏。 现指定从第1个人开始报数,报数到第m个人时,该人出圈,然后从其下一个人重新开始报数,仍是报数到第m个人出圈,如此重复下去,直到所有人都出圈。总人数不足m时将循环报数。请输出所有人出圈的顺序。
输入格式:
一行,两个整数n和m。n表示游戏的人数,m表示报数出圈的数字,1≤n≤50000,1≤m≤100.

输出格式:
一行,n个用空格分隔的整数,表示所有人出圈的顺序

输入样例:
在这里给出一组输入。例如:

5 2

输出样例:
在这里给出相应的输出。例如:

2 4 1 5 3

解题思路

这个题就是一个典型的约瑟夫环问题,在大一上初学C语言的时候在慕课上就做过类似的作业不过那个是叫猴子选大王。这个题的思路也很简单就是建立一个数组来保存每个人的编号,之后每次出队都将该编号输出并将其删除(就是把后面的所有编号依次前移),这样最终数组中剩下的一个就是最后出圈的(也就是大王)。

参考代码

#include<stdio.h>
int main()
{
	int n;
	int m;
	int i,j=0;
	long N[500001];
	scanf("%d %d",&n,&m);
	for(i=0;i<n;i++)
	{
		N[i]=i+1;
	}
	while(n>1)
	{
		j=(j+m-1)%n;
    	printf("%ld ",N[j]);
    	for(i=j;i<n-1;i++)
		{
			N[i]=N[i+1];
		}
		n--;
    }
    printf("%ld\n",N[0]);
    return 0;
	
}

三、算数表达式计算

题目

任务: 计算算术表达式的值。

算术表达式按中缀给出,以=号结束,包括+,-,/四种运算和(、)分隔符。运算数的范围是非负整数,没有正负符号,小于等于109 。

计算过程中,如果出现除数为0的情况,表达式的结果为”NaN” ; 如果中间结果超出32位有符号整型范围,仍按整型计算,不必特殊处理。 输入保证表达式正确。

输入格式:
一行,包括1个算术表达式。算术表达式的长度小于等于1000。

输出格式:
一行,算术表达式的值 。

输入样例:
在这里给出一组输入。例如:

(1+30)/3=

输出样例:
在这里给出相应的输出。例如:

10

解题思路

这个题是谷老师提前透露给我们的所以我也是提前打了一下这个题还去特意复习了一下中缀表达式转后缀表达式,复习复习发现上课的时候讲的是变转后缀边计算,思路就是建立两个栈来保存操作数和操作符,开始时将中缀表达式保存到一个字符串当中,因为题目已经明确所输入的一定是合法的所以不用考虑别的接下来就是从左一次读表达式如果是操作数就入栈,如果是操作符就需要根据操作符栈来决定下一步的操作,如果栈空则入栈,否则判断栈顶元素与当前元素的优先级如果当前元素优先级高则入栈(‘(’的优先级最高),如果是‘)’则将元素安抚栈中的运算符一次出栈并计算操作数,直至遇到‘(’,如果当前运算符优先级小于等于栈顶运算符等级则先对该运算符进行运算(不入栈)。读完之后如果运算符栈不空则将其全部出栈并计算即可。

参考代码

#include<stdio.h>
#include<stdlib.h>
#include<stack>
#include<string.h>
#include<iostream>
#define L 1001
using namespace std;
stack<int> Stacknum;
stack<char> Stackchar;
void Fun(char e){
	int temp1,temp2;
	temp1=Stacknum.top(); Stacknum.pop();
	temp2=Stacknum.top(); Stacknum.pop();
	switch(e)
	{
		case '+' :  Stacknum.push(temp2+temp1); break;
		case '-' :  Stacknum.push(temp2-temp1); break;
		case '*' :  Stacknum.push(temp2*temp1); break;
		case '/' :  
            if(temp1==0) {printf("NaN");exit(0);}
            else
            Stacknum.push(temp2/temp1); break;
	}
} 
int main(){
	char str[L];
	scanf("%s",str);
	int i;
	int temp;
	for(i=0;str[i]!='=';i++)
	{
		if(str[i]>='0'&&str[i]<='9')
		{
			temp=str[i]-'0';
			while(str[i+1]!='=')
			{
				if(str[i+1]>='0'&&str[i]<='9')
				{
					temp=temp*10+str[i+1]-'0';
					i++;
				}
				else break;
			}
			Stacknum.push(temp);
		}
		else
		{
			char tmp;
			if(str[i]=='+'||str[i]=='-'||str[i]=='*'||str[i]=='/'||str[i]=='('||str[i]==')')
			{
				switch(str[i])
				{
					case '+' :
						if(Stackchar.empty()) {Stackchar.push('+');break;}
						tmp=Stackchar.top();
						if(tmp!='+'&&tmp!='-'&&tmp!='*'&&tmp!='/') Stackchar.push('+');
						else
						{
							while(!Stackchar.empty()&&tmp!='(')
							{
								Stackchar.pop();
								Fun(tmp);
								if(Stackchar.empty()) break;
								else tmp=Stackchar.top();
							}
							Stackchar.push('+');
						}
						break;
					case '-' :
						if(Stackchar.empty()) {Stackchar.push('-');break;}
						tmp=Stackchar.top();
						if(tmp!='+'&&tmp!='-'&&tmp!='*'&&tmp!='/') Stackchar.push('-');
						else
						{
							while(!Stackchar.empty()&&tmp!='(')
							{
								Stackchar.pop();
								Fun(tmp);
								if(Stackchar.empty()) break;
								else tmp=Stackchar.top();
							}
							Stackchar.push('-');
						}
						break;
					case '*' :
						if(Stackchar.empty()) {Stackchar.push('*');break;}
						tmp=Stackchar.top();
						if(tmp!='*'&&tmp!='/') Stackchar.push('*');
						else
						{
							while((tmp=='*'||tmp=='/')&&tmp!='(')
							{
								Stackchar.pop();
								Fun(tmp);
								if(Stackchar.empty()) break;
								else tmp=Stackchar.top();
							}
							Stackchar.push('*');
						}
						break;
					case '/' :
						if(Stackchar.empty()) {Stackchar.push('/');break;}
						tmp=Stackchar.top();
						if(tmp!='*'&&tmp!='/') Stackchar.push('/');
						else
						{
							while((tmp=='*'||tmp=='/')&&tmp!='(')
							{
								Stackchar.pop();
								Fun(tmp);
								if(Stackchar.empty()) break;
								else tmp=Stackchar.top();
							}
							Stackchar.push('/');
						}
						break;
					case '(' :
						Stackchar.push('(');
						break;
					case ')' :
						tmp=Stackchar.top();
						while(tmp!='(')
						{
							Stackchar.pop();
							Fun(tmp);
							tmp=Stackchar.top();
						}
						Stackchar.pop();
						break;
				}
			}
		}
	}
	while(!Stackchar.empty())
	{
		char tmp=Stackchar.top();
		Stackchar.pop();
		Fun(tmp);
	}
	temp=Stacknum.top();
	printf("%d",temp);
	return 0;
}

四、最喜爱的序列

题目

小唐这段时间在研究序列。拿来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

解题思路

因为在之前的联系中做过前缀和的题所以看到这道题首先想到了用前缀和来保存喜爱值的和,这样能节省一些时间,第一次做的时候并没有看清楚题意,以为是找m个数的最大区间,还以为为啥这么简单就把代码实现了一遍,结果总是有几个测试点过不去,等到课后做题的时候才发现是最大m个,因为喜爱值也可能是负值,在课上听了同学是用单调队列做的,谷老师心里的解法也是单调队列,而且单调队列就是用来解决求区间的最大最小值问题的,所以我学习了同学得思路与代码,创建了一个双端队列来实现,要实现单调队列需要维护它的单调性与区间长度。

参考代码

#include<stdio.h>
#include<iostream>
#include<deque> 
using namespace std;
deque<int> mon_deq;
int main(){
	long long sum[500000];
	int left,right;//左右端点
	long long max=0;//最大喜爱值
	int N,m;
	scanf("%d%d",&N,&m);
	int i,j;
	sum[0]=0;
	for(i=1;i<=N;i++)
	{
		scanf("%lld",&sum[i]);
		sum[i]+=sum[i-1];
	}
	mon_deq.push_front(0);
	for(i=1;i<=N;i++)
	{
		while(!mon_deq.empty()&&sum[mon_deq.front()]>sum[i])
			mon_deq.pop_front();
		mon_deq.push_front(i);
		while(!mon_deq.empty()&&(i-mon_deq.back()>m))
		    mon_deq.pop_back();
		if(max<sum[i]-sum[mon_deq.back()])
		{
			max=sum[i]-sum[mon_deq.back()];
			left=mon_deq.back()+1;
			right=i;
		}
	}
	printf("%lld %d %d",max,left,right);
	return 0;
}

热门文章

暂无图片
编程学习 ·

C语言二分查找详解

二分查找是一种知名度很高的查找算法&#xff0c;在对有序数列进行查找时效率远高于传统的顺序查找。 下面这张动图对比了二者的效率差距。 二分查找的基本思想就是通过把目标数和当前数列的中间数进行比较&#xff0c;从而确定目标数是在中间数的左边还是右边&#xff0c;将查…
暂无图片
编程学习 ·

GMX 命令分类列表

建模和计算操作命令&#xff1a; 1.1 . 创建拓扑与坐标文件 gmx editconf - 编辑模拟盒子以及写入子组(subgroups) gmx protonate - 结构质子化 gmx x2top - 根据坐标生成原始拓扑文件 gmx solvate - 体系溶剂化 gmx insert-molecules - 将分子插入已有空位 gmx genconf - 增加…
暂无图片
编程学习 ·

一文高效回顾研究生课程《数值分析》重点

数值分析这门课的本质就是用离散的已知点去估计整体&#xff0c;就是由黑盒子产生的结果去估计这个黑盒子。在数学里这个黑盒子就是一个函数嘛&#xff0c;这门课会介绍许多方法去利用离散点最大化地逼近这个函数&#xff0c;甚至它的导数、积分&#xff0c;甚至微分方程的解。…
暂无图片
编程学习 ·

在职阿里5年,一个28岁女软测工程师的心声

简单的先说一下&#xff0c;坐标杭州&#xff0c;14届本科毕业&#xff0c;算上年前在阿里巴巴的面试&#xff0c;一共有面试了有6家公司&#xff08;因为不想请假&#xff0c;因此只是每个晚上去其他公司面试&#xff0c;所以面试的公司比较少&#xff09; ​ 编辑切换为居中…
暂无图片
编程学习 ·

字符串左旋c语言

目录 题目&#xff1a; 解题思路&#xff1a; 第一步&#xff1a; 第二步&#xff1a; 第三步&#xff1a; 总代码&#xff1a; 题目&#xff1a; 实现一个函数&#xff0c;可以左旋字符串中的k个字符。 例如&#xff1a; ABCD左旋一个字符得到BCDA ABCD左旋两个字符…
暂无图片
编程学习 ·

设计模式--观察者模式笔记

模式的定义与特点 观察者&#xff08;Observer&#xff09;模式的定义&#xff1a;指多个对象间存在一对多的依赖关系&#xff0c;当一个对象的状态发生改变时&#xff0c;所有依赖于它的对象都得到通知并被自动更新。这种模式有时又称作发布-订阅模式、模型-视图模式&#xf…
暂无图片
编程学习 ·

睡觉突然身体动不了,什么是睡眠痽痪症

很多朋友可能有这样的体验&#xff0c;睡觉过程中突然意识清醒&#xff0c;身体却动弹不了。这时候感觉非常恐怖&#xff0c;希望旁边有一个人推自己一下。阳光以前也经常会碰到这样的情况&#xff0c;一年有一百多次&#xff0c;那时候很害怕晚上到来&#xff0c;睡觉了就会出…
暂无图片
编程学习 ·

深入理解C++智能指针——浅析MSVC源码

文章目录unique_ptrshared_ptr 与 weak_ptrstd::bad_weak_ptr 异常std::enable_shared_from_thisunique_ptr unique_ptr 是一个只移型别&#xff08;move-only type&#xff0c;只移型别还有std::mutex等&#xff09;。 结合一下工厂模式&#xff0c;看看其基本用法&#xff…
暂无图片
编程学习 ·

@TableField(exist = false)

TableField(exist false) //申明此字段不在数据库存在&#xff0c;但代码中需要用到它&#xff0c;通知Mybatis-plus在做写库操作是忽略它。,.
暂无图片
编程学习 ·

Java Web day15

第十二章文件上传和下载 一、如何实现文件上传 要实现Web开发中的文件上传功能&#xff0c;通常需要完成两步操作&#xff1a;一.是在Web页面中添加上传输入项&#xff1b;二是在Servlet中读取上传文件的数据&#xff0c;并保存到本地硬盘中。 需要使用一个Apache组织提供一个…
暂无图片
编程学习 ·

【51nod 2478】【单调栈】【前缀和】小b接水

小b接水题目解题思路Code51nod 2478 小b接水 题目 输入样例 12 0 1 0 2 1 0 1 3 2 1 2 1输出样例 6解题思路 可以发现最后能拦住水的都是向两边递减高度&#xff08;&#xff1f;&#xff09; 不管两个高积木之间的的积木是怎样乱七八糟的高度&#xff0c;最后能用来装水的…
暂无图片
编程学习 ·

花了大半天写了一个UVC扩展单元调试工具

基于DIRECTSHOW 实现的&#xff0c;用的是MFC VS2019. 详见&#xff1a;http://www.usbzh.com/article/detail-761.html 获取方法 加QQ群:952873936&#xff0c;然后在群文件\USB调试工具&测试软件\UVCXU-V1.0(UVC扩展单元调试工具-USB中文网官方版).exe USB中文网 USB中文…
暂无图片
编程学习 ·

贪心(一):区间问题、Huffman树

区间问题 例题一&#xff1a;区间选点 给定 N 个闭区间 [ai,bi]请你在数轴上选择尽量少的点&#xff0c;使得每个区间内至少包含一个选出的点。 输出选择的点的最小数量。 位于区间端点上的点也算作区间内。 输入格式 第一行包含整数 N&#xff0c;表示区间数。 接下来 …
暂无图片
编程学习 ·

C语言练习实例——费氏数列

目录 题目 解法 输出结果 题目 Fibonacci为1200年代的欧洲数学家&#xff0c;在他的着作中曾经提到&#xff1a;「若有一只免子每个月生一只小免子&#xff0c;一个月后小免子也开始生产。起初只有一只免子&#xff0c;一个月后就有两只免子&#xff0c;二个月后有三只免子…
暂无图片
编程学习 ·

Android开发(2): Android 资源

个人笔记整理 Android 资源 Android中的资源&#xff0c;一般分为两类&#xff1a; 系统内置资源&#xff1a;Android SDK中所提供的已经定义好的资源&#xff0c;用户可以直接拿来使用。 用户自定义资源&#xff1a;用户自己定义或引入的&#xff0c;只适用于当前应用的资源…
暂无图片
编程学习 ·

零基础如何在短时间内拿到算法offer

​算法工程师是利用算法处理事物的职业 算法&#xff08;Algorithm&#xff09;是一系列解决问题的清晰指令&#xff0c;也就是说&#xff0c;能够对一定规范的输入&#xff0c;在有限时间内获得所要求的输出。 如果一个算法有缺陷&#xff0c;或不适合于某个问题&#xff0c;执…
暂无图片
编程学习 ·

人工智能:知识图谱实战总结

人工智能python&#xff0c;NLP&#xff0c;知识图谱&#xff0c;机器学习&#xff0c;深度学习人工智能&#xff1a;知识图谱实战前言一、实体建模工具Protegepython&#xff0c;NLP&#xff0c;知识图谱&#xff0c;机器学习&#xff0c;深度学习 人工智能&#xff1a;知识图…
暂无图片
编程学习 ·

【无标题】

这里写自定义目录标题欢迎使用Markdown编辑器新的改变功能快捷键合理的创建标题&#xff0c;有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右SmartyPants创建一个自定义列表如何创建一个注…