Năm mới hỗn loạn hackerrank giải pháp python

vợ tôi và tôi sẽ có công ty ăn trưa. Một thành viên gia đình sẽ tham gia chiều nay. Do thời tiết thay đổi nên vợ chồng tôi không còn đi bộ vào buổi sáng nữa. Chúng tôi đang đi bộ khoảng giữa trưa. Mặt trời (nếu nó ló dạng ngày nay) ở trên chúng ta vào thời điểm đó. Có nó trên mặt của chúng tôi trên đường trở lại là không vui. Ngoài ra, có vẻ như khoảng 06. 00 PM lỗi thích hoạt động

Chúng tôi vừa mất quyền truy cập Internet. Tôi đặt lại bộ định tuyến nhưng không có kết quả. Vợ tôi sẽ gọi cho nhà cung cấp của chúng tôi để xem vấn đề có lan rộng hay cụ thể đối với chúng tôi không. Thật ngạc nhiên là chúng ta đã quen với việc phụ thuộc vào công nghệ như thế nào

Có vẻ như blog này tại thời điểm này đã đạt được 9.434 người đăng ký . Cảm ơn tất cả các bạn đã đăng ký nó.

Sáng hôm qua, tôi đã giải quyết vấn đề HackerRank “New Year Chaos” bằng cách sử dụng Java. Tôi không có cơ hội để tạo một bài viết. Tôi đang làm như vậy giữa các khối 2 giờ

It is New Year's Day and people are in line for the Wonderland rollercoaster ride. 
Each person wears a sticker indicating their initial position in the queue from 1 to n. 
Any person can bribe the person directly in front of them to swap positions, but they still wear their original sticker. 
One person can bribe at most two others.

Determine the minimum number of bribes that took place to get to a given queue order. 
Print the number of bribes, or, if anyone has bribed more than two people, print `Too chaotic`.

Vì một số lý do, mô tả của vấn đề này phức tạp hơn những gì nó phải là. Không chỉ vậy; . Tôi đoán rằng theo thời gian, các thay đổi được thực hiện đối với các mô tả và toàn bộ vấn đề không được cập nhật đúng cách

Trong bài đăng này, chúng tôi sẽ cố gắng giải quyết vấn đề bằng ngôn ngữ lập trình Java bằng VSCode IDE trên máy tính Windows. Cách đơn giản nhất để giải quyết vấn đề là sử dụng IDE do HackerRank cung cấp. Mà nói;

Vì chúng tôi đang giải quyết vấn đề này trên máy tính của mình, chúng tôi sẽ cần một khung thử nghiệm để thu thập đầu vào, khai báo và điền dữ liệu đầu vào và gọi hàm quan tâm. Trong trường hợp này, có vẻ như các giá trị không được trả về nên chức năng quan tâm phải hiển thị kết quả

Tóm lại, chúng ta được cung cấp một danh sách các số nguyên trong phạm vi [1 … n] đại diện cho một hàng người đang chờ lên tàu lượn siêu tốc. Có vẻ như một số người có thể vượt lên trước trong hàng đợi. Ta cần đếm xem có bao nhiêu người vượt lên trước một, hai bậc trở lên. Chúng ta cần đếm số lần hối lộ của những kẻ ngang ngược. Có một cảnh báo. Nếu ai đó mua trước trong hàng đợi hơn hai điểm, chúng tôi sẽ ngừng đếm và in thông báo sau “Quá hỗn loạn” để cho biết rằng mọi thứ nằm ngoài tầm kiểm soát và chúng tôi sẽ ngừng đếm

Nói chung HackerRank thích tạo ra các mô tả dài dòng cho hầu hết các vấn đề. Có vẻ như cái này hơi dài dòng

    /*
     * Complete the 'minimumBribes' function below.
     *
     * The function accepts INTEGER_ARRAY q as parameter.
     */
    public static void minimumBribes(List q) {
    // Write your code here

    }

