找一个一起学 CS61B 的同学

mod #1 · 2023-11-13

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

#2 · 2023-11-13

是 mm 还是 gg？

mod #3 · 2023-11-13

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

mod #4 · 2023-11-13

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

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

#5 · 2023-11-13

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

mod #6 · 2023-11-13

东川路第二小绫波

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

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

#7 · 2023-11-13

我有一个打卡贴：

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

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

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

LeetCode 148. Sort List

1 Selection sort

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

class Solution {

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

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

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

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

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

2 Insertion sort

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

class Solution {

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

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

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

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

            prev = prev.next;
        }
    }
}

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

3 Mergesort

Divide and conquer. Use top-down mergesort.

class Solution {

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

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

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

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

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

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

        return sentinel.next;
    }
}

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

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

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

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

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

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

#8 · 2023-11-13

玉米🌽

学“完”是不可能了，但是学得够用几天就行。今天看了一天 C# 语法特性，快要接近疯狂了 😫。

#9 · 2023-11-13

全部学透感觉有点难了，鱼鱼的 DS 和 Algorithm 都是跟着泥交的课刷 leetcode 学的，所以 61a 结束之后现在正在 61c 里艰难爬行（x

mod #10 · 2023-11-13

TsuinoSora

支持😤

#11 · 2023-11-13

TsuinoSora

已经私戳你了
也不是什么成熟的群，现在挺冷的，好多大一小朋友并不知道怎么刷课。
作为群主感觉有点失败，所以要引入外部力量早日帮群 u 们破除内卷观念 😗
顺带捞一个刷 pa 和 081 的搭子

#12 · 2023-11-13

东川路第二小绫波

戳戳我好吗 🥺

mod #13 · 2023-11-13

东川路第二小绫波

求戳 🥰

#14 · 2023-11-13

Risc_lt

学 61c 要写 c 和 asm 了，然而泥交的程序设计基础和数据结构全是用 c 教的，已经品尝够多了

#15 · 2023-11-13

c 不行，学 c 不如学 go，学 c++ 不如学 rust

#16 · 2023-11-13

东川路第二小绫波

求戳😘

mod #18 · 2023-11-13

呜，什么时候能看到有同学一起刷 GAMES 课啊 😭

mod #20 · 2023-11-13

东川路第二小绫波

戳戳🐭🐭

mod #21 · 2023-11-13

uika_winwing

hxd 用的是哪本书 👁️对我个人来说，看书之后立刻上手确实比网课效率高一点 🤗

#22 · 2023-11-13

主治医师李大华

书就是贴子标题那本啰，在有一楼还发了几张内容的照片

#23 · 2023-11-13

greyishsong

GAMES 有什么 prerequisites 呢

#24 · 2023-11-13

Post #19

被 pa 挤压了生存空间（雾）
这 pa 该死的耗时间
抽机会刷 games 吧，反正寒假之前要刷掉

#25 · 2023-11-13

楼里面几个都戳了
入群答案直接看我现在 id 也行

mod #26 · 2023-11-14

uika_winwing

GAMES 课程有很多，基本上 10x 是基础，20x 是进阶。

101 入门，只需要微积分、线性代数和 C++ 语法
102 几何基础，最好会一些数值方法/计算几何/微分几何，不会的话现学现用也行
103 物理模拟，需要对大学物理有一定理解
104 游戏引擎构建，需要一定的 C++ 工程能力和一个（好几个？）强大的肝
105 角色动画，不了解但应该不会比 101 的要求高很多，可能要求一些刚体运动学
106 现代渲染管线，基本上是从头开始教所以大致看过 101 就够了
201 物理引擎实战，提升自 103，我不是搞物理模拟的所以不了解
202 高质量实时渲染，提升自 101，要求对硬件图形 API、多线程有一定的理解
203 三维重建，以 102 为基础但不是对应关系

30x 和 40x 刚放出没多久，好像也不能算入门课了，我就不往这儿放了 🤣

mod #28 · 2023-11-14

Post #27

不懂学习的鲸鱼，post:27, topic:7184, username:Risc_lt:

如果以后工作不打算往游戏方向靠感觉边际价值就不太高了

很多朋友都会觉得 Graphics 只和游戏强相关，但其实完全不是这样……就工作来说，除了游戏以外还包括：

视频和动画三维特效，比如字节一直在招聘有图形学背景的人去抖音核心部门做视频特效
CAD/CAM/CAE，比如 Autodesk 这样的外企或者中望这样的国内企业，又或者上海有一些做 3D 打印的企业对图形学背景也有很强的需求
动画和影视，目前为止主要是国外（美国）有条件，比如皮克斯、迪士尼都有极强的图形学需求和实力，国内这方面还很菜，刚刚开始有一点（比如负责流浪地球的图形特效的那个公司）
SLAM 和三维重建，比如各种做文物/城市数字化、GIS、自动驾驶和导航的公司，这就属于比较散碎的需求了，但也不少

国内这些方向搞图形的企业，如果说和互联网/游戏比高薪那确实是比不过的，但也不算差，毕竟不是每个人都有互联网大厂 SP offer 的，其他条件那就得具体对比了。国外像 NVIDIA、Autodesk、迪士尼这些待遇应该是不输互联网的，不过难度也都很高。

如果想搞学术，现在除了经典图形之外 3D Vision 和 Vision for Graphics 也算是相当热门，因为门槛比纯 2D CV 要高不少所以处在竞争激烈但还没白热化的阶段。

mod #30 · 2023-11-14

顺便推一下我们自己的实验框架 🤣 自认为比 GAMES 101 的实验更灵活而且有意思（通过大量的支撑代码，我们的实验完成后支持加载和渲染任何模型，101 的实验效果都是完全固定的）。目前我们的框架可以替代一部分 101 和一部分 102 的实验，详情可以看看交大門的 计算机图形学 板块。

