问题: 给定连个数组包含了一些矩阵, 判断这些矩阵能否完美组合成一个大矩阵。
我的思路很简单。
// __________________
// | | |
// | R0 | |
// |--------| R1 |
// | h | |
// |________|_______|
我们找左下角的矩阵,然后直接递归。 但是超时了。 一开始用list来存放,每次偶读会扫一次list,后来改用priority queue, 只需要部分扫描, 依然超时。
看了discuss, 有人提出了一个corner统计的方法, 确实厉害,很难想到。而且,还给出了证明。虽然,没用AC自己的算法,但没有什么关系。毕竟只是练习coding。 期间, pq用toList方法和pq dequeueall得到的序列是不一样的。最后, 贴一下TLE的code。
/**
* Created by lilisun on 7/25/19.
* Got TLE, this solution is straight forward but we need to scan the rectangles too many times
* There is a O(n) solution on the discussion board. Check the following link.
* link: https://leetcode.com/problems/perfect-rectangle/discuss/87180/O(n)-solution-by-counting-corners-with-detailed-explaination
* I have try 2 implementation of my alo. By list and priority queue, but not lucky
*
*/
import scala.collection.mutable
object No391 {
object listImpl {
// (a, b, c, d) represents matrix:
// (a, d) (c, d)
//
// (a, b) (c, b)
// final matrix:
// (a min , d max ), (c max, d max)
// (a min , b min ), (c max, b min)
// find the matrix contains point(a min, b min, c1, d1)
// if it's not unique, return false
// solve rectangle cover for M0 (a min, b min, c1, d max)
// filter all the rectangle, that in or overlap with M0.
// if not perfect cover for M0, return false
// update recatangles, for the overlap matrixs,
// refine it to a new matrix, and repeat.
// M0 <- (c1, b min, c2, d max)
// To speed up, sort the matrix by the left down point(can be chosed as other corners)
// When we refine a matrix, the refined matrix is sure to be the candidate of the next
// iteration.
//
def isRectangleCover(A: Array[Array[Int]]): Boolean = {
def f(l: List[Array[Int]], M: Array[Int]): Boolean = {
println("-----")
println(l map { x => x.toList })
println(M.toList)
if (zeroRectangle(M) && l.isEmpty) true
else
l filter { case Array(a, b, c, d) => a == M(0) && b == M(1) } match {
case Array(a, b, c, d) :: Nil =>
val M0 = Array(a, b, c, M.last)
check(l takeWhile isIntersect(M0) map cut(M0), M0) match {
case false => false
case true =>
f((l takeWhile isIntersect(M0) filter overlap(M0) map refine(M0)) ++ (l dropWhile isIntersect(M0)), Array(M0(2), M(1), M(2), M.last))
}
case _ => false
}
}
// l has a shape like
// ????????
// ????????
// ????????
// --------
// | |
// | |
// --------
// remove the bottom rec. and repeat
def check(l: List[Array[Int]], M: Array[Int]): Boolean = {
l filter { case Array(a, b, c, d) => a == M(0) && b == M(1) && c == M(2) } match {
case Array(a, b, c, d) :: Nil =>
f(l filterNot { case Array(a, b, c, d) => a == M(0) && b == M(1) && c == M(2) }, Array(a, d, c, M.last))
case _ =>
println("#####return at error")
println(l filter { case Array(a, b, c, d) => a == M(0) && b == M(1) && c == M(2) } map { x => x.toList })
println(M.toList)
println("####")
false
}
}
def zeroRectangle(A: Array[Int]): Boolean = {
A(0) == A(2) || A(1) == A(3)
}
// if B is interset with A
def isIntersect(M: Array[Int])(A: Array[Int]): Boolean = {
(M, A) match {
case (Array(a1, b1, c1, d1), Array(a2, b2, c2, d2)) =>
a2 < c1 && b2 < d1
}
}
def refine(M: Array[Int])(A: Array[Int]): Array[Int] = {
(M, A) match {
case (Array(a1, b1, c1, d1), Array(a2, b2, c2, d2)) =>
Array(a1, b2, c2, d2)
}
}
def cut(M: Array[Int])(A: Array[Int]): Array[Int] = {
(M, A) match {
case (Array(a1, b1, c1, d1), Array(a2, b2, c2, d2)) =>
Array(a2, b2, c1 min c2, d2)
}
}
def overlap(M: Array[Int])(A: Array[Int]): Boolean = {
(M, A) match {
case (Array(a1, b1, c1, d1), Array(a2, b2, c2, d2)) =>
c2 > c1
}
}
def g(l: List[Array[Int]], a_min: Int, b_min: Int, c_max: Int, d_max: Int): Array[Int] = l match {
case Nil => Array(a_min, b_min, c_max, d_max)
case Array(a, b, c, d) :: t => g(t, a_min min a, b_min min b, c_max max c, d_max max d)
}
f(A.sortBy { case Array(a, b, c, d) => (a, b, c, d) }.toList,
g(A.toList, Int.MaxValue, Int.MaxValue, Int.MinValue, Int.MinValue)
)
}
}
object pqImpl {
def isRectangleCover(A: Array[Array[Int]]): Boolean = {
// Initial:
val M0 = Array(Int.MaxValue, Int.MaxValue, Int.MinValue, Int.MinValue)
val pq = mutable.PriorityQueue[(Int, Int, Int, Int)]()(Ordering.by { case (a, b, c, d) => (-a.toInt, -b.toInt, -c.toInt, -d.toInt)})
A.map(_.toList) foreach { case a::b::c::d::Nil =>
M0(0) = M0(0) min a
M0(1) = M0(1) min b
M0(2) = M0(2) max c
M0(3) = M0(3) max d
pq.enqueue((a, b, c, d))
}
// println("------------------")
//pq.dequeueAll foreach println
//true
solvePQ(pq, M0)
}
def solvePQ(pq: mutable.PriorityQueue[(Int, Int, Int, Int)], M0: Array[Int]): Boolean = {
// 1. dequeue the first element Array(a0, b0, c0, d0)
// 2. dequeue all the element Array(a, b, c, d)
// satisfy a >= a0 && a < c0
val l = pq.dequeueAll
// println(l, M0.toList)
l foreach {x => pq.enqueue(x)}
if (pq.isEmpty) true
else pq.dequeue() match {
case (a0, b0, c0, d0) =>
// println("first rec: ",a0, b0,c0, d0)
//println(s"M0: ${M0.toList}")
if (!(a0 == M0(0) && b0 == M0(1))) {
println("####")
println(a0,b0,c0,d0, M0.toList)
println("####")
return false
}
val subPQ = mutable.PriorityQueue[(Int, Int, Int, Int)]()(Ordering.by { case (a, b, c, d) => (-a,-b,-c,-d) })
// optimize: only look the head element of pq, check
if(pq.isEmpty ) return M0.toList == List(a0, b0, c0, d0)
var h = pq.dequeue()
while (h._1 >= a0 && h._1 < c0) {
subPQ.enqueue((h._1, h._2, h._3 min c0, h._4))
if (h._3 > c0) pq.enqueue((c0, h._2, h._3, h._4))
if(pq.nonEmpty) h = pq.dequeue()
else h = (Int.MaxValue, Int.MaxValue, Int.MinValue, Int.MinValue)
}
if(h._1 != Int.MaxValue) pq.enqueue(h)
// __________________
// | | |
// | R0 | |
// |--------| R1 |
// | h | |
// |________|_______|
solvePQ(subPQ, Array(a0, d0, c0, M0(3))) &&
solvePQ(pq, Array(c0, b0, M0(2), M0(3)))
}
}
}
object cornerCounter {
}
def main(args: Array[String]): Unit = {
val A = Array(
Array(1,1,3,3),
Array(3,1,4,2),
Array(3,2,4,4),
Array(1,3,2,4),
Array(2,3,3,4)
)
println(pqImpl.isRectangleCover(A))
}
}
update:
尝试了discuss的解, 并没有完全看完, 不过按照观察, 每个corner点应该只出现1 ,2 , 4次, 出现一次的点刚好是要构建的矩形。 这样直接会有问题, 例如:
[[0,0,3,3,],[1,1,2,2], [1,1,2,2]]
所以,我试着加入面积的检测。 然后就AC了。 当然, 并不明白为什么这两个条件和问题是等价的。 找到proof的话, 会更新吧。
import scala.collection.mutable
object Solution {
def isRectangleCover(A: Array[Array[Int]]): Boolean = {
var lx = Int.MaxValue
var ly = Int.MaxValue
var rx = Int.MinValue
var ry = Int.MinValue
val count = mutable.HashMap[(Int, Int), Int]()
var area = 0
A foreach {
case Array(a, b, c ,d) =>
lx = lx min a
ly = ly min b
rx = rx max c
ry = ry max d
area += (c - a) * (d - b)
count.put((a, b), count.getOrElse((a, b), 0) + 1)
count.put((c, d), count.getOrElse((c, d), 0) + 1)
count.put((a, d), count.getOrElse((a, d), 0) + 1)
count.put((c, b), count.getOrElse((c, b), 0) + 1)
}
if((rx - lx) * (ry - ly) != area) return false
val ans = List((lx, ly), (rx, ry), (lx, ry), (rx, ly)).sorted
var rem = List.empty[(Int, Int)]
for{ x <- count.keySet}{
if(count(x) == 2 || count(x) == 4){}
else if(count(x) == 1) rem ::= x
else return false
}
rem.sorted == ans
}
}