The signature for the function of interest seems to indicate that the input is an array of int[], but the actual argument is a List. We will use the input list and then extract the associated array.

1
8
5 1 2 3 7 8 6 4
main <<< q: [5, 1, 2, 3, 7, 8, 6, 4]
<<< bribes: 0 arr: [5, 1, 2, 3, 7, 8, 6, 4]
<<< bribes: 2 arr: [5, 1, 2, 3, 7, 6, 4, 8]
<<< bribes: 4 arr: [5, 1, 2, 3, 6, 4, 7, 8]
<<< bribes: 5 arr: [5, 1, 2, 3, 4, 6, 7, 8]
Too chaotic


1
8
1 2 5 3 7 8 6 4
main <<< q: [1, 2, 5, 3, 7, 8, 6, 4]
<<< bribes: 0 arr: [1, 2, 5, 3, 7, 8, 6, 4]
<<< bribes: 2 arr: [1, 2, 5, 3, 7, 6, 4, 8]
<<< bribes: 4 arr: [1, 2, 5, 3, 6, 4, 7, 8]
<<< bribes: 5 arr: [1, 2, 5, 3, 4, 6, 7, 8]
<<< bribes: 7 arr: [1, 2, 3, 4, 5, 6, 7, 8]
7


1
4
4 1 2 3
main <<< q: [4, 1, 2, 3]
<<< bribes: 0 arr: [4, 1, 2, 3]
Too chaotic


1
5
2 1 5 3 4
main <<< q: [2, 1, 5, 3, 4]
<<< bribes: 0 arr: [2, 1, 5, 3, 4]
<<< bribes: 2 arr: [2, 1, 3, 4, 5]
<<< bribes: 3 arr: [1, 2, 3, 4, 5]
3


1
5
2 5 1 3 4
main <<< q: [2, 5, 1, 3, 4]
<<< bribes: 0 arr: [2, 5, 1, 3, 4]
Too chaotic


1
5
1 2 3 5 4
main <<< q: [1, 2, 3, 5, 4]
<<< bribes: 0 arr: [1, 2, 3, 5, 4]
<<< bribes: 1 arr: [1, 2, 3, 4, 5]
1


1
5
3 1 4 2 5
main <<< q: [3, 1, 4, 2, 5]
<<< bribes: 0 arr: [3, 1, 4, 2, 5]
<<< bribes: 1 arr: [3, 1, 2, 4, 5]
<<< bribes: 3 arr: [1, 2, 3, 4, 5]
3

Có một vài trường hợp thử nghiệm được cung cấp. Dòng đầu tiên cho biết số lượng test case. Để dễ sử dụng, tôi đã đặt nó thành `1` để chúng tôi xử lý từng vấn đề một

Dòng đầu vào thứ hai chứa số phần tử/người trong hàng đợi

Dòng đầu vào thứ ba và cuối cùng chứa thứ tự cuối cùng cho những người trong hàng đợi

Khung thử nghiệm của chúng tôi sẽ bỏ qua hai dòng đầu vào đầu tiên

Sau khi xử lý dữ liệu đầu vào, mã kiểm tra của chúng tôi sẽ hiển thị dữ liệu đầu vào để đảm bảo rằng tất cả đều ổn cho đến nay. Lưu ý rằng mô tả gợi ý một mảng nhưng chữ ký gọi hàng đợi/danh sách

Dòng cuối cùng trong tập hợp hiển thị kết quả của chúng tôi. Các đường trung gian KHÔNG PHẢI LÀ MỘT PHẦN CỦA GIẢI PHÁP . Chúng tôi sẽ sử dụng chúng để kiểm tra quy trình đang hoạt động như thế nào.

    /**
     * Test scaffold
     * @throws IOException
     */
    public static void main(String[] args) throws IOException {
        
        // **** open buffered reader ****
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // **** skip # of test cases ****
        br.readLine();

        // **** skip # of elements in the queue ****
        br.readLine();

        // **** read the list of integers ****
        List q = Arrays.stream(br.readLine().trim().split(" "))
                            .map(Integer::parseInt)
                            .collect(Collectors.toList());

        // **** close buffered reader ****
        br.close();

        // ???? ????
        System.out.println("main <<< q: " + q.toString());

        // **** call the function of interest which displays the result ****
        minimumBribes(q);
    }