#31 · 2023-11-14

greyishsong

想问问现在有完整的课程网站或者主页吗 🥰
或者考虑建一个吗
又或者视频上传到 b 站之类
我也感觉 games 系列的框架代码设计得并不能说很好（大雾）

#32 · 2023-11-15

可以考虑拿这个模板做一个：

CS 182: Deep Learning

mod #33 · 2023-11-15

东川路第二小绫波

今年设计新的实验框架花费了我们四个月时间，开课之后各种修复和疑难解决也花了不少精力，所以没做课程主页。

目前我打算后半学期开始筹划正式的课程主页和一些宣传材料，开始早晚取决于教学、科研和其他杂务占用的时间多少，毕竟现在已经很忙了。

不过我们并不是自编教材，而课件基本上是我们所采用教材附带的，我们只有使用权而没有发行权，所以不会在非校内平台上公开课件（这不是安全问题，而是合规问题）。之后的课程主页上也会以公开实验为主。实验文档完全是我们自己写的，不存在这个问题，所以文档是按 CC BY-NC-SA 4.0 协议发布。其实可以看 GAMES 101 用我们的框架 🤣 因为我们的渲染部分有很多代码是移植自 101 作业的。

另外我们终究是一门校内课程，框架又是开源的，不会禁止大家自己 fork 自己填内容。为了避免网上乱传的答案太多影响校内教学，之后主页上公开的实验文档可能会落后于自用版本（就像 CMU 15/462 一样）。如果依然和交大門合作的话，門上还是会更新最新的实验文档。

mod #34 · 2023-11-16

CS61B 刷了过半了，谈谈体会：

CS61B 可分为两部分：

Java 语言及面向对象（其实面向对象在 61A 就讲过，61A 讲的面向对象知识已经覆盖了我校软件工程专业课：面向对象程序设计方法）
数据结构与算法 （至少对我校软件工程专业的数据结构与算法课实现了全覆盖，超覆盖）

前者在 sp18 学习就够了，并且 sp18 的官网提供有 textbook 和配套视频

后者我发现官网没提供 textbook，只有上课录屏的视频。所以在学习后半部分时可以去 fa23 ，也就是现在正在上的学期，这里提供有 textbook 和小段小段的视频，还有更详细的课后练习及答案。另外这个学期的数据结构讲的更多更深，比如 Hashing 在 sp18 只讲了一个课时，在 fa23 就讲了两个课时，内容也更深入。
但是 fa23 的评测没有公开，所以可以在 fa23 学完之后到 sp18 做对应的 HW，lab 等，sp18 的 Gradescope 课程码是公开的，ddl 还有 76 年。

mod #35 · 2023-11-16

还在写 21sp 的 lab2，是关于 junit 类和 debug 的知识，但是还卡在 hidden test 不知道怎么办😣

mod #36 · 2023-11-18

TsuinoSora

18sp 前半部分的 textbook 在哪里？是指 slides 那些 app 吗

mod #37 · 2023-11-19

主治医师李大华

不是，是 Reading 部分

#38 · 2023-11-19

东川路第二小绫波

求戳 +1

mod #39 · 2023-11-19

给自己引下：

Bilibili

【CS61B汉化】七海讲数据结构-二叉搜索树【七海Nana7mi】

视频说明：课程内容基于 CS61B-sp18 与 CS61B-fa23，可以理解为课程的汉化视频。 AI 语音模型来源 BiliBili 用户 @Xz乔希，Ta 的视频【AI七海】在线一键语音生成🦈 因本人也在学习中，有错误敬请指出。参考资源： https://cs61b-2.gitbook.io/cs61b-textbook/ https://sp18.datastructur.es/ https://fa23.datastructur.es/ https://oi-wiki.org/ https://github.com/fishaudio/Bert-VITS2 https://www.modelscope.cn/studios/xzjosh/Bert-VITS2 视频内容相关： “指针” 一词可和 “引用” 等意交换二叉搜索树实现代码： algs4.cs.princeton.edu/32bst/BST.java.html 视频中有一处口误，已在字幕更改七海Nana7mi直播间：https://live.bilibili.com/21452505 课件，字幕仓库：github.com/Hhankyangg/NanamiDS

#40 · 2023-11-19

TsuinoSora

啊？这个 up 是你？🥵
可太眼熟了

mod #41 · 2023-11-19

东川路第二小绫波

草确实是我（

#42 · 2023-11-19

网红是吧

mod #43 · 2023-11-19

Anonymous Coward Old

不到 100 粉丝能叫网红？

mod #44 · 2023-11-19

TsuinoSora

鼠鼠速速去灌注了 😀 😋 🤗

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

mod #45 · 2023-11-19

TsuinoSora

华小科是吧 👁️

mod #46 · 2023-11-19

主治医师李大华

去年看华小科入脑了，她毕业后很长一段时间都很心痛。现在更是时不时看华小科以前的直播以泪洗面。

mod #47 · 2023-11-19

TsuinoSora

原来是真爱粉吗🤔

#48 · 2023-11-20

TsuinoSora

原来是你小子干的好事啊

mod #49 · 2023-11-20

TsuinoSora

更新：没想到真有人看，粉丝也刚刚破一百了（

#50 · 2023-11-22

TsuinoSora

周一早八的时候刷到了，那时候还只有 1w 播放，下午再一看已经 4w+ 了
当时还点进了主页，而且认出来是你了🤣

Dear Eternity

mod #51 · 2023-11-22

TsuinoSora

我在动漫群看见你的视频了 🤣

mod #52 · 2023-11-23

TsuinoSora

今天得开始更新下一期了，大伙等好久了