[HackerRank]Java的雙向佇列(Java Dequeue)


題目描述

在電腦科學的領域,一個雙向佇列(double-ended queue, dequeue, deque)是一種佇列的抽象資料型態,雙向佇列中的每個元素都可以在佇列的最前端或最後端被新增移除。

Deque介面被許多集合類別所實作,像是LinkedList和ArrayDeque。舉例來說,雙向佇列的物件可以用以下方式宣告與實體化:

在這個題目中,您將會得到N個整數。您需要從任意大小為M的連續子陣列中找出其中最大的不同整數的數量。

原題網址

https://www.hackerrank.com/challenges/java-dequeue

輸入格式

輸入第一行包含N和M兩個整數,分別表示整數的數量和子陣列的大小,範圍都在1到100000之間(包含1和100000),M小於等於N。接下來的一行中,包含N個用空格分隔的整數,範圍在0到10000000之間(包含1和10000000)。

輸出格式

輸出所有子陣列中,最大的不重複整數數量。

範例輸入

6 3
5 3 5 2 3 2

範例輸出

3

額外解釋

所有子陣列如下:

s1=⟨5,3,5⟩,有2個不重複的整數。

s2=⟨3,5,2⟩,有3個不重複的整數。

s3=⟨5,2,3⟩,有3個不重複的整數。

s4=⟨2,3,2⟩,有2個不重複的整數。

所以最大不重複整數數量為3。

解題概念

一邊讀入整數一邊將整數存入Dequeue中,並且使用一個HashMap物件來儲存整數出現的次數。當Dequeue的數量大於或是等於m的時候,要先將最先放進Dequeue的元素取出,並且更改HashMap物件的計數內容,才可以再將整數存入Dequeue中。在每次讀入整數後更改HashMap物件的同時,順便去記錄目前出現次數的最大值。最後再將最大值輸出即可。

參考答案

關於作者

Magic Len

各位好,我是Magic Len,是這網站的管理員。我是台灣台中大肚山上人,畢業於台中高工資訊科和台灣科技大學資訊工程系,曾在桃機航警局服役。我熱愛自然也熱愛科學,喜歡和別人分享自己的知識與經驗。如果你有興趣認識我,可以加我的Facebook,並且請註明是從MagicLen來的。

相關文章