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

小红书刚刚到货，虽然一打开就看到了 Java 代码有点呃呃，但用的都是基本语法能看懂 ✌️😓。作业习题什么的就用 C/C++ 写一下好了。

看介绍说这是一本给低年级学生的一学期课程教材，那就是标准的学习时间为 4 个月。但是既然是自己啃，没有规定的课程节奏，那还是希望早一点结束为好。所以我定的目标是 Nov 21, 2023, 11:59:00 PM (Asia/Shanghai)，也就是我的生日前夜。

虽然不一定能做到，可能中途还会有很多意想不到的意外，但是走一步是一步了 ✌️😥。

[calendar defaultView="month"]
[/calendar]

加油🤗👍🏻

加油加油，等一个打卡

加油加油 😀

Sep 14, 2023, 12:52:00 AM (Asia/Shanghai)

结果 1.1 节一上来就是 Java 基础教学。不过也好，不需要太动脑子，光看书就行。之后的练习题也可以用 Java 做了。

当前位置：

1. Fundamentals

   1. Basic Programming Model <-
   2. Data Abstraction
   3. Bags, Queues, and Stacks
   4. Analysis of Algorithms
   5. Case Study: Union-Find

2. Sorting

3. Searching

4. Graphs

5. Strings

6. Context

Sep 16, 2023, 8:12:00 PM (Asia/Shanghai)

做了一下第一节的课后题，但发现官网只给出了 answers for selected problems。所以决定之后学一个算法就在 leetcode 上做相应的题来练习。

当前位置：

1. Fundamentals

   1. Basic Programming Model
   2. Data Abstraction <-
   3. Bags, Queues, and Stacks
   4. Analysis of Algorithms
   5. Case Study: Union-Find

2. Sorting

3. Searching

4. Graphs

5. Strings

6. Context

Oct 16, 2023, 1:30:00 PM (Asia/Shanghai)

因为作业需求，先学了下后面的 Strings 部分内容。然后看完了抽象数据类型这节，了解到了很多 Java 特性，对面向对象编程思想理解更深入了。还学会了用 assertion 进行防御式编程，判断 preconditions 是否成立。

后面两节基本数据结构、算法分析我就比较熟悉了，但是 Bags 还是要看看。最期待 case study。

1. Fundamentals

   1. Basic Programming Model
   2. Data Abstraction
   3. Bags, Queues, and Stacks <-
   4. Analysis of Algorithms
   5. Case Study: Union-Find

2. Sorting

3. Searching

4. Graphs

5. Strings

6. Context

Oct 17, 2023, 7:30:00 PM (Asia/Shanghai)

再熟悉不过的链表和基本数据结构。也学到了 how data structure interplays with algorithms。

1. Fundamentals

   1. Basic Programming Model
   2. Data Abstraction
   3. Bags, Queues, and Stacks
   4. Analysis of Algorithms <-
   5. Case Study: Union-Find

2. Sorting

3. Searching

4. Graphs

5. Strings

6. Context

Oct 18, 2023, 8:38:00 PM (Asia/Shanghai)

你妈，看书太枯燥了，看不下去一点了。但基础部分就这样，还好已经快到头了。期中之前把第一章看完，其实这本书 1/4 就过去了。之后稍微放一放罢，再钻研理论就 hbxql，先学点好玩的。

之前还对理论有点兴趣，太好笑了，真学起来学不进去一点。疯狂！彻底疯狂！

1. Fundamentals

   1. Basic Programming Model
   2. Data Abstraction
   3. Bags, Queues, and Stacks
   4. Analysis of Algorithms
   5. Case Study: Union-Find <-

2. Sorting

3. Searching

4. Graphs

5. Strings

6. Context

加油喵加油喵

Oct 23, 2023, 6:20:00 PM (Asia/Shanghai)

Doubling ratio experiment 可以用来测试算法复杂度 [order of growth]（除了指数型）。其原理是 if $T(N) \sim aN^{b}\lg N$ then $T(2N)/T(N) \sim 2^{b}$. 每次增加一倍的数据量，最终时间增加的倍数将会稳定在某一 2 的幂。

