查看: 473| 回复: 20
收起左侧

算法小白努力刷题找实习

|只看干货
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (11)
 
 
0% (0)    👎

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

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

x
题量只有一百出头,今年感受到了寒气,要认真刷题了

上一篇:求C++项目帮助
下一篇:想学JavaScript和前端框架,求课程推荐。
 楼主| LeApplePear 2022-11-3 11:45:55 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (11)
 
 
0% (0)    👎
547
因为需要计算城市块个数,所以需要理清楚城市之间的链接关系。
- 基于graph theory,a path to b, b path to c。使用经典unionfind
- 同时使用另一个定理,设x为path上一点,path上其他任意一点都与连同

unionfind本质上是add,merge(union), find
unordered_map 既记录城市 也记录 连接关系
add:每次看到新城市,就add
merge:每次看到两点的connection,就看他们是否连同一个点(root),如果可以就在map上串联两点
find:在map内部,通过串联关系,查找是否连同一个点(root)

自此题目就在每个城市vector时add
每个vector内部的连接时merge
    merge内部需要find
回复

使用道具 举报

 楼主| LeApplePear 2022-11-7 06:28:36 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (11)
 
 
0% (0)    👎
1143
dp

因为需要求subsequence,所以要有dp来算区间最优解。
用2d vector 中 i,j 来分别存储text1,2的index(1-based),之所以1-based是为了防止index out of bounds
求出转换函数,得当两个来自text1,2的char不一样时,区间count为max(dp[j], dp[j-1])
当一样时,dp[j] = max(dp[j], dp[i-1][j-1] + 1);

最后进行压缩,把2d vector变成1d
advertisement
回复

使用道具 举报

 楼主| LeApplePear 2022-11-3 12:12:40 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (11)
 
 
0% (0)    👎
1926
走迷宫算步数,经典bfs

用vsisited 2d vector来避免回头路
用queue来存起始位置

只要queue不空就while
为保证每次处理最周边的位置,记录下queue size之后在里面for loop
每pop一个位置,check 是否道出口(在边界位置上),检测周边的位置(是否out of bounds,是否撞墙,是否走过)再enqueue
回复

使用道具 举报

 楼主| LeApplePear 2022-11-4 11:01:11 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (11)
 
 
0% (0)    👎
1162
bfs

每次grid碰到算最近、最远距离的就用dfs
queue起始点先enqueue所有island
bfs 直到empty
剩下distance-1 就是真实距离(一开始的island也被计算了距离)
回复

使用道具 举报

 楼主| LeApplePear 2022-11-4 11:10:51 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (11)
 
 
0% (0)    👎
1091 同上
不过这次direction vetor里存了八个方向
回复

使用道具 举报

 楼主| LeApplePear 2022-11-7 01:35:06 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (11)
 
 
0% (0)    👎
841
dfs

trace并且记录visited,如果最后全部visited 那就return true
回复

使用道具 举报

 楼主| LeApplePear 2022-11-7 01:36:17 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (11)
 
 
0% (0)    👎
本帖最后由 LeApplePear 于 2022-11-6 12:37 编辑

797
dfs,backtracking
同上,但这次多出一个2d vector存result,一个1d vector用来backtracking
回复

使用道具 举报

 楼主| LeApplePear 2022-11-7 01:38:07 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (11)
 
 
0% (0)    👎
542
bfs
记录距离的普遍用bfs
用一个2d vector grid记录result以及visited
回复

使用道具 举报

 楼主| LeApplePear 2022-11-7 12:40:53 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (11)
 
 
0% (0)    👎
547
定期复习
回复

使用道具 举报

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

本版积分规则

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