Not much to add to the test scaffolding code. We read the input line into a List which we then pass to the function of interest.

    /*
     * Complete the 'minimumBribes' function below.
     *
     * The function accepts INTEGER_ARRAY q as parameter.
     * Failed to pass initial test set.
     */
    public static void minimumBribes0(List q) {

        // **** initialization ****
        int bribes = 0;

        // **** traverse the q forwards ****
        for (int i = 0; i < q.size() - 1; i++) {

            // **** person (for ease of use) ****
            int p = q.get(i);

            // **** check if this person used a bribe ****
            if (p - (i + 1) > 0 ) {

                // ???? ????
                System.out.println("<<< p: " + p + " (p - (i + 1)): " + (p - (i + 1)));

                // **** check if this person is chaotic ****
                if (p - (i + 1) >= 3) {
                    System.out.println("Too chaotic");
                    return;
                }

                // **** increment the bribe count ****
                bribes += (p - (i + 1));
            }
        }

        // **** display # of bribes ****
        System.out.println(bribes);
    }

Tôi đã bắt đầu với một cách tiếp cận khác mà tôi đã bỏ dở vào một lúc nào đó

Ý tưởng là không thực hiện hoán đổi và chỉ đếm chúng. Lý do tôi dừng lại là do quy trình bắt đầu đơn giản nhưng bắt đầu trở nên phức tạp khi giải quyết trường hợp một người tiến lên hai hoặc nhiều bậc trong hàng đợi

Nếu quan tâm, bạn có thể hoàn thành mã này và cho tôi biết. Tôi sẽ cập nhật bài đăng này và sẽ cung cấp cho bạn tín dụng

    /**
     * Auxiliary function.
     * Swaps two elements in the array.
     */
    static private void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i]  = arr[j];
        arr[j]  = tmp;
    }

Đây chỉ là một chức năng phụ trợ đơn giản mà tôi sẽ sử dụng. Tôi gặp sự cố khi đăng mã của mình lên HackerRank. Nó hoạt động tốt trên máy tính của tôi, nhưng điều đó không được tính. Tôi đã kết thúc việc loại bỏ các cuộc gọi đến hàm swap()

    /*
     * Complete the 'minimumBribes' function below.
     *
     * The function accepts INTEGER_ARRAY q as parameter.
     * 
     * Execution: O(n) - Space: O(1)
     */
    public static void minimumBribes(List q) {

        // **** initialization ****
        int bribes  = 0;
        int tmp     = 0;

        // **** generate array from queue (for ease of use) ****
        // Integer[] arr = q.toArray(Integer[]::new);
        int[] arr = new int[q.size()];
        for (int i = 0; i < arr.length; i++)
            arr[i] = q.get(i);

        // ???? ????
        System.out.println("<<< bribes: " + bribes + " arr: " + Arrays.toString(arr));

        // **** traverse the array backwards swapping elements back in place ****
        for (int i = arr.length - 1; i > 0; i--) {

            // **** person in proper place in the queue ****
            if (arr[i] == (i + 1))
                continue;

            // **** swap people one appart ****
            else if (arr[i - 1] == (i + 1)) {

                // **** ****
                // swap(arr, i - 1, i);
                tmp         = arr[i - 1];
                arr[i - 1]  = arr[i];
                arr[i]      = tmp;

                // **** increment bribe count ****
                bribes++;
            }

            // **** swap people two appart ****
            else if (arr[i - 2] == (i + 1)) {

                // **** ****
                // swap(arr, i - 2, i - 1);
                tmp         = arr[i - 2];
                arr[i - 2]  = arr[i - 1];
                arr[i - 1]  = tmp;

                // swap(arr, i - 1, i);
                tmp         = arr[i - 1];
                arr[i - 1]  = arr[i];
                arr[i]      = tmp;

                // **** increment bribe count ****
                bribes += 2;
            }

            // **** too many swaps ****
            else {
                System.out.println("Too chaotic");
                return;
            }

            // ???? ????
            System.out.println("<<< bribes: " + bribes + " arr: " + Arrays.toString(arr));
        }

        // **** display # of bribes ****
        System.out.println(bribes);
    }

