当前位置: 首页 > news >正文

1302机器翻译(队列)

目录

题目描述

提示

解题思路

代码部分


题目描述

小晨的电脑上安装了一个机器翻译软件,他经常用这个软件来翻译英语文章。

这个翻译软件的原理很简单,它只是从头到尾,依次将每个英文单词用对应的中文含义来替换。对于每个英文单词,软件会先在内存中查找这个单词的中文含义,如果内存中有,软件就会用它进行翻译;如果内存中没有,软件就会在外存中的词典内查找,查出单词的中文含义然后翻译,并将这个单词和译义放入内存,以备后续的查找和翻译。

假设内存中有M个单元,每单元能存放一个单词和译义。每当软件将一个新单词存入内存前,如果当前内存中已存入的单词数不超过M−1,软件会将新单词存入一个未使用的内存单元;若内存中已存入M 个单词,软件会清空最早进入内存的那个单词,腾出单元来,存放新单词。

假设一篇英语文章的长度为N个单词。给定这篇待译文章,翻译软件需要去外存查找多少次词典?假设在翻译开始前,内存中没有任何单词。

输入

共2行。每行中两个数之间用一个空格隔开。

第一行为两个正整数M和N,代表内存容量和文章的长度。

第二行为N个非负整数,按照文章的顺序,每个数(大小不超过1000)代表一个英文单词。文章中两个单词是同一个单词,当且仅当它们对应的非负整数相同。

输出

共1行,包含一个整数,为软件需要查词典的次数。

样例1输入

3 7
1 2 1 5 4 4 1

样例1输出

5

提示

样例2输入:

2 108 824 11 78 11 78 11 78 8 264

样例2输出:

6

提示:

输入输出样例 1 说明:

整个查字典过程如下:每行表示一个单词的翻译,冒号前为本次翻译后的内存状况:

空:内存初始状态为空。

1.1:查找单词1并调入内存。

2.1 2:查找单词2并调入内存。

3.1 2:在内存中找到单词1。

4.1 2 5:查找单词5并调入内存。

5.2 5 4:查找单词4并调入内存替代单词1。

6.2 5 4:在内存中找到单词4。

7.5 4 1:查找单词1并调入内存替代单词2。

共计查了5 次词典。

解题思路

建立队列。用队列长度模拟内存容量,即队列长度等于m。

依次输入每次查询的数字。

对于其中某个数字,如果想要分类讨论,有以下2个分类标准:

该数字是否已经入过队并且现在还在队中;

队列容量是否满了。

因此,对每个可能入队的元素都应作一标记,标记的分类标准是:这个数字现在在不在队中,

如果现在在队中,标记为1或true;如果现在不在队中,标记为0或false。

根据分类标准,可以分为以下几种情况。

1.如果将要输入的这个数字已经入过队且现在还在队中,翻译成题目背景下的含义代表

“如果内存中有,软件就会用它进行翻译”。这种情况下,不做任何处理,继续读入下一个数据。

2.如果将要输入的数字不在队中:

   分为以下两种情况:1.1  队长度>=m ;

                                           解决方案:将队首元素弹出,队首元素的标记变为0;

                                                             在队尾追加新增数字,并将这个元素的标记修改为1;

                                    1.2   队长度<m;

                                            解决方案:直接将新增数字追加到队尾,并把这个元素的标记修改为1;

                                   两种方案结束之后都要做的一件事情是:记一次数。因为,这属于题目背景                                     中所说的“查找了一次字典”。

最后输出计数次数即可。

代码部分

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
bool len[1001];//标记数组
queue<int>q;//建立队列
int main()
{int m, n;cin >> m >> n;int x;int head;int cnt = 0;//用于计数for (int i = 0; i < n; i++){cin >> x;if (len[x] == 1)continue;//如果x现在再队中,继续执行下一次循环else if (len[x] == 0)//如果x不在队中{if (q.size() >= m)//如果对长度达到上限{head = q.front();len[head] = 0;q.pop();//抛头}q.push(x);//推尾len[x] = 1;//标记cnt++;//计数}}cout << cnt << endl;//输出return 0;
}

相关文章:

1302机器翻译(队列)

目录 题目描述 提示 解题思路 代码部分 题目描述 小晨的电脑上安装了一个机器翻译软件&#xff0c;他经常用这个软件来翻译英语文章。 这个翻译软件的原理很简单&#xff0c;它只是从头到尾&#xff0c;依次将每个英文单词用对应的中文含义来替换。对于每个英文单词&#…...

AcWing、第 90 场周赛:4806. 首字母大写、4807. 找数字、4808. 构造字符串(C++)

目录 4806. 首字母大写 题目描述&#xff1a; 实现代码&#xff1a; 4807. 找数字 题目描述&#xff1a; 实现代码&#xff1a; 回溯&#xff08;超时&#xff09;&#xff1a; 原理思路&#xff1a; 贪心&#xff1a; 原理思路&#xff1a; 4808. 构造字符串 问题…...

跟同事杠上了,Apache Beanutils为什么被禁止使用?

