吃橙子的鸭子 - 个人主页动态

2024-08-28 13:31

已编辑

134. 加油站 如果从 i 开始 到 j 有和小于 0，则 i 和 j 中所有节点都不能作为起始点。如果整个 list 的和大于 0 那必然可以分成一部分小于 0 一部分大于 0 的两部分，也就是有解。 135. 分发糖果 先都看左边，再都看右边860.柠檬水找零 优先用 10 块的 406.根据身高重建队列 身高从大到小排序，然后考虑把小一点的数插入到大的数前面，这样不影响大数的排列（符合比大数还大的数目规则）记录一下 python insert 的语法 res.insert(people[i][1],people[i])

0 点赞评论收藏

2024-08-27 09:45

National University of Singapore 前端工程师

day28|贪心

122.买卖股票的最佳时机II 贪心，有利润差可以赚就加入到最终的值，如果后续发现后续继续增长，继续加到利润差里面。 55. 跳跃游戏 顺序遍历数组，每次更新可以跳到的最远位置 45.跳跃游戏II 顺序遍历数组，每次更新可以跳到的最远位置。 当当前位置是上一轮跳到的最远位置，增加Step 1005.K次取反后最大化的数组和 按照 abs 排序，尽可能翻转最大的负数。 如果数组全部都变为正数则翻转 abs 最小的数

0 点赞评论收藏

2024-08-26 20:59

National University of Singapore 前端工程师

day27|贪心

三道题目 发饼干，最长子序和，摆动序列。主要是摆动序列。 如果发现有摆动的情况直接加入即可。 如果是同向的则要更新上一次的差值，让摆动的可能性尽可能大一些。

0 点赞评论收藏

2024-08-25 17:39

National University of Singapore 前端工程师

day25|排列回溯

三道题目非递减子序列这个用 used 数组，避免同一个数添加到 path 数组里面多次全排列因为是所有可能的全排列， 所以每个数 都从头开始遍历。 同样用used 数组避免一个数添加多次全排列 2由于出现了重复的树，为了保证(a1,a2) 和(a2,a1) 只有一种排序（这里的a1和 a2 数值相同，只是说明遍历过程的两种情况），我们需要规定遍历时候的一个顺序。我们对原数组进行一个排序。 排序完之后因为不是组合所以必须从头开始遍历。 这样我们就无法利用对原数组排序后来避免重复的情况。 一个简单的方法就是如果 a1 已经遍历过了，那么我们就自动跳过 a2 的从头遍历。 显然此时就是a1 的 us...

0 点赞评论收藏

2024-08-23 14:50

National University of Singapore 前端工程师

day24|回溯 2

子集这题和之前组合的类似。 只是添加到最终 res 的条件不一样，只要有存在就可以添加。子集 2这里和子集的区别主要是会出现重复的数字。 由于我们求得是组合而不是排序，所以我们会单向遍历数组来避免出现重复的情况。 由于可能会有重复的数字，两个重复数字在原有的情况是会重叠的。解决方法就是对数组进行一个排序，如果该层有相同的元素就跳过复原 IP 地址首先写单位的 IP 组成元素的有效算法相当于四层树，依次遍历。 四层用完的时候判断有效性

0 点赞评论收藏

2024-08-22 15:09

已编辑

National University of Singapore 前端工程师

day23| 回溯

三道题目 组合组合这道题和之前的类似，因为可以是重复的，所以起始点从自己开始组合之和 2组合之和这题，给的 list 里面存在重复的数字。 所以在给下一级进行遍历的时候，如果这一层取了相同的数字就会出现重复的情况，这里用 used 排除这样的情况。 同时仅仅在一层里面进行去重的情况是不够的，因为数字不是有序的，可能会出现在下一级的时候使用了之前已经用过的数字，为了避免这样的情况，我们对数字进行一个排序，这样可以保证后面的数字式觉得不会和前面的数字重复了。 组合没有进行排序的原因是因为数字是不重复的，不用考虑重复情况的影响分割回文子串有的类似于遍历二叉树，截取一段回文串，剩下的一段递归调用。 这...

0 点赞评论收藏

2024-08-21 20:53

National University of Singapore 前端工程师

day22| 回溯算法

三道题目 组合 组合之和 和电话号码组合之和和组合异曲同工。大概逻辑就是首先明确组合和排序的区别。 在组合里面我们要确保不能有重复的序列我们保持整体序列是有序的，这样就避免了在遍历的过程中出现重复的状况假设我们输入一个 cur 那么我们就遍历所有比 cur 大的数在代码中就相当于while last<=n:这里的遍历 def dfs(path): if len(path)==k: res.append(path[:]) return last = path[-1] if path else 0 # 剪枝 if len(p...

0 点赞评论收藏

2024-08-20 20:14