Chúng tôi bắt đầu bằng cách khởi tạo một vài biến

Sau đó, chúng tôi điền vào một mảng int[] với nội dung của hàng đợi đầu vào. Dòng nhận xét hoạt động tốt trong VSCode IDE tôi đã sử dụng để phát triển

Xin lưu ý rằng các câu lệnh in được tiến hành bởi “// ???? . Chúng được sử dụng để giúp chúng ta hình dung thuật toán tiến triển như thế nào. NOT PART OF THE SOLUTION. They are used to help us visualize how the algorithm progresses.

Sau đó, chúng tôi nhập một vòng lặp được sử dụng để duyệt ngược mảng đầu vào

Sau đó, chúng tôi xử lý dữ liệu dựa trên vị trí của cá nhân hiện tại trong hàng đợi. Điều kiện đầu tiên giải quyết một người ở vị trí thích hợp của họ (không hối lộ)

Tiếp theo, chúng tôi đề cập đến những người đã di chuyển một vị trí trước vị trí của họ trong hàng đợi. Để xử lý chúng ta cần hoán đổi vị trí và tăng số lượng hối lộ lên một

Trong phần tiếp theo nếu chúng ta xử lý tình huống khi một người hối lộ hai vị trí phía trước trong hàng đợi. Trong những trường hợp như vậy, chúng ta cần hoán đổi hai vị trí trước đó và tăng số lần hối lộ lên hai

Trong trường hợp mặc định khác, chúng tôi đề cập đến những cá nhân đã hối lộ theo cách của họ hơn hai điểm trong hàng đợi. Theo hướng dẫn, chúng tôi hiển thị thông báo “Quá hỗn loạn” (đảm bảo bạn đánh vần đúng chính tả vì nội dung gửi của bạn sẽ không thành công) và quay lại để cho biết chúng tôi đã xử lý xong phần còn lại của hàng đợi

Giải pháp này đã được HackerRank chấp nhận. Vấn đề chạy trong thời gian O(n) và không gian O(1)

Tôi đã có một khoảng thời gian vui vẻ khi giải quyết vấn đề này mặc dù mô tả phức tạp. Nói chung khi gặp sự cố, người ta nên chắt lọc các yêu cầu thành một mô tả đơn giản trước khi thử viết mã.

Toàn bộ mã cho dự án này có thể được tìm thấy trong kho lưu trữ GitHub của tôi

Xin lưu ý rằng mã được trình bày ở đây có thể không phải là giải pháp tốt nhất có thể. Trong hầu hết các trường hợp, sau khi giải quyết vấn đề, bạn có thể xem giải pháp được chấp nhận tốt nhất do các trang web khác nhau cung cấp (i. e. , HackerRank, LeetCode)

Nếu bạn có nhận xét hoặc câu hỏi liên quan đến điều này, hoặc bất kỳ bài đăng nào khác trong blog này, xin đừng ngần ngại và để lại cho tôi một ghi chú bên dưới. Tôi sẽ trả lời càng sớm càng tốt

Tiếp tục đọc và thử nghiệm. Đây là một trong những cách tốt nhất để học hỏi, trở nên thành thạo, cập nhật kiến ​​thức và nâng cao bộ công cụ dành cho nhà phát triển của bạn