由于是转码 也深知代码能力的重要性 但之前断断续续的刷总觉得没什么长进 今天痛定思痛 决定开一个帖子 用来记录我的刷题过程 以此监督自己 。
2023.5.15
今天练习了贪心思想 目前我觉得比较关键的点是 排序 与 搞清楚贪心的对象。
455没有什么好说的 435需要明白 我们需要贪边界最小 这样后续就可以容纳更多的区间 452射气球还是排序后 贪最小的边界.
406还是有些不太明白
2023.5.30
该死啊 中午电脑死机我直接重启 忘了 这篇博客还处在编辑状态 导致15号至今的刷题记录没了 无奈从头开始 这段时间先是学习了贪心思想 然后继续做算法思想的题时 猛然发觉自己关于数据结构的题已经记忆模糊了 于是直接找到跟着刷题的目录里的数据结构篇章 从链表开始刷 在做的时候 发现大佬的做法都是使用递归来解决 代码很优雅很简洁 我又去认真学习了递归 学习博客放这里 这篇博客写的十分好三道题套路解决递归问题 | lyl's blog
543 二叉树的直径 细节处自己考虑的不是很清楚
2023.6.1
昨天实验室研三师兄们回来了 去拍照 去听毕业答辩 去做课程作业 226翻转二叉树 用递归 但说实话 我虽然做出来 但对其中递归的步骤却是手推了一遍才明白过来 搞清楚你这个递归函数在干什么 我觉得有利于写出递归 617合并二叉树 在写每一级递归应该干什么的时候还是太过于瞻前顾后 递归应该只专注于当前
2023.6.3
昨日上课+谢师宴 喝多了 112 路径综合 还是使用递归 自己写的思路大致没问题 但细节上还是有欠缺 用例没全通过 437路径总和 没做出来 简单的想法是进行双重递归 第一重遍历所有节点 第二重在每一个节点上 当做根节点计算路径和 时间复杂度很高 难一点的做法是利用前缀和来做 很妙
2023.6.4
572 另一个树的子树 我的想法是使用两重递归来做 但没有写出来 看了题解与评论发现这道题还有更高深的方法 看懂了dfs+kmp的方法 但是没看懂第三种 101对称二叉树 想用递归解决 还是没能做出来 评论有一大哥说的很对还是没有深刻理解递归思想111二叉树最小深度 这道题之前用递归做过 又重新做了一遍 做出来了 还不错 看了题解发现可以用广度搜索 更简洁404 统计左叶子节点的和 将判断条件写的不对导致第一遍没做出来 看了评论进行修改
2023.6.6
昨日与导师讨论了论文 改了算法 在跑实验。
687最长同值路径 这道题还是利用递归来做 评论给出的分析很清晰 每一层递归 我们只需要判断左子树和右子树是否和当前节点相同 相同+1 利用静态变量始终保存最长路径 返回值是左右子树的加上当前节点的最大值 很清楚337 打家劫舍 很难 看了题解恍然大悟 用unordered_map来记录当前节点偷与不偷的值 返回最大的671二叉树中第二小的节点 由于题目设置 只需要找到第一个比根节点大的就可以 最小的一定是根节点
2023.6.7
637二叉树层平均值 使用层次遍历就可 513找树左下角的值 层次遍历+记录每一层最左边的值144 实现二叉树的前序遍历 我刚开始使用了递归 然后又用非递归方式重写了一遍 对于非递归方式没太掌握 继续学习一下 ps是chatgpt给出的代码有点高端 没看明白 换了种方式就懂了145后序遍历94中序遍历 都用了递归和非递归写 理解到 递归本质就是利用栈的特性 可以将递归转换为栈结构写出来
2023.6.8
669 修建二叉搜索树 一开始没想到递归 该死a 之前遍历惯了 一上来就想着利用层次遍历挑选节点然后重新组成bst 但这样做报错栈溢出 没找到原因 一看评论 递归真实又简单又好懂a 230二叉搜索树第k小节点 我直接中序遍历得到一个数组 属于笨办法了 高明一点的解法是每颗子树上的节点和k去对比 以此确定要找的点在左右子树哪一个里 递归解决 235二叉搜索树的最近公共祖先 当想明白 利用bst的性质 若两个点的值都小于当前root值 那么一定在root的左子树中 大于就在右子树中 若一大一小 则当前root即为最近祖先 想明白这个就立刻用递归能做出来 236 二叉树的最近公共祖先 做了之前那道 满脑子是递归 但找不到可递归的点 被上一道紧固思维了 看了评论才反映过来
2023.6.25
这段时间没有刷题 主要原因有三个 一是之前参加的一项比赛快截止了 我们参赛的东西还没做出来 加了一段时间的班 在搞比赛项目 二是论文写作写到实验部分 制表学习latex 画图等等一系列事情 三是和同学一起接了一个小程序开发 需要学一些东西
现在比赛项目交上去了 论文实验部分也写的差不多了 目前就剩小程序开发以及论文motivation的书写 想了想还是每一天花一些时间进行做题吧 明天重拾 加油
2023.6.26
108有序数组转换为二叉搜索树 题目不难就是长时间没写c++了 手有点生 好多东西模糊了比如 容器vector的长度是size还是lenth 109有序链表转换为二叉搜索树了 看到第一想法是链表转换为数组直接套用上一题 用链表的方法没想出来 看了评论 很经典 快慢指针找到链表中点 进行切割 当前节点为root 递归进行左右子树
2023.6.27
653两数之和 查看二叉搜索树里有无两个元素之和等于特定值的 感觉不难 但是没有做出来 用中序遍历得到一个升序数组后利用双指针就可 我陷入了牛角 一直想着它肯定要包含头结点 530求二叉搜索树的最小绝对值 照搬上一题做法 遍历得到数组然后再找 但是应该可以 用递归或者迭代来做 因为这个差值要么是当前节点减去左节点 要么是右节点减去当前节点 针对每一个节点都是这样的操作 但是没写 之后二刷可以试试 感觉关于在一个树里找什么值 都应该考虑树里的数据大小关系 组成一个数组来做 但这个做法比较浪费空间 501二叉搜索树里的众数 还是二叉搜索树的性质 但我是保存了数组然后再去遍历 费时费空间 看了题解 可以边遍历边用几个变量进行维护更新 很细节
2023.6.30
前两天没做是因为论文草稿就差introduction 和 related work 部分了 这两个部分至关重要 整理思路好就得立刻写 中断的话 又需要重新捋一遍 再加上每次写的差不多就到一起做小程序的时间了 导致没时间做 208实现Trie前缀树 想着很复杂 没有头绪 一看题解 瞬间觉得自己是煞笔 认真想应该可以做出来677 取巧做了 并没有使用前缀树特点
2023.7.1
树的篇章写完了 开始栈和队列 232利用栈实现队列 没什么好说的 一个输入栈一个输出栈225利用队列实现栈 155最小栈 本来使用了数组来维护最小值和次小值 结果发现并不合理 想着应该要使用两个栈来实现 看了评论 发现使用一个链表即可实现 很巧妙
2023.7.2
20有效的括号 我是用遍历字符串 遇到左括号就入栈 遇到右括号就将栈的第一个拿出对照 看了评论 发现还有更简洁的方法 739每日温度 使用了一个辅助栈将序号压入栈中 小于栈顶的序号都入栈 遇见大于的就挨个分配栈顶的序号
2023.7.3
503 下一个更大元素 这道题一上手就觉得熟悉 想了想和昨天做的每日温度如出一辙 都使用单调栈作为辅助 但做了半天总还是差一点 看了评论发现是判断关系没搞明白以及循环终止条件有点问题1两数之和 开了新模块 哈希表 结果回到了第一题 大多数人的LeetCode做得第一道就是第一题两数之和吧 看到我之前的回答（还是错的）有种梦一样的感觉 217存在重复元素 使用了unordered_map 看了评论发现使用set容器的唯一性再对比长度更简洁 594最长和谐子序列 我是采用了map容器 它的key是有序的 然后遍历一遍 若是key差值==1 则将他们的value相加 看了评论发现先排序使用双指针 类似滑动窗口就可以实现 省去了空间 很妙 128最长连续序列 题目要求时间复杂度需要O(n) 也就是不能sort 继而想到使用set容器去做 我的做法是遍历set 若是前后两者差值为1 用一个变量记录此时的序列长度 另一个维护序列长度最大值 看了评论 遍历set的方法比我巧妙
2023.7.4
242 有效的字母异位词 我被束缚住了 看到第一眼想到的就是利用map来做费空间费时间 看了评论只要将两者进行排序后看看相不相等就可 字符串就是另类vector可以将一些常用处理方法利用到上来
409最长回文串 简单题 我没做出来 利用了map但不知道怎样处理多个奇数的值 看了评论一老哥的解法 很妙
205同构字符串 我是用了一个map 但耗时长一些 题解用了两个map 耗时比我短一点
647回文子串 暴力解O(n^3) 看了眼官解 有O(n^2)是找回文中心点 然后向两边一一比对 还有使用dp的 但是dp思想还没认真学
2023.7.5
9 回文数 看了眼提交记录 是22年刚接触LeetCode 时做得 看了眼代码明显是cv上去的 重新做了一遍 有些细节问题没处理清楚 导致没通过全部用例 看了评论 发现还是网友妙a 反转一般的数跟前面剩的做对比就可 时间空间复杂度都很低
696计数二进制子串 个人感觉难度应该是med 看了评论才做出来 记录连续相同数字的个数 要是发生改变 就比较当前数字个数和上一个子串的长度 很妙
283移动0 我用了双指针来做 看了评论 高赞是也是双指针 但是比我巧妙很多 本来需要两个数组保存 现在通过双指针保存在一个数组里面
566重塑矩阵 我的做法属于暴力了 做了一半直接看题解了 很妙 学到了 将二维数组压扁为一维数组 , 所以 二维数组化为的一维数组中第x个元素 就可以又映射回去
那么我们现在可以实现由二维数组映射到一维数组再映射到二维数组 省去中间一步 直接两个二维数组进行映射