Big-Oh notation 一般用来表示 the upper bound of worst case，然而平均来说算法的表现要好得多。比如 brute-force pattern matching 最坏情况下的时间复杂度为 n * m，但实际情况一般约为 n。还有一种情况是在某些边界值上算法复杂度很高，而平摊 [amortized] 来看其实表现不错。比如 resizing-array implementation of stack。

编写程序时，算法的简单、高效是十分重要的，但将大量精力投入算法优化中其实费力不讨好。只需注意选择正确的数据结构与算法，并在编写程序时注意防止冗余，就可以了。至于极致的算法优化，交给 theoretical computer scientists 去做。

1. Fundamentals

   1. Basic Programming Model
   2. Data Abstraction
   3. Bags, Queues, and Stacks
   4. Analysis of Algorithms
   5. Case Study: Union-Find <-

2. Sorting

3. Searching

4. Graphs

5. Strings

6. Context

此贴打算转型，不再局限于算法第四版这本书，而是记录我的算法学习历程 🤔。

书上第一章的内容特别长，占了整本书的 1/4。读完之后准备开始做 LeetCode 每日一题（？）

稍微学一下 Java 之后做一下 CS61b 的大作业罢，不写大项目实在是枯燥。

好好好，我困在 proj2 好一段时间

草，好。

Oct 24, 2023 (Asia/Shanghai)

10 月 23 日 LeetCode 每日一题：342. Power of Four

bool isPowerOfFour(int n) {
    if (n < 1) return false;
    while (n % 4 == 0) n /= 4;
    return n == 1 ? true : false;
}

草？

其实一开始想到 bit fiddling，但不会。

一开始想到判断是不是 2 的偶数次方就行，然后想到可能要位运算，我不太会。。
然后又不想就用普通的循环 / 递归
于是用了个这个：

class Solution:
    def isPowerOfFour(self, n: int) -> bool:
        ans = [1]
        i = 0
        cnt = 0
        while i <= 31:
            ans.append(ans[cnt] * 2 * 2)
            i += 2
            cnt += 1

        return n in ans

（反正给了范围，一共也就十几项（

写了个位操作 [bit fiddling] 版的：

bool isPowerOfFour(int n){
    if (n < 1) return false;
    for (unsigned i = (unsigned)(sizeof(int) * 8); i > 0; i -= 2, n >>= 2) {
        switch (n & 0x3) {
            case 0x0:
                continue;
            case 0x1:
                return n == 1 ? true : false;
            default:
                return false;
        }
    }
    return true;
}

Oct 24, 2023, 10:40:00 PM (Asia/Shanghai)

见证了 Union-Find 算法一步一步建构、优化的过程，真是乐趣无穷。

本章从 Java 基础编程模型开始，先介绍了抽象数据类型，然后是一些基本数据结构，最后是算法的分析方法。Now I am armed with the fundamentals of data structure and algorithms.

主要学到的算法有：

• Pushdown stack (resizing array)
• Pushdown stack (linked-list)
• FIFO queue
• Bag
• Union-find

1. Fundamentals

2. Sorting

   1. Elementary sorts <-
   2. Mergesort
   3. Quicksort
   4. Priority queues
   5. Applications

3. Searching

4. Graphs

5. Strings

6. Context

今天的 LeetCode 每日一题用到了二叉树。虽然学了二叉树，但还不会实现和使用。看今天能不能突击一下。

Oct 27, 2023, 8:28:00 PM (Asia/Shanghai)

练习时长两天半 😎，我要成为 Jvav 大师 😾。

学了下 Java，做了 CS61b proj0，真是极致爽滑。

JAV 是吧

你怎么知道今晚准备打交 😾。

jav 很好，cs61b proj0 也很好，赞美啊！😺😺

唉，之前我还计划着学 java 来着，这几天都看小说 + 学数学😭，下周我们数据结构就开始了 😭 现在 🐁 🐁Java 还没入门

数学领域大神 🙀。

