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
quicksort
   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õ

4 nhận xét:

Được tạo bởi Blogger.