Gái ngành coding phiêu lưu ký - part 2 - Lễ tân liệt truyện

Hồi thứ 2

Chốn công đường, Trâm tiểu thư tỏ lòng trong sạch

Nơi cầu thang, Phương lễ tân lộ mặt lọc lừa

Lại nói chuyện từ hồi 1, Trâm tiểu thư và Khá công tử bị quan binh ập vào bắt tại kĩ viện Mưa Hồng. Mặc dù đã tìm mọi cách giải thích nhưng 2 người vẫn bị bổ đầu áp giải đi giam vào ngục. 

3 ngày sau, quan phủ cho đánh trống thăng đường xét xử, truyền đưa 2 người vào. Vị quan này họ Bao tên Chửng, tự là Cao Su, nổi tiếng thanh liêm, liệu việc như thần.

Bao Cao Su đập bàn hương án hét lớn

Chốn kinh kỳ là nơi thanh lịch văn minh, há đâu để 2 ngươi bày trò chim chuột?

Khá công tử mặt không đổi sắc, quỳ xuống thưa rằng

Thảo dân chỉ là một nho sinh, vốn làm developer ở FSOFT, xưa nay chỉ lấy máy tính làm bầu bạn, viết code để giải buồn, là người học hành đến bậc cử nhân, đâu phải hạng chơi bời lãng tử mà làm trò như vậy. Rõ ràng có kẻ muốn hãm hại. Xin đại nhân minh xét

Bao Cao Su nhìn kĩ khuôn mặt của Khá công tử, thấy mặt như dồi phấn, môi tựa thoa son, tướng tá nho sinh. Còn nhìn Trâm tiểu thư, lông mày lá liễu, da trắng như tuyết, dáng vẻ yểu điệu thục nữ, rõ ràng là một tiểu thư trâm anh thế phiệt, không phải là phường kĩ nữ lăng loàn. Trong lòng cảm thấy nghi hoặc

Đang lúc suy nghĩ, thì có quan tổng quản là Xuân Hồng ghé tai nói nhỏ

Đại nhân cứ làm như vầy, như vầy…

Bao Cao Su nghe xong khen phải, liền đập bàn hét lớn

Ngươi nói là developer thì phải giỏi code, nay ta cho bài toán lập trình nếu không giải được thì trị tội.

Nay phủ ta quanh năm mưa lớn, nên bản phủ có đặt mua 1 lượng lu nước về. Một là để chống ngập lụt, hai là để phát triển nền thủ công gốm sứ nước nhà. Tuy nhiên lu nước thì size khác nhau, có cái nhỏ cái to, cũng phải quản lý cho chặt tránh bị thất thoát.

Coi như mỗi lu nước được lưu vào một array, value của phần tử là size của lu nước

Ngươi hãy viết code để sắp xếp lu từ size lớn đến bé cho ta xem

Khá công tử nghe xong ứng khẩu nói luôn

Nếu thì dùng thuật toán Bubble Sort để sắp xếp ạ. Ý tưởng như vầy

Giải sử array có 5 chiếc lu như ở dưới

 

void bubbleSort(int arrLu[])

    {

        int n = arrLu.length;

        for (int i = 0; i < n-1; i++)

            for (int j = 0; j < n-i-1; j++)

                if (arrLu[j] > arrLu[j+1])

                {

                    // swap temp and arrLu[i]

                    int temp = arrLu[j];

                    arrLu[j] = arrLu[j+1];

                    arrLu[j+1] = temp;

                }

    }

Bao Cao Su nghe xong cả giận đập hương án thét lớn

Đúng là con gà, thuật toán này người loop 2 lớp, độ phức tạp phải là O(n2). Nay số lu ngươi nói mới có 5 chiếc. Trong khi thành Thăng Long đất vuông ngàn dặm tính ra phải cả triệu cái lu. Người dùng cách này thì máy tính chạy bao giờ mới xong, có đủ memory không. Ngươi không tính đến phép tối ưu thuật toán à?

Xin đại nhân bớt giận, thật ra có nhiều thuật toán sắp xếp, có thể dùng thuật toán QuickSort sẽ tối ưu hơn

Thuật toán này có thể gọi là chia để trị như sau

Thảo dân lấy 1 phần tử bên phải gọi là pivot number (70)

Những phần tử nào nhỏ hơn 70 nhóm lại cho sang trái

Lớn hơn thì cho sang phải

