950. Reveal Cards In Increasing Order

leetcode medium

#array#csharp#leetcode#medium#queue#sort

Task

Вам дана колода целочисленных массивов. Имеется колода карт, в которой каждая карта имеет уникальное целое число. Целое число на i-й карте - deck[i]. Вы можете упорядочить колоду в любом порядке. Изначально все карты в одной колоде лежат лицевой стороной вниз (нераскрытыми). Вы будете выполнять следующие действия несколько раз, пока все карты не будут раскрыты: возьмите верхнюю карту колоды, раскройте ее и выньте из колоды. Если в колоде еще есть карты, положите следующую верхнюю карту колоды на дно колоды. Если еще есть нераскрытые карты, вернитесь к шагу 1. В противном случае остановитесь. Верните порядок колоды, при котором карты раскрываются в порядке возрастания. Обратите внимание, что первая запись в ответе считается верхом колоды.

Пример:

Input: deck = [17,13,11,2,3,5,7]

Output: [2,13,3,11,5,17,7]

C# solution

matched/original

using System;
using System.Collections.Generic;
public class Solution {
    public int[] DeckRevealedIncreasing(int[] deck) {
        int n = deck.Length;
        Queue<int> index = new Queue<int>();
        for (int i = 0; i < n; i++) {
            index.Enqueue(i);
        }
        
        Array.Sort(deck);
        int[] result = new int[n];
        
        foreach (int card in deck) {
            result[index.Dequeue()] = card;
            if (index.Count > 0) {
                index.Enqueue(index.Dequeue());
            }
        }
        
        return result;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public vector<int>& DeckRevealedIncreasing(vector<int>& deck) {
        int n = deck.size();
        queue<int> index = new queue<int>();
        for (int i = 0; i < n; i++) {
            index.Enqueue(i);
        }
        
        sort(deck.begin(), deck.end());
        vector<int>& result = new int[n];
        
        foreach (int card in deck) {
            result[index.Dequeue()] = card;
            if (index.size() > 0) {
                index.Enqueue(index.Dequeue());
            }
        }
        
        return result;
    }
}

Java solution

matched/original

import java.util.*;

class Solution {
    public int[] deckRevealedIncreasing(int[] deck) {
        int n = deck.length;
        Queue<Integer> index = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            index.add(i);
        }
        
        Arrays.sort(deck);
        int[] result = new int[n];
        
        for (int card : deck) {
            result[index.poll()] = card;
            if (!index.isEmpty()) {
                index.add(index.poll());
            }
        }
        
        return result;
    }
}

JavaScript solution

matched/original

var deckRevealedIncreasing = function(deck) {
    let n = deck.length;
    let index = Array.from({length: n}, (_, i) => i);
    let result = new Array(n);
    deck.sort((a, b) => a - b);
    
    for (let card of deck) {
        result[index.shift()] = card;
        if (index.length) {
            index.push(index.shift());
        }
    }
    
    return result;
};

Explanation

Algorithm

1⃣Создать индексы карт в порядке, в котором они будут раскрываться.

2⃣Отсортировать колоду карт по возрастанию.

3⃣Заполнить результат раскрытия карт по ранее созданным индексам.

😎