📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 2443| 回复: 10
跳转到指定楼层
上一主题 下一主题
收起左侧

[Leetcode] 自由的码工

全局:

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
身处不断转印度的小公司,再不刷题,饭碗难保。突然感到,对于码工,想做到自由出入,一个重要的方法,就是要把题刷到纯熟。现在,感到题目刷的不熟,加上市场不繁荣,一直没有投简历,也一直在这个小公司,窝着。

先把最怕的部分,图,重新拾起来,主动学习,不断总结提炼,觉得比上课老师讲的,领悟的多了。(1). 图分三种表示:邻list, 邻matrix, 边list (2). 三种计算disjoint sets: 快查(记录root), 快并(记录父亲),ranked快并 (3). 三FS: DFS(stack), BFS(queue), WFS(PQ) (4). 二Top Sort: DFS(三状态+递减钟), BFS(记录零indegree) (5). 三PQ: MST(PQ边+快并), MST/Prim(PQ点点重+BFS),SSSP/Dijk(PQ距离+放松) (6). 三SSSP组成:初始化(起点0它无穷),紧张吗(三角关系),放松吧(娶小) (7). 三类SSSP:Ford(放松所有紧张边直到无紧张),BellmanFord(对所有边做点数-1次放松),BellmanFordDP(dp[i, v]: 对于点v, 从起点最多经过i 个边的最小距离)(8).三APSP之DP算法:BellmanFord(dp[u,v,l]: 用最多l边,从u到v最短路径;Kleene(dp[u,v,r]: 用最多r点,…);FloydWarshall(三重所有顶点循环,三点恰是三角,那就紧张吗放松吧。此算法容易记,容易懂,容易写)。

写了很多,不知道大家是否喜欢这个图总结。总结之总结:图核心就是DFS+BFS+WFS+DP。

把最怕的图过了,接着我把所有容易和中等题过了一遍,只是思考解法和看答案,实操较少。

最近实操DP题,有些感悟: DP首要寻找子问题, 子问题着眼点要放开思路,0…i, i…j是常有思路,一个常数c, 往往可以是一个着眼点, 可以是0…c, bit DP是一个典型, amount是常见题型, 引入其他变量,上图里面说了很多。再次,定义好dp[i][j]代表具体含义,这样能把混乱的思维定住。然后找转移关系,这一步充满挑战与技巧,完全背包就是一例;如果失败,表示子问题找的不对或着眼点不对,需要重新找,或者不能用DP。如果找到,考虑如何循环。都定了,考虑空间优化。

待续……

为了码工自由,加油努力中……

评分

参与人数 3大米 +5 收起 理由
zzzAALO + 1 赞一个
14417335 + 3 给你点个赞!
BZH + 1 赞一个

查看全部评分


上一篇:有没有人用Intellij刷题
下一篇:请教:Java为何stack被Deque代替

本帖被以下淘专辑推荐:

🔗
vincent_great 2024-7-31 03:55:54 | 只看该作者
全局:
最小生成树应该可以跳过。。。
回复

使用道具 举报

🔗
 楼主| 微信用户_2ey91 2024-7-31 04:19:26 来自APP | 只看该作者
全局:
vincent_great 发表于 2024-07-30 12:55:54
最小生成树应该可以跳过。。。
谢谢回复。能给一个原因吗?
回复

使用道具 举报

🔗
vincent_great 2024-7-31 04:23:39 | 只看该作者
全局:
微信用户_2ey91 发表于 2024-7-30 20:19
谢谢回复。能给一个原因吗?

leetcode上都没几道MST的题,面试遇到的应该更少。。。
回复

使用道具 举报

🔗
 楼主| 微信用户_2ey91 2024-7-31 04:36:18 来自APP | 只看该作者
全局:
vincent_great 发表于 2024-07-30 13:23:39
leetcode上都没几道MST的题,面试遇到的应该更少。。。
Got it. Thanks.
回复

使用道具 举报

🔗
ygmm 2024-8-21 01:22:25 | 只看该作者
全局:
还没刷到图,好奇你都刷了哪些图的题目啊领悟力很强,有没有leetcode上的list链接?
回复

使用道具 举报

🔗
ourgit 2024-8-21 08:16:00 | 只看该作者
全局:
刷题能自由?
回复

使用道具 举报

🔗
navy 2024-9-8 15:10:14 | 只看该作者
全局:
WFS(PQ) 这个W是啥意思?
感觉是用Priority Queue? 那不相当于Dijkstra吗?
回复

使用道具 举报

全局:
不明觉厉。想知道楼主近况
回复

使用道具 举报

🔗
 楼主| 微信用户_2ey91 2024-9-24 00:47:17 来自APP | 只看该作者
全局:
小亩_6c8e7a8 发表于 2024-09-23 09:28:36
不明觉厉。想知道楼主近况
把DP, mono stack中题目做了一遍,把几百高频题做了一遍。现在向hard题进军了……不知道你是否有指教?
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表