Đối với nhóm bên trái và bên phải cứ lặp lại các bước như trên đến khi ko chia được nữa

   int partition(int arrLu[], int left, int right) 

    { 

        int pivot = arrLu[right];  

        int i = (left-1); // index of smaller element 

        for (int j=left; j<right; j++) 

        { 

            // If current element is smaller than or 

            // equal to pivot 

            if (arrLu[j] <= pivot) 

            { 

                i++; 

  

                // swap arrLu[i] and arrLu[j] 

                int temp = arrLu[i]; 

                arrLu[i] = arrLu[j]; 

                arrLu[j] = temp; 

            } 

        } 

  

        // swap arrLu[i+1] and arrLu[right] (or pivot) 

        int temp = arrLu[i+1]; 

        arrLu[i+1] = arrLu[right]; 

        arrLu[right] = temp; 

  

        return i+1; 

    } 

  

  

    /* The main function that implements QuickSort() 

      arrLu[] --> arrLuay to be sorted, 

      left  --> Starting index, 

      right  --> Ending index */

    void sort(int arrLu[], int left, int right) 

    { 

        if (left < right) 

        { 

            /* pi is partitioning index, arrLu[pi] is  

              now at right place */

            int pi = partition(arrLu, left, right); 

  

            // Recursively sort elements before 

            // partition and after partition 

            sort(arrLu, left, pi-1); 

            sort(arrLu, pi+1, right); 

        } 

    }

Lúc này độ phức tạp chỉ còn là O(n log(n)) performance tốt hơn nhiều

Bao Cao Su nghe xong gật gù: Được

Hôm trước bản phủ có nhập về N = 10 chiếc lu kích thước từ 0 đến 9, giờ kiểm kê chỉ còn thế này

arrLu =[1, 2, 3, 4, 6, 9, 8]

Tức là ta bị mất 3 cái kích thước  0, 5, 7 🡪 Làm sao để tính ra được?

Dạ có thế này ạ

// main function

    public static void main (String[] args)

    {

        // input array contains n numbers between [1 to n - 1]

        // with one duplicate, where n = A.length

        int[] arrLu = {1, 2, 3, 4, 6, 9, 7,8};

        boolean tmpArr[] = new boolean[10];

        for (int i = 0; i < arrLu.length; i++) { 

            tmpArr[arrLu[i]]= true;          

        }   

        

        for (int i = 0; i < tmpArr.length;i++) {

            if (tmpArr[i] == false)

            System.out.println(i);

        }

    }

Bao Cao Su gật gù, nhưng thật ra không có lu nào mà lại có size = 0 cả, size bé nhất là 1 thôi. Lu của ta kích thước là 1 🡪 10

Tức là chính xác phải là 5, 7, 10 thì làm sao

Dạ có thể dùng BitSet của Java như ở dưới

  private static void findMissingLu(int[] arrLu, int count) {

        int missingCount = count - arrLu.length;

        BitSet bitSet = new BitSet(count);

        for (int number : arrLu) {

            bitSet.set(number - 1);

        }

        System.out.printf("Missing Lu in integer array %s, with total number %d is %n",

        Arrays.toString(arrLu), count);

        int lastMissingIndex = 0;

        for (int i = 0; i < missingCount; i++) {

            lastMissingIndex = bitSet.nextClearBit(lastMissingIndex);

            System.out.println(++lastMissingIndex);

        }

    }

Bao Cao Su nghe xong hết sức hài lòng vỗ đùi đánh đét

Ngươi đúng là code giỏi, rõ ràng là có kẻ ngậm máu phun người. 

Nói xong cho gọi nhân chứng vào xét hỏi. Đó là một cô nương tên Phương làm lễ tân ở quán mưa hồng. Bao Cao Su nạt lớn

Ngươi tố cáo 2 người này quan hệ mãi dâm, ngươi thấy họ ở đâu

Dạ ở cầu thang của quán

Người làm nghề lễ tân đáng ra phải đứng ở sảnh làm việc, chui ra cầu thang làm gì. Rõ ràng là điêu dân to gan.

Em Phương Lễ Tân hoảng kinh hồn vía lên mây nên mới quỳ xuống lạy thưa

Tiểu nhân lỡ dại. Hôm đó tiểu nhân ra cầu thang để quay clip. Nào ngờ Trâm Tiểu Thư có clip 9 phút mà tiểu nhân chỉ quay dc có 4 phút với 87s nên sinh lòng đố kị, nên mới bày đặt tố cáo chuyện này. Xin đại nhân tha mạng

Bao Cao Su nạt lớn

Đem ả tiên nhân này đánh 20 hèo giam vào ngục

Không biết số phận của Phương Lễ Tân thế nào xem hồi sau sẽ rõ