Минимальное количество свопов, необходимое для перевода очереди в конечное состояние, не более 2 свопов на элемент - PullRequest
Новая
       42

Минимальное количество свопов, необходимое для перевода очереди в конечное состояние, не более 2 свопов на элемент

1 голос
/ 11 октября 2019

Сценарий или постановка задачи:

Это Новый год, и каждый в очереди на катание на американских горках! Есть несколько человек, стоящих в очереди, и каждый человек носит наклейку, указывающую их начальную позицию в очереди. Начальные позиции увеличиваются на 1 с 1 в начале строки до n в конце.

Любой человек в очереди может подкупить человека, находящегося прямо перед ним, чтобы поменяться местами. Если два человека меняются местами, они все равно носят одну и ту же наклейку, обозначающую их первоначальные места в очереди. Один человек может подкупить не более двух других. Например, если n = 8 и Лицо 5 подкупит Лица 4, очередь будет выглядеть следующим образом: 1,2,3,5,4,6,7,8.

Очарованная этой хаотической очередью, вырешите, что вы должны знать минимальное количество взяток, которые имели место, чтобы перевести очередь в ее текущее состояние!

Описание функции

Завершите функциюimumBribes в редакторе ниже. Он должен вывести целое число, представляющее минимальное количество необходимых взяток, или слишком хаотичный, если конфигурация линии невозможна.

MinimBribes имеет следующие параметры:

q: массивцелые числа

Формат ввода

Первая строка содержит целое число, количество тестовых случаев.

Каждая из следующих пар строк выглядит следующим образом: - Первая строка содержитцелое число, число людей в очереди - во второй строке заданы разделенные пробелом целые числа, описывающие конечное состояние очереди.

Формат вывода

Печать целого числа, обозначающего минимальное количество взятокнужно было привести очередь в конечное состояние. Печать Слишком хаотично, если состояние недопустимо, т. Е. Требуется, чтобы человек подкупил больше людей.

Образец ввода 

2
8
5 1 2 3 7 8 6 4
8
1 2 5 3 7 8 6 4

Образец вывода 

Too chaotic
7

Iв основном пытаюсь создать метод, который принимает значения очереди в этом (конечном) состоянии и возвращает количество взяток, необходимое для перехода в конечное состояние, начиная с 1,2,3,4,5, ... состояние, в случае, если количество взяток на человека в очереди не превышает 2, иначе «Слишком хаотично».

Код, который в некоторых случаях дает сбой при использовании потоков Java, приведен ниже, я хочузнаете, почему я не могу получить вывод с помощью Java Streams? 

static void minimumBribes(int[] q) {

        AtomicInteger bribeCount = new AtomicInteger(0);
        AtomicReference<String> chaoticString = new AtomicReference<String>();

        IntStream.rangeClosed(1, q.length).forEach(i -> {
            if (q[i - 1] > i) {
                if (q[i - 1] - i > 2) {
                    chaoticString.set("Too chaotic");
                } else {
                    bribeCount.addAndGet(q[i - 1] - i);
                }
            }
        });

        if (chaoticString.get() == "Too chaotic")
            System.out.print(chaoticString.get());
        else
            System.out.print(bribeCount.get());

    }

Код, который проходит без использования потоков Java, приведен ниже: 

static void minimumBribes(int[] q) {

        for (int i = 0; i < q.length; i++) {
            if (q[i] - (i + 1) > 2) {
                System.out.println("Too chaotic");
                return;
            }
        }

        int bribe = 0;
        for (int i = 0; i < q.length; i++) {
            for (int j = i + 1; j < q.length; j++) {
                if(q[i] > q[j]) {
                    q[j] = q[i] + q[j];
                    q[i] = q[j] - q[i];
                    q[j] = q[j] - q[i];
                    bribe++;
                }
            }
        }
        System.out.println(bribe);
    }

public class MaximumTwoBribesAllowedForMovingForwardInQueue {

//Method that needs to be filled in
    static void minimumBribes(int[] q) {

    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) {
        int t = scanner.nextInt();
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        for (int tItr = 0; tItr < t; tItr++) {
            int n = scanner.nextInt();
            scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

            int[] q = new int[n];

            String[] qItems = scanner.nextLine().split(" ");
            scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

            for (int i = 0; i < n; i++) {
                int qItem = Integer.parseInt(qItems[i]);
                q[i] = qItem;
            }
            minimumBribes(q);
        }
        scanner.close();
    }
}

Можете ли вы помочь порекомендовать изменения, если таковые имеются, для достижения этого с помощью потоков Java?

Пример ввода: 

2
8
5 1 2 3 7 8 6 4
8
1 2 5 3 7 8 6 4

Ожидаемый правильный вывод: 

Too chaotic
7

Фактический неверный вывод 

Too chaotic
6
...