何牧的工作日志
-
-
2021/1/25
刷题
日期 题目 思路或总结 2021/1/25 959. 由斜杠划分区域 并查集 or DFS or BFS 烟草系统
今天一天都在和烟草甲方处理测试服务器部署的问题,由于要部署微信小程序,必须要部署HTTPS,折腾了半天用自己域名的子域名申了个免费的SSL证书部署了,完整走了一编HTTPS的部署流程,又学到了许多
-
-
2021/1/26
刷题
日期 题目 思路或总结 2021/1/26 1128. 等价多米诺骨牌对的数量 将二维化作一维然后遍历数组 烟草系统
邓超反应历史查询有点慢且容易卡住的问题,上皖南服务器看了看,8个G的表,能不慢吗。。。900W条数据,一次查就可能查出来七八万。最后写脚本把无效数据删了一些,大概去了200w左右,等那边的下一步反馈把。
找工作进度
整完烟草的琐事就开始复习数据结构基础知识,对着java.util包,反键生成diagram,然后一个个对着看,算是初步看完总结了几种经典的数据结构的底层实现和相关特性。感觉多线程和锁这块还得下狠功夫。
种子杯重构
明天一定搞完部署!!,立个FLAG!
-
@holdice 已阅
-
2021/1/27
刷题
日期 题目 思路或总结 2021/1/27 1579. 保证图可完全遍历 并查集,最小生成树分别构建,先处理公共边,再处理独占边 烟草系统
白天依旧是被烟草拿下的一天,历史查询出现了很慢甚至卡死的现象,理论上查询速度不应该这么慢或者卡死,最后发现是django的QuerySet写法有点问题,等有时间再仔细看看吧,关键是bug修好了!
种子杯重构
修完烟草的bug奖励了自己几把酒馆战棋(3连鸡),打完才想起来昨天还立了FLAG,规范了error code,晚上和郭老师讨论了一波排行榜这种变数比较大的接口的规范问题并根据规范实现这个接口。(再也不随便立FLAG了
-
-
2021/1/28
刷题
日期 题目 思路或总结 2021/1/28 724. 寻找数组的中心索引 遍历,注意技巧避免求和次数重复,降低效率 种子杯重构
完成排行榜接口的编写和测试,以及其他重构工作,整理接口文档,部署
内网4G项目
完成第一版数据库设计
-
@holdice 做得怎么样了,种子杯
-
@pengzc 后端这边暂时没啥可做的了,再做可能就是进一步优化和一些注释的完善。已经完成的模块有用户模块、队伍模块、还有一个是排行榜接口,便于首页展示。提交和判分还没写,如果要写demo的话到时候可能得开个会商量下接口(但感觉现在写,到时候还得改。。。
-
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. 滑动窗口中位数 自建满足题意地数据结构,双堆维护+延迟删除 自闭症儿童助教平台 大创
组织开会讨论方向
找工作进度
蚂蚁金服二面结束,感觉问的都挺宽泛的, 没有一面问的那么细,但都挺基础的,最后也无算法题。
-