cur*_*rio 5 java algorithm union-find
我正在学习coursera上的算法，第一部分课程，并被困在第一个作业的奖励问题上。我已经提交了我的解决方案并获得了分数。这只是出于好奇。
反冲洗是交叉点在此图像中显示为完整（蓝色）。发生这种情况是因为我使用虚拟顶部和底部节点并连接它们下方/上方的行以满足复杂性要求；因此，将顶部连接到底部会使连接到底部的所有节点都连接到顶部。这个描述可能看起来不完整，所以我强烈建议阅读规格链接。
克服这个问题的一个解决方案是使用另一个 WeightedQuickUnion 对象并复制其中的网格而不包括底部虚拟节点。现在，此解决方案不满足评分者对奖金问题的内存要求（检查总内存 <= 11 n^2 + 128 n + 1024 字节）。我已经想到了一些解决方法（例如使用数组/堆栈来存储底行的开放站点），但所有这些方法都使用复杂度为 O(n) 的额外方法，而分配不允许这样做。根据赋值规范，除了构造函数之外，所有方法都应该有一个恒定的时间 + 对 union() 和 find() 的恒定调用次数。
您可以完全摆脱虚拟站点。
维护一个byte数组，其中第 i个元素存储WeightedQuickUnionUF对象中第 i个节点/站点的数据。
数组的每个元素将存储 3 位。
位操作在利用这个数组时会很方便。
打开以前阻止的站点时，请适当设置这些位。在执行两个站点的OR计算时，用先前根的数据更新新根的数据。union()
连接组件的状态由规范元素或该组件的根的数据来传达isFull()。percolates()
在该open()方法中，打开先前被阻止的站点后，检查更新的连接组件是否导致系统渗透并存储结果。在方法中返回这个存储的值percolates()。
您会发现此 pdf很有用。在文档中搜索“反洗”。
ps：我已经使用此解决方案获得了奖励积分。
干杯!
小智 5
我使用 int[] 转换为字节来跟踪每个站点的状态：
每次调用 open() 时，在调用 wquf.union(adjacent,site) 之前，我都会检索站点 (rootPrevious) 及其相邻站点 (rootAdjacent) 的规范元素。
然后我再次检索了站点 wquf.find(site) 的 newRoot （因为它可能在 WeightedQuickUnionFind 平衡后发生了变化）。
最后我使用了包含位或组合器 | 将所有站点的状态合并为结果状态，我用它来更新所有相关站点的状态。这是一个廉价的常量时间操作，可以为 isFull() 和 percolation() 节省堆。您可以将其视为所有相关站点之间的“污染/传播”状态。
然后在离开 open() 之前，我查询站点的状态以检查它是否等于 111（一个同时连接到顶部和底部的开放站点）并将此布尔值存储在由 percolation() 返回的 doesPercolate 字段中，如下所示p7x 表示。
瞧！
总分：101.25% 估计学生记忆力 = 9.00 n^2 + 0.00 n + 192.00 (R^2 = 1.000)
其余的完全按照上面的 p7x 建议。PS：臭代码强制转换 int[] 而不是 byte[] 同意，但无论如何现在还是保存了我的按位算术。
