{"topic":{"id":5645,"title":"【记录】这是什么？算法（第 4 版）？速通一下","slug":"topic","categoryId":54,"createdAt":"2023-09-13 05:04:52.004637","bumpedAt":"2023-12-20 18:45:29.807533","views":1533,"postsCount":76,"highestPostNumber":83,"likeCount":19,"closed":false,"pinned":false,"pinnedGlobally":false,"pinnedAt":null,"pinnedUntil":null,"isBanner":false,"excerpt":"小红书刚刚到货，虽然一打开就看到了 Java 代码有点呃呃，但用的都是基本语法能看懂 ✌️😓。作业习题什么的就用 C/C++ 写一下好了。看介绍说这是一本给低年级学生的一学期课程教材，那就是标准的学习时间为 4 个月。但是既然是自己啃，没有规定的课程节奏，那还是希望早一点结束为好。所以我定的目标是 Nov 21, 2023, 11:59:00 PM (Asia/Shanghai)，也就是我的生日前夜。虽然不一定能做到，可能中途还会…","deletedAt":null,"isAnonymous":false,"category":{"id":54,"name":"学术专区","slug":"academic","color":"9EB83B"},"author":{"id":6205,"username":"uika_winwing","name":null,"avatarUrl":"/uploads/image/76/3b/763b1e5ad8a424c4450bb26cea5ae532e7b1cd9da926ac5d99215d7123bf6002.avif"},"tags":["cs","algorithm"]},"posts":[{"id":11160,"postNumber":1,"raw":"*小红书*刚刚到货，虽然一打开就看到了 Java 代码有点呃呃，但用的都是基本语法能看懂 ✌️😓。作业习题什么的就用 C/C++ 写一下好了。\n\n看介绍说这是一本给低年级学生的一学期课程教材，那就是标准的学习时间为 *4 个月*。但是既然是自己啃，没有规定的课程节奏，那还是希望早一点结束为好。所以我定的目标是 [date=2023-11-21 time=23:59:00 timezone=\"Asia/Shanghai\"]，也就是*我的生日前夜*。\n\n虽然不一定能做到，可能中途还会有很多意想不到的意外，但是走一步是一步了 ✌️😥。\n\n[calendar defaultView=\"month\"]\n[/calendar]","cooked":"

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

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

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

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

\n","createdAt":"2023-09-13 05:04:52.094992","updatedAt":"2024-10-25 11:17:35.401769","replyToPostNumber":null,"replyCount":0,"likeCount":2,"wordCount":187,"liked":false,"bookmarked":false,"polls":[],"reactions":[{"reaction":"💯️","count":1,"users":[{"id":20,"username":"QuantumAssHitter","name":"量子打屁手"}],"hasReacted":false},{"reaction":"👍️","count":1,"users":[{"id":39,"username":"Jeremy","name":"YBY"}],"hasReacted":false},{"reaction":"❤️","count":2,"users":[{"id":1047,"username":"anonymous_coward_old","name":"Anonymous Coward Old"},{"id":1780,"username":"prote","name":null}],"hasReacted":false}],"wiki":false,"version":2,"publicVersion":2,"deletedAt":null,"isAnonymous":false,"user":{"id":6205,"username":"uika_winwing","name":null,"avatarUrl":"/uploads/image/76/3b/763b1e5ad8a424c4450bb26cea5ae532e7b1cd9da926ac5d99215d7123bf6002.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":11161,"postNumber":2,"raw":"加油🤗👍🏻","cooked":"

加油🤗👍🏻

\n","createdAt":"2023-09-13 07:01:53.237035","updatedAt":"2023-09-13 07:01:53.237035","replyToPostNumber":null,"replyCount":0,"likeCount":0,"wordCount":3,"liked":false,"bookmarked":false,"polls":[],"reactions":[{"reaction":"😚️","count":1,"users":[{"id":431,"username":"anon10589529","name":null}],"hasReacted":false}],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":30,"username":"一只玉米人","name":"玉米🌽","avatarUrl":"/uploads/blob/14/96/14961aeaa46ccbb75a61eec0c27b26e74fb5d1c00ccdcbbe898ca9ea37087dd6.svg","admin":false,"moderator":true,"signatureRaw":"*年月擦身过，暂且问，会更好吗？*","signatureCooked":"

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

\n"}},{"id":11163,"postNumber":3,"raw":"加油加油，等一个打卡","cooked":"

加油加油，等一个打卡

\n","createdAt":"2023-09-13 10:06:19.351366","updatedAt":"2023-09-13 10:06:19.351366","replyToPostNumber":null,"replyCount":0,"likeCount":0,"wordCount":10,"liked":false,"bookmarked":false,"polls":[],"reactions":[{"reaction":"😚️","count":1,"users":[{"id":431,"username":"anon10589529","name":null}],"hasReacted":false}],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":1303,"username":"ddf4142","name":"学猹","avatarUrl":null,"admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":11167,"postNumber":4,"raw":"加油加油 :grinning:","cooked":"

加油加油 😀

\n","createdAt":"2023-09-13 12:22:15.689685","updatedAt":"2023-09-13 12:22:15.689685","replyToPostNumber":null,"replyCount":0,"likeCount":0,"wordCount":5,"liked":false,"bookmarked":false,"polls":[],"reactions":[{"reaction":"😚️","count":1,"users":[{"id":431,"username":"anon10589529","name":null}],"hasReacted":false}],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":1288,"username":"LittleWangInShanghai","name":"小王在上海","avatarUrl":"/uploads/image/63/d2/63d25f4f2f6693f9ab450f32bd8d04e2d29f96a980b51555a585423f113c4a58.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":11177,"postNumber":5,"raw":"[date=2023-09-14 time=00:52:00 timezone=\"Asia/Shanghai\"]\n\n结果 1.1 节一上来就是 Java 基础教学。不过也好，不需要太动脑子，光看书就行。之后的练习题也可以用 Java 做了。\n\n当前位置：\n\n1. Fundamentals\n\n 1. *Basic Programming Model <-*\n 2. Data Abstraction\n 3. Bags, Queues, and Stacks\n 4. Analysis of Algorithms\n 5. Case Study: Union-Find\n\n2. Sorting\n3. Searching\n4. Graphs\n5. Strings\n6. Context","cooked":"

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

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

当前位置：

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

\n","createdAt":"2023-09-13 17:00:02.100883","updatedAt":"2024-10-25 11:17:36.178689","replyToPostNumber":null,"replyCount":0,"likeCount":0,"wordCount":89,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":6205,"username":"uika_winwing","name":null,"avatarUrl":"/uploads/image/76/3b/763b1e5ad8a424c4450bb26cea5ae532e7b1cd9da926ac5d99215d7123bf6002.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":11291,"postNumber":6,"raw":"[date=2023-09-16 time=20:12:00 timezone=\"Asia/Shanghai\"]\n\n做了一下第一节的课后题，但发现官网只给出了 answers for selected problems。所以决定之后学一个算法就在 leetcode 上做相应的题来练习。\n\n当前位置：\n\n1. Fundamentals\n\n 1. Basic Programming Model\n 2. *Data Abstraction <-*\n 3. Bags, Queues, and Stacks\n 4. Analysis of Algorithms\n 5. Case Study: Union-Find\n\n2. Sorting\n3. Searching\n4. Graphs\n5. Strings\n6. Context","cooked":"

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

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

当前位置：

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

\n","createdAt":"2023-09-16 12:12:18.502335","updatedAt":"2024-10-25 11:17:36.610515","replyToPostNumber":null,"replyCount":0,"likeCount":0,"wordCount":90,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":6205,"username":"uika_winwing","name":null,"avatarUrl":"/uploads/image/76/3b/763b1e5ad8a424c4450bb26cea5ae532e7b1cd9da926ac5d99215d7123bf6002.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":13953,"postNumber":7,"raw":"[date=2023-10-16 time=13:30:00 timezone=\"Asia/Shanghai\"]\n\n因为作业需求，先学了下后面的 Strings 部分内容。然后看完了抽象数据类型这节，了解到了很多 Java 特性，对面向对象编程思想理解更深入了。还学会了用 *assertion* 进行防御式编程，判断 preconditions 是否成立。\n\n后面两节基本数据结构、算法分析我就比较熟悉了，但是 Bags 还是要看看。最期待 case study。\n\n1. Fundamentals\n\n 1. Basic Programming Model\n 2. Data Abstraction\n 3. *Bags, Queues, and Stacks <-*\n 4. Analysis of Algorithms\n 5. Case Study: Union-Find\n\n2. Sorting\n3. Searching\n4. Graphs\n5. Strings\n6. Context","cooked":"

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

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

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

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

\n","createdAt":"2023-10-16 08:51:25.35687","updatedAt":"2024-10-25 11:17:37.097639","replyToPostNumber":null,"replyCount":0,"likeCount":1,"wordCount":155,"liked":false,"bookmarked":false,"polls":[],"reactions":[{"reaction":"❤️","count":1,"users":[{"id":31,"username":"TsuinoSora","name":null}],"hasReacted":false}],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":6205,"username":"uika_winwing","name":null,"avatarUrl":"/uploads/image/76/3b/763b1e5ad8a424c4450bb26cea5ae532e7b1cd9da926ac5d99215d7123bf6002.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":14088,"postNumber":8,"raw":"[date=2023-10-17 time=19:30:00 timezone=\"Asia/Shanghai\"]\n\n再熟悉不过的链表和基本数据结构。也学到了 *how data structure interplays with algorithms*。\n\n1. Fundamentals\n\n 1. Basic Programming Model\n 2. Data Abstraction\n 3. Bags, Queues, and Stacks\n 4. *Analysis of Algorithms <-*\n 5. Case Study: Union-Find\n\n2. Sorting\n3. Searching\n4. Graphs\n5. Strings\n6. Context","cooked":"

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

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

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

\n","createdAt":"2023-10-17 12:34:38.471352","updatedAt":"2024-10-25 11:17:37.305498","replyToPostNumber":null,"replyCount":0,"likeCount":0,"wordCount":62,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":6205,"username":"uika_winwing","name":null,"avatarUrl":"/uploads/image/76/3b/763b1e5ad8a424c4450bb26cea5ae532e7b1cd9da926ac5d99215d7123bf6002.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":14141,"postNumber":9,"raw":"[date=2023-10-18 time=20:38:00 timezone=\"Asia/Shanghai\"]\n\n你妈，看书太枯燥了，看不下去一点了。但基础部分就这样，还好已经快到头了。期中之前把第一章看完，其实这本书 1/4 就过去了。之后稍微放一放罢，再钻研理论就 hbxql，先学点好玩的。\n\n之前还对理论有点兴趣，太好笑了，真学起来学不进去一点。疯狂！彻底疯狂！\n\n1. Fundamentals\n\n 1. Basic Programming Model\n 2. Data Abstraction\n 3. Bags, Queues, and Stacks\n 4. Analysis of Algorithms\n 5. *Case Study: Union-Find <-*\n\n2. Sorting\n3. Searching\n4. Graphs\n5. Strings\n6. Context","cooked":"

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

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

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

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

\n","createdAt":"2023-10-18 12:37:56.529005","updatedAt":"2024-10-25 11:17:37.902264","replyToPostNumber":null,"replyCount":1,"likeCount":2,"wordCount":152,"liked":false,"bookmarked":false,"polls":[],"reactions":[{"reaction":"❤️","count":2,"users":[{"id":31,"username":"TsuinoSora","name":null},{"id":1047,"username":"anonymous_coward_old","name":"Anonymous Coward Old"}],"hasReacted":false}],"wiki":false,"version":2,"publicVersion":2,"deletedAt":null,"isAnonymous":false,"user":{"id":6205,"username":"uika_winwing","name":null,"avatarUrl":"/uploads/image/76/3b/763b1e5ad8a424c4450bb26cea5ae532e7b1cd9da926ac5d99215d7123bf6002.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":14166,"postNumber":10,"raw":"加油喵加油喵","cooked":"

加油喵加油喵

\n","createdAt":"2023-10-18 18:09:10.110361","updatedAt":"2023-10-18 18:09:10.110361","replyToPostNumber":9,"replyCount":0,"likeCount":0,"wordCount":6,"liked":false,"bookmarked":false,"polls":[],"reactions":[{"reaction":"🥺️","count":1,"users":[{"id":431,"username":"anon10589529","name":null}],"hasReacted":false}],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":31,"username":"TsuinoSora","name":null,"avatarUrl":"/uploads/image/77/06/7706643ba6d3ee1ec9d0070db0ad8a22bed8651fa8eb829cf44df4d20fa24b3b.avif","admin":false,"moderator":true,"signatureRaw":null,"signatureCooked":null}},{"id":14367,"postNumber":11,"raw":"[date=2023-10-23 time=18:20:00 timezone=\"Asia/Shanghai\"]\n\n*Doubling ratio experiment* 可以用来测试算法复杂度 *[order of growth]*（除了指数型）。其原理是 if $T(N) \\sim aN^{b}\\lg N$ then $T(2N)/T(N) \\sim 2^{b}$. 每次增加一倍的数据量，最终时间增加的倍数将会稳定在某一 2 的幂。\n\nBig-Oh notation 一般用来表示 the upper bound of worst case，然而平均来说算法的表现要好得多。比如 *brute-force pattern matching* 最坏情况下的时间复杂度为 `n * m`，但实际情况一般约为 `n`。还有一种情况是在某些边界值上算法复杂度很高，而平摊 *[amortized]* 来看其实表现不错。比如 *resizing-array implementation of stack*。\n\n编写程序时，算法的简单、高效是十分重要的，但将大量精力投入算法优化中其实费力不讨好。只需注意选择正确的数据结构与算法，并在编写程序时注意防止冗余，就可以了。至于极致的算法优化，交给 theoretical computer scientists 去做。\n\n1. Fundamentals\n\n 1. Basic Programming Model\n 2. Data Abstraction\n 3. Bags, Queues, and Stacks\n 4. Analysis of Algorithms\n 5. *Case Study: Union-Find <-*\n\n2. Sorting\n3. Searching\n4. Graphs\n5. Strings\n6. Context","cooked":"

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

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

\n","createdAt":"2023-10-23 10:58:46.072885","updatedAt":"2024-10-25 11:17:38.50668","replyToPostNumber":null,"replyCount":0,"likeCount":0,"wordCount":300,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":6205,"username":"uika_winwing","name":null,"avatarUrl":"/uploads/image/76/3b/763b1e5ad8a424c4450bb26cea5ae532e7b1cd9da926ac5d99215d7123bf6002.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":14379,"postNumber":12,"raw":"此贴打算转型，不再局限于算法第四版这本书，而是记录我的算法学习历程 🤔。\n\n书上第一章的内容特别长，占了整本书的 1/4。读完之后准备开始做 LeetCode 每日一题（？）\n\n稍微学一下 Java 之后做一下 CS61b 的大作业罢，不写大项目实在是枯燥。","cooked":"

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

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

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

\n","createdAt":"2023-10-23 15:38:23.771191","updatedAt":"2024-10-25 11:17:39.176759","replyToPostNumber":null,"replyCount":1,"likeCount":0,"wordCount":97,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":6205,"username":"uika_winwing","name":null,"avatarUrl":"/uploads/image/76/3b/763b1e5ad8a424c4450bb26cea5ae532e7b1cd9da926ac5d99215d7123bf6002.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":14383,"postNumber":13,"raw":"好好好，我困在 proj2 好一段时间","cooked":"

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

\n","createdAt":"2023-10-23 15:59:47.132548","updatedAt":"2023-10-23 15:59:47.132548","replyToPostNumber":12,"replyCount":1,"likeCount":0,"wordCount":13,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":31,"username":"TsuinoSora","name":null,"avatarUrl":"/uploads/image/77/06/7706643ba6d3ee1ec9d0070db0ad8a22bed8651fa8eb829cf44df4d20fa24b3b.avif","admin":false,"moderator":true,"signatureRaw":null,"signatureCooked":null}},{"id":14386,"postNumber":14,"raw":"草，好。","cooked":"

草，好。

\n","createdAt":"2023-10-23 16:07:03.849688","updatedAt":"2024-10-25 11:17:39.573903","replyToPostNumber":13,"replyCount":0,"likeCount":0,"wordCount":4,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":6205,"username":"uika_winwing","name":null,"avatarUrl":"/uploads/image/76/3b/763b1e5ad8a424c4450bb26cea5ae532e7b1cd9da926ac5d99215d7123bf6002.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":14387,"postNumber":15,"raw":"[date=2023-10-24 timezone=\"Asia/Shanghai\"]\n\n10 月 23 日 LeetCode 每日一题：*[342. Power of Four](https://leetcode.com/problems/power-of-four/)*\n\n```c\nbool isPowerOfFour(int n) {\n if (n < 1) return false;\n while (n % 4 == 0) n /= 4;\n return n == 1 ? true : false;\n}\n```\n\n草？\n\n其实一开始想到 bit fiddling，但不会。","cooked":"

Oct 24, 2023 (Asia/Shanghai)

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

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

草？

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

\n","createdAt":"2023-10-23 16:50:25.792267","updatedAt":"2024-10-25 11:17:39.800143","replyToPostNumber":null,"replyCount":1,"likeCount":0,"wordCount":60,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":6205,"username":"uika_winwing","name":null,"avatarUrl":"/uploads/image/76/3b/763b1e5ad8a424c4450bb26cea5ae532e7b1cd9da926ac5d99215d7123bf6002.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":14388,"postNumber":16,"raw":"一开始想到判断是不是 2 的偶数次方就行，然后想到可能要位运算，我不太会。。\n然后又不想就用普通的循环 / 递归\n于是用了个这个：\n```python\nclass Solution:\n def isPowerOfFour(self, n: int) -> bool:\n ans = [1]\n i = 0\n cnt = 0\n while i <= 31:\n ans.append(ans[cnt] * 2 * 2)\n i += 2\n cnt += 1\n\n return n in ans\n```\n\n（反正给了范围，一共也就十几项（","cooked":"

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

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

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

\n","createdAt":"2023-10-23 19:17:18.099549","updatedAt":"2023-10-23 19:29:29.152323","replyToPostNumber":15,"replyCount":1,"likeCount":0,"wordCount":112,"liked":false,"bookmarked":false,"polls":[],"reactions":[{"reaction":"💯️","count":1,"users":[{"id":431,"username":"anon10589529","name":null}],"hasReacted":false}],"wiki":false,"version":2,"publicVersion":2,"deletedAt":null,"isAnonymous":false,"user":{"id":31,"username":"TsuinoSora","name":null,"avatarUrl":"/uploads/image/77/06/7706643ba6d3ee1ec9d0070db0ad8a22bed8651fa8eb829cf44df4d20fa24b3b.avif","admin":false,"moderator":true,"signatureRaw":null,"signatureCooked":null}},{"id":14399,"postNumber":17,"raw":"写了个位操作 *[bit fiddling]* 版的：\n\n```c\nbool isPowerOfFour(int n){\n if (n < 1) return false;\n for (unsigned i = (unsigned)(sizeof(int) * 8); i > 0; i -= 2, n >>= 2) {\n switch (n & 0x3) {\n case 0x0:\n continue;\n case 0x1:\n return n == 1 ? true : false;\n default:\n return false;\n }\n }\n return true;\n}\n```","cooked":"

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

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

\n","createdAt":"2023-10-24 12:27:42.535016","updatedAt":"2024-10-25 11:17:39.947526","replyToPostNumber":16,"replyCount":0,"likeCount":0,"wordCount":65,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":6205,"username":"uika_winwing","name":null,"avatarUrl":"/uploads/image/76/3b/763b1e5ad8a424c4450bb26cea5ae532e7b1cd9da926ac5d99215d7123bf6002.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":14409,"postNumber":18,"raw":"[date=2023-10-24 time=22:40:00 timezone=\"Asia/Shanghai\"]\n\n见证了 *Union-Find* 算法一步一步建构、优化的过程，真是乐趣无穷。\n\n本章从 Java 基础编程模型开始，先介绍了抽象数据类型，然后是一些基本数据结构，最后是算法的分析方法。Now I am armed with the fundamentals of data structure and algorithms.\n\n主要学到的算法有：\n\n- Pushdown stack (resizing array)\n- Pushdown stack (linked-list)\n- FIFO queue\n- Bag\n- Union-find\n\n---\n\n1. Fundamentals\n2. Sorting\n\n *1. Elementary sorts <-*\n 2. Mergesort\n 3. Quicksort\n 4. Priority queues\n 5. Applications\n\n3. Searching\n4. Graphs\n5. Strings\n6. Context","cooked":"

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

\n
Fundamentals
\n
\n
Sorting
\n
1. Elementary sorts <-
\n2. Mergesort
\n3. Quicksort
\n4. Priority queues
\n5. Applications
\n
\n
Searching
\n
\n
Graphs
\n
\n
Strings
\n
\n
Context
\n

\n","createdAt":"2023-10-24 14:44:02.608255","updatedAt":"2024-10-25 11:17:40.317359","replyToPostNumber":null,"replyCount":0,"likeCount":0,"wordCount":138,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":2,"publicVersion":2,"deletedAt":null,"isAnonymous":false,"user":{"id":6205,"username":"uika_winwing","name":null,"avatarUrl":"/uploads/image/76/3b/763b1e5ad8a424c4450bb26cea5ae532e7b1cd9da926ac5d99215d7123bf6002.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":14410,"postNumber":19,"raw":"今天的 LeetCode 每日一题用到了二叉树。虽然学了二叉树，但还不会实现和使用。看今天能不能突击一下。","cooked":"

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

\n","createdAt":"2023-10-24 14:50:03.180095","updatedAt":"2024-10-25 11:17:40.717877","replyToPostNumber":null,"replyCount":0,"likeCount":0,"wordCount":44,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":6205,"username":"uika_winwing","name":null,"avatarUrl":"/uploads/image/76/3b/763b1e5ad8a424c4450bb26cea5ae532e7b1cd9da926ac5d99215d7123bf6002.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":15065,"postNumber":20,"raw":"[date=2023-10-27 time=20:28:00 timezone=\"Asia/Shanghai\"]\n\n练习时长两天半 😎，我要成为 Jvav 大师 😾。\n\n学了下 Java，做了 CS61b proj0，真是极致爽滑。","cooked":"

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

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

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

\n","createdAt":"2023-10-27 12:28:14.121656","updatedAt":"2024-10-25 11:17:40.91264","replyToPostNumber":null,"replyCount":1,"likeCount":0,"wordCount":34,"liked":false,"bookmarked":false,"polls":[],"reactions":[{"reaction":"👍️","count":1,"users":[{"id":30,"username":"一只玉米人","name":"玉米🌽"}],"hasReacted":false}],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":6205,"username":"uika_winwing","name":null,"avatarUrl":"/uploads/image/76/3b/763b1e5ad8a424c4450bb26cea5ae532e7b1cd9da926ac5d99215d7123bf6002.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":15070,"postNumber":21,"raw":"JAV 是吧","cooked":"

JAV 是吧

\n","createdAt":"2023-10-27 13:14:04.247288","updatedAt":"2023-10-27 13:14:04.247288","replyToPostNumber":null,"replyCount":1,"likeCount":0,"wordCount":3,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":1047,"username":"anonymous_coward_old","name":"Anonymous Coward Old","avatarUrl":"/uploads/image/43/32/4332638c11248b8ff07033c11de0759a55205facfbec85e14458245a91991faf.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":15076,"postNumber":22,"raw":"你怎么知道今晚准备打交 😾。","cooked":"

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

\n","createdAt":"2023-10-27 13:29:38.363837","updatedAt":"2024-10-25 11:17:41.157778","replyToPostNumber":21,"replyCount":1,"likeCount":0,"wordCount":12,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":6205,"username":"uika_winwing","name":null,"avatarUrl":"/uploads/image/76/3b/763b1e5ad8a424c4450bb26cea5ae532e7b1cd9da926ac5d99215d7123bf6002.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":15077,"postNumber":23,"raw":"jav 很好，cs61b proj0 也很好，赞美啊！😺😺","cooked":"

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

\n","createdAt":"2023-10-27 13:37:10.436681","updatedAt":"2023-10-27 13:37:22.187007","replyToPostNumber":22,"replyCount":0,"likeCount":0,"wordCount":13,"liked":false,"bookmarked":false,"polls":[],"reactions":[{"reaction":"😸️","count":1,"users":[{"id":431,"username":"anon10589529","name":null}],"hasReacted":false}],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":31,"username":"TsuinoSora","name":null,"avatarUrl":"/uploads/image/77/06/7706643ba6d3ee1ec9d0070db0ad8a22bed8651fa8eb829cf44df4d20fa24b3b.avif","admin":false,"moderator":true,"signatureRaw":null,"signatureCooked":null}},{"id":15080,"postNumber":24,"raw":"唉，之前我还计划着学 java 来着，这几天都看小说 + 学数学:loudly_crying_face:，下周我们数据结构就开始了 :loudly_crying_face: 现在 :mouse: :mouse:Java 还没入门","cooked":"

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

\n","createdAt":"2023-10-27 14:15:48.405927","updatedAt":"2023-10-27 14:15:48.405927","replyToPostNumber":20,"replyCount":1,"likeCount":0,"wordCount":47,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":30,"username":"一只玉米人","name":"玉米🌽","avatarUrl":"/uploads/blob/14/96/14961aeaa46ccbb75a61eec0c27b26e74fb5d1c00ccdcbbe898ca9ea37087dd6.svg","admin":false,"moderator":true,"signatureRaw":"*年月擦身过，暂且问，会更好吗？*","signatureCooked":"

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

\n"}},{"id":15089,"postNumber":25,"raw":"数学领域大神 🙀。\n\n好好，我宣布成立胶带门数据结构学习小组，狠狠学习 😾。","cooked":"

数学领域大神 🙀。

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

\n","createdAt":"2023-10-27 14:48:46.324931","updatedAt":"2024-10-25 11:17:41.546523","replyToPostNumber":24,"replyCount":2,"likeCount":0,"wordCount":32,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":6205,"username":"uika_winwing","name":null,"avatarUrl":"/uploads/image/76/3b/763b1e5ad8a424c4450bb26cea5ae532e7b1cd9da926ac5d99215d7123bf6002.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":15090,"postNumber":26,"raw":"好好好","cooked":"

好好好

\n","createdAt":"2023-10-27 14:49:19.427717","updatedAt":"2023-10-27 14:49:19.427717","replyToPostNumber":25,"replyCount":0,"likeCount":0,"wordCount":3,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":31,"username":"TsuinoSora","name":null,"avatarUrl":"/uploads/image/77/06/7706643ba6d3ee1ec9d0070db0ad8a22bed8651fa8eb829cf44df4d20fa24b3b.avif","admin":false,"moderator":true,"signatureRaw":null,"signatureCooked":null}},{"id":15092,"postNumber":27,"raw":"狠狠加入大神的学习小组 :savoring_food: :hug:","cooked":"

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

\n","createdAt":"2023-10-27 14:51:31.179629","updatedAt":"2023-10-27 14:51:31.179629","replyToPostNumber":25,"replyCount":1,"likeCount":0,"wordCount":13,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":30,"username":"一只玉米人","name":"玉米🌽","avatarUrl":"/uploads/blob/14/96/14961aeaa46ccbb75a61eec0c27b26e74fb5d1c00ccdcbbe898ca9ea37087dd6.svg","admin":false,"moderator":true,"signatureRaw":"*年月擦身过，暂且问，会更好吗？*","signatureCooked":"

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

\n"}},{"id":15094,"postNumber":28,"raw":"学习小组有了，大神在哪 🙀","cooked":"

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

\n","createdAt":"2023-10-27 14:52:22.41655","updatedAt":"2024-10-25 11:17:41.805094","replyToPostNumber":27,"replyCount":0,"likeCount":0,"wordCount":12,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":6205,"username":"uika_winwing","name":null,"avatarUrl":"/uploads/image/76/3b/763b1e5ad8a424c4450bb26cea5ae532e7b1cd9da926ac5d99215d7123bf6002.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":15484,"postNumber":29,"raw":"这是 Autograder 的 Halloween 彩蛋吗 :fearful:，刚看到还被吓到了。\n\n```md\nASAG: If you are looking for ransom, I can tell you I don't have money. But what\nI do have are a very particular set of skills; skills I have acquired over a\nvery long career. Skills that make me a nightmare for people like you. If you\nlet my daughter go now, that'll be the end of it. I will not look for you, I\nwill not pursue you. But if you don't, I will look for you, I will find you and\nI will give you a zero.\n```","cooked":"

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

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

\n","createdAt":"2023-10-31 10:18:02.430016","updatedAt":"2024-10-25 11:17:42.028826","replyToPostNumber":null,"replyCount":0,"likeCount":0,"wordCount":110,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":6205,"username":"uika_winwing","name":null,"avatarUrl":"/uploads/image/76/3b/763b1e5ad8a424c4450bb26cea5ae532e7b1cd9da926ac5d99215d7123bf6002.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":15485,"postNumber":30,"raw":"[date=2023-10-31 time=18:24:00 timezone=\"Asia/Shanghai\"]\n\n做完了 cs61b proj1a。第一次用 Java 写双向队列，过程中还是遇到了些问题的。使用了 resizing-array 和 DLList 两种数据结构实现，还使用 jUnit 写了 unit test。（虽然还是没搞懂 vscode 怎么检测 Java project 的，不能直接在 vscode 中启动测试）\n\n修完 bug 提交后，用完了三次提交资格，但还有 style 的 2.5 分没拿到。是 hidden field error，其实是命名的问题。我在 class 中调用成员变量和函数都 explicitly 使用了 `this`，所以其实没大碍。\n\n顺便，还看到了今天 Autograder 的一个彩蛋，还稍稍被吓到了点 :kissing:。\n\n明天就 11 月了啊，天气也是越来越冷了，我也该加快速度了。Searching 部分的树和二叉树学过了，但还没有实现过，快速过一遍就开始上手。Sorting 部分的书还得看。还要做一下 proj1b。","cooked":"

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。

\n","createdAt":"2023-10-31 10:30:29.758581","updatedAt":"2024-10-25 11:17:42.290928","replyToPostNumber":null,"replyCount":0,"likeCount":2,"wordCount":248,"liked":false,"bookmarked":false,"polls":[],"reactions":[{"reaction":"❤️","count":2,"users":[{"id":30,"username":"一只玉米人","name":"玉米🌽"},{"id":1047,"username":"anonymous_coward_old","name":"Anonymous Coward Old"}],"hasReacted":false}],"wiki":false,"version":2,"publicVersion":2,"deletedAt":null,"isAnonymous":false,"user":{"id":6205,"username":"uika_winwing","name":null,"avatarUrl":"/uploads/image/76/3b/763b1e5ad8a424c4450bb26cea5ae532e7b1cd9da926ac5d99215d7123bf6002.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":15497,"postNumber":31,"raw":"Autograder score: 50.0 / 50.0\n\nASAG: Because your code deserves the best\n\n好 😋。","cooked":"

Autograder score: 50.0 / 50.0

ASAG: Because your code deserves the best

好 😋。

\n","createdAt":"2023-10-31 11:59:18.477584","updatedAt":"2024-10-25 11:17:42.613637","replyToPostNumber":null,"replyCount":1,"likeCount":0,"wordCount":14,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":6205,"username":"uika_winwing","name":null,"avatarUrl":"/uploads/image/76/3b/763b1e5ad8a424c4450bb26cea5ae532e7b1cd9da926ac5d99215d7123bf6002.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":15498,"postNumber":32,"raw":"好耶","cooked":"

好耶

\n","createdAt":"2023-10-31 12:19:12.028989","updatedAt":"2023-10-31 12:19:12.028989","replyToPostNumber":31,"replyCount":0,"likeCount":1,"wordCount":2,"liked":false,"bookmarked":false,"polls":[],"reactions":[{"reaction":"❤️","count":1,"users":[{"id":6205,"username":"uika_winwing","name":null}],"hasReacted":false}],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":31,"username":"TsuinoSora","name":null,"avatarUrl":"/uploads/image/77/06/7706643ba6d3ee1ec9d0070db0ad8a22bed8651fa8eb829cf44df4d20fa24b3b.avif","admin":false,"moderator":true,"signatureRaw":null,"signatureCooked":null}},{"id":15603,"postNumber":33,"raw":"[date=2023-11-02 time=03:10:00 timezone=\"Asia/Shanghai\"]\n\ncs61b proj1b 堂堂完成！这节主要是应用之前 proj1a 中编写的 deque 数据结构，简单的。","cooked":"

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

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

\n","createdAt":"2023-11-01 19:10:13.853346","updatedAt":"2024-10-25 11:17:42.821808","replyToPostNumber":null,"replyCount":0,"likeCount":3,"wordCount":34,"liked":false,"bookmarked":false,"polls":[],"reactions":[{"reaction":"❤️","count":3,"users":[{"id":172,"username":"HCCH","name":"HCCH"},{"id":1047,"username":"anonymous_coward_old","name":"Anonymous Coward Old"},{"id":1850,"username":"Reina","name":"星野露比"}],"hasReacted":false}],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":6205,"username":"uika_winwing","name":null,"avatarUrl":"/uploads/image/76/3b/763b1e5ad8a424c4450bb26cea5ae532e7b1cd9da926ac5d99215d7123bf6002.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":16413,"postNumber":34,"raw":"[date=2023-11-06 time=20:40:00 timezone=\"Asia/Shanghai\"]\n\n**讲得太好了！** Sedgewick 为什么是神：\n\n排序算法部分先给出了最简单、符合直觉的 Selection sort 和 Insertion sort。这两种算法复杂度都是 $O(N^{2})$ ，但是 Insertion 要略快一些。\n\n在 Insertion 的基础上进行优化，先把每隔 h 个元素的子数列排序好（h-sorted），再减小 h 的值直到 1。这样使得每个元素首先抵达自己目的地附近的位置，减少交换的次数。如此得到了 Shellsort，虽然不能证明其复杂度，但是 it's complexity is not necessarily $\\sim N^{2}$ 。\n\nMergesort 是将数列切分成两个字数列，分别排序好后再进行合并。可以使用递归的 Top-down mergesort，也可以使用非递归的 Bottom-up mergesort。\n\n递归的 divide and conquer 思想与数学归纳法相对应，于是可以用 Induction 来证明其复杂度为 $\\sim N \\log N$ 。作者也使用二叉树证明了任何基于比较的排序方法，其复杂度都不可能比 $N \\log N$ 更优。（这段证明看得本 🍠 是浑身喜悦，接近高潮）\n\n虽然 Mergesort 已经是 asymptotically optimal，但是其使用了辅助数列，所以空间复杂度不是最优。书中也给出了几个小优化点，可以在常数层面上进行优化。\n\n在工程中应该永远首先使用最简单直观的方式，只有在这个算法成为 bottleneck 的时候再去优化它。\n\n---\n\n1. Fundamentals\n2. Sorting\n\n 1. Elementary sorts\n 2. Mergesort\n 3. *Quicksort <-*\n 4. Priority queues\n 5. Applications\n\n3. Searching\n4. Graphs\n5. Strings\n6. Context","cooked":"

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 的时候再去优化它。

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

\n","createdAt":"2023-11-06 12:39:53.173257","updatedAt":"2024-10-25 11:17:42.964644","replyToPostNumber":null,"replyCount":0,"likeCount":0,"wordCount":419,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":6205,"username":"uika_winwing","name":null,"avatarUrl":"/uploads/image/76/3b/763b1e5ad8a424c4450bb26cea5ae532e7b1cd9da926ac5d99215d7123bf6002.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":16435,"postNumber":35,"raw":"我一定要把这段 post 出来，写得太好了 😾。\n\n[grid mode=\"tile\"]\n![IMG_6990|375x500](/uploads/image/d1/9e/d19e411639d4b4f50075d21e48a7313402a4f2147f67e274f0301edf10aa61c7.avif)\n\n![IMG_6991|375x500](/uploads/image/b3/df/b3df6ce9cfc154c5ec6a7ac8a38a3399ae60283cb5bfc2868df77b9e7086fdd2.avif)\n\n![IMG_6992|375x500](/uploads/image/7b/4d/7b4d8fc92dfeb923c25fdf839940bbfd1258396a49761b9d4fbb273bea6b6c07.avif)\n\n![IMG_6993|375x500](/uploads/image/d4/df/d4df0946ae1ace29344f9a9dc159c3eb9fbe8121226194dad0ae2398a92b76f9.avif)\n[/grid]","cooked":"

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

$\"IMG_6990\"$

$\"IMG_6991\"$

$\"IMG_6992\"$

$\"IMG_6993\"$

\n","createdAt":"2023-11-06 15:47:46.738931","updatedAt":"2024-10-25 11:17:43.302315","replyToPostNumber":null,"replyCount":1,"likeCount":1,"wordCount":24,"liked":false,"bookmarked":false,"polls":[],"reactions":[{"reaction":"❤️","count":1,"users":[{"id":1047,"username":"anonymous_coward_old","name":"Anonymous Coward Old"}],"hasReacted":false}],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":6205,"username":"uika_winwing","name":null,"avatarUrl":"/uploads/image/76/3b/763b1e5ad8a424c4450bb26cea5ae532e7b1cd9da926ac5d99215d7123bf6002.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":16438,"postNumber":36,"raw":"老哥买的英文原版啊，应该很贵吧......","cooked":"

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

\n","createdAt":"2023-11-06 16:07:45.276533","updatedAt":"2023-11-06 16:07:45.276533","replyToPostNumber":35,"replyCount":1,"likeCount":0,"wordCount":16,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":1288,"username":"LittleWangInShanghai","name":"小王在上海","avatarUrl":"/uploads/image/63/d2/63d25f4f2f6693f9ab450f32bd8d04e2d29f96a980b51555a585423f113c4a58.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":16441,"postNumber":37,"raw":"不是进口的，是人民邮电出版社和中国工信出版集团在大陆出版的。定价是 129，当时买的应该能稍微便宜一点。","cooked":"

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

\n","createdAt":"2023-11-06 16:28:21.389088","updatedAt":"2024-10-25 11:17:43.520883","replyToPostNumber":36,"replyCount":0,"likeCount":0,"wordCount":48,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":6205,"username":"uika_winwing","name":null,"avatarUrl":"/uploads/image/76/3b/763b1e5ad8a424c4450bb26cea5ae532e7b1cd9da926ac5d99215d7123bf6002.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":16493,"postNumber":38,"raw":"[date=2023-11-07 time=21:50:00 timezone=\"Asia/Shanghai\"]\n\nQuicksort 与 mergesort 相比，不用创建辅助数组，因此空间占用更少。精细调整后的 quicksort 还可以将复杂度由 $\\sim N\\log N$ 降低到 $\\sim NH - N$ ，其中 $H$ 为 Shannon 熵。对于存在大量重复 key 的数组，复杂度甚至可以达到 linear。\n\n---\n\n1. Fundamentals\n2. Sorting\n\n 1. Elementary sorts\n 2. Mergesort\n 3. Quicksort\n 4. *Priority queues <-*\n 5. Applications\n\n3. Searching\n4. Graphs\n5. Strings\n6. Context","cooked":"

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

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

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

\n","createdAt":"2023-11-07 13:51:46.291015","updatedAt":"2024-10-25 11:17:43.709863","replyToPostNumber":null,"replyCount":1,"likeCount":1,"wordCount":109,"liked":false,"bookmarked":false,"polls":[],"reactions":[{"reaction":"❤️","count":1,"users":[{"id":1047,"username":"anonymous_coward_old","name":"Anonymous Coward Old"}],"hasReacted":false}],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":6205,"username":"uika_winwing","name":null,"avatarUrl":"/uploads/image/76/3b/763b1e5ad8a424c4450bb26cea5ae532e7b1cd9da926ac5d99215d7123bf6002.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":16494,"postNumber":39,"raw":"书好像开胶了 :scream_cat:，有点心疼 :crying_cat:","cooked":"

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

\n","createdAt":"2023-11-07 14:02:07.591896","updatedAt":"2024-10-25 11:17:44.073528","replyToPostNumber":null,"replyCount":0,"likeCount":0,"wordCount":12,"liked":false,"bookmarked":false,"polls":[],"reactions":[{"reaction":"💔️","count":1,"users":[{"id":31,"username":"TsuinoSora","name":null}],"hasReacted":false}],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":6205,"username":"uika_winwing","name":null,"avatarUrl":"/uploads/image/76/3b/763b1e5ad8a424c4450bb26cea5ae532e7b1cd9da926ac5d99215d7123bf6002.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":16503,"postNumber":40,"raw":"[quote=\"uika_winwing, post:38, topic:5645\"]\n精细调整后的 quicksort 还可以将复杂度由 \\sim N\\log N∼NlogN\\sim N\\log N 降低到 \\sim NH - N∼NH−N\\sim NH - N，其中 HHH 为 Shannon 熵。\n[/quote]\n\n这个可以和哈夫曼编码一块看\n\n[quote=\"uika_winwing, post:38, topic:5645\"]\n对于存在大量重复 key 的数组，复杂度甚至可以达到 linear。\n[/quote]\n这个书上写的是前面那个结论的直接推论吗？","cooked":"

\n\t\t\t\t\t\t\t

\n\t\t\t\t\t\t\t\t

\n\t\t\t\t\t\t\t\t\t

\n\t\t\t\t\t\t\t\t\t\t\n\t\t\t\t\t\t\t\t\t

\n\t\t\t\t\t\t\t\t\tuika_winwing:\n\t\t\t\t\t\t\t\t

\n\t\t\t\t\t\t\t\t

\n\t\t\t\t\t\t\t\t\t\n\t\t\t\t\t\t\t\t\t\n\t\t\t\t\t\t\t\t\t\t\n\t\t\t\t\t\t\t\t\t\n\t\t\t\t\t\t\t\t

\n\t\t\t\t\t\t\t

\n
精细调整后的 quicksort 还可以将复杂度由 \\sim N\\log N∼NlogN\\sim N\\log N 降低到 \\sim NH - N∼NH−N\\sim NH - N，其中 HHH 为 Shannon 熵。
\n

\n\t\t\t\t\t\t

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

\n\t\t\t\t\t\t\t

\n\t\t\t\t\t\t\t\t

\n\t\t\t\t\t\t\t\t\t

\n\t\t\t\t\t\t\t\t\t\t\n\t\t\t\t\t\t\t\t\t

\n\t\t\t\t\t\t\t\t\tuika_winwing:\n\t\t\t\t\t\t\t\t

\n\t\t\t\t\t\t\t\t

\n\t\t\t\t\t\t\t\t\t\n\t\t\t\t\t\t\t\t\t\n\t\t\t\t\t\t\t\t\t\t\n\t\t\t\t\t\t\t\t\t\n\t\t\t\t\t\t\t\t

\n\t\t\t\t\t\t\t

\n
对于存在大量重复 key 的数组，复杂度甚至可以达到 linear。
\n

\n\t\t\t\t\t\t

这个书上写的是前面那个结论的直接推论吗？

\n","createdAt":"2023-11-07 15:49:32.012075","updatedAt":"2024-04-07 08:33:49.138232","replyToPostNumber":38,"replyCount":1,"likeCount":0,"wordCount":101,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":1047,"username":"anonymous_coward_old","name":"Anonymous Coward Old","avatarUrl":"/uploads/image/43/32/4332638c11248b8ff07033c11de0759a55205facfbec85e14458245a91991faf.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":16506,"postNumber":41,"raw":"二叉树和 Huffman 编码有了解，然后后面那个是 quicksort with 3-way partitioning 的性质。它使用 $\\sim (2 ln 2) NH$ 次比较，当没有重复键时， $H = lg N$ 此时复杂度为 $\\sim N lg N$ 当重复键非常多时， $H$ 接近常数值。","cooked":"

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

\n","createdAt":"2023-11-07 16:10:12.601443","updatedAt":"2024-10-25 11:17:44.650121","replyToPostNumber":40,"replyCount":0,"likeCount":0,"wordCount":76,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":6205,"username":"uika_winwing","name":null,"avatarUrl":"/uploads/image/76/3b/763b1e5ad8a424c4450bb26cea5ae532e7b1cd9da926ac5d99215d7123bf6002.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":16659,"postNumber":42,"raw":"[date=2023-11-09 time=17:00:00 timezone=\"Asia/Shanghai\"]\n\n非常好 heap 数据结构和 heapsort 算法，使我的时间复杂度 $\\sim N log N$ ，空间复杂度 $1$ 。Priority queue 用处多多，非常好。\n\n知道了这么多种排序方法，综合来说最好用的是 quicksort，但是当 stability 比较重要而 extra space 不太重要的时候最好用的还是 mergesort。\n\n在 Java 中有非常好库方法 `java.util.Arrays.sort()`，但是在 Java 中要注意维护 immutability。\n\n---\n\n1. Fundamentals\n2. Sorting\n3. Searching\n\n 1. *Symbol tables <-*\n 2. Binary search trees\n 3. Balanced search trees\n 4. Hash tables\n 5. Applications\n\n4. Graphs\n5. Strings\n6. Context","cooked":"

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。

\n
Fundamentals
\n
\n
Sorting
\n
\n
Searching
\n
1. Symbol tables <-
2. Binary search trees
3. Balanced search trees
4. Hash tables
5. Applications
\n
\n
Graphs
\n
\n
Strings
\n
\n
Context
\n

\n","createdAt":"2023-11-09 09:19:49.627642","updatedAt":"2024-10-25 11:17:45.063988","replyToPostNumber":null,"replyCount":0,"likeCount":0,"wordCount":145,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":6205,"username":"uika_winwing","name":null,"avatarUrl":"/uploads/image/76/3b/763b1e5ad8a424c4450bb26cea5ae532e7b1cd9da926ac5d99215d7123bf6002.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":16680,"postNumber":44,"raw":"[date=2023-11-09 time=22:10:00 timezone=\"Asia/Shanghai\"]\n\n已完成 cs61b hw1: Packages, Interfaces, Generics, Exceptions, Iteration。","cooked":"

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

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

\n","createdAt":"2023-11-09 14:10:44.546248","updatedAt":"2024-10-25 11:17:45.653327","replyToPostNumber":null,"replyCount":0,"likeCount":0,"wordCount":13,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":6205,"username":"uika_winwing","name":null,"avatarUrl":"/uploads/image/76/3b/763b1e5ad8a424c4450bb26cea5ae532e7b1cd9da926ac5d99215d7123bf6002.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":16683,"postNumber":45,"raw":"我也能在这里打卡吗，我懒得开贴了（x","cooked":"

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

\n","createdAt":"2023-11-09 15:05:59.449531","updatedAt":"2023-11-09 15:05:59.449531","replyToPostNumber":null,"replyCount":1,"likeCount":0,"wordCount":17,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":31,"username":"TsuinoSora","name":null,"avatarUrl":"/uploads/image/77/06/7706643ba6d3ee1ec9d0070db0ad8a22bed8651fa8eb829cf44df4d20fa24b3b.avif","admin":false,"moderator":true,"signatureRaw":null,"signatureCooked":null}},{"id":16684,"postNumber":46,"raw":"好哇好哇 🥳","cooked":"

好哇好哇 🥳

\n","createdAt":"2023-11-09 15:06:36.388699","updatedAt":"2024-10-25 11:17:46.151308","replyToPostNumber":45,"replyCount":0,"likeCount":0,"wordCount":5,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":6205,"username":"uika_winwing","name":null,"avatarUrl":"/uploads/image/76/3b/763b1e5ad8a424c4450bb26cea5ae532e7b1cd9da926ac5d99215d7123bf6002.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":16691,"postNumber":52,"raw":"[date=2023-11-10 time=03:02:00 timezone=\"Asia/Shanghai\"]\n\n你已经掌握了排序算法的奥秘了，那么就来一场试炼罢。\n\nLeetCode [148. Sort List](https://leetcode.com/problems/sort-list/)\n\n## 1 Selection sort\n\n创建一个 sentinel node，每次选出最大的 node，append 到 sentinel 后面。\n\n```java\nclass Solution {\n\n public ListNode sortList(ListNode head) {\n return selectionSort(head);\n }\n\n private static ListNode selectionSort(ListNode head) {\n ListNode sentinel = new ListNode(0, null);\n while (head != null) {\n ListNode largestPrev = findLargestPrev(head);\n ListNode largest = largestPrev.next;\n\n if (largest == head) {\n head = head.next;\n }\n largestPrev.next = largest.next;\n largest.next = sentinel.next;\n sentinel.next = largest;\n }\n return sentinel.next;\n }\n\n /** return the previous node of the largest node */\n private static ListNode findLargestPrev(ListNode head) {\n ListNode largestPrev = new ListNode(0, head);\n ListNode currentPrev = largestPrev;\n while (currentPrev.next != null) {\n if (currentPrev.next.val > largestPrev.next.val) {\n largestPrev = currentPrev;\n }\n currentPrev = currentPrev.next;\n }\n return largestPrev;\n }\n}\n```\n\n时间复杂度 $O(N^{2})$ ，空间复杂度 $O(1)$ ，不出意外的 TLE。\n\n## 2 Insertion sort\n\n数组的 insertion sort 是从头开始遍历，如果比左边小就向左交换位置。对于 SLList，依然是创建一个 sentinel node，从 head 节点开始一个一个插入 sentinel 之后，若比后面节点大则向右交换。\n\n```java\nclass Solution {\n\n public ListNode sortList(ListNode head) {\n return insertionSort(head);\n }\n\n private static ListNode insertionSort(ListNode head) {\n ListNode sentinel = new ListNode(0, null);\n while (head != null) {\n ListNode temp = head;\n head = head.next;\n temp.next = sentinel.next;\n sentinel.next = temp;\n swapHelper(sentinel);\n }\n return sentinel.next;\n }\n\n /** swap first node of sorted list rightwards while larger than right */\n private static void swapHelper(ListNode sentinel) {\n ListNode prev = sentinel;\n ListNode newly = sentinel.next;\n\n while (newly.next != null && newly.val > newly.next.val) {\n prev.next = newly.next;\n newly.next = newly.next.next;\n prev.next.next = newly;\n\n prev = prev.next;\n }\n }\n}\n```\n\n时间复杂度 $O(N^{2})$ ，空间复杂度 $O(1)$ ，又是令人欣慰的 TLE。但是这个指针操作比上一个要优雅多了。\n\n## 3 Mergesort\n\nDivide and conquer. Use top-down mergesort.\n\n```java\nclass Solution {\n\n public ListNode sortList(ListNode head) {\n if (head == null) return null;\n return mergesort(head);\n }\n\n /** recursively split and merge */\n private static ListNode mergesort(ListNode head) {\n if (head.next == null) return head;\n ListNode mid = split(head);\n ListNode leftSorted = mergesort(head);\n ListNode rightSorted = mergesort(mid);\n return merge(leftSorted, rightSorted);\n }\n\n /** split the given list into two and return the pointer to the second half */\n private static ListNode split(ListNode head) {\n ListNode fast = head.next;\n ListNode slow = head;\n while (fast != null && fast.next != null) {\n fast = fast.next.next;\n slow = slow.next;\n }\n\n ListNode mid = slow.next;\n slow.next = null;\n return mid;\n }\n\n /** merge left list and right list */\n private static ListNode merge(ListNode left, ListNode right) {\n ListNode sentinel = new ListNode(0, null);\n ListNode rear = sentinel;\n while (left != null && right != null) {\n if (left.val <= right.val) {\n ListNode temp = left;\n left = left.next;\n temp.next = null;\n rear.next = temp;\n } else {\n ListNode temp = right;\n right = right.next;\n temp.next = null;\n rear.next = temp;\n }\n rear = rear.next;\n }\n\n if (left == null) {\n while (right != null) {\n ListNode temp = right;\n right = right.next;\n temp.next = null;\n rear.next = temp;\n rear = rear.next;\n }\n } else { // right == null\n while (left != null) {\n ListNode temp = left;\n left = left.next;\n temp.next = null;\n rear.next = temp;\n rear = rear.next;\n }\n }\n\n return sentinel.next;\n }\n}\n```\n\n时间复杂度 $O(NlogN)$ ，空间复杂度 $O(1)$ ，顺利 AC。\n\n---\n\n对 SLList 进行 quicksort 用 Java 太难实现了，遂放弃。（因为 Java 方法只能返回一个值，并且不能像 C/C++ 一样传递指针的指针来实现多返回值。）\n\nSLList 的节点只有一个指针空间，故也不能实现 Heapsort。所以 mergesort 事坠吼的。\n\n但是有一点小问题：为了避免 mergesort 的 worst case，在数组版本中首先对待排序数组进行 shuffle，链表好像不是很好进行 shuffle。第二个就是为了方便在 SLList 中进行节点插入删除，我使用了 `currentPrev.next == current`。但感觉这样很不优雅，不知道有没有什么修改方法。\n\nInsertion sort 中我函数抽象的层次不对，应该把可复用的 `swap()` 抽象出来，而不是依赖于调用函数的 `swapHelper()`。","cooked":"

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

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

LeetCode 148. Sort List

1 Selection sort

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

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

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

2 Insertion sort

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

class Solution {\n\n    public ListNode sortList(ListNode head) {\n        return insertionSort(head);\n    }\n\n    private static ListNode insertionSort(ListNode head) {\n        ListNode sentinel = new ListNode(0, null);\n        while (head != null) {\n            ListNode temp = head;\n            head = head.next;\n            temp.next = sentinel.next;\n            sentinel.next = temp;\n            swapHelper(sentinel);\n        }\n        return sentinel.next;\n    }\n\n    /** swap first node of sorted list rightwards while larger than right */\n    private static void swapHelper(ListNode sentinel) {\n        ListNode prev = sentinel;\n        ListNode newly = sentinel.next;\n\n        while (newly.next != null && newly.val > newly.next.val) {\n            prev.next = newly.next;\n            newly.next = newly.next.next;\n            prev.next.next = newly;\n\n            prev = prev.next;\n        }\n    }\n}\n

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

3 Mergesort

Divide and conquer. Use top-down mergesort.

class Solution {\n\n    public ListNode sortList(ListNode head) {\n        if (head == null) return null;\n        return mergesort(head);\n    }\n\n    /** recursively split and merge */\n    private static ListNode mergesort(ListNode head) {\n        if (head.next == null) return head;\n        ListNode mid = split(head);\n        ListNode leftSorted = mergesort(head);\n        ListNode rightSorted = mergesort(mid);\n        return merge(leftSorted, rightSorted);\n    }\n\n    /** split the given list into two and return the pointer to the second half */\n    private static ListNode split(ListNode head) {\n        ListNode fast = head.next;\n        ListNode slow = head;\n        while (fast != null && fast.next != null) {\n            fast = fast.next.next;\n            slow = slow.next;\n        }\n\n        ListNode mid = slow.next;\n        slow.next = null;\n        return mid;\n    }\n\n    /** merge left list and right list */\n    private static ListNode merge(ListNode left, ListNode right) {\n        ListNode sentinel = new ListNode(0, null);\n        ListNode rear = sentinel;\n        while (left != null && right != null) {\n            if (left.val <= right.val) {\n                ListNode temp = left;\n                left = left.next;\n                temp.next = null;\n                rear.next = temp;\n            } else {\n                ListNode temp = right;\n                right = right.next;\n                temp.next = null;\n                rear.next = temp;\n            }\n            rear = rear.next;\n        }\n\n        if (left == null) {\n            while (right != null) {\n                ListNode temp = right;\n                right = right.next;\n                temp.next = null;\n                rear.next = temp;\n                rear = rear.next;\n            }\n        } else { // right == null\n            while (left != null) {\n                ListNode temp = left;\n                left = left.next;\n                temp.next = null;\n                rear.next = temp;\n                rear = rear.next;\n            }\n        }\n\n        return sentinel.next;\n    }\n}\n

时间复杂度 $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()。

\n","createdAt":"2023-11-09 17:47:52.130864","updatedAt":"2024-10-25 11:17:46.446501","replyToPostNumber":null,"replyCount":0,"likeCount":0,"wordCount":881,"liked":false,"bookmarked":false,"polls":[],"reactions":[{"reaction":"👍️","count":1,"users":[{"id":1381,"username":"greyishsong","name":"greyishsong"}],"hasReacted":false}],"wiki":false,"version":5,"publicVersion":5,"deletedAt":null,"isAnonymous":false,"user":{"id":6205,"username":"uika_winwing","name":null,"avatarUrl":"/uploads/image/76/3b/763b1e5ad8a424c4450bb26cea5ae532e7b1cd9da926ac5d99215d7123bf6002.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":16927,"postNumber":53,"raw":"今天刷了 2 节 c s61b，复习了下 BST 和 AVL 树，学到了 B 树和红黑树\n\n学 B 树使我水元素充盈，太牛逼了\n\n但是像 AVL 树，B 树，红黑树这些都是平衡二叉搜索树的实现方法，结果都是一样的？都是为了 $O(\\log N)$ 的搜索时间复杂度","cooked":"

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

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

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

\n","createdAt":"2023-11-13 12:30:39.266102","updatedAt":"2023-11-13 12:30:39.266102","replyToPostNumber":null,"replyCount":2,"likeCount":1,"wordCount":91,"liked":false,"bookmarked":false,"polls":[],"reactions":[{"reaction":"❤️","count":1,"users":[{"id":6205,"username":"uika_winwing","name":null}],"hasReacted":false}],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":31,"username":"TsuinoSora","name":null,"avatarUrl":"/uploads/image/77/06/7706643ba6d3ee1ec9d0070db0ad8a22bed8651fa8eb829cf44df4d20fa24b3b.avif","admin":false,"moderator":true,"signatureRaw":null,"signatureCooked":null}},{"id":16929,"postNumber":54,"raw":"哦，b 树可以做操作系统的文件索引和数据库索引，酷","cooked":"

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

\n","createdAt":"2023-11-13 12:41:27.350978","updatedAt":"2023-11-13 12:41:27.350978","replyToPostNumber":53,"replyCount":1,"likeCount":0,"wordCount":23,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":31,"username":"TsuinoSora","name":null,"avatarUrl":"/uploads/image/77/06/7706643ba6d3ee1ec9d0070db0ad8a22bed8651fa8eb829cf44df4d20fa24b3b.avif","admin":false,"moderator":true,"signatureRaw":null,"signatureCooked":null}},{"id":16936,"postNumber":55,"raw":"渐进时间复杂度一样，但实际应用的时候并不是只看大 O 复杂度的。比如说\n\n- 红黑树不是严格平衡，这会导致它每次操作的时间不完全稳定（虽然这个影响比较小），极少数情况下会被人挑毛病\n- AVL 实现起来一般比较麻烦，导致大多数 AVL 实现的时间常数都比较大。以至于虽然理论上它是严格平衡（稳定）的，但实际上大家经常嫌麻烦（不想写）或者嫌常数太大（慢好多）\n\n更不严格的平衡二叉搜索树 Splay 甚至是**均摊 O(log N) 复杂度**的，也就是可能出现有的操作非常慢而有的非常快这种现象。感觉公司里搞开发的时候就不喜欢用 Splay，只是竞赛选手刷题的时候还比较常见。","cooked":"

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

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

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

\n","createdAt":"2023-11-13 13:04:56.66676","updatedAt":"2023-11-13 13:05:11.989582","replyToPostNumber":53,"replyCount":1,"likeCount":3,"wordCount":249,"liked":false,"bookmarked":false,"polls":[],"reactions":[{"reaction":"❤️","count":3,"users":[{"id":31,"username":"TsuinoSora","name":null},{"id":1649,"username":"triple7","name":null},{"id":6205,"username":"uika_winwing","name":null}],"hasReacted":false}],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":1381,"username":"greyishsong","name":"greyishsong","avatarUrl":"/uploads/image/da/bc/dabc731b0311f59850625bbeb55ed969fcfac0430c5ef0f68441e5466b7aa496.avif","admin":false,"moderator":true,"signatureRaw":null,"signatureCooked":null}},{"id":16938,"postNumber":56,"raw":"主流 linux FS btrfs，XFS，ext4 都是","cooked":"

主流 linux FS btrfs，XFS，ext4 都是

\n","createdAt":"2023-11-13 13:08:57.973582","updatedAt":"2025-05-18 14:32:03.819991","replyToPostNumber":54,"replyCount":1,"likeCount":1,"wordCount":7,"liked":false,"bookmarked":false,"polls":[],"reactions":[{"reaction":"❤️","count":1,"users":[{"id":31,"username":"TsuinoSora","name":null}],"hasReacted":false}],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":1047,"username":"anonymous_coward_old","name":"Anonymous Coward Old","avatarUrl":"/uploads/image/43/32/4332638c11248b8ff07033c11de0759a55205facfbec85e14458245a91991faf.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":16941,"postNumber":57,"raw":"谢谢！\n\n----\n\n另外你叫 success，可以和本站 @3ee28fe1a60c95b89d29317f122c70 组成 cp :kissing_cat: :heart_eyes_cat:","cooked":"

谢谢！

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

\n","createdAt":"2023-11-13 13:12:34.827488","updatedAt":"2023-11-13 13:12:34.827488","replyToPostNumber":56,"replyCount":0,"likeCount":0,"wordCount":20,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":31,"username":"TsuinoSora","name":null,"avatarUrl":"/uploads/image/77/06/7706643ba6d3ee1ec9d0070db0ad8a22bed8651fa8eb829cf44df4d20fa24b3b.avif","admin":false,"moderator":true,"signatureRaw":null,"signatureCooked":null}},{"id":16942,"postNumber":58,"raw":":kissing_cat: :grinning_cat:","cooked":"

😽 😺

\n","createdAt":"2023-11-13 13:12:58.171713","updatedAt":"2023-11-13 13:12:58.171713","replyToPostNumber":55,"replyCount":0,"likeCount":0,"wordCount":2,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":31,"username":"TsuinoSora","name":null,"avatarUrl":"/uploads/image/77/06/7706643ba6d3ee1ec9d0070db0ad8a22bed8651fa8eb829cf44df4d20fa24b3b.avif","admin":false,"moderator":true,"signatureRaw":null,"signatureCooked":null}},{"id":17305,"postNumber":59,"raw":"21sp 的 lab2 有几个 hidden test 过不了，如果我写的测试用例都能通过，我要怎么找 bug 呢:smiling_face_with_tear:","cooked":"

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

\n","createdAt":"2023-11-16 17:06:21.571857","updatedAt":"2023-11-16 17:06:21.571857","replyToPostNumber":null,"replyCount":1,"likeCount":0,"wordCount":34,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":1628,"username":"Lorange","name":"主治医师李大华","avatarUrl":"/uploads/image/f8/ec/f8ecbeb887c4a1311f4f0bf05928476c7b3f632d15bb2b24e782baf2ba6f0d71.avif","admin":false,"moderator":true,"signatureRaw":null,"signatureCooked":null}},{"id":17376,"postNumber":61,"raw":"hidden test 就是考验你自己找问题的时候了（\ntest case 可能不够全面，可能有些 marginal case 没有照顾到","cooked":"

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

\n","createdAt":"2023-11-17 15:56:40.109085","updatedAt":"2024-10-25 11:17:47.255332","replyToPostNumber":59,"replyCount":1,"likeCount":0,"wordCount":37,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":6205,"username":"uika_winwing","name":null,"avatarUrl":"/uploads/image/76/3b/763b1e5ad8a424c4450bb26cea5ae532e7b1cd9da926ac5d99215d7123bf6002.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":17378,"postNumber":62,"raw":"找到几个 bug 了，现在正在被 Velocity Limiting 折磨 :smiling_face_with_tear:","cooked":"

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

\n","createdAt":"2023-11-17 16:14:56.050223","updatedAt":"2023-11-17 16:14:56.050223","replyToPostNumber":61,"replyCount":0,"likeCount":0,"wordCount":17,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":1628,"username":"Lorange","name":"主治医师李大华","avatarUrl":"/uploads/image/f8/ec/f8ecbeb887c4a1311f4f0bf05928476c7b3f632d15bb2b24e782baf2ba6f0d71.avif","admin":false,"moderator":true,"signatureRaw":null,"signatureCooked":null}},{"id":17768,"postNumber":63,"raw":"两月之期已到，然而才学到二叉树和搜索，后面还有图与字符串。这几天光看人类简史和微软 semantic kernel 的文档了。","cooked":"

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

\n","createdAt":"2023-11-21 16:03:20.818991","updatedAt":"2024-10-25 11:17:47.990433","replyToPostNumber":null,"replyCount":0,"likeCount":0,"wordCount":48,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":6205,"username":"uika_winwing","name":null,"avatarUrl":"/uploads/image/76/3b/763b1e5ad8a424c4450bb26cea5ae532e7b1cd9da926ac5d99215d7123bf6002.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":18020,"postNumber":64,"raw":"把 B 树的视频投了，做这个太麻烦了，我在思考自动化生产视频","cooked":"

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

\n","createdAt":"2023-11-26 17:27:32.824936","updatedAt":"2023-11-26 17:27:32.824936","replyToPostNumber":null,"replyCount":4,"likeCount":0,"wordCount":28,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":31,"username":"TsuinoSora","name":null,"avatarUrl":"/uploads/image/77/06/7706643ba6d3ee1ec9d0070db0ad8a22bed8651fa8eb829cf44df4d20fa24b3b.avif","admin":false,"moderator":true,"signatureRaw":null,"signatureCooked":null}},{"id":18071,"postNumber":65,"raw":"今天在 ISO C++ 群看到 B 树视频了","cooked":"

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

\n","createdAt":"2023-11-27 11:05:23.442298","updatedAt":"2023-11-27 11:05:23.442298","replyToPostNumber":64,"replyCount":1,"likeCount":0,"wordCount":13,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":178,"username":"Hypocrisy","name":"rotartsinimdA","avatarUrl":"/uploads/image/ce/f3/cef3773e378e161524cc7523c8a63dff0698d22802b0c1ab669894d395ee36a3.avif","admin":false,"moderator":true,"signatureRaw":null,"signatureCooked":null}},{"id":18073,"postNumber":66,"raw":"恭喜，本站第一个用户网红","cooked":"

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

\n","createdAt":"2023-11-27 11:37:06.984519","updatedAt":"2024-03-17 13:05:26.251836","replyToPostNumber":64,"replyCount":1,"likeCount":0,"wordCount":12,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":2,"publicVersion":2,"deletedAt":null,"isAnonymous":false,"user":{"id":1047,"username":"anonymous_coward_old","name":"Anonymous Coward Old","avatarUrl":"/uploads/image/43/32/4332638c11248b8ff07033c11de0759a55205facfbec85e14458245a91991faf.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":18076,"postNumber":67,"raw":"我就是因为 CS61abc 的群里有个位置陕西西安 19 岁的二次元头像用户转发了你的新 B 站视频，所以导致我开盒失败😤","cooked":"

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

\n","createdAt":"2023-11-27 11:56:11.131705","updatedAt":"2023-11-27 12:50:07.674761","replyToPostNumber":64,"replyCount":0,"likeCount":0,"wordCount":48,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":2,"publicVersion":2,"deletedAt":null,"isAnonymous":false,"user":{"id":30,"username":"一只玉米人","name":"玉米🌽","avatarUrl":"/uploads/blob/14/96/14961aeaa46ccbb75a61eec0c27b26e74fb5d1c00ccdcbbe898ca9ea37087dd6.svg","admin":false,"moderator":true,"signatureRaw":"*年月擦身过，暂且问，会更好吗？*","signatureCooked":"

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

\n"}}],"hasMore":true,"lastReadPostNumber":55,"hasUrlPostNumber":true}