BYOW个人记录
codex辅助，差不多一天半搞完了，统计说是10h，不知道准不准 从开始写 BYOW 到最后收尾，感觉这个项目比前面的 proj 更像是在真正做一个小型游戏系统。最后实现出来的版本大致包括：根据 seed 确定性生成随机世界，房间之间用 MST 保证连通，再额外加一些边让地图不那么像树；玩家可以通过 WASD 移动，:Q 保存，L 读取，R 回放，M 返回菜单；HUD 会显示鼠标所在 tile 的描述和当前收集进度；地图里有多个 light source，玩家走到灯上就会吃掉它，目标是吃完所有灯。 比较满意的是后期把结构拆开了：Engine 主要负责菜单、输入、渲染循环和 save/load；WorldGenerator 专门负责地图生成；GameState 负责玩家位置、移动、灯光、视野和历史输入。这样比一开始全部堆在 Engine 里舒服很多。灯光系统用了两份世界：一份是真实逻辑地图 world，一份是经过光照计算后的 lightedWorld。有限视野默认开启，用的是玩家周围的菱形范围；灯光则根据光源距离和墙体遮挡决定地板显示成哪一档蓝色亮度。 我的个人实现：CS61B p...
gitlet个人记录
从开始动手到完工约16h 跨度4days，这几天基本上除了上课就是写这个 当然很多东西问了ai,把我的copilot额度差点干完了 开始前看完spec人都是懵的，而且英语太差很多具体意思扫一眼根本看不懂，参考了别人的persistence再仔细钻研(问ai)后脑子才慢慢有个框架。感觉最难的部分就是起步阶段，起步啥都没有，想写点什么就会发现它的依赖项还没写，去写依赖项时又发现它依赖别的，或又依赖回刚才的东西，会比较困难一点。而且debug起来比较麻烦，反正我是纯通过test结果自己找bug，找得挺痛苦的。现在回看之前所有的project都跟过家家一样，gitlet的skeleton代码简直就是一具空壳，you have to design almost everything by youself. 我的个人实现： CS61B proj2 Gitlet 一些记录下来的bug 1 in Commit.java 12345678910111213/** Update the stage area to a new commit. */ public void clearStage() ...
接雨水
42. 接雨水 - 力扣（LeetCode） 单调栈 初实现： 123456789101112131415161718192021222324252627int trap(vector<int>& height) { int res = 0, pre = 0; stack<int> st; for (int i = 0; i < height.size(); i++) { if (height[i] >= pre) { while (!st.empty()) { res += pre - st.top(); st.pop(); } pre = height[i]; st.push(pre); continue; } if (height[i] &l...
高斯二项式系数
q-number: (下标qqq可以省略) [k]q=∑i=0k−1qi={1−qk1−q,q≠1k,q=1[k]_{q} = \sum_{i=0}^{k-1} q^{i}= \begin{cases} \frac{1-q^{k}}{1-q}, & q \neq 1 \\ k, & q = 1 \end{cases} [k]q=i=0∑k−1qi={1−q1−qk,k,q=1q=1 [n]q!=[1]q[2]q⋯[n]q[n]_{q}! = [1]_{q}[2]_{q}\cdots[n]_{q} [n]q!=[1]q[2]q⋯[n]q 高斯二项式系数: [mr]={[m]q![r]q![m−r]q!,r≤m0,r>m\begin{bmatrix} m \\ r \end{bmatrix}= \begin{cases} \frac{[m]_{q}!}{[r]_{q}![m-r]_{q}!}, & r\leq m \\ 0 , & r > m \end{cases} [mr]={[r]q![m−r]...
分糖果
135. 分发糖果 - 力扣（LeetCode） n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。 你需要按照以下要求，给这些孩子分发糖果： 每个孩子至少分配到 1 个糖果。 相邻两个孩子中，评分更高的那个会获得更多的糖果。 请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。 示例 1： 输入：ratings = [1,0,2] 输出：5 解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。 示例 2： 输入：**ratings = [1,2,2] 输出：4 解释：你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。 第三个孩子只得到 1 颗糖果，这满足题面中的两个条件。 提示： n == ratings.length 1 <= n <= 2 * 10^4 0 <= ratings[i] <= 2 * 10^4 标准的解法是前后两次遍历取最大，但这样会消耗O(n)O(n)O(n)的空间，这里给出一次遍历贪心算法的实现. 思路: 首先只考虑ratings不减的情况：若ratings...
Kadane算法
如果往事已成负担，那你需要扔掉过去重新开始 53. 最大子数组和 918. 环形子数组的最大和 题目描述 53.给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 子数组是数组中的一个连续部分。 示例 1： 输入nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。 示例 2： 输入：nums = [1] 输出：1 示例 3： 输入：nums = [5,4,-1,7,8] 输出：23 提示： 1 <= nums.length <= 10^5 -10^4 <= nums[i] <= 10^4 918.即为环形版的53. Kadane算法 Kadane算法是一种用于解决最大子数组和问题的动态规划算法。这类问题的目标是在给定数组中找到一个连续的子数组，使其元素之和最大（数组含有负数）。 算法的核心思想是通过迭代数组的每个元素，维护两个变量来跟踪局部最优解和全局最优解。 53. 这里我们需要维护两个变量pre与l...
摆动序列
题链 如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。 例如， [1,7,4,9,2,5] 是一个摆动序列，因为差值 (6,-3,5,-7,3) 是正负交替出现的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。 给定一个整数序列，返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。 示例 1: 输入: [1,7,4,9,2,5] 输出: 6 解释: 整个序列均为摆动序列。 示例 2: 输入: [1,17,5,10,13,15,10,5,16,8] 输出: 7 解释: 这个序列包含几个长度为 7 摆动序列，其中一个可为[1,17,10,13,10,16,8]。 示例 3: 输入: [1,2,3,4,5,6,7,8,9] 输出: 2 注意：输入序列中可能有相同的数字 贪心算法 思路： 首先，在尽...
组合总和II
题链40.组合总和II 给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字在每个组合中只能使用 一次 。 **注意：解集不能包含重复的组合。 ** 示例 1: 输入: candidates = [10,1,2,7,6,1,5], target = 8, 输出: [ [1,1,6], [1,2,5], [1,7], [2,6] ] 示例 2: 输入: candidates = [2,5,2,1,2], target = 5, 输出: [ [1,2,2], [5] ] 本题是一道较综合的题 主体为: 回溯 + 去重 以下给出两种去重思路: 1. used数组 首先将candidates进行排序方便去重 以candidates=[1,1,1,2,4],target=7为例 从第一个1开始：第一组结果[1,1,1,4] 第二组结果[1,2,4] 而从第二个1开始，便会有[1,2,4]的重复 以此，对于连续的数字，我们只需取第一个即可，后面的相...
Morris中序遍历
达到O(1)空间复杂度同时时间复杂度仍保持O(n)的算法 12345678910111213141516171819202122vector<int> inorderTraversal(TreeNode* root) { vector<int> res; TreeNode *pre = nullptr, *cur = root; while(cur) { if (cur->left) pre = cur->left; else { res.emplace_back(cur->val); cur = cur->right; continue; } while(pre->right && pre->right != cur) pre = pre->right; if (pre->right) ...
二叉树的非递归遍历
题目链接: 144. 二叉树的前序遍历 - 力扣（LeetCode） 94. 二叉树的中序遍历 - 力扣（LeetCode） 145. 二叉树的后序遍历 - 力扣（LeetCode） 普通迭代 由于后序遍历可通过左右颠倒的前序反转后得到，所以我们只用完成前序和中序两种。 (1)前序 思路： 指针从根节点开始：中节点加入数组，右节点入栈，指针移至左节点 重复上述过程直至结束(栈空+指针指空) 12345678910111213141516vector<int> preorderTraversal(TreeNode* root) { vector<int> res; stack<TreeNode*> st; TreeNode* p = root; while (p != nullptr || !st.empty()) { if (p == nullptr) { p = st.top(); st.pop(); } e...