ImageOverlap [source code]
public class ImageOverlap {
static
/****************************************************************************/
class Solution {
public int largestOverlap(int[][] A, int[][] B) {
int res = -1, N = A.length;
res = Math.max (res, overlap (A, B, 0, 0));
res = Math.max (res, overlap (A, B, 0, N - 1));
res = Math.max (res, overlap (A, B, N - 1, 0));
res = Math.max (res, overlap (A, B, N - 1, N - 1));
return res;
}
int overlap (int[][] A, int[][] B, int xa, int ya) {
int N = A.length, xa_incre = xa == 0 ? 1 : -1, ya_incre = ya == 0 ? 1 : -1;
int xb = N - 1 - xa, yb = N - 1 - ya, xb_incre = -xa_incre, yb_incre = -ya_incre;
int max_count = -1;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
int xa_end = xa + xa_incre * i, ya_end = ya + ya_incre * j;
int xb_end = xb + xb_incre * i, yb_end = yb + yb_incre * j;
int count = 0;
for (int ofs_x = 0; ofs_x <= i; ofs_x++) {
for (int ofs_y = 0; ofs_y <= j; ofs_y++) {
if (A[xa + xa_incre * ofs_x][ya + ya_incre * ofs_y] == 1 &&
B[xb_end + xa_incre * ofs_x][yb_end + ya_incre * ofs_y] == 1) {
count++;
}
}
}
max_count = Math.max (max_count, count);
}
}
return max_count;
}
}
/****************************************************************************/
public static void main(String[] args) {
ImageOverlap.Solution tester = new ImageOverlap.Solution();
int[][][] inputs = {
{{1,1,0},
{0,1,0},
{0,1,0}},
{{0,0,0},
{0,1,1},
{0,0,1}}, {{3}} ,
};
for (int i = 0; i < inputs.length / 3; i++) {
System.out.println (Printer.separator ());
int[][] A = inputs[3 * i], B = inputs[3 * i + 1];
int ans = inputs[3 * i + 2][0][0], output = tester.largestOverlap (A, B);
System.out.printf ("%sand\n%s%s\n%d\n",
Matrix.printMatrix (A), Matrix.printMatrix (B), Printer.wrap (output + "", output == ans ? 92 : 91), ans
);
}
}
}
这个题干看起来有意思哦;
首先, 类似很多变形题, 这题其实给了很多的自由度, 让题目看起来很难; 那么我们思考一下, 是否可以通过观察得到simplifying observation来减少自由度? 通常这个可以降低题目难度;
比如你可以往左移动, 也可以往右移动, 那么最后的最佳答案里面, 有没有可能既包含left也包含right呢? 我认为是不可能的. 因为你left之后, 就损失了一些1: 按照给的例子, 默认补全应该是0, 不对哦, 给的这个例子不好诶; 这个可能最好要问一下, 默认补全到底是多少, 面试的时候问面试官;
不对, 我感觉这个题目不要用array shift那个思路来做: 出界的扔掉, 另一头的自动补全为0这种; 而是用这样一个扑克牌重叠的思路:
出界和补全怎么弄, 根本无所谓的;
那么按照这个思路, 可不可以同时有left和right? 当然不可以, 因为这个你脑子里的visual就是一个纯粹的物理动画一样, 左边过去几个又回来右边, 其实是无用功;
脑子里有动画之后, 感觉有点思路; 虽然有点麻烦, 不过应该能写; 这题核心应该不要纠结于怎么move, 而是看最后重叠的状态本身;
首先, 想清楚, 重叠到底是什么?
感觉有思路但是这个复杂度无法控制, 好像计算上有什么诀窍;
naive的做法复杂度能到N^4, 感觉会被TLE;
这题好难的样子, 50分钟的时候uwi还没有做出来. 那我先看下一题了;
感觉好像要用点对称性的东西;
这题估计是contest历史上最难之一了, 因为contest结束的时候 6/1600的AC, 你感受一下:
uwi也没有做出来;
这个就是我当时自己想的naive的做法, 感觉有点什么思路, 但是你仔细看, 这里实际上是无法找到一个合理的subproblem结构的, 所以最后很可能只有用一个N^2的笨办法来做; 这个办法肯定TLE, uwi手速那么快, 他肯定尝试了这个办法;
好像后来发现比赛的时候OJ有点问题; discuss新的风暴已经出现;
2018-05-17 15:03:04
过几天回来看, 好像AC rate正常了, 估计是OJ修好了;
另外, 最后实际contest的时候我也是根本就没有写出什么像样的算法, 所以直接看答案了;
大概看了一眼contest, 居然N^6也能AC, 所以我想, 还是先自己写写看; 说不定能AC呢;
之前看到uwi居然没有做完, 估计其实好像是因为contest的时候的OJ的问题, 所以他应该还是有办法做的;
自己尝试写的时候, 发现这个就算是简单粗暴的实现, 也不是特别简单; 感觉对于怎样提供reuseability, 有很多需要考虑的地方;
这个代码很多难点; 首先, 你要想一下, 你这里要有几层循环?
想起来突然去网站看了一下, 好像他们OJ改过来之后, 所有的结果重跑了一下, uwi的那个答案被AC了;
顺手一说, 这里我在思考写一个reuse度很高的函数的时候, 其实花了很多的时间. 我认为这个思考过程并不算是浪费时间, 因为我们最后的目标是写出来一个面试过程能够写完并且讲清楚的解法;
如果这里所有的包括四方向对称的枚举, 全部都用手写来完成, 你真正面试的时候估计是完全写不完的;
或许你可以尝试跟面试官说: 其他四个方向是对称的, 所以代码是差不多的, 那么十有八九, 面试官会反问你: 既然你知道是对称代码, 那么你能不能热factor一下, 给我一个通用函数呢?
所以这个思考感觉其实是躲不掉的;
要炸了, 完全想不通怎么有效的写这个函数; 放弃了, 很丢人; 我的想法是这样的:
也就是首先这个通用函数传进来的参数是A的顶点, 然后B的顶点什么的, 都可以很方便的计算, increment什么的;
然后在这个通用函数里面, 首先是一个针对这两个ofs的循环, 是N^2;
然后针对每一个ofs, 再进行一个小矩形里面的遍历, 又是N^2, 所以最后总共是N^4;
但是好麻烦啊, 感觉这个函数的设计;
倒不是说写单独一种情况的难; 而是如果要让我的通用函数能够兼顾所有四个顶点的情况, 这个计算感觉就很麻烦;
写不了了, 不写了; 半成品:
int overlap (int[][] A, int[][] B, int xa, int ya) {
int N = A.length, xa_incre = xa == 0 ? 1 : -1, ya_incre = ya == 0 ? 1 : -1;
int xb = N - 1 - xa, yb = N - 1 - ya, xb_incre = -xa_incre, yb_incre = -ya_incre;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
int xa_end = xa + xa_incre * i, ya_end = ya + ya_incre * j;
int xb_end = xb + xb_incre * i, yb_end = yb + yb_incre * j;
for (int ofs_x = 0; ofs_x <= xa_end; ofs_x += xa_incre) {
for (int ofs_y = 0; ofs_y <= )
}
}
}
}
这里放弃的原因是因为上面的这个i,j的计算到底对吗? 我这里默认i和j都是正数, 这样一个assumption真的成立吗;
好像没关系? 因为offset这个概念本身就应该是不带正负号的; 正负号用incre来处理就行了;
我特么都无语了? 写的时候头皮都扯光了, 居然最后直接就AC了? 一个bug都没有.
整个人都不好了; 这个算法实现还是挺绕人的. 速度是45ms(NA);
这个问题的难点在于, 就是你要完成这个对称性refactor
symmetry refactor
没有想到我最后这里居然处理的还很不错, 开森;
写代码的时候, 还是注意一个问题, 就是我上面那里, 你写一个变量, 是干什么用的, 图上标出来; 这样一来是避免自己写着写着出错(比如忘记了这个变量的定义), 二来是面试的时候, 也可以让面试官更容易跟住你的思路;
isolation of offset vs. direction
这个是我这里实现的时候的一个重要技巧, 就是你看我通用函数里面, incre(代表方向), 和offset(i, j, ofs_x, ofs_y)是有严格的区分的;
这样一个区分的好处是很明显的, 最后循环写起来简单很多; 注意, offset变量始终是非负数(看循环范围); 最后如果有负向移动, 完全用incre这些方向变量来操作: 而incre因为是一个只能在1和-1之间取值的变量, 管理起来最后就方便很多;
算是一个separation of concern理念的应用吧; 每一个变量类型管理的东西变少之后, 整体设计的复杂度也降低很多;
说起来, 这个理念实际上我当初survivalmaps的时候, 就很多. 感觉现在学写代码, 很多基本理念是不停的闪回.
最后一个草稿解释一下最后循环:
注意这里不是对向进行了, 而是同向, 所以你看里面对B给的index的写法(尤其是incre给的什么), 是有点讲究的; 我给的直接是xa的incre, 也可以给-xb_incre这种;
注意看, 我给i和j都定义成为了offset(也就是最外层两个循环决定iterate的是offset之后), 我其实里面那两个循环是可以决定iterate index的; 但是我最后还是决定里面两个循环还是iterate offset, 就是因为实现的时候会更简单: 如果你iterate index, 你就免不了又要处理方向; 那么你就违背了separation of concerns, 因为我们已经决定所有的方向变量全都扔个incre来处理了;
另外, 一个小的需要提到的地方, 就是虽然我最后写出来的通用函数是要完成一个对于A的四个顶点, 都能handle的能力, 但是最后实际上写代码的时候, 还是用左上角这一个情况来帮助trace的;
这个也应该是很熟悉的一个技巧了;
这样一个用例子来帮助写代码的技巧需要稍微注意一点的地方, 就是避免hardcode东西; 比如假设你要iterate index, 那么不是你说++就是++, 你说--就是--的; 要看咱们当前的incre是什么, 不是你自己看看例子一拍脑袋就乱写的; 用concrete来协助开发, 但是脑子里面始终要有一个尊重abstract的概念;
很开心, 自己居然写了一个不错的解法, 那么可以很放心的去看editorial给的这些解法了;
UNFINISHED
editorial
Approach #1: Translate by Delta [Accepted]
首先, 看了一眼下面的复杂度, 原来N^6的都能AC, 两种做法里面稍微好一点的那种也只能做到N^4; 果然, 我要是一开始直接自己写就好了;
Intuition and Algorithm
For each translation delta, we calculate the candidate answer overlap(delta), which is the size of the overlap if we shifted the matrix A by delta.
We only need to check delta for which some point in A maps to some point in B, since a candidate overlap must be at least 1. Using seen, we don't perform this expensive check more than once per delta.
We use java.awt.Point (or complex in Python) to handle our 2D vectors gracefully. We could have also mapped a vector delta = (x, y) (which has coordinates between -(N-1) and N-1) to
2*N x + yfor convenience. Note that we cannot map it toN*dx, dy as there would be interference: (0, N-1) and (1, -1) would map to the same point.
graceful个鬼, 就喜欢用这种很ad-hoc的方法来完成封装; 无论是工程角度还是hackish的角度, 我觉得都不是好的做法; 我反正现在是彻底摆脱这种借用其他结构(包括数组)来完成封装的习惯了;
import java.awt.Point;
class Solution {
public int largestOverlap(int[][] A, int[][] B) {
int N = A.length;
List<Point> A2 = new ArrayList(), B2 = new ArrayList();
for (int i = 0; i < N*N; ++i) {
if (A[i/N][i%N] == 1) A2.add(new Point(i/N, i%N));
if (B[i/N][i%N] == 1) B2.add(new Point(i/N, i%N));
}
Set<Point> Bset = new HashSet(B2);
int ans = 0;
Set<Point> seen = new HashSet();
for (Point a: A2) for (Point b: B2) {
Point delta = new Point(b.x - a.x, b.y - a.y);
if (!seen.contains(delta)) {
seen.add(delta);
int cand = 0;
for (Point p: A2)
if (Bset.contains(new Point(p.x + delta.x, p.y + delta.y)))
cand++;
ans = Math.max(ans, cand);
}
}
return ans;
}
}
第一个循环写的好蠢; 非要用i作为一个1D坐标来循环, 结果循环里面又把这个1D坐标重新给解出来了; 为什么不直接就用2D呢? 你又没有去存这个1D的坐标;
首先, A2和B2什么意思, 要记得一下, 其实就是sparsify之后的AB两个里面的1的点的坐标;
然后Bset是一个把B2装到一个set里面, 因为后面需要用到set的操作;
然后看delta的计算: 看到delta就要想到一个问题, delta这个概念, 是有方向的, 所以这里的这个delta, 实际上是什么方向? 实际上是一个A->B的方向;
然后你看cand的这个循环, 这个时候我们其实定住的是a和b, 两个点都定住的, 但是b的定住更加重要; 然后我们站在b, 重新遍历A2(用p), 这个时候, 我们做的这个p + delta, 检查是否在B里面, 这个是正确的, 因为delta是A->B的方向, 所以p+delta得到的是一个与B对应的坐标;
他的操作的内涵就是, A的所有的point1啊, 我们全都走一遍, 然后看看, 这个delta的shift给他之后, 能不能映射到B里面去. 这个最后得到的cand, 就是对应这个delta的得分; 每一个delta有一个自己的得分;
这样一个eager的打分系统的好处是, 可以用一个seen这样的结构来避免重复; 不过因为循环量其实很大, 所以最后复杂度就上升很多;
整体算法目的还是看得懂的;
这个算法刚开始看的时候还是有点费劲的, 主要是因为用到的东西太多了; 如果单纯的一行一行的流水账那样去看, 很容易看着看着不知道整个流程在干什么;
后面变成了一种加强上下呼应的看法; 首先, 肯定是要不停的提醒自己, 每一个变量是什么意思;
然后看seen这些干的是什么, 之类的;
当然了, awice的代码, 国际惯例, 看完代码之后回头重新看他的解释, 会有很大的帮助;
看完这个算法, 一个很自然的想法就是, 这个eager scoring的办法, 能不能更优雅的解决? 比如既然是要给每一个delta打分, 能不能直接就走一遍两个矩阵, 然后用一个类似accummulate的思路, 让点与点之间自动给对应的delta加分?
另外, 其实虽然理解了这个算法在干什么, 但是其实没有认真的去思考这个算法最后实际上为什么可以这样做? 为什么可以这样给一个delta打分?
实际上也没有什么好理解的; 这题为什么他要转换为计算delta, 因为我们最后所谓的这个overlap什么的, 就是要你回答, 一个shift之后得到的结果, shift最后就是可以对应于不同的delta;
我的扑克牌思路, 其实也可以用delta思路来理解:
每一个delta最后(假装A是不动的, 不对, 假装B一开始是从和A重叠开始的), 对应的得到的就是一种overlap, 也就是一种我自己的做法当时想到的这个扑克牌重叠;
所以最后我们肯定希望知道, 有哪些valid的delta(实际上就是至少能让一个Apoint1和一个Bpoint1进行重叠). 这个可以单独一个循环来解决; awice这里的做法更加奇怪; 实际上他这个做法并没有什么优势;
这个做法的难点就是意识到delta这个隐藏概念的存在; 怎么意识到? 我暂时还没有很好的结论;
Approach #2: Count by Delta [Accepted]
Intuition and Algorithm
We can do the reverse of Approach #1: count every possible delta = b - a we see. If we see say, 5 of the same delta = b - a, then the translation by delta must have overlap 5.
没错, 这个就是一个lazy scoring, 也就是我上面描述的;
class Solution {
public int largestOverlap(int[][] A, int[][] B) {
int N = A.length;
int[][] count = new int[2*N+1][2*N+1];
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
if (A[i][j] == 1)
for (int i2 = 0; i2 < N; ++i2)
for (int j2 = 0; j2 < N; ++j2)
if (B[i2][j2] == 1)
count[i-i2 +N][j-j2 +N] += 1;
int ans = 0;
for (int[] row: count)
for (int v: row)
ans = Math.max(ans, v);
return ans;
}
}
最后这个lazy counting实际上实现起来非常简单;
不得不说他这个做法实际上比我的做法还是简单太多了;
当然, 我还是觉得我的做法提供了一个全新的角度; editorial给的这两个做法实际上都是依赖于对delta这个概念的理解来完成实现的;
而我自己的这个symmetric iteration的设计, 我觉得还是很有意思的;
大概记得, to identify one of all the symmetric counterparts, 你需要的是一个起点坐标, 和一个incre, 就够了; end往往可以根据上面这两个来计算出来;
这题因为有所特殊性, 连incre实际上都不需要作为参数提供, 直接可以通过start坐标来推导;
uwi:
class Solution {
public int largestOverlap(int[][] A, int[][] B) {
int n = A.length;
int[][] t = new int[2*n+1][2*n+1];
for(int i = 0;i < n;i++){
for(int j = 0;j < n;j++){
for(int k = 0;k < n;k++){
for(int l = 0;l < n;l++){
t[k-i+n][l-j+n] += A[i][j] * B[k][l];
}
}
}
}
int ret = 0;
for(int[] row : t){
for(int v : row){
ret = Math.max(ret, v);
}
}
return ret;
}
}
很简短, 4分钟;
完全就是editorial2的解法; 只能说uwi还是牛逼, 迅速就把握了问题的本质, 我还在用扑克牌一点一点的凑; 4分钟就想到这么好的点子, 有点无语的;
Problem Description
Two images A and B are given, represented as binary, square matrices of the same size. (A binary matrix has only 0s and 1s as values.)
We translate one image however we choose (sliding it left, right, up, or down any number of units), and place it on top of the other image. After, the overlap of this translation is the number of positions that have a 1 in both images.
(Note also that a translation does not include any kind of rotation.)
What is the largest possible overlap?
Example 1:
Input: A = [[1,1,0],
[0,1,0],
[0,1,0]]
B = [[0,0,0],
[0,1,1],
[0,0,1]]
Output: 3
Explanation: We slide A to right by 1 unit and down by 1 unit.
Notes:
- 1 <= A.length = A[0].length = B.length = B[0].length <= 30
- 0 <= A[i][j], B[i][j] <= 1
Difficulty:Medium
Total Accepted:12
Total Submissions:1.6K
Contributor:awice
Companies
google
Related Topics
array