好好，我宣布成立胶带门数据结构学习小组，狠狠学习 😾。

好好好

狠狠加入大神的学习小组 😋 🤗

学习小组有了，大神在哪 🙀

这是 Autograder 的 Halloween 彩蛋吗 😨，刚看到还被吓到了。

ASAG: If you are looking for ransom, I can tell you I don't have money. But what
I do have are a very particular set of skills; skills I have acquired over a
very long career. Skills that make me a nightmare for people like you. If you
let my daughter go now, that'll be the end of it. I will not look for you, I
will not pursue you. But if you don't, I will look for you, I will find you and
I will give you a zero.

Oct 31, 2023, 6:24:00 PM (Asia/Shanghai)

做完了 cs61b proj1a。第一次用 Java 写双向队列，过程中还是遇到了些问题的。使用了 resizing-array 和 DLList 两种数据结构实现，还使用 jUnit 写了 unit test。（虽然还是没搞懂 vscode 怎么检测 Java project 的，不能直接在 vscode 中启动测试）

修完 bug 提交后，用完了三次提交资格，但还有 style 的 2.5 分没拿到。是 hidden field error，其实是命名的问题。我在 class 中调用成员变量和函数都 explicitly 使用了 this，所以其实没大碍。

顺便，还看到了今天 Autograder 的一个彩蛋，还稍稍被吓到了点 😗。

明天就 11 月了啊，天气也是越来越冷了，我也该加快速度了。Searching 部分的树和二叉树学过了，但还没有实现过，快速过一遍就开始上手。Sorting 部分的书还得看。还要做一下 proj1b。

Autograder score: 50.0 / 50.0

ASAG: Because your code deserves the best

好 😋。

好耶

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

cs61b proj1b 堂堂完成！这节主要是应用之前 proj1a 中编写的 deque 数据结构，简单的。

Nov 6, 2023, 8:40:00 PM (Asia/Shanghai)

讲得太好了！ Sedgewick 为什么是神：

排序算法部分先给出了最简单、符合直觉的 Selection sort 和 Insertion sort。这两种算法复杂度都是 $O(N^{2})$ ，但是 Insertion 要略快一些。

在 Insertion 的基础上进行优化，先把每隔 h 个元素的子数列排序好（h-sorted），再减小 h 的值直到 1。这样使得每个元素首先抵达自己目的地附近的位置，减少交换的次数。如此得到了 Shellsort，虽然不能证明其复杂度，但是 it's complexity is not necessarily $\sim N^{2}$ 。

Mergesort 是将数列切分成两个字数列，分别排序好后再进行合并。可以使用递归的 Top-down mergesort，也可以使用非递归的 Bottom-up mergesort。

递归的 divide and conquer 思想与数学归纳法相对应，于是可以用 Induction 来证明其复杂度为 $\sim N \log N$ 。作者也使用二叉树证明了任何基于比较的排序方法，其复杂度都不可能比 $N \log N$ 更优。（这段证明看得本 🍠 是浑身喜悦，接近高潮）

虽然 Mergesort 已经是 asymptotically optimal，但是其使用了辅助数列，所以空间复杂度不是最优。书中也给出了几个小优化点，可以在常数层面上进行优化。

在工程中应该永远首先使用最简单直观的方式，只有在这个算法成为 bottleneck 的时候再去优化它。

1. Fundamentals

2. Sorting

   1. Elementary sorts
   2. Mergesort
   3. Quicksort <-
   4. Priority queues
   5. Applications

3. Searching

4. Graphs

5. Strings

6. Context

我一定要把这段 post 出来，写得太好了 😾。

老哥买的英文原版啊，应该很贵吧......

不是进口的，是人民邮电出版社和中国工信出版集团在大陆出版的。定价是 129，当时买的应该能稍微便宜一点。

Nov 7, 2023, 9:50:00 PM (Asia/Shanghai)

Quicksort 与 mergesort 相比，不用创建辅助数组，因此空间占用更少。精细调整后的 quicksort 还可以将复杂度由 $\sim N\log N$ 降低到 $\sim NH - N$ ，其中 $H$ 为 Shannon 熵。对于存在大量重复 key 的数组，复杂度甚至可以达到 linear。

