Ôn lại kỹ năng lập trình trên Leetcode

Lâu rồi mình chưa làm lại thuật toán. Mình thấy trang Leetcode khá hay, dùng để ôn lại môn Cấu trúc dữ liệu và Giải thuật.

Tuy nhiên, bạn cần xem lại kiến thức trước khi giải bài. Mình đã làm thử 1 bài về Merge Sort, thì đây là bài biến tấu, không phải bài dạng cơ bản, và bạn cần ôn lại kiến thức để đưa data về dạng dữ liệu của bài toán MergeSort

Merge Sort là gì?

Trong khoa học máy tính, sắp xếp trộn (merge sort) là một thuật toán sắp xếp để sắp xếp các danh sách (hoặc bất kỳ cấu trúc dữ liệu nào có thể truy cập tuần tự, v.d. luồng tập tin) theo một trật tự nào đó. Nó được xếp vào thể loại sắp xếp so sánh. Thuật toán này là một ví dụ tương đối điển hình của lối thuật toán chia để trị do John von Neumann đưa ra lần đầu năm 1945. Một thuật toán chi tiết được Goldstine và Neumann đưa ra năm 1948

Do Merge Sort đòi hỏi cần cấp phát vùng bộ nhớ lớn, nên cấu trúc dữ liệu phù hợp là con trỏ

Bài toán

You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

Merge nums1 and nums2 into a single array sorted in non-decreasing order.

The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.

Example 1:

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Explanation: The arrays we are merging are [1,2,3] and [2,5,6].
The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.

Example 2:

Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]
Explanation: The arrays we are merging are [1] and [].
The result of the merge is [1].

Example 3:

Input: nums1 = [0], m = 0, nums2 = [1], n = 1
Output: [1]
Explanation: The arrays we are merging are [] and [1].
The result of the merge is [1].
Note that because m = 0, there are no elements in nums1. The 0 is only there to ensure the merge result can fit in nums1.

Constraints:

• nums1.length == m + n
• nums2.length == n
• 0 <= m, n <= 200
• 1 <= m + n <= 200
• -109 <= nums1[i], nums2[j] <= 109

Follow up: Can you come up with an algorithm that runs in O(m + n) time?

Giải 1 bài toán như thế nào?

1. Đọc hiểu đề bài
2. Đưa ra những bộ test khác nhau
3. Chọn ngôn ngữ để thực hiện
   
4. Xác định thuật toán cần dùng
5. Transform data về đúng kiểu dữ liệu để giải quyết
6. Thực hiện thuật toán

Mình thấy ngôn ngữ C++ là phù hợp để giải các thuật toán. Bạn có thể dùng Java, C# nhưng không phù hợp lắm.

Trước khi Submit đoạn code, bạn cần thực hiện kiểm tra thật kỹ ở khung Test case

Sau khi Submit, nếu pass tất cả các Test cases, bạn sẽ nhận được Success Details

Để chia sẽ thành quả cùng với đoạn code với bạn bè, ở tab Submissions, bạn click phải vào chữ Accepted màu xanh lá để copy link.

Trang Submission Detail sẽ gồm 4 phần:

1. Khung đầu tiên là số lượng Test cases đã pass, thời gian thực hiện. Bạn có thể click vào các thanh Bar để xem thuật toán tối ưu khác.
   
2. Thuật toán của bạn đánh bại được bao nhiêu thuật toán khác ở khung Accepted Solutions Runtime Distribution
3. Memory được sử dụng ở khung Accepted Solutions Memory Distribution
4. Đoạn code mà bạn đã thực hiện

Dưới đây là đoạn code thực hiện trong vòng 120ms

public class Solution {
    public void Merge(int[] nums1, int m, int[] nums2, int n) {
        
        List<int> arr1 = new List<int>();
        List<int> arr2 = new List<int>();
        List<int> final = new List<int>();
        
        arr1 = RemoveZeros(nums1,m);
        arr2 = RemoveZeros(nums2,n);
        
          for(int i=0;i<(arr1.Count);i++)
        {
            final.Add(arr1[i]);
        }
        
        for(int i=0;i<(arr2.Count);i++)
        {
            final.Add(arr2[i]);
        }
           final.Sort();
         for(int i=0;i<final.Count;i++)
        {
         nums1[i] = final[i];
        }
        
     
    }
    
    private List<int> RemoveZeros(int[] arr,int length)
    {
        List<int> newArray = new List<int>();
        for( int i=0; i<length;i++)
        {
                newArray.Add(arr[i]);
        }
        return newArray;
    }
}

Đoạn code sau sử dụng Merge Sort mà mình giải bài toán phía trên

Do lâu rồi mình không sử dụng C++ nên mình đành dùng C#. Trên C++, bạn sử dụng con trỏ để tạo ra danh sách kết quả sẽ nhanh hơn việc copy các phần tử từ nums1 sang shadowNums1

Do data chưa đúng chuẩn Merge Sort, nên mình thực hiện việc Transform Data sang shadowNums1.

Từ đó bạn sẽ có 2 danh sách shadowsNums1 và nums2 đại diện cho 2 danh sách cần được merge.

Duyệt qua 2 danh sách, chọn phần tử bé nhất và thêm phần tử đó vào nums1 (danh sách kết quả). Tăng index của danh sách chứa phần tử vừa chọn.

Sau khi 1 trong các điều kiện thỏa là duyệt qua hết các danh sách, lúc này sẽ còn 1 danh sách chưa được duyệt xong. Bạn thực hiện việc kiểm tra và copy các phần tử còn lại vào danh sách nums1

public class Solution {
    public void Merge(int[] nums1, int m, int[] nums2, int n) {
        var countA = m + n;
        var shadowNums1 = new int[m];
        for (var i = 0; i < m; i++)
        {
            shadowNums1[i] = nums1[i];
        }
        var pointerA = 0;
        var pointerB = 0;
        var index = 0;

        while (pointerA < m && pointerB < n)
        {
            var compareResult = Compare(shadowNums1[pointerA], nums2[pointerB]);
            switch (compareResult)
            {
                case 1:
                    nums1[index] = nums2[pointerB];
                    pointerB++;
                    break;
                default:
                    nums1[index] = shadowNums1[pointerA];
                    pointerA++;
                    break;
            }
            index++;
        }
        if (pointerA < m)
        {
            for (var i = pointerA; i < m; i++, index++)
            {
                nums1[index] = shadowNums1[i];
            }
        }
        if (pointerB < n)
        {
            for (var i = pointerB; i < n; i++, index++)
            {
                nums1[index] = nums2[i];
            }
        }
    }
    /*
    a: element in num1
    b: element in num2
    0: use a b
    1: use b a
    */
    public int Compare(int a, int b){
        if(a <= b)
            return 0;
        else
            return 1;
    }
}

Chúc các bạn thành công.