DEV Community

Beatriz Maciel
Beatriz Maciel

Posted on

3

HackerRank #40 | Java Dequeue | đŸ‡§đŸ‡·

Esse exercĂ­cio recebe dois inputs iniciais: um integer N, relativo Ă  quantidade de nĂșmeros em um array, e um integer M, relativo a um subarray deslocĂĄvel que farĂĄ a "varredura" dentro do array principal.

HackerRank Dequeue Imagem

N = quantidade de nĂșmeros do array
M = tamanho do subarray que varrerĂĄ o array principal

Dessa forma, os arrays estruturados com M = 3 serĂŁo:

[5, 3, 5]
. . . [3, 5, 2]
. . . . . [5, 2, 3]
. . . . . . . [2, 3, 2]

Como todos os subarrays precisam ter M nĂșmeros, nesse caso esses serĂŁo os subarrays possĂ­veis.

Depois disso, precisamos que o programa contabilize qual Ă© o mĂĄximo de nĂșmeros Ășnicos existentes em um subarray de tamanho M.

[5, 3, 5] = 2 nĂșmeros Ășnicos
[3, 5, 2] = 3 nĂșmeros Ășnicos
[5, 2, 3] = 3 nĂșmeros Ășnicos
[2, 3, 2] = 2 nĂșmeros Ășnicos

Sendo assim, o mĂĄximo de nĂșmeros Ășnicos em um subarray serĂĄ 3. Esse precisa ser o output.

Vamos para a solução, dividida em partes:

  • Primeiro declaramos um Array de Integers de nome deque.
  • Declaramos tambĂ©m um Hashset de Integers de nome hashset. Lembrando que um Hashset nĂŁo repete nĂșmeros, e isso vai ser Ăștil para que possamos contabilizar nĂșmeros Ășnicos.
  • Depois escaneamos os ints N, M e maxUniqueIntegers (nossa resposta final)
  • Dentro de uma iteração, pegaremos, atravĂ©s de um input, os nĂșmeros do array. Lembrando: a quantidade de nĂșmeros do array Ă© delimitada por N, mas serĂĄ inserida pelo usuĂĄrio.
  • Vamos adicionar todos os nĂșmeros do input no Array deque e no Hashset hashset atravĂ©s do .add
  • Faremos uma condicional que diz que nosso Array deque, tendo o mesmo tamanho de M, farĂĄ com que o hashset receba o maxUniqueIntegers para ir contabilizando as entradas de nĂșmeros Ășnicos. Como o hashset sĂł permite nĂșmeros Ășnicos, o maxUniqueIntegers tambĂ©m sĂł receberĂĄ a quantidade de nĂșmeros Ășnicos.
  • Depois, declararemos uma variĂĄvel firstQueueNumber que farĂĄ a remoção do primeiro nĂșmero do nosso array deque. A propriedade .remove sempre remove o primeiro elemento, ou o elemento que tem a menor posição i (leia mais sobre isso nas referĂȘncias)
  • Por fim, imprimimos o maxUniqueNumbers, com a quantidade de nĂșmeros Ășnicos.

O cĂłdigo final fica assim:

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        Deque<Integer> deque = new ArrayDeque<>();
        HashSet<Integer> hashset = new HashSet<>();

        int n = in.nextInt();
        int m = in.nextInt();
        int maxUniqueIntegers = 0;

        for (int i = 0; i < n; i++) {
            int num = in.nextInt();

            deque.add(num);
            hashset.add(num);

            if (deque.size() == m) {
                if (hashset.size() > maxUniqueIntegers) {
                    maxUniqueIntegers = hashset.size();
                }
                int firstQueueNumber = deque.remove();
                if (!deque.contains(firstQueueNumber)) {
                    hashset.remove(firstQueueNumber);
                } 
            }
        }

        System.out.println(maxUniqueIntegers);
    }
}
Enter fullscreen mode Exit fullscreen mode

=======

ReferĂȘncias:

ArrayList : Oracle

============

Essa publicação faz parte de uma série de exercícios resolvidos em Java no HackerRank. Acesse a série completa:

Top comments (0)

Great read:

Is it Time to go Back to the Monolith?

History repeats itself. Everything old is new again and I’ve been around long enough to see ideas discarded, rediscovered and return triumphantly to overtake the fad. In recent years SQL has made a tremendous comeback from the dead. We love relational databases all over again. I think the Monolith will have its space odyssey moment again. Microservices and serverless are trends pushed by the cloud vendors, designed to sell us more cloud computing resources.

Microservices make very little sense financially for most use cases. Yes, they can ramp down. But when they scale up, they pay the costs in dividends. The increased observability costs alone line the pockets of the “big cloud” vendors.