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

#1 · 2023-09-13

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

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

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

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

mod #2 · 2023-09-13

加油🤗👍🏻

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

#3 · 2023-09-13

加油加油，等一个打卡

#4 · 2023-09-13

加油加油 😀

#5 · 2023-09-13

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

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

当前位置：

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

#6 · 2023-09-16

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

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

当前位置：

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

#7 · 2023-10-16

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

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

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

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

#8 · 2023-10-17

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

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

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

#9 · 2023-10-18

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

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

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

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

mod #10 · 2023-10-18

uika_winwing

加油喵加油喵

#11 · 2023-10-23

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 去做。

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

#12 · 2023-10-23

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

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

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

mod #13 · 2023-10-23

uika_winwing

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

#14 · 2023-10-23

TsuinoSora

草，好。

#15 · 2023-10-23

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，但不会。

mod #16 · 2023-10-23

uika_winwing

一开始想到判断是不是 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

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

#17 · 2023-10-24

TsuinoSora

写了个位操作 [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;
}

#18 · 2023-10-24

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

Fundamentals
Sorting

1. Elementary sorts <-
2. Mergesort
3. Quicksort
4. Priority queues
5. Applications
Searching
Graphs
Strings
Context

#19 · 2023-10-24

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

#20 · 2023-10-27

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

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

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