收录于热门专栏Java基础教程系列&#xff08;进阶篇&#xff09; 在实际的项目开发中&#xff0c;对象间赋值普遍存在&#xff0c;随着双十一、秒杀等电商过程愈加复杂&#xff0c;数据量也在不断攀升&#xff0c;效率问题&#xff0c;浮出水面。 问&#xff1a;如果是你来写…...

Golang 模糊测试的使用

一 背景 在 Go 1.18 中,Go 语言新增模糊测试(Fuzzing)。Fuzzing,又叫fuzz testing,中文叫做模糊测试或随机测试。其本质上是一种自动化测试技术,更具体一点,它是一种基于随机输入的自动化测试技术,常被用于发现处理用户输入的代码中存在的bug和问题。模糊测试和常规的功能…...

RSA公钥加密机制跨语言应用实战

在公钥密码学中(也称为非对称密码学)&#xff0c;加密机制依赖于两个密钥&#xff1a;公钥和私钥。公钥用于加密消息&#xff0c;而只有私钥的所有者才能解密消息。实际应用中通常需要对公钥和私钥进行序列化&#xff0c;然后分发密钥实现在不同场景、不同语言环境中使用。本文…...

P7面试送命题

面试总结&#xff0c;对标市场P7。什么叫送命题&#xff0c;一道题回答不上来面试直接挂的题目。JVM 运行时数据区域内存回收机制GC root有哪些volatile原理synchronize原理JDK 集合家族介绍HashMap原理ConcurrentHashMap原理Thread生命周期ThreadPoolExecutor生命周期、实例化…...

零信任-微软零信任介绍(2)

微软零信任是什么&#xff1f; Microsoft Zero Trust 是一种安全架构&#xff0c;旨在在没有信任任何设备、用户或网络的情况下保护网络。这种架构使用多重验证和分段技术&#xff0c;以确保每个请求和资源的安全性。 零信任不假定任何内部用户或设备是安全的&#xff…...

C++中对象调用成员函数this指针的作用

C中对象调用成员函数this指针的作用 Sales_data total;//定义对象 total.isbn();//调用对象中的成员函数isbn成员函数isbn()通过一个名为this的额外隐式参数来访问调用它的对象total。当我们调用一个成员函数时&#xff0c;用请求该函数的对象地址初始化this。 例如&#xff0…...

JavaScript------数组

目录 一、简介 1、什么是数组&#xff1f; 2、创建数组 3、数组的数据类型 4、向数组中添加元素 5、读取数组中的元素 6、实例属性&#xff1a;length 二、遍历数组 方式一&#xff1a;for循环 方式二&#xff1a;for...of 三、数组方法&#xff08;常用&#xff09…...

迷宫《1》

一天蒜头君掉进了一个迷宫里面&#xff0c;蒜头君想逃出去&#xff0c;可怜的蒜头君连迷宫是否有能逃出去的路都不知道。看在蒜头君这么可怜的份上&#xff0c;就请聪明的你告诉蒜头君是否有可以逃出去的路。输入格式第一行输入两个整数 &#xfffd;n 和 &#xfffd;m&#x…...

剑指 Offer 20. 表示数值的字符串

剑指 Offer 20. 表示数值的字符串 请实现一个函数用来判断字符串是否表示数值&#xff08;包括整数和小数&#xff09;。 数值&#xff08;按顺序&#xff09;可以分成以下几个部分&#xff1a; 若干空格 一个 小数 或者 整数 &#xff08;可选&#xff09;一个 ‘e’ 或 ‘…...

阻抗匹配之反射波形测量

稍微接触过高速信号的朋友&#xff0c;一定对阻抗匹配和信号反射都有所了解&#xff0c;甚至可以按照公式&#xff0c;把反射波形一路推导出来。但是&#xff0c;纸上得来终绝浅&#xff0c;绝知此事要躬行。 今天&#xff0c;我们就来实测一下信号反射波形&#xff0c;测试环…...

微信小程序 java家校通Springboot中小学家校联系电子作业系统

小程序前端框架&#xff1a;uniapp 小程序运行软件&#xff1a;微信开发者 后端技术:javaSsm(SpringSpringMVCMyBatis)vue.js 后端开发环境:idea/eclipse 数据库:mysql 通过对各种资料的收集&#xff0c;了解到“校讯通”是联系社会的窗口&#xff0c;是实现家校联系工作和学校…...

Fluent Python 笔记 第 8 章 对象引用、可变性和垃圾回收

本章先以一个比喻说明 Python 的变量&#xff1a;变量是标注&#xff0c;而不是盒子。如果你不知道引用式变量是什么&#xff0c;可以像这样对别人解释别名。 然后&#xff0c;本章讨论对象标识、值和别名等概念。随后&#xff0c;本章会揭露元组的一个神奇特性&#xff1a;元…...

转义字符的分类

什们是转义字符 可显示字符在字符集中&#xff0c;有一类字符具有这样的特性&#xff1a;当从键盘上输入这个字符时&#xff0c;显示器上就可以显示这个字符&#xff0c;即输入什么就显示什么。这类字符称为可显示字符&#xff0c;如a、b、c、$、和空格符等都是可显示字符。 控…...