National University of Singapore 前端工程师

0 点赞评论收藏

2024-08-19 21:16

National University of Singapore 前端工程师

day 20| BST的插入删除和最深层公共祖先

全部都回顾一下吧BST 的最深公共祖先这里根据 BST 的定义，对于cur，左边的节点都小于他。 从上往下遍历，给定一个值，如果该值在两个节点值之间则必然是他们的公共祖先。 （在向下遍历的话显然会被分成两颗树，向上的话就不是最深的了）所以用 BFS 可以直接坐。删除BST 节点这里稍微卡顿了一下。对于要删除的节点有左右子节点的情况找到右子树的最左侧节点 将 root 的左子树挂到最左侧节点的左侧返回root 的右节点写的过程中我老是想找到 root 的最左侧节点，然后替代原来的 root 节点。 导致的结果就是可能这个节点就是 root 的右节点，循环引用，然后时间超时。 必须要考虑一些边缘情...

0 点赞评论收藏

2024-08-17 21:45

已编辑

National University of Singapore 前端工程师

JAVA 八股文结束

打卡了四十天，给自己写个句号。其实中间一段时间已经打算不攻克 JAVA 的，不过想着后续面国企的时候可能会面到相关的内容，索性就继续坚持下去了。虽然说是八股，但其实很多都是满基础的内容，也算是给自己回顾了一次。顺便也发现录音的时候自己经常会以嗯开头。 其实用录音来检测是一个蛮好的方式，后续无论是报告还是和领导闲聊沟通，如果不能把脑子里想的流畅的表达出来会变得事倍功半的。写作也是这样的， 说话和写作都是自己思考的一部分。 在大脑里不断的process 不输出 那么就永远不会是学习成果的一部分。 甚至有时候会形成混沌。 任何内容都要以输出作为目标，与大家共勉。后续的一个月打算以做项目为主，先混熟一...

0 点赞评论收藏

2024-08-17 21:38

National University of Singapore 前端工程师

day18| 二叉树

三道题目 众数，最小差和公共祖先。众数和最小差的逻辑类似，都是利用 BFS 的中序遍历是有序的，因此在遍历过程中可以利用有序的特性减少复杂度。以最小差为例 # 二叉树 中序是有序的 我们在中序查找每个最小差值即可 while cur or stack: while cur: stack.append(cur) cur=cur.left cur = stack.pop() if pre: mindif...

0 点赞评论收藏

2024-08-16 22:08

National University of Singapore 前端工程师

day17|二叉树| python的变量范围导致的bug?

今天四道题目 654.最大二叉树 617.合并二叉树 700.二叉搜索树中的搜索 98.验证二叉搜索树 除了验证二叉搜索树其他都一次过。二叉搜索树这题首先是原理部分中序遍历的顺序是有序的 (ASC)然后简单的做法是遍历一次，检查顺序是否有序。我在做的时候用 py 递归进行遍历，然后每次插入遍历数组前检查是否有序，如果是没序的话提前退出，做一个减枝的操作。但是 python 里面递归函数栈对全局变量的依赖好像不会变（我改了全局的变量，但是过去递归调用的函数里面的变量没有改变）。 应该是这个原因，调试半天没有跳出来? 最后还是硬暴力的遍历了一遍中序的结构。希望有人看到能指点一下。 d...

0 点赞评论收藏

2024-08-15 21:16

National University of Singapore 前端工程师

day16| 中后序二叉树和DFS

今天三道题中后序构建二叉树最下最左的节点DFS 获取 root->leaf 的路径然后基本一次过,卡的点有DFS 新增 path 的时候直接把 append 表达式放到参数里面了 ， 但append 返回的不是数组最小最左节点没有写递归的写法，看了下解析递归记录深度，先递归左节点的话，相同深度，左侧肯定能先遍历到。

0 点赞评论收藏

2024-08-14 20:34

National University of Singapore 前端工程师

day15|二叉树

0 点赞评论收藏

2024-08-13 20:07

National University of Singapore 前端工程师

day14 | 二叉树

今天四道题 翻转，对称，max深度和 min 深度基本都一次过。 求最小深度的时候有点卡顿，记录一下。主要问题就是是叶子结点的，我们的递归方程如下 return min(getDepth(root.left),getDepth(root.right))+1 如果左边是一个None 节点的话，我们是返回inf还是返回0比较合适呢?如果是 inf 的话，那么最刚开始，空节点进入的时候 leetcode 要求我们返回的是 0如果返回是 0 的话，那么如果该节点不是叶子结点，那么他的最小深度就变成是 1了我这里单纯的把最刚开始进入的和后面具体计算的这两种情况分开来了。完整代码如下 def mi...

0 点赞评论收藏

创作者周榜

关注他的用户也关注了：