首页
学习
活动
专区
工具
TVP
发布

数据结构练习题解答

换到vmatrix后是不是很高兴呢,而且还没有了讨人厌的memory check,开心不开心?

这周共有5题,大概做了30多分钟吧,还是挺有趣的。这次就不直接放代码了,每题简单说一下。

第一题矩阵:

这题没说清楚,应该是方阵。做法就是找到首字母后dfs,每次看看四周有没有下一个字母,没有就是找不到,有就继续dfs。复杂度不明(题目没给数据范围)

第二题地铁:

最小生成树,用Kruskal算法,先把边按权值排序,每次取出当前权值最小的边,拿出来并查集,取出n-1条边后说明树已经建好,算法结束。复杂度O(n^2logn)

第三题迷宫:

从左上角直接bfs,能到右下角就输出答案,不行就输出0。复杂度O(n^2)

第四题插排:

和插排几乎没有关系,只要记录此时最大的数即可,新进来的数如果不是最大,时间就+5。复杂度O(n)

第五题射击:

题目没说数据范围,不过应该不会太大,直接Catalan数打表。复杂度O(1)

  • 发表于:
  • 原文链接http://kuaibao.qq.com/s/20180103G0MOI800?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码

添加站长 进交流群

领取专属 10元无门槛券

私享最新 技术干货

扫码加入开发者社群
领券