打表-(POJ)机器翻译

╰+哭是因爲堅強的太久メ 2022-05-18 06:53 174阅读 0赞

*  # 打表-(POJ)机器翻译 #

--------------------

题目链接：[机器翻译][Link 1]

*  ## 思路 ##

看了下题目数据的范围，百万级，如果定义队列然后每输入一个单词去查找是否存在，耗费的时间巨大

所以定义一个布尔类型数组，初始化false（表示元素不存在内存）

当输入一个单词，**如果存在内存中，那么不做任何操作**

如果**不存在内存**，那么按题目要求是**该单词入队**，**如果队满弹出队头再入队**

**出队单词在布尔数组中需要重置****false****，而入队置****true**

众所周知普通数组队列在一系列出队入队后实际的队列容量会减小

为了避免这种情况，本题使用了***循环队列***

*  ## 代码 ##

#include<iostream>
    #include<cstdio>
    using namespace std;
    //算法与数据结构Mooc（第三章栈与队列11机器翻译
    bool Memory_Record[1000005] = { 0 };
    
    int main()
    {
    	int *Model_Queue;
    	int Front = 0, Rear = 0;
    	int MAX_SIZE, Check_Time, Word;
    	int Find_Time = 0;
    	//cin >> MAX_SIZE >> Check_Time;
    	scanf("%d%d", &MAX_SIZE, &Check_Time);
    	MAX_SIZE++;							//+1的原因是循环队列具有一个单元的缓冲空间
    	Model_Queue = new int[MAX_SIZE];
    	while (Check_Time--)
    	{
    		
    		//cin >> Word;
    		scanf("%d", &Word);
    		if (Memory_Record[Word])		//find
    			continue;
    		if ((Rear + 1) % MAX_SIZE == Front)		//full
    		{
    			Front = (Front + 1) % MAX_SIZE;    //pop
    			Memory_Record[Model_Queue[Front]] = false;    //修改该单词为不存在内存中
    		}
    		Memory_Record[Word] = true;   //新入队单词标记为存在
    		Rear = (Rear + 1) % MAX_SIZE;
    		Model_Queue[Rear] = Word;
    		Find_Time++;
    	}
    	//cout << Find_Time << endl;
    	printf("%d\n", Find_Time);
    	return 0;
    }

[Link 1]: http://dsalgo.openjudge.cn/stackqueue/11/

发表评论取消回复

表情：

评论列表（有 0 条评论，174人围观）

还没有评论，来说两句吧...

相关阅读

相关 pytorch-机器翻译

机器翻译和数据集机器翻译（MT）：将一段文本从一种语言自动翻译为另一种语言，用神经网络解决这个问题通常称为神经机器翻译（NMT）。主要特征：输出是单词序列而不是单

傷城~/ 2023年07月06日 10:28/ 0 赞/ 49 阅读

相关机器翻译

统计机器翻译《统计机器翻译宗成庆》 [统计机器翻译 ][Link 1] [NLP 学习笔记 04 (M

﹏ヽ暗。殇╰゛Y/ 2022年09月24日 06:16/ 0 赞/ 170 阅读

相关 1067 机器翻译

题目描述 Description 小晨的电脑上安装了一个机器翻译软件，他经常用这个软件来翻译英语文章。这个翻译软件的原理很简单，它只是从头到尾，依次将每个英文单词用对应的中

雨点打透心脏的1/2处/ 2022年06月16日 09:48/ 0 赞/ 142 阅读

相关 N皇后（打表）

![Center][] ![Center 1][] [Center]: /images/20220610/4b54052db2ce46799ae4f302a1ae7

我会带着你远行/ 2022年06月10日 02:21/ 0 赞/ 132 阅读

相关素数打表

我们经常会使用到素数打表这个工具，判断方法是多种多样的，下面我列举一种好理解的判断方法思路： 1、初始化visit数组，初始化为true,用visit\[i\]=tr

阳光穿透心脏的1/2处/ 2022年05月30日 05:56/ 0 赞/ 280 阅读

相关打表-(POJ)机器翻译

打表-(POJ)机器翻译 -------------------- 题目链接：[机器翻译][Link 1] 思路看了下题目数据的范围，百万级，如果

╰+哭是因爲堅強的太久メ/ 2022年05月18日 06:53/ 0 赞/ 175 阅读

相关 P1540 机器翻译

本题考的是考虑曲折情况的能力（注意细读题，特别测试用例的使用方法）先描述一下题干，然后粘贴出AC代码；题目背景小晨的电脑上安装了一个机器翻译软件，他经常用这

逃离我推掉我的手/ 2022年05月14日 11:51/ 0 赞/ 191 阅读

相关洛谷P1540——机器翻译

题目背景小晨的电脑上安装了一个机器翻译软件，他经常用这个软件来翻译英语文章。题目描述这个翻译软件的原理很简单，它只是从头到尾，依次将每个英文单词用对应的中文含义

傷城~/ 2022年04月14日 06:55/ 0 赞/ 304 阅读

相关打表法

\include<iostream> \include<stdio.h> \include<math.h> using namespace std; bool z

朴灿烈づ我的快乐病毒、/ 2022年02月27日 05:24/ 0 赞/ 183 阅读

相关 Semi-prime H-numbers POJ - 3292 (数学打表)

This problem is based on an exercise of David Hilbert, who pedagogically suggested that

淡淡的烟草味﹌/ 2022年02月20日 13:48/ 0 赞/ 196 阅读