数据结构练习题解答

换到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

相关快讯

扫码关注云+社区