剑指 Offer 03. 数组中重复的数字

剑指 Offer 03. 数组中重复的数字 一、题目描述&#xff1a; 找出数组中重复的数字。 在一个长度为 n 的数组 nums 里的所有数字都在 0&#xff5e;n-1 的范围内。数组中某些数字是重复的&#xff0c;但不知道有几个数字重复了&#xff0c;也不知道每个数字重复了几次。请找出…...

飞速创新更新IPO招股书:计划募资约14亿元,向伟为实际控制人

近日&#xff0c;深圳市飞速创新技术股份有限公司&#xff08;下称“飞速创新”&#xff09;预披露更新招股书&#xff0c;准备在深圳证券交易所主板上市。本次冲刺上市&#xff0c;飞速创新计划募资13.54亿元&#xff0c;招商证券为其保荐机构。 据介绍&#xff0c;飞速创新专…...

JUC(java.util.concurrent) 的常见类

1.ReentrantLock 可重入互斥锁. 和 synchronized 定位类似, 都是用来实现互斥效果, 保证线程安全. ReentrantLock 也是可重入锁. "Reentrant" 这个单词的原意就是 "可重入. ReentrantLock 的用法: lock(): 加锁, 如果获取不到锁就死等.trylock(超时时间):…...

Angular4 中 ckeditor5 插件的使用

Angular4 中 ckeditor5 插件的使用 0 环境、新建项目 环境&#xff1a; Windows10Angular/cli1.4.10&#xff08;安装 Angular 的过程略过&#xff0c;Angular4 版本比较古老&#xff0c;这也导致项目安装插件及其他操作比较麻烦&#xff09; 1. ckeditor5 官方用法 基础用…...

[python刷题模板] 前缀函数/next数组/kmp算法

[python刷题模板] 前缀函数/next数组/kmp算法 一、 算法&数据结构1. 描述2. 复杂度分析3. 常见应用4. 常用优化二、 模板代码1. 裸前缀函数2. 树上kmp3. 裸kmp三、其他四、更多例题五、参考链接一、 算法&数据结构 1. 描述 前缀函数和next数组基本上是一个东西&#…...

Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?

Golang 面试经典题&#xff1a;map 的 key 可以是什么类型&#xff1f;哪些不可以&#xff1f; 在 Golang 的面试中&#xff0c;map 类型的使用是一个常见的考点&#xff0c;其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...

高频面试之3Zookeeper

高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个&#xff1f;3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制&#xff08;过半机制&#xff0…...

MMaDA: Multimodal Large Diffusion Language Models

CODE &#xff1a; https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA&#xff0c;它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构&#xf…...

NLP学习路线图(二十三):长短期记忆网络(LSTM)

在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...

浪潮交换机配置track检测实现高速公路收费网络主备切换NQA

浪潮交换机track配置 项目背景高速网络拓扑网络情况分析通信线路收费网络路由 收费汇聚交换机相应配置收费汇聚track配置 项目背景 在实施省内一条高速公路时遇到的需求&#xff0c;本次涉及的主要是收费汇聚交换机的配置&#xff0c;浪潮网络设备在高速项目很少&#xff0c;通…...

算法:模拟

1.替换所有的问号 1576. 替换所有的问号 - 力扣&#xff08;LeetCode&#xff09; ​遍历字符串​&#xff1a;通过外层循环逐一检查每个字符。​遇到 ? 时处理​&#xff1a; 内层循环遍历小写字母&#xff08;a 到 z&#xff09;。对每个字母检查是否满足&#xff1a; ​与…...

AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别

【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而&#xff0c;传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案&#xff0c;能够实现大范围覆盖并远程采集数据。尽管具备这些优势&#xf…...

9-Oracle 23 ai Vector Search 特性 知识准备

很多小伙伴是不是参加了 免费认证课程&#xff08;限时至2025/5/15&#xff09; Oracle AI Vector Search 1Z0-184-25考试&#xff0c;都顺利拿到certified了没。 各行各业的AI 大模型的到来&#xff0c;传统的数据库中的SQL还能不能打&#xff0c;结构化和非结构的话数据如何和…...

Elastic 获得 AWS 教育 ISV 合作伙伴资质,进一步增强教育解决方案产品组合

作者&#xff1a;来自 Elastic Udayasimha Theepireddy (Uday), Brian Bergholm, Marianna Jonsdottir 通过搜索 AI 和云创新推动教育领域的数字化转型。 我们非常高兴地宣布&#xff0c;Elastic 已获得 AWS 教育 ISV 合作伙伴资质。这一重要认证表明&#xff0c;Elastic 作为 …...

MySQL的pymysql操作

本章是MySQL的最后一章&#xff0c;MySQL到此完结&#xff0c;下一站Hadoop&#xff01;&#xff01;&#xff01; 这章很简单&#xff0c;完整代码在最后&#xff0c;详细讲解之前python课程里面也有&#xff0c;感兴趣的可以往前找一下 一、查询操作 我们需要打开pycharm …...