{"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":1535,"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}}],"hasMore":true,"lastReadPostNumber":33,"hasUrlPostNumber":true}