洛谷:线性表

2023-12-28 20:39:52

? ? ?今天开始刷洛谷,之前刷leetcode都是核心代码模式,现在突然让我用ACM模式,刚开始还是很不习惯的,但做了几道题好点了,只能说洛谷题的难度是比leetcode大的。

? ? 还有就是,STL牛逼!

1.询问学号(vector)

#include<iostream>
#include<vector>
using namespace std;
int main()
{
   vector<int>ret;
   int n,m,a,b;
   cin>>n>>m;
   while(n--)
  {
    cin>>a;
    ret.push_back(a);
  }
   while(m--)
  {
    cin>>b;
    cout<<ret[b-1]<<endl;
  }
 
}

? ? ? ?这道题还是比较简单的,首先我们要想用什么数据结构来存储数据,我们看到,要存储n名同学的学号,其次要询问第i个进入教室的同学的学号,什么数据结构能让我们在知道下标的情况下快速访问呢,那必然是数组啊,所以我先定义了一个动态变化的vector数组用来存储n名同学的学号,然后就是先获取学生个数和访问次数,然后输入这n名同学的学号,之后就是知道了下标b,直接输出ret[b-1]即可,还是很简单的。

2.寄包柜(map)

#include <iostream>
#include<map>
#include<cstdio>
using namespace std;
map <int, int> mat[100005];  
int main() {
	int n, q;
	scanf("%d%d", &n, &q);
	while (q--) {
		int x, i, j, k;
		scanf("%d", &x);
		if (x == 1) {
			scanf("%d%d%d", &i, &j, &k);  
			mat[i][j] = k;  
		} else {
			scanf("%d%d", &i, &j);
			printf("%d\n", mat[i][j]); 
		}
	} 
	return 0;
}

? ? ?这道题的核心是如何根据给出的第i个寄包柜来获取有多少格子,你肯定会首先想到用二维数组来做,但不好意思,你看看数量级,如果我们要访问第10^5寄包柜,好,我们开辟了这么多空间,前面的用不到啊,这不是在浪费空间还是在干什么?什么?你说vector容器,好家伙,vector容器的下标也是连续的啊,你访问第i个,前面的空间肯定也开辟出来了啊,本质还是数组。那就没有什么办法了?那肯定是没.......肯定有啊,想啥呢?

? ? ? 我们使用map关联容器来做,map主要用来存储和检索集合中的数据元素,里面的数据均成一种映射关系,是一种包含关键字和值的键值对,关键字和值可以是字符串,数字等等,map里面的元素都是一个键值对,所以我们通过寄包柜和格子的映射关系来进行高效地存储和查找,当我们知道第i个寄包柜试,就通过map快速查找有多少个格子,这是离散并非连续的。

? ? ? ?所以我们定义一个map,第一个int是第几个柜子,第二个int是该柜子的格子数量,格子是有序的,当x=1时,我们就往第i个寄包柜的第j个格子里放物品;当x=2时,我们就输出第i个柜子的第j个格子的物品是什么。

3.验证栈序列(stack)

#include<iostream>
#include<stack>
using namespace std;
stack<int>stk;
int q,n;
int main()
{
  cin>>q;
  while(q--)
  {
	cin>>n;
	int a[n+1],b[n+1],cnt=1; 
	for(int i=1;i<=n;i++)
	cin>>a[i];
	for(int i=1;i<=n;i++)
	cin>>b[i]; 
	for(int i=1;i<=n;i++)
	{
		stk.push(a[i]);
		while((stk.top())==b[cnt])
		{
			stk.pop();
            cnt++;
			if(stk.empty())break;//这里也要注意,当我们已经比对完所有的元素时,假如都能比对上,则此时栈已经空了,如果我们还继续进行循环执行pop操作是会出错的,所以要对栈是否为空进行判断。
		}
	}
	if(stk.empty()) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
    while(!stk.empty())stk.pop();//如果前面栈不为空一定要清空栈再进入下一次循环
   }
	return 0; 
}

? ? ?这个题已经不能再明显了,肯定栈的题,我们先获取入栈序列和出栈序列,然后对栈进行入栈(push)操作,全部入栈完毕后,我们一个一个元素进行比较,如果相同,则将该栈元素弹出,cnt++,继续比较下一个,需要注意的点我在上面已经写了,栈为空时结束循环,此时也要进行判断,如果栈为空说明出栈序列是对的输出"Yes",否则输出"No",最后一定要把栈清空再进入下一次循环!

4.约瑟夫问题(queue)

#include<iostream>
#include<queue>
using namespace std;
int main()
{
  queue<int>q;
  int n,m;
  int num=1;
  cin>>n>>m;
  for(int i=1;i<=n;i++)
  {
    q.push(i);
  }
   while(!q.empty())
  {
     if(num==m)
     {
       cout<<q.front()<<" ";
       q.pop();
       num=1;
     }
     else
     {
        num++;
        q.push(q.front());//队首的人压到队尾
        q.pop(); //删除队首的人 
      }
   }
   cout<<endl;
   return 0;
}

? ? ?这道题第一次在leetcode没做出来,在洛谷上用queue容器秒了。

? ? ?约瑟夫问题也是一个很经典的问题,n个人围成一个圈圈,给定一个数字k,从第一个人开始报数,数到k的人出圈,其他人依旧围成一个圈,同时出圈的人的下一个人从1开始报数,最后所有人都会出圈,我第一次想到循环队列,其实也可以用链表做,但个人认为循环队列超级简洁。

? ? ?首先定义一个队列,用num来记录编号到哪个人时num=m,然后就是向队列中插数,当队列不为空时,如果我的num不等于m的话,说明不是这个人,那我们就把队首的人压到队尾,同时删除队首的人,一直到num=m时,我们找到了第一个出局的人,把它输出并删除,同时令num=1,寻找下一个人。

5.机器翻译(queue)

#include<iostream>
#include<queue>
using namespace std; 
queue<int>q;
int m,n;
int cnt[1005]={0};//如果把数组放在主函数外,全部初始化为0,放在主函数内就是随机值,这时候就要初始化为0
int main()
{
  int ans=0;
  cin>>m>>n;
  int word;
  while(n--)
  {
    cin>>word;
    if(cnt[word])continue;
    else
    {
       if(q.size()>=m)
       { 
        cnt[q.front()]=0;//顺序不能调换,一旦调换就获取不到原来的队首元素了
        q.pop();
       }
        q.push(word);
        ans++;
        cnt[word]++;
    }
  }
    cout<<ans;
    return 0;
}

? ? ?这道题看前面的文字描述可能有点头皮发麻,直接看样例解释我们可以清楚这是一个在一端插入元素,在另一端删除元素的队列问题,需要注意的是,队列并没有count函数哦,我们需要用一个cnt数组来统计单词是否在字典中,输入单词,如果出现过就continue跳过,如果没有出现过,进一步判断队列是否已满,没满直接插入,ans++,cnt[word]++即可;如果已经满了,就先令队首元素在cnt数组的值为0,因为此时这个单词已经被删除了,查询结束返回ans即可。

? ? 还有一点就是在定义数组的时候一定要定义在主函数外面啊,如果定义在主函数里面而且你不初始化,数组里面就全是随机值,因为这个卡了一些时间,定义在主函数外面就是全局变量,你自己忘了初始化,系统也会自动给你初始化为0的,但在主函数里面就不会,需要自己进行初始化。

文章来源:https://blog.csdn.net/pancodearea/article/details/135275224
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。