何牧的工作日志
-
2021/1/29
刷题
日期 题目 思路或总结 2021/1/29 1631. 最小体力消耗路径 并查集,将所有边按权值排序,从小边往上加,加到起点和终点连通为止,此时这条边的权值便是答案 内网4G
完成数据上传接口的编写和优化
-
@holdice 牧宝太强了,妈妈爱了
-
2021/1/30
刷题
日期 题目 思路或总结 2021/1/30 778. 水位上升的泳池中游泳 并查集,将水池中各个方格看作点,两点之间的边为二者的平台高度的较大者,那么问题就简单了,将边按权值从小到大的顺序加入并查集,判断起点和终点是否相连,只要相连,此时加入的边长就是这条路径的最长边长,也就是所需等待的时间 这里记录一个朋友打CF看到的题目,题目意思大概是这样的:
假设有N个点,N个点之间被N-1条有向边连接成链状,假设你从这N个点的每个点出发,你只能顺着边的方向走,并且每走一步所有边反向。
问从每个点出发,能达到的最大点数
输入示例:
N = 7
LLRLRL
N范围3e5,也就是最高接受n logn的时间复杂度解法:分层图 + 并查集
由于边的情况只会有两种状态,初始状态和所有边反向后的状态,那么我们可以建立另外一张所有边反向的链状图,那么从一个点出发走到相邻的点的这一过程直接走到相对的那张图即可,这里可能不太好表述,来张图:
假设我从2出发,那么向右走一步,到达的不再是3,而是10,再往右走就到达4,并且很容易看出来,这样斜着走过去是可以再走回来的,所以相当于图中红色标注的点都互相可到达,这种连通性就可以用并查集很好的解决,将所有能走的边的两点加入并查集合并后,通过连通分量就可以算出这个连通块的点数,即可算出到达的点数。
那么对于每个点,只要遍历一遍初始图上的所有点,就可以算出每个点所能走到的点的数量。
(今天出去玩了一天,啥也没干。。。
-
@holdice 摸~
-
2021/1/31
刷题
日期 题目 思路或总结 2021/1/31 839. 相似字符串组 并查集,俩俩相似即可的特性特别像连通图,所以通过遍历每一对字符串,判断是否相似,相似则加入并查集合并,最后并查集的连通分量就是答案 内网4G项目
完成了获取缩略数据的接口和获取完整数据的接口,至此应该大体的获取数据和上传数据功能已初步完成,接下来应该就是整理文档和进一步测试优化工作了
-
-
-
-
2021/2/3
刷题
日期 题目 思路或总结 2021/2/3 480. 滑动窗口中位数 自建满足题意地数据结构,双堆维护+延迟删除 自闭症儿童助教平台 大创
组织开会讨论方向
找工作进度
蚂蚁金服二面结束,感觉问的都挺宽泛的, 没有一面问的那么细,但都挺基础的,最后也无算法题。
-
-
-
2021/2/6
刷题
日期 题目 思路或总结 2021/2/6 1423. 可获得的最大点数 找出n-k长度的最小合连续子串,其余就是合最大子串 内网4G
修复项目打包成jar包后application.yml无效的问题
部署项目,整理接口文档
-
-
2021/2/8
刷题
日期 题目 思路或总结 2021/2/8 162. 寻找峰值 二分递归,根据nums[i]和nums[i+1]确定往左递归还是往右 2021/2/8 978. 最长湍流子数组 滑动窗口 随便捣鼓
配置HTTPS图床,测试hugo的shortcodes,真有趣
-
2021/2/9
刷题
日期 题目 思路或总结 2021/2/9 992. K 个不同整数的子数组 「最多存在 K
个不同整数的子区间的个数」与「最多存在K-1
个不同整数的子区间的个数」的差恰好等于「恰好存在K
个不同整数的子区间的个数」摸~
-
-
2021/2/11
刷题
日期 题目 思路或总结 2021/2/11 703. 数据流中的第 K 大元素 维护一个固定长度的优先队列,保证队列首一直是第K大的元素 回乡下了,时隔好几年又放了烟花,好耶!
-
-
-
2021/2/13
刷题
日期 题目 思路或总结 2021/2/13 448. 找到所有数组中消失的数字 原地修改,最后遍历找出结果 2021/2/13 剑指 Offer 33. 二叉搜索树的后序遍历序列 递归解决 昨晚总结了一下2020,希望2021能走得更远吧!