1. Fundamentals

2. Sorting

   1. Elementary sorts
   2. Mergesort
   3. Quicksort
   4. Priority queues <-
   5. Applications

3. Searching

4. Graphs

5. Strings

6. Context

书好像开胶了 🙀，有点心疼 😿

这个可以和哈夫曼编码一块看

二叉树和 Huffman 编码有了解，然后后面那个是 quicksort with 3-way partitioning 的性质。它使用 $\sim (2 ln 2) NH$ 次比较，当没有重复键时， $H = lg N$ 此时复杂度为 $\sim N lg N$ 当重复键非常多时， $H$ 接近常数值。

Nov 9, 2023, 5:00:00 PM (Asia/Shanghai)

非常好 heap 数据结构和 heapsort 算法，使我的时间复杂度 $\sim N log N$ ，空间复杂度 $1$ 。Priority queue 用处多多，非常好。

知道了这么多种排序方法，综合来说最好用的是 quicksort，但是当 stability 比较重要而 extra space 不太重要的时候最好用的还是 mergesort。

在 Java 中有非常好库方法 java.util.Arrays.sort()，但是在 Java 中要注意维护 immutability。

1. Fundamentals

2. Sorting

3. Searching

   1. Symbol tables <-
   2. Binary search trees
   3. Balanced search trees
   4. Hash tables
   5. Applications

4. Graphs

5. Strings

6. Context

Nov 9, 2023, 10:10:00 PM (Asia/Shanghai)

已完成 cs61b hw1: Packages, Interfaces, Generics, Exceptions, Iteration。

我也能在这里打卡吗，我懒得开贴了（x

好哇好哇 🥳

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()。

今天刷了 2 节 c s61b，复习了下 BST 和 AVL 树，学到了 B 树 和 红黑树

学 B 树 使我水元素充盈，太牛逼了

但是像 AVL 树，B 树，红黑树 这些都是平衡二叉搜索树的实现方法，结果都是一样的？都是为了 $O(\log N)$ 的搜索时间复杂度

哦，b 树可以做操作系统的文件索引和数据库索引，酷

渐进时间复杂度一样，但实际应用的时候并不是只看大 O 复杂度的。比如说

• 红黑树不是严格平衡，这会导致它每次操作的时间不完全稳定（虽然这个影响比较小），极少数情况下会被人挑毛病
• AVL 实现起来一般比较麻烦，导致大多数 AVL 实现的时间常数都比较大。以至于虽然理论上它是严格平衡（稳定）的，但实际上大家经常嫌麻烦（不想写）或者嫌常数太大（慢好多）

更不严格的平衡二叉搜索树 Splay 甚至是均摊 O(log N) 复杂度的，也就是可能出现有的操作非常慢而有的非常快这种现象。感觉公司里搞开发的时候就不喜欢用 Splay，只是竞赛选手刷题的时候还比较常见。

主流 linux FS btrfs，XFS，ext4 都是

谢谢！

另外你叫 success，可以和本站 @3ee28fe1a60c95b89d29317f122c70 组成 cp 😽 😻

😽 😺

21sp 的 lab2 有几个 hidden test 过不了，如果我写的测试用例都能通过，我要怎么找 bug 呢🥲

hidden test 就是考验你自己找问题的时候了（
test case 可能不够全面，可能有些 marginal case 没有照顾到

找到几个 bug 了，现在正在被 Velocity Limiting 折磨 🥲

两月之期已到，然而才学到二叉树和搜索，后面还有图与字符串。这几天光看人类简史和微软 semantic kernel 的文档了。

把 B 树的视频投了，做这个太麻烦了，我在思考自动化生产视频

今天在 ISO C++ 群看到 B 树视频了

恭喜，本站第一个用户网红

我就是因为 CS61abc 的群里有个位置陕西西安 19 岁的二次元头像用户转发了你的新 B 站视频，所以导致我开盒失败😤