niyongsheng / algorithmicproblem

有意思的算法问题</coding>

AlgorithmicProblem

记录些有意思的算法问题。
Some interesting algorithm problems.

problem_1

2D接雨滴

给定n个非负整数表示每个宽度单位为1的方块的高度图，计算按此排列的方块，下雨之后能接多少雨水。

代码实现

raindrop_2d.c

raindrop_2d.java

• 解法：最小堆
• 时间复杂度：O(n)
• 空间复杂度：O(n)

problem_2

3D接雨滴

代码实现

raindrop_3d.c

JAVA

raindrop_3d.java

初步尝试打算用2d的方法递推3d情况，发现在某些情况下会失效❌；

• 解法：最小堆
• 时间复杂度：O(MN)
• 空间复杂度：O(MN)
  • 使用优先队列作为辅助数据结构，其空间复杂度取决于输入的大小和队列中元素的数量，但由于最多只存储一行或一列的元素，因此可以忽略不计。

SurfaceAreaDFS.java

通过最大高度构建分层空间，每层进行深度优先搜索遍历出封闭区域；
超大矩阵下空间占用太大

• 解法：DFS
• 时间复杂度：
• 空间复杂度：

OptimizeSurfaceAreaDFS.java

移除分层空间三维数组(优化边界情况)，直接构建每层进行深度优先搜索遍历出封闭区域
超大矩阵下时间开销太大

• 解法：DFS
• 时间复杂度：
• 空间复杂度：

ParallelOptimizeSurfaceAreaDFS.java

多线程逐层进行深度优先搜索遍历出封闭区域；
leetcode好像不认可多线程方式，执行超时(也可能主要耗时仍发生在构建分层矩阵上)

• 解法：DFS
• 时间复杂度：
• 空间复杂度：

Letcode.java

leetcode官方广度优先搜索解法:

• 解法：BFS
• 时间复杂度：O(M^2 * N^2)
• 空间复杂度：O(M*N)

Expansion

《Hello 算法》

Krahets 笔面试精选 88 题

Contact Me

• E-mail: [email protected]
• Weibo: @Ni永胜