找一个一起学 CS61B 的同学

mod #1 · 2023-11-13

大二，不是西交学生，想补一补数据结构兼带练一练 java。最近在看 21sp 的 lab2，天资愚钝，一个人学习有点痛苦，有点交流可能会好得多，哪怕聊聊天也是好的 🥲

#2 · 2023-11-13

是 mm 还是 gg？

mod #3 · 2023-11-13

我正在学，目前到 21. Trees, BSTs

mod #4 · 2023-11-13

好好好，如果🐭🐭这周能学完 Java
那下周就狠狠追更这里😋
在这里狠狠问大佬们问题🤗

年月擦身过，暂且问，会更好吗？

#5 · 2023-11-13

在想要不要把 sjtu 刷课群推广到 xjtu
但交大门是开放论坛这一点让我有些犹豫

mod #6 · 2023-11-13

东川路第二小绫波

sjtu 还有这种东西
xjtu 就从来没听说过

开放论坛确实是个问题，不过你可以小窗给我吗我也在学（可以小窗给在学习的門友）

#7 · 2023-11-13

我有一个打卡贴：

uika_winwing — #52 in 【记录】这是什么？算法（第 4 版）？速通一下

Nov 10, 2023, 3:02:00 AM (Asia/Shanghai)

你已经掌握了排序算法的奥秘了，那么就来一场试炼罢。

LeetCode 148. Sort List

1 Selection sort

创建一个 sentinel node，每次选出最大的 node，append 到 sentinel 后面。

class Solution {

    public ListNode sortList(ListNode head) {
        return selectionSort(head);
    }

    private static ListNode selectionSort(ListNode head) {
        ListNode sentinel = new ListNode(0, null);
        while (head != null) {
            ListNode largestPrev = findLargestPrev(head);
            ListNode largest = largestPrev.next;

            if (largest == head) {
                head = head.next;
            }
            largestPrev.next = largest.next;
            largest.next = sentinel.next;
            sentinel.next = largest;
        }
        return sentinel.next;
    }

    /** return the previous node of the largest node */
    private static ListNode findLargestPrev(ListNode head) {
        ListNode largestPrev = new ListNode(0, head);
        ListNode currentPrev = largestPrev;
        while (currentPrev.next != null) {
            if (currentPrev.next.val > largestPrev.next.val) {
                largestPrev = currentPrev;
            }
            currentPrev = currentPrev.next;
        }
        return largestPrev;
    }
}

时间复杂度 $O(N^{2})$ ，空间复杂度 $O(1)$ ，不出意外的 TLE。

2 Insertion sort

数组的 insertion sort 是从头开始遍历，如果比左边小就向左交换位置。对于 SLList，依然是创建一个 sentinel node，从 head 节点开始一个一个插入 sentinel 之后，若比后面节点大则向右交换。

class Solution {

    public ListNode sortList(ListNode head) {
        return insertionSort(head);
    }

    private static ListNode insertionSort(ListNode head) {
        ListNode sentinel = new ListNode(0, null);
        while (head != null) {
            ListNode temp = head;
            head = head.next;
            temp.next = sentinel.next;
            sentinel.next = temp;
            swapHelper(sentinel);
        }
        return sentinel.next;
    }

    /** swap first node of sorted list rightwards while larger than right */
    private static void swapHelper(ListNode sentinel) {
        ListNode prev = sentinel;
        ListNode newly = sentinel.next;

        while (newly.next != null && newly.val > newly.next.val) {
            prev.next = newly.next;
            newly.next = newly.next.next;
            prev.next.next = newly;

            prev = prev.next;
        }
    }
}

时间复杂度 $O(N^{2})$ ，空间复杂度 $O(1)$ ，又是令人欣慰的 TLE。但是这个指针操作比上一个要优雅多了。

3 Mergesort

Divide and conquer. Use top-down mergesort.

class Solution {

    public ListNode sortList(ListNode head) {
        if (head == null) return null;
        return mergesort(head);
    }

    /** recursively split and merge */
    private static ListNode mergesort(ListNode head) {
        if (head.next == null) return head;
        ListNode mid = split(head);
        ListNode leftSorted = mergesort(head);
        ListNode rightSorted = mergesort(mid);
        return merge(leftSorted, rightSorted);
    }

    /** split the given list into two and return the pointer to the second half */
    private static ListNode split(ListNode head) {
        ListNode fast = head.next;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        ListNode mid = slow.next;
        slow.next = null;
        return mid;
    }

    /** merge left list and right list */
    private static ListNode merge(ListNode left, ListNode right) {
        ListNode sentinel = new ListNode(0, null);
        ListNode rear = sentinel;
        while (left != null && right != null) {
            if (left.val <= right.val) {
                ListNode temp = left;
                left = left.next;
                temp.next = null;
                rear.next = temp;
            } else {
                ListNode temp = right;
                right = right.next;
                temp.next = null;
                rear.next = temp;
            }
            rear = rear.next;
        }

        if (left == null) {
            while (right != null) {
                ListNode temp = right;
                right = right.next;
                temp.next = null;
                rear.next = temp;
                rear = rear.next;
            }
        } else { // right == null
            while (left != null) {
                ListNode temp = left;
                left = left.next;
                temp.next = null;
                rear.next = temp;
                rear = rear.next;
            }
        }

        return sentinel.next;
    }
}

时间复杂度 $O(NlogN)$ ，空间复杂度 $O(1)$ ，顺利 AC。

对 SLList 进行 quicksort 用 Java 太难实现了，遂放弃。（因为 Java 方法只能返回一个值，并且不能像 C/C++ 一样传递指针的指针来实现多返回值。）

SLList 的节点只有一个指针空间，故也不能实现 Heapsort。所以 mergesort 事坠吼的。

但是有一点小问题：为了避免 mergesort 的 worst case，在数组版本中首先对待排序数组进行 shuffle，链表好像不是很好进行 shuffle。第二个就是为了方便在 SLList 中进行节点插入删除，我使用了 currentPrev.next == current。但感觉这样很不优雅，不知道有没有什么修改方法。

Insertion sort 中我函数抽象的层次不对，应该把可复用的 swap() 抽象出来，而不是依赖于调用函数的 swapHelper()。

但是不太喜欢网课，主要是看书学，再配上做一些题目。会做一些 CS61b 的 hw 和 proj。然后我和 @TsuinoSora 看的都是 Spring 2018 学期。